백준 4013 : ATM
문제 유향 그래프가 주어지고, 출발 정점이 주어진다. 정점마다 visit시 얻을 수 있는 금액이 주어진다. 금액은 맨 처음 visit할 때 한번만 얻을 수 있으며, 0 ~ 4000의 값을 가진다. 하나 이상의 도착 정점이 주어진다. 이때, 출발 정점에서 출발하여, 도착 정점 중 하나에 도달했을 때 얻을 수 있는 금액의 최대 액수를 구해야 한다. 단, 하나의 정점을 여러번 […]
[카테고리:] 알고리즘
타잔 알고리즘
Directed Graph에서 SCC(Strongly Connected Component)를 추출한다. 아래 슈도코드에서는 각 정점이 속한 SCC 번호를 담은 배열을 구한다.(배열 vertex2scc[N]) Time complexity: worst: O(V + E) Pseudocode:
백준 10360 the mountain of gold?
마운틴 오브 골드 문제 설명: 음의 간선을 포함한 weighted 그래프가 있을 때, 정해진 출발점에서 시작해 같은 곳으로 돌아왔을 때 경로의 weight의 합이 음이 될 수 있는가. 제약 사항: 모든 간선은 서로 다른 정점 사이를 잇는다. 같은 간선을 두 번 이상 지날 수도 있다. 모든 점은 출발점에서 도달 가능하다. 풀이: 경로가 음이 되는 방법은 경로 상에 […]
백준 1043 거짓말
. 그래프의 연결성connectivity를 알아내는 문제다. 여러번 나와 같은 파티에 참가한 사람이 어쩔 땐 거짓말을 듣고 어쩔 땐 진실을 들으면 안된다. 그리고 어떤 사람에게 거짓말이나 진실을 말하면 해당 파티의 모든 사람들도 똑같이 거짓말이나 진실을 들어야 한다. 그리고 그렇게 이야기를 들은 사람들은 각자 같은 이야기를 참석한 다른 파티에 가서도 하게 된다. 따라서 이 문제는 각 파티를 그래프의 […]
1496 : 기타 고르기
백준 1496번 : 기타 고르기 minimax 알고리즘에 기반한 동적 계획법 코드이다. dp 배열은 두개로, 하나는 minimax의 pmax함수에 해당하고, 다른 하나는 pmin에 해당한다. 맨 처음에 환형 구조를 깨고 나선 기타 하나를 고를 때 비어있지 않은 연속된 기타의 배열이 둘로 깨지게 된다. 이렇게 깨져서 생길 수 있는 연속된 기타의 배열은 최대 50개가 한계다. 그리고 게임을 플레이 할때 […]
1238 : 파티
백준 1238 : 파티 유향 그래프의 노드와 변, 그리고 변의 비용이 주어질 때, 각 노드에서 정해진 목적지 노드까지 변을 타고 간 다음, 다시 원래대로 돌아오는 비용이 가장 큰 노드를 구하는 문제이다. 사실 이 문제는 다익스트라(O(N + E)) 두 번만으로 풀리는데, 한번 플로이드 와샬 알고리즘을 써보고 싶어서 그렇게 했다가 많이 느려졌다. (O(N^3)) 추후 다시 구현해볼 예정이다. […]
백준 1432 그래프 수정
백준 1432 위상 정렬로 풀면 된다. 그런데 특이한 점은 보통의 위상정렬(in degree 0인 정점부터 제거)가 아닌, 리버스(?) 위상 정렬로 풀어야 한다.(out degree 0인 정점부터 제거) 처음엔 이 둘의 결과가 차이난다는 것을(단순히 순서가 뒤집히는 정도가 아니다) 납득하지 못해 직접 테스트 케이스를 생성해 결과까지 대조해봤다. 처음 소스(보통의 위상 정렬) 도저히 맞는 것 같은데 CA가 안뜨길레 정답이라도 알아야 […]
빰 