문제 https://www.acmicpc.net/problem/2206 2206번: 벽 부수고 이동하기 N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 당신은 (1, 1)에서 (N, M)의 위치까지 이동하려 하는데, 이때 최단 경로 www.acmicpc.net 풀이 BFS와 3차원 배열을 사용했습니다. 최단 거리를 저장할 3차원 배열 visited를 선언하고 0으로 초기화 합니다.(visited[0][0][1] = 1) smash가 1일 경우 벽을 뚫을 수 있는 상태라는 것을 나타냅니다. 큐에서 popleft한 값이 벽일 경우(1) smash가 1일 때 벽을 부수고 smash를 0으로 변경하여 큐에 푸쉬하고, visited..

문제 https://www.acmicpc.net/problem/9613 9613번: GCD 합 첫째 줄에 테스트 케이스의 개수 t (1 ≤ t ≤ 100)이 주어진다. 각 테스트 케이스는 한 줄로 이루어져 있다. 각 테스트 케이스는 수의 개수 n (1 b) 두 수가 있을 때, a와 b의 최대공약수 G는 b와 a%b의 최대공약수 G'과 같다는 알고리즘입니다. 코드 import sys from itertools import combinations def GCD(A: int, B: int) -> int: if B == 0: return A return GC..

문제 https://www.acmicpc.net/problem/1890 1890번: 점프 첫째 줄에 게임 판의 크기 N (4 ≤ N ≤ 100)이 주어진다. 그 다음 N개 줄에는 각 칸에 적혀져 있는 수가 N개씩 주어진다. 칸에 적혀있는 수는 0보다 크거나 같고, 9보다 작거나 같은 정수이며, 가장 www.acmicpc.net 풀이 처음에 BFS로 풀 때는 메모리 초과가 나오고 DFS로 풀 때는 시간 초과가 나왔습니다. BFS 코드: import sys from collections import deque n = int(sys.stdin.readline().rstrip()) matrix = [] answer = 0 for _ in range(n): matrix.append(list(map(int, sys..

문제 https://www.acmicpc.net/problem/2630 2630번: 색종이 만들기 첫째 줄에는 전체 종이의 한 변의 길이 N이 주어져 있다. N은 2, 4, 8, 16, 32, 64, 128 중 하나이다. 색종이의 각 가로줄의 정사각형칸들의 색이 윗줄부터 차례로 둘째 줄부터 마지막 줄까지 주어진다. www.acmicpc.net 풀이 현재 선택된 색종이의 색이 모두 같은 색으로 칠해져 있는지 확인하는 check_color 메서드를 선언합니다. 재귀로 check_color의 결과값이 False인 색종이는 4등분하는 solution 메서드를 선언합니다. 코드 import sys def check_color(y, x, length): color = matrix[y][x] for i in rang..

문제 https://www.acmicpc.net/problem/1004 1004번: 어린 왕자 입력의 첫 줄에는 테스트 케이스의 개수 T가 주어진다. 그 다음 줄부터 각각의 테스트케이스에 대해 첫째 줄에 출발점 (x1, y1)과 도착점 (x2, y2)이 주어진다. 두 번째 줄에는 행성계의 개수 n이 주 www.acmicpc.net 풀이 (x, y)와 (a, b)의 두 점 거리 = ((x - a) ** 2 + (y - b) ** 2)) ** 0.5 아래의 경우에만 진입/이탈 횟수를 1 증가시킵니다. 1. 행성계 안에 출발 지점이 있고 행성계 밖에 도착 지점이 있을 때 2. 행성계 안에 도착 지점이 있고 행성계 밖에 출발 지점이 있을 때 코드 import sys t = int(sys.stdin.readlin..

문제 https://www.acmicpc.net/problem/2293 2293번: 동전 1 첫째 줄에 n, k가 주어진다. (1 ≤ n ≤ 100, 1 ≤ k ≤ 10,000) 다음 n개의 줄에는 각각의 동전의 가치가 주어진다. 동전의 가치는 100,000보다 작거나 같은 자연수이다. www.acmicpc.net 풀이 다이나믹 프로그래밍을 이용해서 풉니다. 다이나믹 프로그래밍은 큰 문제를 작은 문제들로 나누어 푸는 것을 말합니다. 이 문제에서 동전 가치의 합이 k가 되는 조합의 수를 구하는 큰 문제를 동전별로 작은 문제로 나누어 풀 것입니다. dp 배열의 index는 가치의 합을 나타내고 dp[index]는 가치 합이 index가 되는 동전 조합의 수를 나타냅니다. dp를 0으로 초기화하고 dp[0]은..