Dev_Diary

https://www.acmicpc.net/problem/11726 11726번: 2×n 타일링 2×n 크기의 직사각형을 1×2, 2×1 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오. 아래 그림은 2×5 크기의 직사각형을 채운 한 가지 방법의 예이다. www.acmicpc.net 어떤 경우의 수로 나눠서 풀어야할지만 생각하면 간단하지만 이를 생각하기가 어려운 문제였습니다. 마지막에 오는 타일의 모양을 생각하면 쉽게 풀 수 있습니다. def solution(n): # DP memo = [0 for _ in range(n+1)] # 2까지만 채우기 memo[1] = 1 if n == 1: return memo[1] memo[2] = 2 # i 번째 맨 뒤가 = 모양이면 # (i-2) 가지 이고 #..

https://www.acmicpc.net/problem/11659 11659번: 구간 합 구하기 4 첫째 줄에 수의 개수 N과 합을 구해야 하는 횟수 M이 주어진다. 둘째 줄에는 N개의 수가 주어진다. 수는 1,000보다 작거나 같은 자연수이다. 셋째 줄부터 M개의 줄에는 합을 구해야 하는 구간 i와 j www.acmicpc.net 누적합 알고리즘을 알고있다면 간단한 문제였습니다. def solution(N, M, num_list, data_list): # 누적합 리스트 만들기 sum_list = make_sum_list(N, num_list) # i ~ j 구간의 합은 (j 까지의 누적합) - (i-1 까지의 누적합) for i, j in data_list: print(sum_list[j] - sum..

https://www.acmicpc.net/problem/2579 2579번: 계단 오르기 계단 오르기 게임은 계단 아래 시작점부터 계단 꼭대기에 위치한 도착점까지 가는 게임이다. 과 같이 각각의 계단에는 일정한 점수가 쓰여 있는데 계단을 밟으면 그 계단에 쓰여 있는 점 www.acmicpc.net def solution(N, data_list): # memo 와 자릿수 맞추기 data_list = [0] + data_list # DP # 2 까지는 미리 채우기 memo = [0 for _ in range(N+1)] memo[1] = data_list[1] # N 이 1이면 if N == 1: return memo[1] memo[2] = memo[1] + data_list[2] # N 이 2면 if N ..

https://www.acmicpc.net/problem/1149 1149번: RGB거리 첫째 줄에 집의 수 N(2 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 각 집을 빨강, 초록, 파랑으로 칠하는 비용이 1번 집부터 한 줄에 하나씩 주어진다. 집을 칠하는 비용은 1,000보다 작거나 www.acmicpc.net 전형적인 DP 기본 문제입니다. 하지만 처음 선택한 색에 따라 최솟값이 달라지므로 시작이 다른 세 가지 경우 모두 값을 계산해보고 그 중 최솟값을 출력해야 합니다. def solution(N, data_list): # 인덱스 맞추기 data_list = [[0, 0, 0, 0]] + data_list # 시스템 상 최댓값 inf = 1000001 # 2차원 DP # 첫 선택에..

https://www.acmicpc.net/problem/1463 1463번: 1로 만들기 첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다. www.acmicpc.net DP 알고리즘의 전형적인 문제입니다. 어떤 조건에서 이전 단계와 다음 단계를 연결할 수 있는지 생각하면 쉽게 풀 수 있습니다. def solution(N): # 앞에서부터 메모 memo = [-1 for _ in range(N+1)] # 앞에 1 은 자체니까 0 memo[1] = 0 i = 2 while True: # 정지 조건 if i > N: return memo[-1] # 가능 목록 # 3으로 나눠지면 3으로 나눈 인덱스 # 2로 나눠지면 2로 나눈 인덱스 # 1보다 크면 1을 뺀 인덱스 candid_li..

