프로그래밍/알고리즘
BOJ 10026 · 적록색약
알고리즘 분류 : BFS 적록색약인과 비색약인이 구별하는 색의 영역 개수를 구하는 문제다. BFS를 통해 구현할 수 있다. BFS를 이용하여 맵을 탐색한다.먼저 비색약인으로 모든 영역을 탐색하면서, 영역의 개수를 카운트한다.다음으로 적록색약인으로 모든 영역을 탐색한다.적록색약인의 경우, 적색(R)과 녹색(G)을 같은 색으로 취급한다. C++ 소스코드 #include #include #include using namespace std; struct color { int x, y; }; int n; char a[101][101]; bool check[101][101]; const int dx[] = {-1, 0, 1, 0}, dy[] = {0, 1, 0, -1}; // c is color. // w is a..
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..