기록

문제 보기 [사용한 알고리즘] 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개 이상 있으면 ?를 리턴합니다. (여러 가지 경우의 수가 나올 ..

문제 보기 [사용한 알고리즘] 크루스칼(Kruskal) [문제 접근] 모든 도시는 항상 연결 그래프의 형태이며 최대로 비용을 절약하는 문제이기 때문에 MST(Minimal Spanning Tree) 문제라고 생각하였습니다. [알고리즘] 1. 입력받은 도로의 비용을 기준으로 오름차순 정렬합니다. 2. 비용이 낮은 순서대로 하나씩 선택하여 두 도시를 연결하는 도로를 설치할 수 있는지 확인합니다. - 해당 도로 설치로 인해 사이클이 생성될 수 있다면 해당 도로를 설치하지 않습니다. 3. 설치하지 않은 도로의 합을 출력합니다. [코드] import sys def find_parent(x, parent): if parent[x] != x: parent[x] = find_parent(parent[x], parent..

문제 보기 [사용한 알고리즘] 구현 [문제 접근] 주어진 시뮬레이션을 수행하면서 충돌이 발생하면 어떻게 충돌이 발생했는지 출력해야 합니다. 따라서 로봇들의 정보를 딕셔너리로 관리하였고 이외의 시뮬레이션은 특별한 알고리즘을 사용하지 않고 문제에서 주어진대로 구현하였습니다. [알고리즘] 1. 입력받은 로봇들의 정보를 딕셔너리에 저장합니다. 2. 각 명령을 반복 횟수만큼 수행합니다. 3. 충돌이 일어났다면 충돌이 일어난 상황을 출력하고 충돌이 일어나지 않으면 OK를 출력합니다. [코드] import sys def rotation_left(d): # 왼쪽으로 90도 회전 if d == "N": return "W" elif d == "W": return "S" elif d == "S": return "E" eli..

문제 보기 [사용한 알고리즘] 플로이드-워셜 [문제 접근] 물건을 정점, 물건의 무게 비교 결과를 선분으로 표시하여 그래프를 구현합니다. 그래프를 구현하고 플로이드-워셜 알고리즘을 사용하여 모든 정점 간의 최단 거리를 계산합니다. 이후 서로 다른 물건이 도달할 수 있으면 비교 결과를 알 수 있고, 도달할 수 없으면 비교 결과를 확인할 수 없다고 생각하였습니다. [알고리즘] 1. 물건의 비교 결과를 이용해서 그래프를 구현합니다. 2. 플로이드-워셜 알고리즘을 사용하여 모든 정점 간의 도달 가능 여부를 계산합니다. 3. 도달할 수 없는 물건의 개수를 출력합니다. [코드] import sys INF = 1E9 if __name__ == "__main__": n = int(sys.stdin.readline())..