note

https://www.acmicpc.net/problem/2252 2252번: 줄 세우기 첫째 줄에 N(1 ≤ N ≤ 32,000), M(1 ≤ M ≤ 100,000)이 주어진다. M은 키를 비교한 회수이다. 다음 M개의 줄에는 키를 비교한 두 학생의 번호 A, B가 주어진다. 이는 학생 A가 학생 B의 앞에 서야 한다는 의 www.acmicpc.net import sys from collections import deque input = sys.stdin.readline n, m = map(int, input().split()) students = [[] for _ in range(n+1)] # 간선에 대한 정보 (순서 저장) indegree = [0] * (n+1) # 진입차수 for _ in ran..

https://www.acmicpc.net/problem/2887 2887번: 행성 터널 첫째 줄에 행성의 개수 N이 주어진다. (1 ≤ N ≤ 100,000) 다음 N개 줄에는 각 행성의 x, y, z좌표가 주어진다. 좌표는 -109보다 크거나 같고, 109보다 작거나 같은 정수이다. 한 위치에 행성이 두 개 이 www.acmicpc.net 처음에는 1774번(우주신과의 교감) 문제처럼 비용에 따른 간선을 모두 정의해주었다. 하지만 문제 조건에서 n의 수가 굉장히 크기 때문에 메모리 초과가 발생한다. import sys input = sys.stdin.readline def find(parent, x): if parent[x] != x: parent[x] = find(parent, parent[x]) ..

https://www.acmicpc.net/problem/1774 1774번: 우주신과의 교감 (1,1) (3,1) (2,3) (4,3) 이렇게 우주신들과 황선자씨의 좌표가 주어졌고 1번하고 4번이 연결되어 있다. 그렇다면 1번하고 2번을 잇는 통로를 만들고 3번하고 4번을 잇는 통로를 만들면 신들과 선자씨끼 www.acmicpc.net 크루스칼 알고리즘에서 이미 연결된 노드들을 미리 연결해주고 노드들의 간선을 직접 정의해주면 되는 문제다 처음 생각했던 건 이미 연결된 통로들을 따로 저장하고 합친 후 그 통로들을 빼고 간선들을 모두 돌면서 union하는 거였는데 시간 초과가 떴다ㅠ def find(parent, x): if parent[x] != x: parent[x] = find(parent, pare..

https://www.acmicpc.net/problem/1197 1197번: 최소 스패닝 트리 첫째 줄에 정점의 개수 V(1 ≤ V ≤ 10,000)와 간선의 개수 E(1 ≤ E ≤ 100,000)가 주어진다. 다음 E개의 줄에는 각 간선에 대한 정보를 나타내는 세 정수 A, B, C가 주어진다. 이는 A번 정점과 B번 정점이 www.acmicpc.net 일반적인 크루스칼 알고리즘으로 풀면 된다. 1. 간선 -> 비용 기준 오름차순 정렬 2. 사이클이 발생하지 않으면(= parent가 같지 않으면) union 한번 에러났었는데,,, 어이없게도 cost 기준으로 정렬한다는 생각에 사로잡혀서 간선에 대한 정보 a, b, c를 입력 받을 때 c, a, b로 입력받음,,ㅎ 실수하지 말자 import sys s..

https://www.acmicpc.net/problem/4195 4195번: 친구 네트워크 첫째 줄에 테스트 케이스의 개수가 주어진다. 각 테스트 케이스의 첫째 줄에는 친구 관계의 수 F가 주어지며, 이 값은 100,000을 넘지 않는다. 다음 F개의 줄에는 친구 관계가 생긴 순서대로 주어진 www.acmicpc.net 입력받는 요소가 사람이름이기 때문에 숫자로 관리하기 위해 딕셔너리(people)를 선언하고 1. a, b 입력받아서 2. 딕셔너리에 존재하지 않으면 추가, parent 추가 3. union 그 후 연결되어 있는 요소들의 개수를 출력하기 위해 원래 count 함수를 썼는데 제대로 못 잡아내길래 for문을 썼다 ㅎㅎ시간초과 import sys sys.setrecursionlimit(1000..

