Dev_Diary

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 # ..

https://www.acmicpc.net/problem/5014 5014번: 스타트링크 첫째 줄에 F, S, G, U, D가 주어진다. (1 ≤ S, G ≤ F ≤ 1000000, 0 ≤ U, D ≤ 1000000) 건물은 1층부터 시작하고, 가장 높은 층은 F층이다. www.acmicpc.net 이 문제는 전형적인 그래프 탐색 문제입니다. BFS 와 DFS 중 적절하게 선택해 풀면 됩니다. # BFS 쓸거라 deque from collections import deque def solution(F, S, G, U, D): # 선택지 selects = [U, -D] # 방문한 위치 visited = [1 if floor != S else 0 for floor in range(F+1)] que = deq..

https://www.acmicpc.net/problem/2644 2644번: 촌수계산 사람들은 1, 2, 3, …, n (1 ≤ n ≤ 100)의 연속된 번호로 각각 표시된다. 입력 파일의 첫째 줄에는 전체 사람의 수 n이 주어지고, 둘째 줄에는 촌수를 계산해야 하는 서로 다른 두 사람의 번호가 주어 www.acmicpc.net 전형적인 그래프 탐색 문제입니다. 일반적으로 DFS, BFS 중 선택해서 풀면 됩니다. def solution(a, b, n, m, data_list): # 방문기록 visited = [1 for _ in range(n+1)] visited[a] = 0 # 트리 tree = [[] for _ in range(n+1)] for parent, child in data_list: t..

https://www.acmicpc.net/problem/12865 12865번: 평범한 배낭 첫 줄에 물품의 수 N(1 ≤ N ≤ 100)과 준서가 버틸 수 있는 무게 K(1 ≤ K ≤ 100,000)가 주어진다. 두 번째 줄부터 N개의 줄에 거쳐 각 물건의 무게 W(1 ≤ W ≤ 100,000)와 해당 물건의 가치 V(0 ≤ V ≤ 1,000) www.acmicpc.net 이 문제는 냅색 알고리즘이라고 불리는 알고리즘의 전형적인 문제입니다 간단하게 설명하자면 무게와 물체 두 축을 가진 2차원 memoization 이라고 할 수 있습니다. # 배낭문제 (냅색 알고리즘) def solution(N, K, objects): # 정렬 objects = sorted(objects, key=lambda x: (..