학교에서 인터넷 프로그래밍 및 실습 강의에서 과제로 슬라이딩 퍼즐을 푸는 알고리즘을 구현해본 적이 있다. 당시 코드 이번에 모 기업의 지원서를 쓰면서 그때의 경험을 썼는데 이번 기회에 당시 과제를 해결하면서 사용했던 알고리즘인 A , IDA 알고리…

G4) 2636. 치즈 문제 아래 <그림 1>과 같이 정사각형 칸들로 이루어진 사각형 모양의 판이 있고, 그 위에 얇은 치즈(회색으로 표시된 부분)가 놓여 있다. 판의 가장자리(<그림 1>에서 네모 칸에 X친 부분)에는 치즈가 놓여 있지 않으며 치즈…

G3) 16236. 아기 상어 문제 N×N 크기의 공간에 물고기 M마리와 아기 상어 1마리가 있다. 공간은 1×1 크기의 정사각형 칸으로 나누어져 있다. 한 칸에는 물고기가 최대 1마리 존재한다. 아기 상어와 물고기는 모두 크기를 가지고 있고, 이 …

S1) 9205. 맥주 마시면서 걸어가기 문제 송도에 사는 상근이와 친구들은 송도에서 열리는 펜타포트 락 페스티벌에 가려고 한다. 올해는 맥주를 마시면서 걸어가기로 했다. 출발은 상근이네 집에서 하고, 맥주 한 박스를 들고 출발한다. 맥주 한 박스에…

플로이드-워셜 알고리즘 그래프 상에서 가능한 모든 노드 쌍들에 대해 최단 거리를 구하는 알고리즘이다. 같은 최단 거리 알고리즘인 다익스트라 알고리즘과는 달리 모든 노드 쌍에 대해 최단 거리를 구할 수 있고, 음의 가중치를 가진 간선이 그래프에 있어도…

최장 증가 부분 수열 (LIS, Longest Increasing Subsequence) 어떤 수열의 부분 수열 중 수열의 순서를 유지하면서 크기가 점점 증가하는 가장 긴 부분 수열을 말한다. 예를 들어 크기가 6인 수열 { 5, 8, 9, 4, 2…

G4) 2239. 스도쿠 문제 스도쿠는 매우 간단한 숫자 퍼즐이다. 9×9 크기의 보드가 있을 때, 각 행과 각 열, 그리고 9개의 3×3 크기의 보드에 1부터 9까지의 숫자가 중복 없이 나타나도록 보드를 채우면 된다. 예를 들어 다음을 보자. 위 …

S4) 1018. 체스판 다시 칠하기 문제 지민이는 자신의 저택에서 MN개의 단위 정사각형으로 나누어져 있는 M×N 크기의 보드를 찾았다. 어떤 정사각형은 검은색으로 칠해져 있고, 나머지는 흰색으로 칠해져 있다. 지민이는 이 보드를 잘라서 8×8 크…

S2) 1012. 유기농 배추 문제 차세대 영농인 한나는 강원도 고랭지에서 유기농 배추를 재배하기로 하였다. 농약을 쓰지 않고 배추를 재배하려면 배추를 해충으로부터 보호하는 것이 중요하기 때문에, 한나는 해충 방지에 효과적인 배추흰지렁이를 구입하기로…

S5) 1010. 다리 놓기 문제 재원이는 한 도시의 시장이 되었다. 이 도시에는 도시를 동쪽과 서쪽으로 나누는 큰 일직선 모양의 강이 흐르고 있다. 하지만 재원이는 다리가 없어서 시민들이 강을 건너는데 큰 불편을 겪고 있음을 알고 다리를 짓기로 결…