BOJ
BOJ 2644 · 촌수계산
알고리즘 분류 : BFS BFS를 통해 촌수를 계산하는 문제다. 촌수는 거리로 바꿔서 생각하면 된다.부모와 자식 간의 관계를 인접리스트로 변환하여 저장한다.사람(X) 부터 BFS로 탐색하면서 사람(Y)를 만나면 종료한다.BFS 탐색이 끝날 때 까지 사람(Y)를 만나지 못하면, 촌수 계산이 불가능하므로 -1을 출력한다. C++ 소스코드 #include #include #include using namespace std; int n; int x, y; vector a[101]; int dist[101]; int bfs() { queue q; q.push(x); while (!q.empty()) { int now = q.front(); q.pop(); if (now == y) return dist[now]; ..
BOJ 2573 · 빙산
알고리즘 분류 : DFS, BFS 1년마다 빙산이 녹는데, 빙산이 두 덩어리 이상으로 나눠지는 최초 연도를 구하는 문제다. 0은 바다고, 1 이상의 숫자는 빙산의 높이다. 빙산은 인접한 바다의 수(상하좌우)만큼 녹는다. 예를 들어 빙산의 위쪽과 왼쪽이 바다라면, 1년에 2만큼 녹는다. 입력받을 때 바다를 0대신 -1로 저장하고, 빙산의 위치는 Queue에 집어넣는다.빙산이 녹는 것은 BFS와 비슷한 방법으로, 빙산에 인접한 상하좌우를 확인한다.만약 인접한 곳이 바다라면, 인접한 수만큼 빙산을 녹인다.빙산의 개수만큼 모두 녹이고, 연도를 1년 증가시킨다.DFS(또는 BFS)를 통해 두 덩어리 이상으로 쪼개져있는지 확인한다. 2개 이상이라면 연도를 반환하고 종료한다.두 덩어리 이상이 될 때까지 계속 빙산을 ..
BOJ 10974 · 모든 순열
알고리즘 분류 : 브루트 포스 C++ STL의 algorithm에 구현되어 있는 next_permutation 함수를 사용하면 된다.next_permutation 구현은 다음 글을 참조. C++ 소스코드 #include #include using namespace std; int main() { int n; scanf("%d", &n); int a[n]; for (int i=0; i 0 and a[i-1] >= a[i]: i -= 1 if i == 0: return False j = n while a[i-1] >= a[j]: j -= 1 a[i-1], a[j] = a[j], a[i-1] j = n while i
BOJ 10973 · 이전 순열
알고리즘 분류 : 브루트 포스 C++ STL의 algorithm에 있는 prev_permutation 함수를 사용하면 된다.prev_permutation 구현 방법은 next_permutation과 똑같이 구현할 수 있으며, 순서만 바꾸면 된다.next_permutation 구현 방법은 다음 글을 참조. C++ 소스코드 #include #include using namespace std; int main() { int n; scanf("%d", &n); int a[n]; for (int i=0; i 0 && a[i-1] 0 and a[i-1]
BOJ 10972 · 다음 순열
알고리즘 분류 : 브루트 포스 순열 알고리즘은 C++ STL에 구현되어 있다. algorithm 라이브러리에 있는 next_permutation 함수를 이용하면 된다. next_permutation은 배열(또는 벡터)의 범위를 인자로 받고, 다음 순열이 존재하면 true를 없으면 false를 반환한다. next_permutation을 구현하는 방법은 아래와 같다. 배열 또는 벡터의 이름이 a라고 가정하자.인덱스 i가 0보다 크고, a[i-1] >= a[i] 를 만족하면, 인덱스 i를 1씩 반복적으로 감소시킨다.반복문을 벗어난 후, 인덱스 i가 0이면, 다음 순열이 존재하지 않으므로 false를 반환한다.a[i-1] >= a[j] 를 만족하면, 인덱스 j를 1씩 반복적으로 감소시킨다.a[i-1]의 값과 a..
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..