문제 www.acmicpc.net/problem/7562 7562번: 나이트의 이동 체스판 위에 한 나이트가 놓여져 있다. 나이트가 한 번에 이동할 수 있는 칸은 아래 그림에 나와있다. 나이트가 이동하려고 하는 칸이 주어진다. 나이트는 몇 번 움직이면 이 칸으로 이동할 수 www.acmicpc.net 풀이 최단 거리와 관련된 그래프 탐색 문제는 너비 우선 탐색(BFS)를 통해 해결한다. 큐에 좌표(y,x)와 함께 이동횟수(cnt)를 함께 삽입하여 탐색시 1씩 증가하게 한다. 만약 이동하려는 칸의 좌표에 도달하면 이동횟수를 출력하고 탐색을 종료한다. 코드 import sys, collections dx = [-2, -2, -1, -1, 1, 1, 2, 2] dy = [1, -1, 2, -2, 2, -2, ..
문제 www.acmicpc.net/problem/2293 2293번: 동전 1 첫째 줄에 n, k가 주어진다. (1 ≤ n ≤ 100, 1 ≤ k ≤ 10,000) 다음 n개의 줄에는 각각의 동전의 가치가 주어진다. 동전의 가치는 100,000보다 작거나 같은 자연수이다. www.acmicpc.net 풀이 k 0 1 2 3 4 5 6 7 8 9 10 coin 0 0 0 0 0 0 0 0 0 0 0 1 1 0+1=1 0+1=1 0+1=1 0+1=1 0+1=1 0+1=1 0+1=1 0+1=1 0+1=1 0+1=1 2 1 1 1+1=2 1+1=2 1+2=3 1+2=3 1+3=4 1+3=4 1+4=5 1+4=5 1+5 = 6 5 1 1 1 2 3 3+1=4 4+1=5 4+2=6 5+2=7 5+3=8 6+4=10..
문제 www.acmicpc.net/problem/11057 11057번: 오르막 수 오르막 수는 수의 자리가 오름차순을 이루는 수를 말한다. 이때, 인접한 수가 같아도 오름차순으로 친다. 예를 들어, 2234와 3678, 11119는 오르막 수이지만, 2232, 3676, 91111은 오르막 수가 아니다. 수 www.acmicpc.net 풀이 쉬운 계단 수 문제와 아주 유사한 문제다. 하지만 수가 0으로 시작될 수 있다는 점에서 주의해야 한다. 맨 앞자리 수가 0이면 다음 숫자로 0~9까지 다 올 수 있으므로 dp[i][0] = dp[i-1][0] + dp[i-1][1] + ... + dp[i-1][8] + dp[i-1][9] 맨 앞자리 수가 1이면 다음 숫자로 1~9까지 올 수 있으므로 dp[i][1]..
문제 www.acmicpc.net/problem/1182 1182번: 부분수열의 합 첫째 줄에 정수의 개수를 나타내는 N과 정수 S가 주어진다. (1 ≤ N ≤ 20, |S| ≤ 1,000,000) 둘째 줄에 N개의 정수가 빈 칸을 사이에 두고 주어진다. 주어지는 정수의 절댓값은 100,000을 넘지 않는다. www.acmicpc.net 풀이 문제가 약간 이상하다. 당연히 경우의 수를 구하는 것이기 때문에 중복을 제거해줘야 한다고 생각했는데 중복을 제거하면 틀리게 나온다. 조합을 사용하거나 재귀를 이용하여 풀 수 있다. 조합을 사용하는 방법이 더 직관적이지만, 재귀를 이용하는 방법이 메모리나 속도면에서 효율적이다. 리스트의 첫번째 인덱스에서 시작해서 해당 요소를 건너뛰고 다음 인덱스로 가거나 해당 요소를..
문제 www.acmicpc.net/problem/4963 4963번: 섬의 개수 입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스의 첫째 줄에는 지도의 너비 w와 높이 h가 주어진다. w와 h는 50보다 작거나 같은 양의 정수이다. 둘째 줄부터 h개 줄에는 지도 www.acmicpc.net 풀이 DFS나 BFS를 이용해서 풀 수 있는 기본적인 그래프 탐색 문제다. 코드 BFS import sys, collections while True: w, h = map(int, sys.stdin.readline().split()) if w == 0 and h == 0: break g, lands, visited = [], [], [[0 for _ in range(w)] for _ in range(..