KMF

주어진 조건에 따라 구현하는 문제이다. 먼저 모든 구역의 인구의 합을 구하고 1-4 구역을 나눈 뒤 해당 인구를 모두 제외하면 5구역의 인구를 구할 수 있다. 경계선을 먼저 만든 후 구역을 나눌때 주의해야할 사항이 있다. 만일 경계선을 만날 경우 다음행으로 바로 넘어가도록 코드를 작성할 경우 1, 3번 구역은 정상적으로 나뉘어진다. 하지만 2, 4 번 구역은 경계선의 우측에 위치하기 때문에 경계선에서 부터 인덱스가 시작할 수 있다. 따라서 열의 역순으로 구역을 채워나가야한다. Python Java

R과 C 연산에 따라 나온 각각 행과 열에 속하는 수를 1. 등장 횟수, 2. 수의 크기(오름 차순)을 기준으로 정렬하는 문제이다. 시간이 100까지 반복되기 떄문에 매 초마다 파이썬 정렬 내장 함수를 사용하고 싶지 않아 dict와 count 배열을 사용하여 정렬하였다. count 배열에는 각각의 행 혹은 열에있는 수들의 등장 횟수를 저장한 배열이다. dict에서는 등장 횟수를 key 로 하여 숫자 배열이 저장된다. 저장된 dict의 key 값을 1 ~ 100 까지 순회하여 key와 value를 가지고 새로운 배열을 만들면 된다. Python

소문난 칠공주를 결성할 수 있는 모든 경우의 수를 구하는 문제이다. 브루트 포스, 백트래킹 알고리즘 유형에 해당한다. 단, 소문난 칠공주는 가로 또는 세로로 모두 인접해야하며, 이다솜파가 과반수(4)이상 이어야 한다. 여학생반의 크기는 5*5 크기로 고정되어 있기 떄문에 학생들을 0 ~ 24로 인덱싱한다. n번 학생의 위치는 (n / 5, n%5 )에 위치한다. DFS를 통해 0번 부터 24번 학생까지 순회한다. 현재 학생을 I라고 하면 I 학생은 이다솜파, 임도연파 중 하나이며 소문난 칠공주에 포함할 지 결정한다. 7명을 모두 소집한 경우 모두 인접한지 확인한다. 시작점을 기준으로 상, 하, 좌, 우 인접한 노드를 DFS로 방문하여 인접한 경우 카운트를 1 증가시키고 7이 되는 경우 모두 인접한 것으로..

