[문제] https://www.acmicpc.net/problem/1005 [처음 생각] 힌트가 위상정렬인걸 보고 일단 위상정렬을 찾아봤다... 찾아보니 위상정렬 알고리즘은 여러 일들에 순서가 정해져있을 때 순서에 맞게 나열할 때 사용하는 알고리즘이어서 이 문제처럼 건설 순서가 정해져있고 순환이 없는 그래프이므로 사용하기 적절한 듯 하다. 위상정렬 알고리즘을 그대로 사용하되 중간에 max 값 갱신해주는 부분만 넣어주면 되지 않을까?! [풀이] 위의 방법처럼 하려고 했는데 위상정렬을 짜려니 길어져서 혹여나 다른 방법으로 할 수 있을까 찾아보니 DP 재귀로 한 사람이 있었다. 위상정렬을 하면 나중에 의존관계를 고려해야 하는데 DP로 풀면 의존관계를 고려하지 않고 거꾸로 지어야 할 마지막 건물번호를 기준으로 ..
[위상 정렬이란?] 여러 일들에 순서가 정해져 있을 때 순서에 맞게끔 나열하는 것을 말한다. 먼저 위상 정렬을 하기 위해서는 자료들을 순서에 맞게 그래프로 표현해야 한다. 위상 정렬 알고리즘이란 그래프 상의 정점들을 순서에 맞게 나열하는 것이다. 그래프 상의 간선의 방향이 정점들의 순서를 나타낸다. 만약 A가 B를 가리키면, A가 B보다 먼저 앞선다는 뜻이다. 그래프에서는 진입차수와 진출차수라는 개념이 있다. 진입차수는 밖에서 한 정점으로 들어오는 간선의 수이고 진출차수는 한 정점에서 나가는 간선의 수를 말한다. [위상 정렬 과정] 1. 진입차수가 0인 정점과 이와 연결된 모든 간선을 지운다. 2. 남아있는 정점의 진입차수를 갱신한다. 3. 그래프에 모든 정점이 없어질때까지 1과 2과정을 반복한다. 1번..
- Total
- Today
- Yesterday
- 알파벳 찾기
- 13460
- parametric search
- 이진 검색
- 2048 game
- 파라메트릭
- acmpicpc
- 7576
- 자료구조
- 조합 알고리즘
- mybatis
- acmicpc
- 1157
- Java
- 알고리즘
- 이진 탐색
- ACM Craft
- spring
- 10809
- BOJ
- 단어 공부
- 1085
- lottie
- 약수
- 위상정렬
- 7569
- 째로탈출2
- 1037
- 12100
- combination
일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
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 |