기록

문제 보기 [사용한 알고리즘] 다이나믹 프로그래밍 [알고리즘] 1. 체크 포인트 사이의 거리를 구하여 distance 2차원 배열에 저장합니다. - distance[i][j] : i번째 체크포인트와 j번째 체크포인트 사이의 거리입니다. 2. dp 2차원 배열을 INF(=1e10) 값으로 초기화합니다. - dp[k][n] : 체크포인트를 최대 k개 건너뛸 수 있는 상황에서 n번째 체크포인트까지 달릴 수 있는 최소거리입니다. 3. 3차원 반복문을 통해서 dp 배열을 채워나갑니다. - k값이 1일 때부터 순차적으로 dp 배열을 채워나갑니다. - 현재 체크포인트까지 달릴 수 있는 최소거리는 k값을 적게 사용한 곳에서 현재 위치로 이동한 거리와 동일하게 k값을 사용한 곳에서 현재 위치로 이동한 거리를 비교하여 최..

문제 보기 [사용한 알고리즘] 정렬, 구현 [알고리즘] 1. 공을 크기 순으로 오름차순 정렬합니다. 2. 0번 인덱스 공부터 순차적으로 탐색합니다. - 현재 인덱스까지 공 무게의 총합을 total 변수에 저장합니다. - 각 색깔별로 공 무게 누적합을 ball_size_sum 딕셔너리에 저장합니다. - 현재 인덱스까지 공 무게 총합 - 현재 색깔 공 무게 누적합은 현재 인덱스 플레이어가 사로잡을 수 있는 모든 공들의 크기의 합입니다. ※ 단순한 2중 for문으로 구현하면 n이 200,000으로 큰 수이기 때문에 시간 초과가 발생합니다. 따라서 안쪽의 for문의 횟수를 줄이기 위해 바깥쪽 for문의 인덱스를 순차적으로 증가시키면서 안쪽의 for문은 while문으로 변경하여 불필요한 반복은 수행하지 않도록 구..

문제 보기 [사용한 알고리즘] Union-Find [알고리즘] 1. 친구의 친구는 친구이기 때문에 서로 친구들인 모임을 Union-Find를 이용해서 찾습니다. 2. 해당 모임에서 친구 비용이 가장 작은 학생을 친구로 만듭니다. 3. 위 과정을 모든 학생과 친구를 맺을 때까지 반복합니다. 4. 모든 학생과 친구를 맺는 비용이 현재 가지고 있는 비용보다 적으면 친구로 만드는데 드는 최소비용을 출력합니다. 만약 현재 가지고 있는 비용이 모든 학생과 친구를 맺는 비용보다 적다면 Oh no를 출력합니다. [코드] import sys def find_parent(parent, x): if parent[x] != x: parent[x] = find_parent(parent, parent[x]) return pare..

문제 보기 [사용한 알고리즘] BFS(너비 우선 탐색) [알고리즘] 1. (1, 1)을 시작점으로 BFS 탐색을 수행합니다. 2. 현재 위치에서 다른 위치의 불을 켤 수 있다면 불을 켭니다. 3. 현재 위치에서 상, 하, 좌, 우로 움직일 수 있는 공간이 있다면 움직입니다. 4. 위 과정을 더 이상 움직일 수 없을 때까지 반복합니다. [코드] from collections import deque import sys dx = [-1, 1, 0, 0] dy = [0, 0, -1, 1] def bfs(): q = deque() q.append((1, 1)) visited = {(1, 1)} count = {(1, 1)} switch[1][1] = True while q: x, y = q.popleft() # ..

문제 보기 [사용한 알고리즘] 백트랙킹(backtracking) [알고리즘] 1. 0부터 수를 증가시키면서 N번째 감소하는 수를 찾을 때까지 2, 3번 과정을 반복합니다. 2. 현재 수가 감소하는 수이면 현재 수 + 1을 수행합니다. 3. 현재 수가 감소하는 수가 아니면 감소하지 않는 위치가 감소하도록 수정합니다. 4. N번째 감소하는 수를 찾으면 출력합니다. ※ N이 1022일 때 9876543210이므로 1023부터는 -1을 출력합니다. [코드] import sys sys.setrecursionlimit(10 ** 9) def solve(n): cnt = 0 num = 1 while True: str_num = str(num) flag = True if len(str_num) == 1: # 길이가 1..