https://www.acmicpc.net/problem/1976 1976번: 여행 가자 동혁이는 친구들과 함께 여행을 가려고 한다. 한국에는 도시가 N개 있고 임의의 두 도시 사이에 길이 있을 수도, 없을 수도 있다. 동혁이의 여행 일정이 주어졌을 때, 이 여행 경로가 가능한 것인 www.acmicpc.net 문제의 해결법은 쉽게 생각해낼 수 있었다. 입력된 여행 계획의 도시들이 서로 연결되어 있는지만 확인하면 된다. 도시들의 연결 정보를 입력받을 때 1이면 union해준다. 계획을 입력받은 후 시간을 줄이기 위해 리스트에서 중복 원소를 제거해주고 find를 통해 모두 같은 부모를 가지고 있는지(= 하나의 집합인지) 확인해주면 된다. def find_parent(parent, x): if parent[..

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 이코테에서 풀었던 문제 그대로 나왔다. https://sssbin.tistory.com/193 그래서 알고리즘 다시 정리한다는 마음으로 내 손으로 직접 풀었지만 ,, 시간 초과로 실패 def find_parent(parent, x): if parent[x] != x: parent[x] = find_parent(parent, parent[x]) return ..

다양한 그래프 알고리즘 - 그래프: 노드 + 간선 ㄴ '서로 다른 개체(혹은 객체)가 연결되어 있다' ㄴ 인접행렬(2차원 배열) - 메모리↑, 시간↓ / 인접리스트(리스트) - 메모리↓, 시간↑ - 그래프 vs 트리 그래프 트리 방향성 방향 그래프 / 무방향 그래프 방향 그래프 순환성 순환 / 비순환 비순환 루트 노드 존재 여부 X O 노드간 관계성 X 부모-자식 관계 모델의 종류 네트워크 모델 계층 모델 서로소 집합 - 서로소 집합: 공통 원소가 없는 두 집합 - 서로소 집합 자료구조: 서로소 부분 집합들로 나누어진 원소들의 데이터를 처리하기 위한 자료구조 ㄴ union: 2개의 원소가 포함된 집합을 하나의 집합으로 합치는 연산 ㄴ find: 특정한 원소가 속한 집합이 어떤 집합인지 알려주는 연산 # ..

https://www.acmicpc.net/problem/11657 11657번: 타임머신 첫째 줄에 도시의 개수 N (1 ≤ N ≤ 500), 버스 노선의 개수 M (1 ≤ M ≤ 6,000)이 주어진다. 둘째 줄부터 M개의 줄에는 버스 노선의 정보 A, B, C (1 ≤ A, B ≤ N, -10,000 ≤ C ≤ 10,000)가 주어진다. www.acmicpc.net 처음엔 예제를 봐도 문제가 이해가 잘 안 갔었다. 그래서 관련 글들을 찾아보다가,, 벨만-포드 알고리즘이라는 것을 알았다. 이 문제는 음수 간선이 존재하기 때문에 사이클을 순환할수록 가중치가 감소하는 경우가 발생한다. 따라서 일반적인 다익스트라 알고리즘으로 풀 수 없고, 벨만-포드 알고리즘으로 풀어야 한다. 예제2를 보면 사이클을 계속 ..

https://www.acmicpc.net/problem/1504 1504번: 특정한 최단 경로 첫째 줄에 정점의 개수 N과 간선의 개수 E가 주어진다. (2 ≤ N ≤ 800, 0 ≤ E ≤ 200,000) 둘째 줄부터 E개의 줄에 걸쳐서 세 개의 정수 a, b, c가 주어지는데, a번 정점에서 b번 정점까지 양방향 길이 존 www.acmicpc.net 반드시 통과해야만 하는 정점이 있기 때문에 1 -> v1 -> v2 -> n 1 -> v2 -> v1 -> n 다익스트라를 세번(1번 출발, v1 출발, v2 출발) 돌려서 두 값 중에 최소값을 찾아주면 된다 처음에 실패해서 찾아보니까 값을 세번 더하기 때문에 무한값을 줄여주면 된다고 해서 줄였는데 (1e9 -> 1e8) 여전히 틀림,,,, 자세히 보니..