프로그래밍
BOJ 2680 · QR
알고리즘 분류 : 시뮬레이션, 문자열 처리 이 문제는 최소 사이즈(21*21)의 QR 코드를 디코딩하는 문제다. 구현보다 문제 이해가 어려운 문제다. 인코딩된 16진수 코드를 원래 정보로 복원해야 한다. 문자열로 처리하여 다소 무식하게 구현했다. 헥스 코드를 바이너리 코드로 변환한다.바이너리 코드를 앞에서부터 순서대로 읽으면서, 모드 비트(Mode Bits)와 카운트 비트(Count Bits)를 먼저 처리한다.숫자(Numeric)인 경우, 2진수를 10진수로 변환한다.숫자/문자(Alphanumeric)인 경우, 별도의 알파뉴메릭 배열을 만들어서 변환한다.8비트 문자(8 bit Byte) 또는 한자(Kanji)인 경우, 아스키 문자로 변환하거나 아스키 범위를 벗어나면 숫자로 출력한다.종료(Terminati..
BOJ 2589 · 보물섬
알고리즘 분류 : BFS BFS를 통해 맵을 탐색하면서 최단 거리를 구한다. 최단 거리 중에서 가장 긴 거리가 정답이다. 보물섬에서 이동할 때, 땅(L)에서 땅(L)으로만 이동할 수 있다. 물(W)로는 이동할 수 없다.BFS 탐색을 하면서 매번 이동 거리를 저장하고, 가장 큰 이동거리를 별도로 저장한다.전체 맵에 있는 땅(L)의 개수만큼 BFS 탐색을 반복한다.BFS 탐색 결과로 나오는 이동 거리 중, 가장 큰 값을 정답으로 낸다. C++ 소스코드 #include #include #include using namespace std; struct treasure { int x, y, d; }; int n, m; char a[51][51]; bool check[51][51]; const int dx[] = ..
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..