문제 보기 [사용한 알고리즘] BFS(너비 우선 탐색) [알고리즘] 1. (0, 0)을 시작점으로 BFS 탐색을 합니다. - 홀수, 짝수 줄을 구분하여 이동합니다. - 나중에 경로를 찾기 위해서 이동한 위치에는 이전 위치를 저장하는 경로 배열을 선언하고 관리합니다. - 나중에 경로의 길이를 구하기 위해 현재 위치까지 도달한 길이 + 1 값을 저장하는 거리 배열을 선언하고 관리합니다. 2. (n - 1, n -1)부터 (0, 0)까지 역방향으로 거리 배열을 읽습니다. - 가장 먼저 0이 아닌 길이가 나오는 위치는 (0, 0) 시작점에서 도달할 수 있는 가장 큰 타일 혹은 도착 지점입니다. 3. 2번에서 찾은 위치와 경로 배열을 통해 경로를 찾습니다. [코드] from collections import de..

문제 보기 [사용한 알고리즘] BFS(너비 우선 탐색) [문제 접근] 일반적인 BFS 최단 거리 문제와 달리 가장 먼저 발견한 경로가 최단 경로가 아닐 수 있습니다. 따라서 이동할 수 있는 모든 경로를 BFS 방식으로 확인하였습니다. [알고리즘] 1. 견우의 시작점 (0, 0)에서 출발합니다. 2. 상, 하, 좌, 우로 이동할 수 있는 위치가 있는지 확인합니다. - 1은 바로 이동할 수 있습니다. - 오작교를 연속해서 건널 수 없습니다. - 절벽이 교차하는 구간은 오작교를 설치할 수 없습니다. - 오작교는 시간 주기가 일치할 때((현재 시간 + 1) % 시간 주기 = 0) 이동할 수 있습니다. 3. 직녀를 만날 때마다 최단 경로 변수에 최단 값을 저장합니다. [코드] from collections imp..

문제 보기 [사용한 알고리즘] 순열(permutation) [문제 접근] 운동 키트를 순서대로 나열할 수 있는 모든 경우의 수를 구한 후 조건 검사를 하는 문제입니다. N의 최댓값이 8이기 때문에 순열을 사용해도 시간 복잡도가 여유로웠습니다. [알고리즘] 1. 순열을 통해 운동 키트 나열 순서를 구합니다. 2. 해당 순서로 운동을 수행하였을 때 중량 500을 유지할 수 있는지 확인합니다. 3. 중량 500을 유지할 수 있는 순서의 수를 출력합니다. [코드] import sys from itertools import permutations if __name__ == "__main__": n, k = map(int, sys.stdin.readline().split()) array = list(map(int,..

문제 보기 [사용한 알고리즘] 구현, Dictionary [문제 접근] A[a], B[b]의 값의 덧셈으로 만들 수 있는 결과를 딕셔너리에 저장합니다. 그리고 C[c], D[d]로 만들 수 있는 값에 -를 붙인 값이 딕셔너리에 존재하는지 확인하여 최종적으로 A[a], B[b], C[c], D[d]의 합이 0인 쌍의 개수를 구하였습니다. [알고리즘] 1. A[a]와 B[b]로 만들 수 있는 딕셔너리를 구현합니다. - 딕셔너리의 key와 value는 만들 수 있는 숫자와 해당 숫자의 개수입니다. 2. C[c]와 D[d]로 만들 수 있는 값에 -를 붙인 값이 해당 딕셔너리에 존재하는지 확인한 후 존재한다면 해당 key의 value 값을 더합니다. [코드] import sys if __name__ == "__m..

문제 보기 [사용한 알고리즘] 위상 정렬(Topological) [문제 접근] 순서를 나열하는 문제는 위상 정렬을 활용하면 효과적으로 구현할 수 있습니다. [알고리즘] 1. 작년 순위 정보를 통해 2차원 graph 배열과 1차원 indegree 배열 값을 할당합니다. - graph[i][j]: i보다 j가 순위가 낮으면 True, 반대는 False를 대입합니다. - indegree [i]: i보다 순위가 낮은 팀의 개수를 대입합니다. 2. 순위 변동이 있는 팀은 graph 값과 indegree 값을 업데이트합니다. 3. 위상 정렬을 수행합니다. - 사이클이 있으면 IMPOSSIBLE을 리턴합니다. (시작점을 찾지 못합니다) - 큐에 값이 2개 이상 있으면 ?를 리턴합니다. (여러 가지 경우의 수가 나올 ..