원숭이가 (0, 0) 지점에서 (W-1, H-1)까지 이동하는 이동 횟수의 최소값을 구하는 문제이다. 처음 문제를 접하고 DP를 사용하면 해결 할 수 있을 것 같아 시도하였지만, 해결하지 못했다. 다른 풀이를 보니 BFS로 해결할 수 있었다. 먼저 DP로 왜 해결할 수 없었는 지에 대해서 설명한다. 입력 1 6 6 0 1 1 1 1 0 0 1 1 1 1 0 0 0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 1 1 0 0 0 1 0 출력(정상) 8 위 값이 입력으로 주어져 DFS & DP 를 수행하면 중간 지점에 아래와 같은 결과가 출력된다. [0, 0, 0, 0, 0, 11] [1, 0, 0, 0, 0, 10] [2, 3, 8, 9, 8, 9] [0, 4, 7, 8, 9, 10] [0, 5, ..

지도의 (0, 0) 지점에서 (M-1, N-1)까지 내리막길로 이동할 수 있는 경로의 수를 구하는 문제이다. 다이내믹 프로그래밍을 사용하여 해결 할 수 있다. 다이내믹 프로그래밍에는 Bottom-up 방식인 Tabulation 기법과 Top-down 방식인 Memoization 기법이 존재한다. Tabulation 기법은 보통 반복문으로 구현하며, Memoization은 보통 재귀 함수로 구현한다. 메모리나 시간 복잡도를 고려하였을 때 Memoization에 비해 Tabulation이 더 효율적이지만 상황에 따라 다르게 적용될 수 있으므로 두 가지 방법 모두 알고있어야 한다. Tabulation 예제 // Tabulated version to find factorial x. int dp[MAXN]; //..

(r, c)를 방문한 순서를 구하는 문제이다. 분할 정복 알고리즘으로 해결할 수 있다. 브루트 포스를 통해 모든 셀을 방문하여 (r, c)에 대한 순서를 구할 수도 있지만 시간 초과가 발생한다. 따라서 이미 주어지는 r, c의 값을 가지고 최적화를 해야한다. 전체 배열의 시작점(가장 왼쪽 구석 지점)을 start_row, start_col이라 가정했을 때, 전체 배열을 4등분하고 각각의 배열 시작점과 끝점을 나타내면 아래와 같다. 시작: start_row, start_col 끝: start_row + 세로의 길이 / 2 -1, start_col+ 가로의 길이 / 2 - 1 시작: start_row, start_col+ 가로의 길이 / 2 끝: start_row + 세로의 길이 / 2 -1, start_c..

10 * 10 격자판의 1을 모두 덮는 최소 색종이 개수를 구하는 문제이다. 단순 반복문 보다는 백트래킹 알고리즘을 사용하면 쉽게 해결할 수 있다. 1. 색종이 사이즈 배열 S에 지금까지 사용한 색종이의 개수를 저장한다. 2. 재귀 함수를 사용한다. 열 번호를 하나씩 증가시키고 열 번호가 10일 경우 행 번호를 하나 증가시키고 다시 열번호를 0으로 초기화한다. 3. 열번호가 10일 경우 색종이의 총 개수를 반환하며, 가장 작은 경우를 출력한다. 색종이 사이즈가 s * s라고 할때 s에 0 - 4를 대입하여 반복한다. 만일 해당 색종이를 5장 미만 사용했다면 해당 구간의 배열을 완전탐색하여 모든 값이 1인 경우 색종이로 덮는다. 이는 1을 0으로 치환하는 것으로 대신한다. 덮은 후 열 번호를 s+1 증가시..

문제에 주어진 조건에 따라 그대로 구현하는 문제이다. 문제를 크게 두개로 나누면 낚시왕이 이동 후 상어를 낚는 것, 상어가 이동하는 것으로 나눌 수 있다. 낚시왕이 상어를 낚는 것 낚시왕은 1초가 지나면 오른쪽으로 이동한다. 이동한 열에서 가장 바닦에 가까운 상어를 낚는다. 상어가 이동하는 것 먼저 방향이 1, 2,(상, 하), 3, 4(우 ,좌)인 것을 나누어 생각한다. 그 중 3, 4인 것을 예로 설명 하겠다. 현재 위치(열 번호)와 끝 지점간 차이를 구한다. 이때 끝 지점은 방향이 3일 경우 C가 되고 4일 경우는 1이 될 것이다. 그 차이가 속도보다 크거나 같은 경우 현재 위치에서 속도를 뺀다. 이는 최대한 도달할 수 있는 지점이 끝 지점이기 때문에 방향을 바꾸어 돌아 오는 것을 생각하지 않아도 ..

N*M의 격자판에서 3명의 궁수를 위치시켜 잡을 수 있는 적의 최대를 구하는 문제이다. 궁수가 적을 잡는 경우 1. 궁수는 D 거리 이하에 있는 적만을 잡을 수 있다. 2. 궁수는 가장 가까운 적을 죽인다. 3. 그러한 적이 여러명 존재할 경우 가장 왼쪽에 위치한 적을 죽인다. 4. 같은 적을 죽일 수 있다. 궁수 배치하기 가능한 모든 궁수들의 배치를 구해야 하기 때문에 itertools 모듈의 combinations를 사용한다. 죽일 적 찾기 & 적 죽이기 D 거리 이하에 위치하고 가장 가까운 적을 찾기 위해서 BFS를 활용한다. 이때 파이썬의 heapq 모듈을 사용한다. 궁수와 적간의 거리, 궁수의 위치를 큐에 저장한다. 단 거리가 D를 초과하면 잡을 수 있는 적이 존재하지 않기 때문에 (-1, -1..

아기 상어가 N * N 크기의 공간을 먹이를 먹으면서 움직이는 최단 거리를 구하는 문제이다. 최단 거리를 구하는 알고리즘은 다양하게 존재하지만 이 문제는 BFS를 사용하여 해결할 수 있다. 파이썬의 heapq 모듈을 사용한다. heaq에는 아기 상어의 이동 횟수, 위치, 크기, 지금까지 먹은 물고기의 수가 저장된다. heapq 모듈은 가장 첫번째 원소를 기준으로 정렬하기 때문에 반드시 이동 횟수를 가장 처음에 위치해야한다. 먹이를 먹는 우선순위가 몇 가지 존재하는데 유의해야한다. 1. 가장 가까운 먹이를 우선적으로 먹는다 heapq모듈을 사용한 BFS로 자연스럽게 해결된다 2. 가장 가까운 먹이가 여러 마리일 경우, 가장 위쪽에 위치한 물고기를 먹는다. 또 그러한 물고기가 여러 마리인 경우 가장 왼쪽에 ..