분류 전체보기
11. [Algorithm] 위상 정렬 (그래프 이론)
11. [Algorithm] 위상 정렬 (그래프 이론)
2023.03.27위상 정렬 (Topological Sorting) 정렬 알고리즘의 일종으로, 순서가 정해져 있는 일련의 작업을 차례대로 수행해야 할 때 사용할 수 있는 알고리즘이다. 조금 더 이론적인 설명은, 사이클이 없는 방향 그래프의 모든 노드를 '방향성에 거스르지 않도록 순서대로 나열하는 것' 을 의미한다. 예시를 통해 확실하게 이해해보도록 하자. 그림과 같이 총 3개의 과목이 있다고 가정하자. 세 과목을 모두 듣기 위해서는 자료구조 → 알고리즘 → 고급알고리즘 (O) 순서로 과목을 들어야 한다. 만약 자료구조 → 고급 알고리즘 → 알고리즘 (X) 순서로 과목을 듣게 되면, 올바른 학습순서가 아니다. 진입차수와 진출차수 위상 정렬 알고리즘을 살펴보기 위해서는 먼저 진입차수와 진출차수에 대한 개념을 알아야한다. 진입..
[백준] 1197번 최소 스패닝 트리(feat. 최소 신장 트리, 크루스칼 알고리즘)
[백준] 1197번 최소 스패닝 트리(feat. 최소 신장 트리, 크루스칼 알고리즘)
2023.03.27https://www.acmicpc.net/problem/1197 문제 분석 첫 번째 단계 (문제 요약 및 조건 파악) 그래프가 주어졌을 때, 그 그래프의 최소 신장 트리 를 구하는 프로그램을 작성하시오. 최소 신장 트리(MST)는 주어진 그래프의 모든 정점들을 연결하는 부분 그래프 중에서 그 가중치의 합이 최소인 트리를 말한다. - 입력 첫째 줄에는 정점의 개수 v(1
10. [Algorithm] 크루스칼 알고리즘 (그래프 이론)
10. [Algorithm] 크루스칼 알고리즘 (그래프 이론)
2023.03.27크루스칼 알고리즘 (Kruskal Algorithm) 신장 트리 중에서 최소 비용으로 만들 수 있는 신장 트리를 찾는 알고리즘을 '최소 신장 트리 알고리즘' 이라고 하는데, 대표적인 최소 신장 트리 알고리즘으로는 크루스칼 알고리즘 이 있다. 크루스칼 알고리즘 을 사용하면 가장 적은 비용으로 모든 노드를 연결할 수 있다. 크루스칼 알고리즘은 대표적인 최소 신장 트리 알고리즘 이다. 그리디 알고리즘으로 분류된다. 그렇다면, 신장 트리란 무엇인가? 신장 트리 란 하나의 그래프가 있을 때 모든 노드를 포함하면서 사이클이 존재하지 않는 부분 그래프를 의미한다. → 이때 모든 노드가 포함되어 서로 연결되면서 사이클이 존재하지 않는 다는 조건은 트리 의 성립 조건이기도 함. 신장 트리는 알겠고.. 그러면 최소 신장 ..
[백준] 4195번 친구 네트워크(feat. 유니온 파인드, 문자열 입력, 딕셔너리)
[백준] 4195번 친구 네트워크(feat. 유니온 파인드, 문자열 입력, 딕셔너리)
2023.03.27https://www.acmicpc.net/problem/4195 문제 분석 첫 번째 단계 (문제 요약 및 조건 파악) 어떤 사이트의 친구 관계가 생긴 순서대로 주어졌을 때, 두 사람의 친구 네트워크에 몇 명이 있는지 구하는 프로그램을 작성하시오. 이때, 친구 네트워크란 친구 관계만으로 이동할 수 있는 사이를 말한다. - 입력 첫째 줄에 테스트 케이스의 개수 주어짐. 각 테스트 케이스의 첫째 줄에는 친구 관계의 수 F가 주어짐 (F b: # a가 b보다 알파벳순으로 뒤에 있으면 parent[a] = b # parent[a]의 value를 b로 저장 network[b] = network[b] + network[a] # b의 친구네트워크 수에다가 a의 친구 네트워크 수도 더해줌 else: parent[b] ..
[백준] 1976번 여행 가자(feat. 유니온 파인드)
[백준] 1976번 여행 가자(feat. 유니온 파인드)
2023.03.26https://www.acmicpc.net/problem/1976 문제 분석 첫 번째 단계(문제 요약 및 조건 파악) N개의 도시가 있다. 임의의 두 도시 사이에 길이 있을 수도 있고, 없을 수도 있다. 여행일정이 주어졌을 때, 이 여행 경로가 가능한 것이지 알아보자. 중간에 다른 도시를 경우해도 OK ex) 도시가 5개 있고, A-B B-C A-D B-D E-A 의길이 잇고, 여행계획이 ECBCD 라면 E-A-B-C-B-C-B-D 라는 여행경로를 통해 목적 달성 OK 도시들의 개수와 도시간의 연결 여부가 주어져있고, 여행계획이 순서대로 주어져있을 때, 여행이 가능한지 판별하는 프로그램 작성 할 것.(같은 도시를 여러 번 방문 OK) - 입력 첫 줄에 도시의 수 N (N
[백준] 1717번 집합의 표현(feat. 유니온 파인드)
[백준] 1717번 집합의 표현(feat. 유니온 파인드)
2023.03.26https://www.acmicpc.net/problem/1717 문제 분석 첫 번째 단계 (문제 요약 및 조건 파악) 초기화 n + 1개의 집합 {0}, {1}, ..., {n}이 있다. 이 집합에 합집합 연산과, 두 원소가 같은 집합에 포함되어 있는지를 확인하는 연산을 수행하려고 한다. 집합을 표현하는 프로그램을 작성할 것. - 입력 조건 첫째 줄에 n, m이 주어진다. 이때 n은 0~n까지의 초기 집합이 주어짐을 의미. m은 입력으로 주어지는 연산의 개수임. 합집합은 0 a b 의 형태로 주어지고, 두 원소가 같은 집합에 포함되어 있는지를 확인하는 연산은 1 a b의 형태로 입력이 주어짐 - 출력 조건 1로 시작하는 입력에 대해서는 a와 b가 같은 집합에 포함되면 "YES" 또는 "yes" 그렇지 ..