![]()
📖 문제 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 💡 풀이 방식 • DFS / BFS + 그리디 필요 자료구조 - 인접 정점 정보 저장할 ArrayList 배열 - 정점 방문 표시할 boolean형 배열 - 가중치 정보 저장할 long형 배열 1. 배열 a의 전체 합한 값이 0인지 확인한다. 0이 아니라면 -1을 리턴한다. 2. 인접 정보를 저장할 ArrayList 배열을 생성해 인접한 값들 정보를 저장한다. 3. 방문 표시 배열과 DFS를 통해 leaf 노드까지 쭉 탐색했다가 차례대로 올라온다. (탐색 방향 : 위에서 아래) 4. 부모 정점은 자식..
![]()
목차 📍 정의 및 특징 사이클이 없는 방향 그래프에서 노드 순서를 찾는 알고리즘 - 어떤 노드를 선택했느냐에 따라 결과가 달라지므로, 항상 같은 결과 보장 X - 시간 복잡도 : O(V + E) #사이클X #방향그래프 📍 필요 변수 ✔ 그래프 데이터 인접 리스트 (ArrayList[]) ✔ 진입 차수 배열 (int[] D) ✔ 진입 차수가 0인 노드 저장할 큐 (= 정렬 배열) 📍 실행 과정 그래프 데이터 인접 리스트 ArrayList[] & 진입 차수 배열 int[] D 초기화 (예 : D[2]++ : 자기 자신을 가리키는 에지 개수) 진입 차수 배열에서 진입 차수가 0인 노드를 큐(=정렬 배열)에 저장하고, 선택된 노드가 가리키는 노드들의 진입 차수를 1씩 빼기 감소했을 때 진입 차수가 0이 되는 노..
![]()
🔺 문제 1948번: 임계경로 첫째 줄에 도시의 개수 n(1 ≤ n ≤ 10,000)이 주어지고 둘째 줄에는 도로의 개수 m(1 ≤ m ≤ 100,000)이 주어진다. 그리고 셋째 줄부터 m+2줄까지 다음과 같은 도로의 정보가 주어진다. 처음에는 도로의 www.acmicpc.net 🔺 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 8..
![]()
🔺 문제 1516번: 게임 개발 첫째 줄에 건물의 종류 수 N(1 ≤ N ≤ 500)이 주어진다. 다음 N개의 줄에는 각 건물을 짓는데 걸리는 시간과 그 건물을 짓기 위해 먼저 지어져야 하는 건물들의 번호가 주어진다. 건물의 번호는 1부 www.acmicpc.net 🔺 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 import java.util.*; import java.io.*; public class Main { public static v..
![]()
🔺 문제 2252번: 줄 세우기 첫째 줄에 N(1 ≤ N ≤ 32,000), M(1 ≤ M ≤ 100,000)이 주어진다. M은 키를 비교한 회수이다. 다음 M개의 줄에는 키를 비교한 두 학생의 번호 A, B가 주어진다. 이는 학생 A가 학생 B의 앞에 서야 한다는 의 www.acmicpc.net 🔺 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 import java.util.*; import java.io.*; public class Main { public static void ma..
