어흥

문제 링크: https://www.acmicpc.net/problem/21276 21276번: 계보 복원가 호석 석호촌에는 N 명의 사람이 살고 있다. 굉장히 활발한 성격인 석호촌 사람들은 옆 집 상도 아버님, 뒷집 하은 할머님 , 강 건너 유리 어머님 등 모두가 한 가족처럼 살아가고 있다. 그러던 어느 날 www.acmicpc.net 1. 주의할 점 - String 형태의 배열을 어떻게 표현할 것인가? - 위상정렬에 대해 알고 있어야 한다 2. 구현 - 사람들에 대한 정보를 People에 담는다 - People을 정렬한 뒤, HashMap에 넣는다 - 하나는 이름을 통해 Index를 알아내는 Map. 그리고 다른 하나는 Index를 통해 이름을 알아내는 revMap. - 관계에 대한 정보는 Li[]에 ..

문제 링크: https://www.acmicpc.net/problem/9470 9470번: Strahler 순서 지질학에서 하천계는 유향그래프로 나타낼 수 있다. 강은 간선으로 나타내며, 물이 흐르는 방향이 간선의 방향이 된다. 노드는 호수나 샘처럼 강이 시작하는 곳, 강이 합쳐지거나 나누어지는 곳 www.acmicpc.net 1. 주의할 점 - 매 TC마다 초기화 작업을 수행한다 - Stahler가 1 늘어나는 기준을 이해한다 2. 구현 - 모든 간선에 대한 정보를 Li[] 에 담는다 - Conn[] 배열을 통해 해당 Node로 도착하는 Node의 수를 저장한다 - Counting[]을 통해 각 Node에 도착한 Stahler 번호를 저장한다. 이때 Stahler번호가 1개도 없었다면 추가, 1개라도 ..

문제 링크: https://www.acmicpc.net/problem/14676 14676번: 영우는 사기꾼? 프로그램의 입력은 표준 입력으로 받는다. 입력의 첫 줄에는 건물 종류의 개수 N, 건물 사이 관계의 개수 M, 영우의 게임 정보의 개수 K가 주어진다.(1 ≤ N, M, K ≤ 100,000) 다음 줄부터 M줄에 걸쳐 www.acmicpc.net 1. 주의할 점 - 위상정렬에 대해 알고 있어야 한다 - 해당 건물이 여러개 지어질 수도 있다 2. 구현 - Li[]를 통해 선행관계를 저장한다 - Building[]을 통해 각 건물이 지어진 수를 저장한다 - Conn[]을 통해 해당 건물을 짓기위해 선행되어야 하는 건물 수를 저장한다 - 각 조건에 따라 치트키 사용여부를 판단한다 import java..

문제 링크: https://www.acmicpc.net/problem/2637 2637번: 장난감조립 첫째 줄에는 자연수 N(3 ≤ N ≤ 100)이 주어지는데, 1부터 N-1까지는 기본 부품이나 중간 부품의 번호를 나타내고, N은 완제품의 번호를 나타낸다. 그리고 그 다음 줄에는 자연수 M(3 ≤ M ≤ 100)이 주 www.acmicpc.net 1. 주의할 점 - 위상정렬로 접근한다 - 필요한 물품의 개수를 List 형태로 담지 않는다 → 메모리 초과 회피 2. 구현 - Info 형태의 구조체를 이용하여 A의 물건을 만들기 위해 Idx번째 물건이 Val만큼 필요하다는 것을 나타낸다 - Need[] 배열을 통해 필요한 총 물건의 수를 저장한다 - Conn[] 배열을 통해 연결된 상위부품의 수를 나타낸다..

문제 링크: www.acmicpc.net/problem/16437 16437번: 양 구출 작전 2, 3, 5번에 사는 모든 양들은 1번 섬으로 갈 수 있지만 7번 섬에 사는 양들은 1번 섬으로 가기 위하여 6번 섬을 거쳐야 하는데 6번 섬에 사는 늑대들의 수가 7번 섬에 사는 양들의 수보다 많으므로 www.acmicpc.net 1. 주의할 점 - 모든 섬에 양이 최대치로 존재 -> 합해지는 과정에서 Int의 범위를 벗어날 수 있다 2. 구현 - 위상정렬의 풀이법으로 접근했다 - Info 구조체를 통해 해당 지점을 도착지점으로 설정한 섬의 수(Conn), 다음 섬으로 연결된 곳(To), 생물의 수(Val)를 나타낸다 - 섬에 늑대가 존재하면, 생물의 개수를 음수로 저장한다. - Info의 성격에 맞게 Ar..

문제 링크: 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 1. 주의할 점 - 위상정렬을 사용할 줄 알아야 한다 2. 구현 - 선행되는 A의 Node에 후행되는 Node B를 추가한다. 그리고 Conn[B]++를 통해 B의 앞에 선행되는 Node가 증가되었음을 표시한다 - For문을 통해 Node 1~N까지 돌며 Conn[]의 값이 0이면 큐에 넣는다 - 큐에서 원소를 뽑으면서 해당 원소를 출력하고, 해당 ..

문제 링크: https://www.acmicpc.net/problem/1005 1005번: ACM Craft 첫째 줄에는 테스트케이스의 개수 T가 주어진다. 각 테스트 케이스는 다음과 같이 주어진다. 첫째 줄에 건물의 개수 N 과 건물간의 건설순서규칙의 총 개수 K이 주어진다. (건물의 번호는 1번부터 N번까지 존재한다) 둘째 줄에는 각 건물당 건설에 걸리는 시간 D가 공백을 사이로 주어진다. 셋째 줄부터 K+2줄까지 건설순서 X Y가 주어진다. (이는 건물 X를 지은 다음에 건물 Y를 짓는 것이 가능하다는 의미이다) 마지막 줄에는 백준이가 승리하기 위해 건 www.acmicpc.net 1. 주의할 점 - 전역변수로 선언된 배열들을 잘 초기화해줘야 한다 (While문의 중간에 break걸리면 Pre값이 ..

문제 링크: https://www.acmicpc.net/problem/1516 1516번: 게임 개발 첫째 줄에 건물의 종류 수 N(1 ≤ N ≤ 500)이 주어진다. 다음 N개의 줄에는 각 건물을 짓는데 걸리는 시간과 그 건물을 짓기 위해 먼저 지어져야 하는 건물들의 번호가 주어진다. 건물의 번호는 1부터 N까지로 하고, 각 줄은 -1로 끝난다고 하자. 각 건물을 짓는데 걸리는 시간은 100,000보다 작거나 같은 자연수이다. www.acmicpc.net 1. 주의할 점 - 위상정렬 알고리즘의 기초에 대해 알고 있어야 한다 - 사용하는 배열이 많기 때문에 주석 혹은 변수명을 잘 사용한다 - Need_time[] : 해당 번호만을 짓는데 걸리는 시간 - Need_pre[]: 해당 Node를 짓기 위해 남..