본문 바로가기
728x90

전체 글279

[Algorithm] 최소 신장 트리 (MST) 신장 트리 n개의 정점으로 이루어진 무방향 그래프에서 n개의 정점과 n-1개의 간선으로 이루어진 트리 최소 신장 트리 (Minimum Spanning Tree) 무방향 가중치 그래프에서 신장 트리를 구성하는 간선들의 가중치의 합이 최소인 신장 트리 Prim Algorithm 하나의 정점에서 연결된 간선들 중에 하나씩 선택하면서 MST를 만들어 가는 방식 임의 정점 하나 선택해서 시작 선택한 정점과 인접하는 정점들 중 최소 비용의 간선이 존재하는 정점 선택 모든 정점이 선택될 때 까지 반복 ''' 6 11 0 1 32 0 2 31 0 5 60 0 6 51 1 2 21 2 4 46 2 6 25 3 4 34 3 5 18 4 5 40 4 6 51 ''' def find_MST(s): key[s] = 0 # 정점.. 2021. 10. 21.
[BOJ/Python] 1717. 집합의 표현 📌 문제 https://www.acmicpc.net/problem/1717 1717번: 집합의 표현 첫째 줄에 n(1 ≤ n ≤ 1,000,000), m(1 ≤ m ≤ 100,000)이 주어진다. m은 입력으로 주어지는 연산의 개수이다. 다음 m개의 줄에는 각각의 연산이 주어진다. 합집합은 0 a b의 형태로 입력이 주어진다. 이는 www.acmicpc.net 📌 문제 접근 방법 상호배타 집합의 find_set연산과 union연산을 구현해서 풀이하였다. 시간초과가 났는데, 해결을 위해서 재귀 깊이를 설정해주고 input을 sys.stdin.readline으로 바꿔줬다. 최대 재귀 깊이는 어떻게 계산해야 하는지 궁금해졌다! 지금까지는 아무거나 큰 값으로 넣어줬는데 어떻게 계산해야하지? 📌 코드 # 백준 1.. 2021. 10. 21.
[Algorithm] 서로소(상호배타) 집합 (Disjoint-sets) 서로소(상호배타) 집합 서로 중복 포함된 원소가 없는 집합 교집합이 없음 집합에 속한 하나의 특정 멤버를 통해 각 집합들을 구분 → 대표자(representative) 상호배타 집합 표현 - 트리 하나의 집합을 하나의 트리로 표현 자식 노드가 부모 노드를 가리키며 루트 노드가 대표자가 됨 상호배타 집합 연산 nodes = [1, 2, 3, 4, 5, 6] parents = [0] * (len(nodes) + 1) # 각 노드의 부모를 저장할 배열 Make-Set(x) : 유일한 멤버 x를 포함하는 새로운 집합을 생성 def make_set(x): parents[x] = x for node in nodes: make_set(node) Find-Set(x) : x를 포함하는 집합을 찾는 연산, 대표자를 반환.. 2021. 10. 20.
[Algorithm] 그래프 그래프 정점(Vertex)들의 집합과 이들을 연결하는 간선(Edge)들의 집합으로 구성된 자료구조 정점의 개수 v개, 간선의 개수 e개 일 때 최대 간선의 개수 : v(v-1)/2 선형 자료구조 / 트리 자료구조로 표현하기 어려운 N : N 관계를 가지는 원소들을 표현하기에 용이 그래프 유형 무향/유향 그래프 : 방향의 유무 가중치 그래프 사이클 없는 방향 그래프 완전 그래프 : 정점들에 대해 가능한 모든 간선들을 가진 그래프 부분 그래프 : 원래 그래프에서 일부의 정점이나 간선을 제외한 그래프 그래프 표현 # 노드, 간선의 개수 V, E = 7, 8 # 간선의 연결 (무방향) temp = [1, 2, 1, 3, 2, 4, 2, 5, 4, 6, 5, 6, 6, 7, 3, 7] 위와 같은 입력이 들어왔을 .. 2021. 10. 20.
[BOJ/Python] 17144. 미세먼지 안녕! 📌 문제 https://www.acmicpc.net/problem/17144 17144번: 미세먼지 안녕! 미세먼지를 제거하기 위해 구사과는 공기청정기를 설치하려고 한다. 공기청정기의 성능을 테스트하기 위해 구사과는 집을 크기가 R×C인 격자판으로 나타냈고, 1×1 크기의 칸으로 나눴다. 구사 www.acmicpc.net 📌 문제 접근 방법 단순 구현 문제! 문제가 시키는 대로 따라서 구현하면 된다. spread 함수를 만들어서 미세먼지가 퍼지도록 한다. dust라는 배열을 따로 만들어서 각 위치의 먼지 변화량을 저장하고 원래 배열과 더해준다. clean 함수를 만들어서 공기청정기를 가동시킨다. 공기청정기의 위치와 방향을 매개변수로 받아서 해당하는 방향대로 값을 swap해준다. 2, 3의 과정을 T번만큼.. 2021. 10. 20.
[SWEA/Python] 1795. 인수의 생일 파티 📌 문제 https://swexpertacademy.com/main/main.do SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com 📌 문제 접근 방법 다익스트라 알고리즘 사용 처음에는 모든 인접한 노드의 시간을 갱신하고, 그 중 최소값을 찾아서 이동하였는데 시간초과 bfs를 사용해서 시간이 더 줄어드는 경로로만 이동하는 방식으로 구현했더니 통과하였다. 📌 코드 import sys sys.stdin = open('input.txt') def dijkstra(start, end): time[start] = 0 for _ in range(N): min_idx = -1 min_time = float('inf') for.. 2021. 10. 19.
[SWEA/Python] 1249. 보급로 📌 문제 https://swexpertacademy.com/main/main.do SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com 📌 문제 접근 방법 다익스트라 알고리즘 사용 출발지에서 인접한 위치를 탐색하며 원래 저장된 비용보다 현재 경로로 온 비용이 적다면 비용을 갱신하고, 현재 위치를 큐에 넣는다. 큐가 빌 때까지 2를 반복 후, 도착지에 저장된 비용을 출력한다. 📌 코드 from collections import deque import sys sys.stdin = open('input.txt') def restore(i, j): queue = deque() queue.append((i, j)) dxy =.. 2021. 10. 19.
[SWEA/Python] 7465. 창용 마을 무리의 개수 📌 문제 https://swexpertacademy.com/main/main.do SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com 📌 문제 접근 방법 어제 풀었던 그룹 나누기와 똑같은 방식의 풀이! 이번엔 다른 코드 참고 안하고 직접 제대로 구현해봤다. 📌 코드 import sys sys.stdin = open('input.txt') def find_leader(p): if p != leader[p]: leader[p] = find_leader(leader[p]) return leader[p] def know(p1, p2): l1 = find_leader(p1) l2 = find_leader(p2) if ran.. 2021. 10. 15.
[SWEA/Python] 1251. 하나로 📌 문제 https://swexpertacademy.com/main/main.do SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com 📌 문제 접근 방법 Prim 알고리즘을 사용하였다. 임의의 섬을 하나 선택하고 방문체크한다. 아직 방문하지 않은 섬을 순회하면서 현재 섬과의 거리와 이미 dist에 저장된 거리를 비교해서 더 작은 값을 dist에 저장한다. 방문하지 않은 섬을 순회하면서 dist가 최소인 섬을 고르고 방문체크한다. 4번의 섬이 2번의 섬과 연결된 것이므로 4번의 섬에 저장된 dist를 E를 곱해서 pay에 더해준다. 모든 섬을 방문할 때까지 위의 과정 반복 📌 코드 import sys sys.stdi.. 2021. 10. 15.
[SWEA/Python] 2814. 최장 경로 📌 문제 https://swexpertacademy.com/main/main.do SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com 📌 문제 접근 방법 처음엔 스택을 이용해서 dfs를 실행해줬었는데, 방문체크를 해제할 수가 없어서 재귀로 바꾼후, 완전탐색을 해줬다. 재귀로 구현하면 목적지를 어떻게 설정하지?가 문제였는데, 그냥 함수가 실행될 때마다 경로에 속한 정점의 개수를 갱신해주면 된다. 📌 코드 import sys sys.stdin = open('input.txt') def dfs(v, cnt): global max_cnt max_cnt = max(max_cnt, cnt) for w in range(1, N.. 2021. 10. 15.
728x90

티스토리툴바