https://www.acmicpc.net/problem/6064 6064번: 카잉 달력 문제 최근에 ICPC 탐사대는 남아메리카의 잉카 제국이 놀라운 문명을 지닌 카잉 제국을 토대로 하여 세워졌다는 사실을 발견했다. 카잉 제국의 백성들은 특이한 달력을 사용한 것으로 알려져 있다. 그들은 M과 N보다 작거나 같은 두 개의 자연수 x, y를 가지고 각 년도를 와 같은 형식으로 표현하였다. 그들은 이 세상의 시초에 해당하는 첫 번째 해를 로 표현하고, 두 번째 해를 로 표현하였다. 의 다음 해를 표현한 것을 이라고 하자. 만일 www.acmicpc.net 문제 접근 방식 x나 y를 1씩 증가시키는 방식으로 진행 시 시간초과를 초래할 수 있다. x를 고정 시키고 출력 해를 M만큼 증가시키는 방식으로 해를 구한..
https://www.acmicpc.net/problem/1890 1890번: 점프 문제 N×N 게임판에 수가 적혀져 있다. 이 게임의 목표는 가장 왼쪽 위 칸에서 가장 오른쪽 아래 칸으로 규칙에 맞게 점프를 해서 가는 것이다. 각 칸에 적혀있는 수는 현재 칸에서 갈 수 있는 거리를 의미한다. 반드시 오른쪽이나 아래쪽으로만 이동해야 한다. 0은 더 이상 진행을 막는 종착점이며, 항상 현재 칸에 적혀있는 수만큼 오른쪽이나 아래로 가야 한다. 한 번 점프를 할 때, 방향을 바꾸면 안 된다. 즉, 한 칸에서 오른쪽으로 점프를 하거나, 아래로 www.acmicpc.net 문제 접근 방식 최초 지점으로 부터 오른쪽 혹은 아래로 이동을 할 수 있다. 도착 지점의 입장에서 생각해보면 왼쪽에서 도착 지점으로 오거나 위..
https://www.acmicpc.net/problem/14442 14442번: 벽 부수고 이동하기 2 첫째 줄에 N(1 ≤ N ≤ 1,000), M(1 ≤ M ≤ 1,000), K(1 ≤ K ≤ 10)이 주어진다. 다음 N개의 줄에 M개의 숫자로 맵이 주어진다. (1, 1)과 (N, M)은 항상 0이라고 가정하자. www.acmicpc.net 주어진 범위의 맵 내부에서 목적지까지 도달하는 최단거리를 구하는 문제입니다. 아래는 코드입니다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53..
https://www.acmicpc.net/problem/3184 3184번: 양 문제 미키의 뒷마당에는 특정 수의 양이 있다. 그가 푹 잠든 사이에 배고픈 늑대는 마당에 들어와 양을 공격했다. 마당은 행과 열로 이루어진 직사각형 모양이다. 글자 '.' (점)은 빈 필드를 의미하며, 글자 '#'는 울타리를, 'o'는 양, 'v'는 늑대를 의미한다. 한 칸에서 수평, 수직만으로 이동하며 울타리를 지나지 않고 다른 칸으로 이동할 수 있다면, 두 칸은 같은 영역 안에 속해 있다고 한다. 마당에서 "탈출"할 수 있는 칸은 어떤 영역에도 속하지 www.acmicpc.net 주어진 범위 안에 있는 각각의 울타리 내부의 양과 늑대의 수를 파악하여 조건에 따라 최종 양과 늑대 수를 출력하는 문제입니다. 아래는 코드입니..
https://www.acmicpc.net/problem/1107 1107번: 리모컨 첫째 줄에 수빈이가 이동하려고 하는 채널 N (0 ≤ N ≤ 500,000)이 주어진다. 둘째 줄에는 고장난 버튼의 개수 M (0 ≤ M ≤ 10)이 주어진다. 고장난 버튼이 있는 경우에는 셋째 줄에는 고장난 버튼이 주어지며, 같은 버튼이 여러 번 주어지는 경우는 없다. www.acmicpc.net 원하는 채널로 이동하기 위한 최소 버튼을 구하는 문제입니다. 최초 채널이 100이라는 점을 잊지 말아야 합니다. 항상 같은 자리수가 최단 거리가 아닐 수 있다는 것도 가정해야합니다. 이동하고 싶은 채널 999 고장난 버튼 수 7개 고장난 버튼 2,3,4,5,6,7,9 이런 경우 888에서 999로 이동하는 것 보다 1000에..
항목 43 : 템플릿으로 만들어진 기본 클래스 안의 이름에 접근하는 방법을 알아 두자 1 2 3 4 5 6 template class MsgSender{ public : ... void sendSecret(const MsgInfo& info){...} }; Colored by Color Scripter 괄호 안에 아무것도 없는 template의 뜻은 "이건 템플릿도 아니고 클래스도 아니다"라는 것입니다. 위의 코드는 MsgSender 템플릿을 템플릿 매개변수가 CompanyZ일 때 쓸 수 있도록 특수화한 버전입니다. 이러한 특수화는 완전 템플릿 특수화라고 합니다. MsgSender 템플릿이 CompanyZ 타입에 대해 특수화되었고, 이때 이 템플릿의 매개변수들이 하나도 빠짐없이 구체적인 타입으로 정해진 ..
항목 42 : typename의 두 가지 의미를 제대로 파악하자 1 2 3 4 5 6 7 8 9 10 11 12 template void print2nd(const C& container) { if(container.size() >= 2) { C::const_iterator iter(container.begin()); ++iter; int value = *iter; std::cout = 2) { typename C::const_iterator iter(container.begin()); ... } } Colored by Color Scripter 어느 때이든지 템플릿 안에서 중첩 의존 이름을 참조할 경우에는, 그 이름 앞에 typename 키워드를 붙여 주는 것을 잊지 마세요. "typename은 중첩 ..
항목 41 : 템플릿 프로그래밍의 천릿길도 암시적 인터페이스와 컴파일 타임 다형성부터 객체 지향 프로그래밍의 세계를 회전시키는 축은 명시적 인터페이스와 런타임 다형성입니다. 예를 들어 아래와 같은 코드가 주어졌고 1 2 3 4 5 6 7 8 9 class Widget { public: Widget(); virtual ~Widget(); virtual std::size_t size() const; virtual void normalize(); void swap(Widget& other); ... }; Colored by Color Scripter 다음의 함수가 있을 때, 1 2 3 4 5 6 7 8 9 void doProcessing(Widget& w) { if(w.size() > 10 && w != so..
스트래티지 패턴(Strategy Pattern)은 알고리즘을 정의하고 각각을 캡슐화하여 교환해서 사용할 수 있도록 만드는 패턴입니다. 이 패턴을 활용하면, 알고리즘을 사용하는 클라이언트와는 독립적으로 알고리즘을 변경할 수 있습니다. 이 패턴을 익히면서 알 수 있는 객체 지향적 원칙이 있습니다. 바뀌는 부분은 캡슐화 한다. 상속보다는 구성을 활용한다. 구현이 아닌 인터페이스에 맞춰서 프로그래밍한다. 기본적으로는 Animal 클래스로부터 상속을 받는 형식으로 구성되어있습니다. 달리고, 날고, 뛰는 등의 행위가 객체마다 다르다고 가정하여 분리를 하였습니다. 아래에 코드가 있습니다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 ..
항목 40 : 다중 상속은 심사숙고해서 사용하자 다중 상속(multiple inheritance: MI)에 대해 꼭 기억하고 있어야 할 점중 하나는, 둘 이상의 기본 클래스로부터 똑같은 이름(함수, typedf 등)을 물려받을 가능성이 생겨 버린다는 점입니다. 다중 상속 때문에 모호성이 생긴다는 것이죠. 아래의 예시를 보시죠. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 class BorrowableItem { // 라이브러리로부터 여러분이 가져올 수 있는 어떤 것 public : void checkOut(); // 라이브러리로부터 체크아웃합니다. ... }; class ElectronicGadget { private: bool checkOut() const; // 자체 테..
