Dev_Diary

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: (..

https://www.acmicpc.net/problem/2668 2668번: 숫자고르기 세로 두 줄, 가로로 N개의 칸으로 이루어진 표가 있다. 첫째 줄의 각 칸에는 정수 1, 2, …, N이 차례대로 들어 있고 둘째 줄의 각 칸에는 1이상 N이하인 정수가 들어 있다. 첫째 줄에서 숫자를 적절 www.acmicpc.net 기본 아이디어는 '무작위로 뽑아서 계산하지 말고 테이블 둘째 줄에 적혀있는 수로 이동하면 적어도 하나의 수는 첫째줄 집합에 포함된다' 입니다. 이런 아이디어를 갖고 어떻게 구현할지 생각해보니 단순히 DFS, 즉 스택을 이용하면 될 것 같다는 생각이 들었습니다. def solution(N, table): # 스택 리스트 stack_list = [] # 자신의 값을 가지면 미리 넣어두기 ..

https://www.acmicpc.net/problem/1655 1655번: 가운데를 말해요 첫째 줄에는 백준이가 외치는 정수의 개수 N이 주어진다. N은 1보다 크거나 같고, 100,000보다 작거나 같은 자연수이다. 그 다음 N줄에 걸쳐서 백준이가 외치는 정수가 차례대로 주어진다. 정수는 -1 www.acmicpc.net 수가 들어올 때 마다 정렬이 되어야 한다 그러므로 정렬에 많은 시간이 소요되면 안된다 다른 순서는 필요없고 중간만 맞으면 된다 라는 특성이 문제를 푸는데 가장 중요한 포인트였습니다. 우선 힙(우선순위큐)를 사용했는데, 이유는 다음과 같습니다. 수가 들어올 때 마다 정렬이 되어야 한다 -> 힙 삽입으로 해결 정렬에 많은 시간이 소요되면 안된다 -> 힙 정렬로 해결 다른 순서는 필요없..

https://www.acmicpc.net/problem/2659 2659번: 십자카드 문제 입력은 한 줄로 이루어지며, 이 한 줄은 카드의 네 모서리에 씌여있는 1 이상 9 이하의 숫자 4개가 시계 방향으로 입력된다. 각 숫자 사이에는 빈칸이 하나 있다. www.acmicpc.net 따로 핵심 아이디어는 없었고 구현만 하면 풀 수 있는 문제였습니다. 다만 몇 번째인지 구할 때 십자수가 아닌 수를 주의하면 쉽게 풀 수 있습니다. def solution(card): clock_num = find_min(card) return count_min(clock_num) # 시계수 찾기 def find_min(card): min_card = int(card) # 카드 돌리면서 최솟값 찾기 for _ in range..