Dev_Diary

https://www.acmicpc.net/problem/1146브루트 포스나 BFS 의 식으로도 풀 수 있지만 시간제한에 걸리게 됩니다.다른 방법을 찾아봅시다. 우리는 N 명의 학생을 줄세워야 합니다.그 중 번호가 가장 큰 N 번째 학생을 P 번째 순서에 줄 세우는 경우를 생각해보겠습니다.그럼 남은 N-1 명의 학생을 줄 세워야 하는데, 어차피 수의 대소만이 중요하기 때문에 지그재그 패턴만 맞으면 어떤 학생이 어디에 서던 중요하지 않습니다.즉 N 번째 학생을 P 번째 세우고 양 옆에 남은 학생들을 다시 줄세우는 작은 단계로 쪼갤 수 있습니다.즉 이 문제를 DP 로 풀 수 있습니다. N 명의 학생 중 P 번째 자리에 N 번째 학생을 줄세운다고 생각하겠습니다.해당 경우를 A_NP 라고 부르겠습니다. P 가..

https://www.acmicpc.net/problem/1153합으로 구해야 하는 네 개의 소수 조합을 모두 찾는다면 시간초과가 발생합니다.그렇다면 조합의 수를 줄여야 하는데, 여기서 사용할 수 있는 이론이 골드바흐의 추측입니다.아직 증명되지는 않았지만 충분히 큰 수에 대해 모두 성립하는 추측이므로 해당 문제에서 사용할 수 있습니다. 모든 짝수에 대해 두 개의 소수의 합으로 표현할 수 있다는 것이 주된 내용인데, 그렇다면 N 이 주어졌을 때 미리 두개를 정해놓고 두개만 조합으로 구할 수 있습니다. N 이 짝수인 경우, 골드바흐 추측을 사용하기 위해 N - K 도 짝수로 만들어야 합니다.그렇다면 K 도 짝수이므로 합이 가장 작은 짝수의 조합인 [2, 2] 를 미리 정해놓을 수 있습니다.N 이 홀수인 경우..

https://www.acmicpc.net/problem/1106전형적인 냅색 알고리즘 문제입니다.다만 최대 비용을 설정할 때 100원에 1명을 모집하는 경우가 최악이므로 최대 비용은 목표인원 x 100 으로 설정하주면 해결할 수 있습니다.import sysinput = sys.stdin.readlinedef solution(C, N, data_list):    # 최대 비용 = 100 원에 1명씩 C 명을 모집할 경우 = 100xC 원    max_cost = 100*C    # 냅색    knapsack = [[0 for _ in range(N)] for __ in range(max_cost+1)]    # 직전 비용까지의 고객 수 최댓값    # 현재 비용에서 필요 비용을 뺀 비용까지의 고객 수 최..

https://www.acmicpc.net/problem/22021해당 문제는 크게 두 부분으로 나누어 생각할 수 있습니다.종류에 상관없이 분무기의 위치를 알아내는 부분 / 위치를 알아낸 뒤 종류를 파악하는 부분 우선 분무기의 위치를 알아내는 부분은 생각하기 쉽습니다.어느 부분에 분무기가 존재한다고 가정하겠습니다.분무기는 십자 형태로 내용물을 살포할텐데, 살포되는 칸의 수는 15칸이 됩니다.그렇다면 자연스럽게 특정 위치에서 자신의 십자범위로 더해지거나 빼진 값의 합을 구하면 홀수가 나오게 됩니다.다른 위치에서의 분무기가 영향을 줄 수 있다고 생각할 수 있는데, 어느 위치에 다른 분무기가 존재하던 십자합에는 짝수만큼의 영향을 주므로 특정 위치의 더해지거나 빼진 값들의 십자합이 홀수라면 해당 위치는 종류에 ..

https://www.acmicpc.net/problem/15558BFS 를 사용하면 풀 수 있는 문제입니다.이동 가능한 모든 위치에 대하여 큐에 넣어주고 큐가 빌때까지 순회하면 됩니다.다만 발판이 하나씩 없어지는 점을 생각해 이동 횟수 - 1 의 인덱스를 갖는 발판을 지워주면 해결됩니다.import sysfrom collections import dequefrom copy import deepcopyinput = sys.stdin.readlinedef solution(N, K, data_list):    # 큐 / 인덱스, 이동 횟수    dq = deque([[[0, 0], 0]])    # 방문 목록    visited = deepcopy(data_list)    # 순회    while dq:  ..