https://www.acmicpc.net/problem/9095 9095번: 1, 2, 3 더하기 각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 방법의 수를 출력한다. www.acmicpc.net DP 문제의 전형적인 케이스로 점화식만 찾는다면 쉬운 문제입니다. 맨 앞에 올 수를 고정시킨다는 느낌으로 생각하면 쉽게 구할 수 있습니다. def solution(n_list): # 하나씩 받으면 다시 계산해야 하니까 리스로 받아서 계산하자 # 리스트 최댓값 target = max(n_list) # 메모 memo = [0 for _ in range(target+1)] # 인덱스 0 은 자신을 더해주는 개념이므로 1 배정 memo[0] = 1 # 인덱스 1 은 하나뿐이므로 미리 작성 memo[1]..

https://www.acmicpc.net/problem/14503 14503번: 로봇 청소기 첫째 줄에 방의 크기 $N$과 $M$이 입력된다. $(3 \le N, M \le 50)$ 둘째 줄에 처음에 로봇 청소기가 있는 칸의 좌표 $(r, c)$와 처음에 로봇 청소기가 바라보는 방향 $d$가 입력된다. $d$가 $0$인 경우 북쪽 www.acmicpc.net 그래프 탐색 문제지만 구현 능력이 조금 필요했습니다. 단순히 이동만 신경쓰는게 아닌 방향이라는 요소가 추가되어 조금 까다롭지만 결국 이 요소만 해결하면 쉽게 해결할 수 있는 문제였습니다. def solution(N, M, r, c, d, data_list): # 움직임 가이드 guide_x = [0, 1, 0, -1, 0, 1, 0, -1, 0] ..

https://www.acmicpc.net/problem/9205 9205번: 맥주 마시면서 걸어가기 송도에 사는 상근이와 친구들은 송도에서 열리는 펜타포트 락 페스티벌에 가려고 한다. 올해는 맥주를 마시면서 걸어가기로 했다. 출발은 상근이네 집에서 하고, 맥주 한 박스를 들고 출발한다. www.acmicpc.net 전형적인 그래프 탐색 문제입니다. 다만 DFS 로 풀었다 시간초과가 발생해서 BFS 로 풀었습니다. from collections import deque def solution(n, field): # 맵 정리 start, field = field[0], field[1:] # BFS 로 풀거 que = deque([start]) # 방문 기록 visited = [1 for _ in range(..

https://www.acmicpc.net/problem/2573 2573번: 빙산 첫 줄에는 이차원 배열의 행의 개수와 열의 개수를 나타내는 두 정수 N과 M이 한 개의 빈칸을 사이에 두고 주어진다. N과 M은 3 이상 300 이하이다. 그 다음 N개의 줄에는 각 줄마다 배열의 각 행을 www.acmicpc.net 단순한 그래프 탐색 문제지만 추가 작업이 필요하다. 탐색을 하면서 빙산을 녹여주며 덩어리의 수를 찾는 작업을 반복하면 된다. 탐색 -> BFS 와 녹이는 작업 같이 -> 덩어리 수 카운트 import copy def solution(N, M, field): # 소요 시간 year = 0 while True: # 덩어리 수 cnt = 0 # 방문 기록 visited = [[1 if field[..

https://www.acmicpc.net/problem/2468 2468번: 안전 영역 재난방재청에서는 많은 비가 내리는 장마철에 대비해서 다음과 같은 일을 계획하고 있다. 먼저 어떤 지역의 높이 정보를 파악한다. 그 다음에 그 지역에 많은 비가 내렸을 때 물에 잠기지 않는 www.acmicpc.net 기본적인 그래프 탐색 문제인데 추가 작업이 몇 개 있다. 물의 수위를 바꿔가며 반복적으로 카운팅을 해주면 된다. def solution(N, field): # 최대 지역 수 max_cnt = 0 # 물의 수위 max_water = max([max(row) for row in field]) # 물의 수위를 변경해가며 for water in range(max_water+1): # 지역 수 cnt = 0 # ..