- 발행일
99클럽 코테 스터디 31일차 TIL + 오늘의 학습 키워드: 동적계획법
99클럽 코테 스터디 31일차 TIL + 오늘의 학습 키워드: 동적계획법
이 글은 네이버 블로그에 2025년 3월 7일에 올렸던 것을 그대로 옮겨온 것입니다.
const fs = require("fs");
const input = fs
.readFileSync(process.platform === "linux" ? "/dev/stdin" : "입력.txt")
.toString()
.trim()
.split("\n");
function solution(data) {
const [[N, _], ...arr] = data.map((el) => el.split(" ").map(Number));
// 그래프 배열
const graph = Array.from({ length: N + 1 }, () => []);
// 진입차수 배열
const rank = Array.from({ length: N + 1 }, () => 0);
arr.forEach(([a, b]) => {
// 선행 노드 a의 그래프 안에 노드 b 추가
graph[a].push(b);
// 1. 진입 차수 계산
// 선행 노드 a가 존재하는 노드 b의 진입차수 증가
rank[b]++;
});
// queue 구현
const queue = [];
let queueIdx = 0;
for (let i = 1; i < N + 1; i++) {
// 2. 진입차수가 0인 정점 선택
if (!rank[i]) queue.push(i);
}
const result = [];
while (queueIdx < queue.length) {
const node = queue[queueIdx++];
// 3,5. 선택한 정점 제거
result.push(node);
// 4. 진입차수 업데이트 ->선택한 정점과 연결된 정점들의 진입차수 감소
graph[node].forEach((next) => {
rank[next]--;
// 5. 진입차수가 0인 정점 선택
if (!rank[next]) queue.push(next);
});
}
// 6. 결과반환
console.log(...result);
}
solution(input);
오늘의 회고
어떤 문제가 있었고, 나는 어떤 시도를 했는지
어떻게 해결했는지
무엇을 새롭게 알았는지
내일 학습할 것은 무엇인지
• 비기너: https://www.acmicpc.net/problem/1755 (45분)
• 미들러: https://www.acmicpc.net/problem/2631 (1시간 30분)
• 챌린저: https://www.acmicpc.net/problem/5972 (1시간 30분)
필수 해시태그: #99클럽 #코딩테스트준비 #개발자취업 #항해99 #TIL
