기록

문제 보기 [사용한 알고리즘] 크루스칼(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..

문제 보기 [사용한 알고리즘] 이진 탐색(Binary Search) [문제 접근] left = 1, right = max(stones)로 초기화한 후 이진 탐색을 통해 최대 몇 명까지 징검다리를 건널 수 있는지 구하였습니다. mid 값((left + right) // 2) 보다 작은 구간이 연속적으로 k개 이상이면 건널 수 없으므로 mid = right - 1로 범위를 좁혀나갔습니다. 마찬가지로 mid 값보다 작은 구간이 연속적으로 k개 미만이면 건널 수 있으므로 left = mid + 1로 범위를 좁혀나갔습니다. [알고리즘] 1. left = 1, right = max(stones)로 초기화합니다. 2. 이진 탐색을 수행합니다. mid 값과 stones의 값을 비교해서 mid 값보다 작은 구간이 연속적..

문제 보기 [사용한 알고리즘] 구현 [문제 접근] 주어진 시뮬레이션을 수행하면서 충돌이 발생하면 어떻게 충돌이 발생했는지 출력해야 합니다. 따라서 로봇들의 정보를 딕셔너리로 관리하였고 이외의 시뮬레이션은 특별한 알고리즘을 사용하지 않고 문제에서 주어진대로 구현하였습니다. [알고리즘] 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..

문제 보기 [사용한 알고리즘] DP(동적 프로그래밍) [문제 접근] 현재 위치의 최고점은 현재 위치 - 1 행의 다른 열 중 최댓값과 현재 위치의 칸의 값을 합치면 됩니다. [알고리즘] 1. dp 배열 첫 행에 입력받은 land 첫 행 값을 대입합니다. 2. 1행부터 위에서 언급한 문제 접근 방식을 구현합니다. 3. 마지막행까지 2번 과정을 수행한 후 마지막행의 최고점을 출력합니다. [코드] def solution(land): dp = [[0] * 4 for _ in range(len(land))] for i in range(4): dp[0][i] = land[0][i] for i in range(1, len(land)): for j in range(4): if j == 0: dp[i][j] = land..

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

문제 보기 [사용한 알고리즘] 브루트 포스, 구현, 부분 집합 [접근 방식] 입력받은 문자열 S가 팰린드롬인지 확인합니다. 만약 팰린드롬이 아니라면 입력 문자열 S를 뒤집어서 부분 팰린드롬의 길이를 찾은 후 최종 팰린드롬의 길이를 출력합니다. 이 과정은 아래 알고리즘에서 자세히 설명하도록 하겠습니다. [알고리즘] 1. 문자열 S가 팰린드롬인지 확인합니다. 만약 팰린드롬이라면 문자열 S의 길이를 출력합니다. 2. 문자열 S가 팰린드롬이 아니라면 reversed(S)에서 인덱스 0부터 시작하는 부분 팰린드롬의 문자열의 길이를 구합니다. 3. 문자열(S)의 길이 * 2 - 부분 팰린드롬 문자열의 길이를 출력합니다. abab를 예로 들어 설명하겠습니다. abab가 팰린드롬인지 확인합니다. 팰린드롬이 아니므로 2..

문제 보기 [사용한 알고리즘] BFS(너비 우선 탐색) [문제 접근] 지도 상의 최단 거리를 구하는 문제는 대부분 DFS보다 BFS가 효율적이라 BFS로 접근하였습니다. DFS는 모든 경우를 탐색해야지 최단 경로인지 알 수 있기 때문입니다. [알고리즘] 1. 현재 위치를 기준으로 상, 하, 좌, 우 이동합니다. (말의 형태로 이동이 가능한 상황이라면 말의 이동도 수행합니다) 2. 이동하려는 공간에 이전에 더 적은 말의 이동으로 도달한 적이 있다면 이동을 하지 않습니다. 3. 큐가 빌 때까지 혹은 도착지점에 도달할 때까지 위 과정을 반복합니다. 4. 도착지에 도달했으면 이동 횟수, 만약에 도달하지 못했으면 -1을 출력합니다. [코드] from collections import deque import sys..

문제 보기 [사용한 알고리즘] dijkstra(다익스트라), BFS(넓이 우선 탐색) [문제 접근] 출발점과 도착점을 알고 있고 음의 가중치가 없는 최단 경로를 구해야 하기 때문에 다익스트라를 사용하였습니다. [알고리즘] 1. 다익스트라 알고리즘을 사용하여 최단 경로의 값을 구합니다. 2. BFS 알고리즘을 사용하여 최단 경로의 경로를 구합니다. 3. BFS 알고리즘으로로 구한 경로를 삭제합니다. 4. 다시 한번 다익스트라 알고리즘을 사용해서 거의 최단 경로를 구합니다. [코드] from collections import deque import sys import heapq INF = 1e9 def dijkstra(): q = [] heapq.heappush(q, (0, s)) distance[s] = ..

문제 보기 [사용한 알고리즘] 이분 탐색(binary search) [문제 접근] N명의 아이들을 놀이기구에 태울 수 있는 시간을 구한 후 놀이기구의 번호를 구하였습니다. N의 범위가 크기 때문에 0초부터 시간을 탐색하는 것이 아니라 이분 탐색으로 시간을 구하였습니다. [알고리즘] 1. 놀이기구의 수보다 아이들의 수가 적으면 아이들의 수를 출력합니다. 2. 이분 탐색을 통해 아이들을 모두 태울 수 있는 시간을 찾습니다. 3. 구한 시간 - 1분까지 몇 명의 아이를 태울 수 있는지 탐색합니다. 4. 구한 시간에 탑승하는 아이들을 계산하면서 제일 마지막에 탑승하는 놀이기구의 번호를 출력합니다. (놀이기구 탑승 인원이 N명이 될 때의 놀이기구 번호를 출력하면 됩니다) [코드] import sys if __na..

문제 보기 [사용한 알고리즘] DFS(깊이 우선 탐색) [문제 접근] 주어진 트리에서 전위 순회와 중위 순회 결과를 적어보니 규칙을 발견하였습니다. 전위 순위에서 발견한 루트 값을 중위 순위에서 찾아보니 루트 값을 기준으로 왼쪽 서브 트리, 오른쪽 서브 트리로 분리되었습니다. 따라서 이를 응용하여 재귀로 구현하면 후위 순위를 구하였습니다. [알고리즘] 1. 전위 순회의 루트와 중위 순회의 값 중 일치하는 인덱스 위치를 찾습니다. 2. 인덱스를 기준으로 왼쪽 서브 트리, 오른쪽 서브 트리를 탐색합니다. 3. 후위 순회이기 때문에 서브 트리 탐색이 끝난 후 루트를 출력합니다. [코드] import sys def solve(root, start, end): for i in range(start, end): i..