문제 https://www.acmicpc.net/problem/1620 1620번: 나는야 포켓몬 마스터 이다솜 첫째 줄에는 도감에 수록되어 있는 포켓몬의 개수 N이랑 내가 맞춰야 하는 문제의 개수 M이 주어져. N과 M은 1보다 크거나 같고, 100,000보다 작거나 같은 자연수인데, 자연수가 뭔지는 알지? 모르면 www.acmicpc.net 풀이 특정값 탐색에 유리한 해시 테이블 자료구조를 사용합니다. 해시 테이블에서 특정값 탐색의 시간 복잡도는 O(1)입니다. 파이썬에선 딕셔너리 타입으로 이를 구현합니다. isalpha()는 해당 문자열이 한글이나 알파벳으로만 이루어져있는지 확인하는 함수입니다. isdecimal()는 해당 문자열이 숫자로만 이루어져있는지 확인하는 함수입니다. 코드 import sy..

문제 https://www.acmicpc.net/problem/2512 2512번: 예산 첫째 줄에는 지방의 수를 의미하는 정수 N이 주어진다. N은 3 이상 10,000 이하이다. 다음 줄에는 각 지방의 예산요청을 표현하는 N개의 정수가 빈칸을 사이에 두고 주어진다. 이 값들은 모두 1 이상 www.acmicpc.net 풀이 이분 탐색을 이용하여 풉니다. n개의 예산 요청액들을 moneys 리스트에 저장하고 이분 탐색의 탐색 범위는 0부터 max(moneys)까지 입니다. 이분 탐색 반복문을 돌면서 총 예산 합(result)이 최대 예산(m)을 넘지 않으면서 가장 큰 값이 될 때의 최대 상한액(limit)을 구합니다. 코드 import sys def binary_search(left, right): r..

문제 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..