프로그래머스 고득점kit(35)
-
Union-Find Algorithm (유니온 파인드 알고리즘) 탬플릿 코드
Union-Find Algorithm (유니온 파인드 알고리즘) 탬플릿 코드n, m = map(int, input().split())parent = [0] * (n + 1)for i in range(n + 1): parent[i] = idef find(node): if node != parent[node]: parent[node] = find(parent[node]) return parent[node]def union(a, b, parent): pa = find(a) pb = find(b) if pa == pb: return if a > b: parent[pa] = pb else: par..
2024.07.21 -
dfs, bfs 탬플릿 코드
DFS (좌표 형태 순회용)def dfs(x, y): dx = [-1, 0, 1, 0] dy = [0, 1, 0, -1] for i in range(4): nx = x + dx[i] ny = y + dy[i] if isRectangle(nx, ny) and copyed_maps[nx][ny] == 1 and chk[nx][ny] == -1: chk[nx][ny] = 1 dfs(nx, ny)def isRectangle(x, y): if 0 DFS ( 노드와 노드 순회용)n = int(input())connects = int(input())connectList = [[0] * (n + 1) for _ in r..
2024.06.11 -
고득점kit) 그래프 #3. 방의 개수
(문제 설명) 원점(0,0)에서 시작해서 아래처럼 숫자가 적힌 방향으로 이동하며 선을 긋습니다. ex) 1일 때는오른쪽 위로 이동 그림을 그릴 때, 사방이 막히면 방 하나로 샙니다. 이동하는 방향이 담긴 배열 arrows가 매개변수로 주어질 때, 방의 개수를 return 하도록 solution 함수를 작성하세요. 제한사항 배열 arrows의 크기는 1 이상 100,000 이하 입니다. arrows의 원소는 0 이상 7 이하 입니다. 방은 다른 방으로 둘러 싸여질 수 있습니다. 입출력 예arrowsreturn [6, 6, 6, 4, 4, 4, 2, 2, 2, 0, 0, 0, 1, 6, 5, 5, 3, 6, 0] 3 입출력 예 설명 (0,0) 부터 시작해서 6(왼쪽) 으로 3번 이동합니다. 그 이후 주어진 ..
2022.05.17 -
고득점kit) 그래프 #2. 순위
( 문제 설명 ) n명의 권투선수가 권투 대회에 참여했고 각각 1번부터 n번까지 번호를 받았습니다. 권투 경기는 1대 1 방식으로 진행이 되고, 만약 A 선수가 B 선수보다 실력이 좋다면 A 선수는 B 선수를 항상 이깁니다. 심판은 주어진 경기 결과를 가지고 선수들의 순위를 매기려 합니다. 하지만 몇몇 경기 결과를 분실하여 정확하게 순위를 매길 수 없습니다. 선수의 수 n, 경기 결과를 담은 2차원 배열 results가 매개변수로 주어질 때 정확하게 순위를 매길 수 있는 선수의 수를 return 하도록 solution 함수를 작성해주세요. 제한사항 선수의 수는 1명 이상 100명 이하입니다. 경기 결과는 1개 이상 4,500개 이하입니다. results 배열 각 행 [A, B]는 A 선수가 B 선수를 이..
2022.05.12 -
고득점kit) 그래프 # 1. 가장 긴 노드
(문제 설명) n개의 노드가 있는 그래프가 있습니다. 각 노드는 1부터 n까지 번호가 적혀있습니다. 1번 노드에서 가장 멀리 떨어진 노드의 갯수를 구하려고 합니다. 가장 멀리 떨어진 노드란 최단경로로 이동했을 때 간선의 개수가 가장 많은 노드들을 의미합니다. 노드의 개수 n, 간선에 대한 정보가 담긴 2차원 배열 vertex가 매개변수로 주어질 때, 1번 노드로부터 가장 멀리 떨어진 노드가 몇 개인지를 return 하도록 solution 함수를 작성해주세요. 제한사항 노드의 개수 n은 2 이상 20,000 이하입니다. 간선은 양방향이며 총 1개 이상 50,000개 이하의 간선이 있습니다. vertex 배열 각 행 [a, b]는 a번 노드와 b번 노드 사이에 간선이 있다는 의미입니다. 입출력 예nverte..
2022.05.11 -
[고득점kit] 이분탐색 #2. 징검 다리
( 문제 설명 ) 출발지점부터 distance만큼 떨어진 곳에 도착지점이 있습니다. 그리고 그사이에는 바위들이 놓여있습니다. 바위 중 몇 개를 제거하려고 합니다. 예를 들어, 도착지점이 25만큼 떨어져 있고, 바위가 [2, 14, 11, 21, 17] 지점에 놓여있을 때 바위 2개를 제거하면 출발지점, 도착지점, 바위 간의 거리가 아래와 같습니다. 제거한 바위의 위치각 바위 사이의 거리거리의 최솟값 [21, 17] [2, 9, 3, 11] 2 [2, 21] [11, 3, 3, 8] 3 [2, 11] [14, 3, 4, 4] 3 [11, 21] [2, 12, 3, 8] 2 [2, 14] [11, 6, 4, 4] 4 위에서 구한 거리의 최솟값 중에 가장 큰 값은 4입니다. 출발지점부터 도착지점까지의 거리 d..
2022.05.06