Younghun Go

1. 다익스트라(Dijkstra) 인공위성 GPS 소프트웨어에서 사용된다는(?) 알고리즘. 한 정점을 기준으로 다른 모든 정점으로 가는 최단 경로를 알 수 있다. 이 때 중요한 건 양의 가중치일 때만 최단 경로 계산이 가능하다. 다익스트라 알고리즘은 다이나믹 프로그래밍 문제이기도 하다. 이 말이 이해가 잘 안됐는데 쉽게 설명하면 우리는 최단 경로를 각 정점을 돌면서 갱신하기 때문에 이전에 기록해뒀던 최단 경로를 비교해가며 갱신한다. 이 때문에 다이나믹 프로그래밍 문제로 볼 수 있다. 시간 복잡도는 어떻게 될까? 기본적으로 다익스트라 알고리즘은 가중치가 작은 정점부터 방문해야한다. 따라서 힙 구조를 사용할 수 있는데 힙 중에서도 Min Heap을 사용한다. $N$개의 정점에 대하여 최소 비용을 탐색할 때 ..

문제 보석 공장에서 보석 상자를 유치원에 기증했다. 각각의 보석은 M가지 서로 다른 색상 중 한 색상이다. 원장 선생님은 모든 보석을 N명의 학생들에게 나누어 주려고 한다. 이때, 보석을 받지 못하는 학생이 있어도 된다. 하지만, 학생은 항상 같은 색상의 보석만 가져간다. 한 아이가 너무 많은 보석을 가져가게 되면, 다른 아이들이 질투를 한다. 원장 선생님은 이런 질투심을 수치화하는데 성공했는데, 질투심은 가장 많은 보석을 가져간 학생이 가지고 있는 보석의 개수이다. 원장 선생님은 질투심이 최소가 되게 보석을 나누어 주려고 한다. 상자에 빨간 보석이 4개 (RRRR), 파란 보석이 7개 (BBBBBBB) 있었고, 이 보석을 5명의 아이들에게 나누어 주는 경우를 생각해보자. RR, RR, BB, BB, B..

문제 N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 당신은 (1, 1)에서 (N, M)의 위치까지 이동하려 하는데, 이때 최단 경로로 이동하려 한다. 최단경로는 맵에서 가장 적은 개수의 칸을 지나는 경로를 말하는데, 이때 시작하는 칸과 끝나는 칸도 포함해서 센다. 만약에 이동하는 도중에 한 개의 벽을 부수고 이동하는 것이 좀 더 경로가 짧아진다면, 벽을 한 개 까지 부수고 이동하여도 된다. 맵이 주어졌을 때, 최단 경로를 구해 내는 프로그램을 작성하시오. 일반적인 BFS로 해결할 수 있는 문제. 벽을 부순 경우, 아닌 경우를 체크해야하기 때문에 현재 이동한 거리와 벽 부순 유무를 큐에 담아준다.

문제 오늘은 직사각형 모양의 방을 로봇 청소기를 이용해 청소하려고 한다. 이 로봇 청소기는 유저가 직접 경로를 설정할 수 있다. 방은 크기가 1×1인 정사각형 칸으로 나누어져 있으며, 로봇 청소기의 크기도 1×1이다. 칸은 깨끗한 칸과 더러운 칸으로 나누어져 있으며, 로봇 청소기는 더러운 칸을 방문해서 깨끗한 칸으로 바꿀 수 있다. 일부 칸에는 가구가 놓여져 있고, 가구의 크기도 1×1이다. 로봇 청소기는 가구가 놓여진 칸으로 이동할 수 없다. 로봇은 한 번 움직일 때, 인접한 칸으로 이동할 수 있다. 또, 로봇은 같은 칸을 여러 번 방문할 수 있다. 방의 정보가 주어졌을 때, 더러운 칸을 모두 깨끗한 칸으로 만드는데 필요한 이동 횟수의 최솟값을 구하는 프로그램을 작성하시오. 방문한 곳을 다시 방문할 수..

문제 피보나치 수는 0과 1로 시작한다. 0번째 피보나치 수는 0이고, 1번째 피보나치 수는 1이다. 그 다음 2번째 부터는 바로 앞 두 피보나치 수의 합이 된다. 이를 식으로 써보면 $F{n} = F{n-1} + F{n-2} (n>=2)$가 된다. n=17일때 까지 피보나치 수를 써보면 다음과 같다. 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597 $n$이 주어졌을 때, $n$번째 피보나치 수를 구하는 프로그램을 작성하시오. long long으로 커버가 안되는 문제. string으로 표현하면 숫자의 범위에 상관없이 표현할 수 있다. python은 big int를 처리해주기 때문에 python으로 짜면 편하다고 한다. top-..

문제 n가지 종류의 동전이 있다. 이 동전들을 적당히 사용해서, 그 가치의 합이 k원이 되도록 하고 싶다. 그러면서 동전의 개수가 최소가 되도록 하려고 한다. 각각의 동전은 몇 개라도 사용할 수 있다. 사용한 동전의 구성이 같은데, 순서만 다른 것은 같은 경우이다. 만약 n가지 종류의 동전이 서로 배수 관계라면 그리디 알고리즘으로 해결이 가능했다. 하지만 배수 관계가 아닌 경우 다이나믹 프로그래밍으로 해결해야한다. 위 문제의 경우 동전이 배수 관계인 경우, 아닌 경우 모두 다루기 때문에 다이나믹 프로그래밍으로 접근한다. 1. 처음 접근은 메모이제이션하려는 DP의 정의를 내린다. $dp[k]$ : $k$원을 만드는데 동전의 최소 사용 횟수 2. 점화식을 세운다 $dp[k] = min(dp[k-coin[i]..