여름 언덕에서 배운 것

📚 문제 한 마을에 모험가가 N명 있습니다. 모험가 길드에서는 N명의 모험가를 대상으로 '공포도'를 측정했는데, '공포도'가 높은 모험가는 쉽게 공포를 느껴 위험 상황에서 제대로 대처할 능력이 떨어진다. 모험가 길드장은 모험가 그룹을 안전하게 구성하고자 공포도가 X인 모험가는 반드시 X명 이상으로 구성한 모험가 그룹에 참여해야 여행을 떠날 수 있도록 규정했다. N명의 모험가에 대한 정보가 주어졌을 때, 여행을 떠날 수 있는 그룹의 최댓값을 구하는 프로그램을 작성하시오. 예를 들어 N=5이고, 각 모험가의 공포도가 2 3 1 2 2과 같다고 가정하자. 이때, 그룹 1에 공포도가 1,2,3인 모험가를 한 명씩 넣고, 그룹 2에 공포도가 2인 남은 두 명을 넣게 되면, 총 2개의 그룹을 만들 수 있다. 또한 ..

위상 정렬이란? 방향 그래프의 모든 노드를 '방향성에 거스르지 않도록 순서대로 나열하는 것' 1) 진입차수가 0인 노드를 큐에 넣는다. 2) 큐가 빌 때까지의 다음의 과정을 반복한다. ⑴ 큐에서 원소를 꺼내 해당 노드에서 출발하는 간선을 그래프에서 제거한다. ⑵ 새롭게 진입차수가 0이 된 노드를 큐에 넣는다. 💡 진입차수란? 특정한 노드로 들어오는 간선의 개수를 의미 이때 모든 원소를 방문하기 전에 큐가 빈다면 사이클이 존재한다고 판단할 수 있다. 다시 말해 큐에서 원소가 V번 추출되기 전에 큐가 비어버리면 사이클이 발생한 것이다. 📍 알고리즘 동작 과정 step0. 진입차수가 0인 노드를 큐에 넣는다. 현재 노드 1의 진입차수만 0이기 때문에 큐에 노드 1만 삽입 step1. 먼저 큐에 들어 있는 노드..

서로소 집합 자료구조 : union과 find 2개의 연산으로 구성 1) union(합집합) 연산을 확인하여, 서로 연결된 두 노드 A,B를 확인 ⑴ A와 B의 루트 노드 A', B'를 각각 찾는다. ⑵ A'를 B'의 부모 노드로 설정한다. 2) 모든 union(합집합) 연산을 처리할 때까지 1번 과정을 반복한다. 예를 들어, 전체 집합 {1, 2, 3, 4, 5, 6}이 6개의 원소로 구성되어 있는 상황을 생각해보자. 이때 다음과 같은 4개의 union 연산이 주어져 있다. (union 1,4) (union 2,3) (union 2,4) (union 5,6) 이러한 union 연산들은 그래프 형태로 표현될 수도 있다. 각 원소는 그래프에서의 노드로 표현되고, '같은 집합에 속한다'는 정보를 담은 uni..

최단 경로 알고리즘 : 가장 짧은 경로를 찾는 알고리즘으로, '길 찾기' 문제라고도 불린다. 최단 경로 문제는 보통 그래프를 이용해 표현하는데 각 지점은 그래프에서 '노드'로 표현되고, 지점간 연결된 도로는 그래프에서 '간선'으로 표현된다. 다익스트라 최단 경로 알고리즘 (알고리즘 대회를 준바한다면 다익스트라 최단 경로 알고리즘은 자다가도 일어나서 바로 코드를 작성할 수 있을 정도로 코드에 숙달되야함) 그래프에서 여러 개의 노드가 있을 때, 특정한 노드에서 출발하여 다른 노드로 가는 각각의 최단 경로를 구해주는 알고리즘 "가장 비용이 적은 노드"를 선택해서 임의의 과정을 반복하는 그리디 알고리즘이기도 함 [1] 출발 노드를 설정한다. [2] 최단 거리 테이블을 초기화한다. [3] 방문하지 않은 노드 중에..