프로그래밍
BOJ 1476 · 날짜 계산
알고리즘 분류 : 브루트 포스 나머지를 이용하여 연도를 구할 수 있다. C++ 소스코드 #include int main() { int e, s, m; scanf("%d %d %d", &e, &s, &m); int year = 0; while (true) { int x = year%15, y = year%28, z = year%19; if (x == e-1 && y == s-1 && z == m-1) break; year++; } printf("%d\n", year+1); return 0; } Python 3 소스코드 e, s, m = map(int, input().split()) year = 0 while True: x, y, z = year%15, year%28, year%19 if x == e-1 a..
BOJ 1966 · 프린터 큐
알고리즘 분류 : 큐 큐 자료구조를 이용하는 알고리즘 문제다. 큐(Queue)는 선입선출(FIFO; First In First Out)의 선형 자료구조이다. 먼저 들어간 데이터가 먼저 나온다는 뜻이다. 이 문제는 우선순위가 있는 큐를 이용해야 한다. N개의 문서에서 우선순위가 높은 문서부터 먼저 출력되고, 이때 M번 문서는 몇 번째에 인쇄되는지 출력해야 한다. 입력받은 데이터를 큐에 집어넣는다.데이터와 함께 데이터의 인덱스를 별도의 큐로 구성하여 문서 번호를 저장한다.큐에서 나온 데이터가 최댓값이 아니면, 다시 큐에 집어넣고, 이를 반복한다.큐에서 나온 데이터가 M번 문서와 일치하면 꺼낸 횟수를 출력하고 종료한다. C++ 소스코드 #include #include using namespace std; st..
BOJ 1065 · 한수
알고리즘 분류 : 브루트 포스 정수 N이 주어질 때, 1부터 N 사이에 존재하는 한수의 수를 구하는 알고리즘을 짜는 문제다. 한수란 각 자릿수가 등차수열을 이루는 수를 말한다. 예를 들면 123은 1, 2, 3 순으로 1씩 증가하는 한수이며, 642는 6, 4, 2 순으로 2씩 감소하는 한수이다. 한 자릿수, 두 자릿수는 모두 한수이며, 세 자릿수 이상은 각 자릿수가 일정한 공차를 이루고 있어야만 한다. N이 100 미만일 경우, N이 한수의 수를 나타낸다.N이 100 이상이면, (백의 자릿수-십의 자릿수) == (십의 자릿수-일의 자릿수)를 판별해서 카운트하면 된다.백의 자릿수는 N/100, 십의 자릿수는 N/10%10, 일의 자릿수는 N%10으로 표현할 수 있다. C++ 소스코드 #include in..
BOJ 2309 · 일곱 난쟁이
알고리즘 분류 : 브루트 포스 난쟁이 9명 중 7명 키의 합이 100이 되는 것을 찾는 간단한 문제다. 9명 중 2명을 빼서 100을 찾는다고 생각하면 더 쉽다. 9명의 키를 입력받으면서 모두 더한다. 입력이 끝나면 정렬한다.모두 더한 값에서 2명을 빼서 100이 되는 값을 찾는다.2명을 제외하고 순서대로 출력한다. C++ 소스코드 #include #include const int N = 9; int a[N], sum; void solve() { std::sort(a, a+N); for (int i=0; i
BOJ 3055 · 탈출
알고리즘 분류 : BFS BFS를 통해 고슴도치가 동굴까지 이동하는 최단 거리를 구하는 문제다. 1분마다 물은 상하좌우로 1칸씩 번지고, 고슴도치도 1칸씩 움직인다. 고슴도치는 물로 이동할 수 없고, 다음 시간에 물이 차는 곳으로도 갈 수 없다. 때문에 물을 먼저 Queue에 넣고, 그다음 고슴도치를 Queue에 넣어 BFS를 돌리면 된다. Queue에 고슴도치의 위치와 물의 위치가 들어가므로, 물과 고슴도치를 구별할 flag를 만든다.map struct의 변수 s가 1인 경우 고슴도치이며, 0인 경우 물이다.입력받을 때, 물(*)은 곧바로 Queue에 넣고, 고슴도치(S)는 위치를 기억해둔다.입력이 끝난 후, 고슴도치의 위치를 Queue에 넣는다.고슴도치와 물은 돌(X)로 이동할 수 없고, 비어있는 칸..
BOJ 9328 · 열쇠
알고리즘 분류 : BFS BFS를 통해 맵을 탐색하면서 문서를 얻는 문제다. 이동 가능한 위치까지 최대한 이동해서 문서를 얻어야 한다. 빌딩 밖을 나갔다가 다시 들어와서 문을 열 수 있으므로, 주어진 맵을 확장할 필요가 있다. 예를 들면 아래 그림처럼 확장한다. 맵을 입력받을 때, 가장자리를 빈 공간(.)으로 만든다. 맵의 범위가 가로(1~W), 세로(1~H)라면, 가로(0, W+1), 세로(0, H+1)를 빈 공간으로 설정하면 된다. C++ 코드에서는 빈 공간을 0으로 처리했다.열쇠를 저장할 26(알파벳 총 개수) 길이의 배열을 만들고, 열쇠가 있으면 true, 없으면 false로 처리한다.큐는 총 2가지 종류이다. 이동 위치를 나타낼 Position queue와, 문의 위치를 나타낼 Door queu..
BOJ 14442 · 벽 부수고 이동하기 2
알고리즘 분류 : BFS 2206번 '벽 부수고 이동하기'를 변형한 문제다. 이전 문제는 벽을 최대 1개까지만 부술 수 있었으나, 이번 문제는 최대 10개까지 가능하다. 1개에서 10개로 늘어난 것이므로, 풀이는 비슷하게 접근할 수 있다. 이전 문제는 이곳에서 참조. dist 배열을 통해 방문 체크를 하고 이동 거리를 저장한다.dist는 3차원 배열이며, 인덱스는 [x좌표] [y좌표] [벽 부순 횟수] 이다. C++ 소스코드 #include #include using namespace std; struct map { int x, y, w; // w is a flag for counting broken walls. 0(Unbroken) 1~10(Broken) }; int n, m, k; char a[100..
BOJ 2206 · 벽 부수고 이동하기
알고리즘 분류 : BFS BFS를 통해 최단 거리를 구할 수 있는 문제다. 미로 탐색에서 약간 변형된 문제이며, 벽을 최대 1개만 부셔서 이동할 수 있다. 벽을 부수지 않거나(0), 벽을 1개 부시는(1) 경우로 나뉜다.위의 경우를 확인하기 위해 flag를 만들고, 이를 Queue에 집어 넣는다.다음 이동에서 벽을 만난 경우, flag가 0이면 벽을 부수고 flag를 1로 바꾼다.방문 여부는 dist 배열로 체크하며, 값이 0이 아니면 방문한 곳이다.dist 배열은 3차원 배열이며, 인덱스는 [x 좌표] [y 좌표] [벽 부순 여부] 이다.마지막 인덱스가 [0]이면 벽을 부수지 않고 (N, M)에 도착한 경우이고, [1]이면 벽을 한 번 부수고 (N, M)에 도착한 경우이다. C++ 소스코드 #inclu..