https://www.acmicpc.net/problem/1516단순한 위상정렬 문제입니다. 연결 관계를 정리해준 뒤 선행 노드가 없는 노드를 시작 노드로 잡습니다.시작 노드부터 BFS 로 순회하며 걸리는 최대 시간을 기록해줍니다. 다만 큐에 다음 노드를 넣을 때는 선행 노드가 모두 방문되어야 모든 건설 시간을 고려할 수 있습니다.import sysfrom collections import dequeinput = sys.stdin.readlinedef solution(N, time_list, topol_list, graph):    # 큐    dq = deque([])    # 방문 기록    visited = [False for _ in range(N+1)]    # 필요한 시간 리스트    max_..

https://www.acmicpc.net/problem/1867이분매칭 알고리즘을 사용하는 문제입니다. 정확하게는 이 문제는 단순한 이분매칭 문제가 아닌 '최소 버텍스 커버(Minimum Vertex Cover)' 문제입니다. 최소 버텍스 커버란 무엇인지 먼저 짚고 넘어가겠습니다.어떠한 그래프가 있습니다.해당 그래프에서 몇 개의 정점을 고르겠습니다. 과연 몇 개의 정점을 골라야 그래프에 존재하는 모든 간선이 고른 정점과 연결되어 있을까요?해당 문제의 답을 찾는 것이 바로 최소 버텍스 커버 문제입니다. 그렇다면 문제는 왜 최소 버텍스 커버 문제일까요?행과 열을 나누어 각각 노드 그룹으로 쪼갠 뒤 돌이 있는 위치의 행 노드와 열 노드를 연결해 그래프를 만든다면 각 간선의 양 끝중 하나의 정점만 선택되어도..

https://www.acmicpc.net/problem/1520단순한 BFS, DFS 로 진행하면 시간초과가 발생합니다.그래서 한번에 모든 길을 찾는게 아닌 중간중간 가능한 경로를 합해주며 진행하겠습니다. A - B - C - D - E - FA - B - G - D - E - F 두 경로로 이동이 가능하다고 가정하면D 의 지점에서 D 까지 도달하는 경로를 병합한 뒤, D 에서 F 까지는 한 번만 탐색하는 방식입니다. 해당 방식을 구현하기 위해 DFS 와 heapq 를 사용했습니다.D 에서 탐색을 시작하기 전에 D 보다 높은 지점에서의 이동 먼저 계산하기 위함입니다.그러므로 heapq 안의 구성요소는 [높이, [인덱스]] 가 됩니다. 일반적으로 heapq 는 최소힙을 기본으로 하기 때문에 최대힙을 사용..

https://www.acmicpc.net/problem/2696입력 가운데 여러번 중앙값을 구하는 문제는 일반적으로 최대힙과 최소힙을 연결해 푸는 경우가 대부분입니다. 하지만 단순히 정렬이 여러 번 이루어지기 때문에 정렬의 속도가 문제라면 이분탐색을 이용한 정렬을 통해 해결할 수 있습니다. 이런 방식은 매번 모든 데이터를 정렬하지 않기 때문에 보다 빠르게 문제를 해결할 수 있습니다. bisect.insort 함수를 사용해 새로운 데이터가 추가될 때 마다 해당 데이터가 들어갈 수 있는 위치를 이분탐색으로 찾아 삽입했습니다.import sysfrom bisect import insortinput = sys.stdin.readlinedef solution(M, data_list):    # 결과 리스트   ..

https://www.acmicpc.net/problem/2143부분합 문제입니다. 단순히 부분합 리스트를 만들고 부분합 / 부분합 쌍을 찾으면 간단히 생각해도 최악의 경우 1000개의 데이터에서 4중 반복문을 돌아야 하기 때문에 다른 방법을 찾아야 합니다. 우선 각 부분합 리스트에서 2중 반복문을 통해 모든 부 배열 합을 기록해줍니다. 데이터 기록을 할 때 딕셔너리와 리스트 중 선택할 수 있는데, 딕셔너리는 일반적으로 시간을 위해 공간을 포기한 경우로 해당 문제에서 딕셔너리에 모든 부 배열 합을 기록하면 메모리초과가 발생합니다. 그러므로 리스트에 기록하도록 합니다. 기록 중 이분 탐색을 통한 빠른 검색을 위해 정렬을 해주어야 하는데, 이분탐색을 활용한 정렬인 bisect.insort 함수를 사용할 수 ..