본문 바로가기

알고리즘44

[BOJ] 백준 9370번: 미확인 도착지 https://www.acmicpc.net/problem/9370 9370번: 미확인 도착지 문제 (취익)B100 요원, 요란한 옷차림을 한 서커스 예술가 한 쌍이 한 도시의 거리들을 이동하고 있다. 너의 임무는 그들이 어디로 가고 있는지 알아내는 것이다. 우리가 알아낸 것은 그들이 s지�� www.acmicpc.net 시작점 s와 지나간 두 정점 g와 h의 정보, 전체 경로들에 대한 정보 및 목적지 후보 t가 주어질 때, 시작점에서 목적지까지 최단 경로가 시작점에서 g와 h를 잇는 간선을 지나 목적지까지 가는 최단경로의 비용이 같은 목적지 후보들을 찾는 문제입니다. 먼저 시작점에서 모든 정점까지 가는 최단 경로를 구합니다. 우선순위 큐를 사용한 다익스트라로 빠르게 구할 수 있습니다. (SPFA + SL.. 2020. 8. 9.
최대 공약수와 최소 공배수 알고리즘 유클리드 호제법은 두 수의 최대 공약수는 큰 수에서 작은 수를 빼가며 어느 한 쪽이 0일때까지 반복하여 마지막에 0이 아닌 다른 한 수임을 이용하는 방법입니다. 예를 들어 gcd(7,15) -> gcd(7,8) -> gcd(7,1) -> gcd(6,1) -> gcd(5,1) -> gcd(4,1) -> gcd(3,1) -> gcd(2,1) -> gcd(1,1) -> gcd(0,1) gcd(6,8) -> gcd(6,2) -> gcd(4,2) -> gcd(2,2) -> gcd(0,2) 와 같이 진행하며 7과 15의 최대 공약수가 1, 6과 8의 최대 공약수가 2임을 알 수 있습니다. max(a,b) - min(a,b) 연산은 max(a,b) % min(a,b) 연산으로 대체 할 수 있으므로 아래와 같이 정리 .. 2020. 8. 9.
[BOJ] 백준 10217번: KCM Travel https://www.acmicpc.net/problem/10217 10217번: KCM Travel 각고의 노력 끝에 찬민이는 2014 Google Code Jam World Finals에 진출하게 되었다. 구글에서 온 초대장을 받고 기뻐했던 것도 잠시, 찬찬히 읽어보던 찬민이는 중요한 사실을 알아차렸다. 최근의 대세�� www.acmicpc.net M원 이하로 1번 도시에서 N번 도시까지 갈 수 있는 경로 중 최단시간을 요구하는 문제입니다. 두가지 방법이 있는데 저는 동적계획법으로 해결했습니다. DP[i][j] 배열을 i 도시에서 j원으로 출발할 때 n 도시까지 걸리는 최단 시간으로 정의했습니다. 주의할 점은 입력 중 출발공항과 도착공항이 같은 여러개의 티켓 정보가 들어올 수 있다는 점입니다. (이걸.. 2020. 8. 9.
C++ 자료구조들에 대하여 그리디 문제를 풀던 도중 vector 의 erase가 O(n) 복잡도로 동작한다는 것을 알았다... 난 너무 그동안 겉핥기 식으로 STL을 써왓던것 같다..그러므로 삽입 삭제가 빈번하게 일어나는 상황에서 vector의 사용은 시간초과를 도래할 수 있따.. 아래 문제가 vector의 erase 남용으로 틀린 문제와 코드다.https://www.acmicpc.net/problem/12021202번: 보석 도둑문제 세계적인 도둑 상덕이는 보석점을 털기로 결심했다. 상덕이가 털 보석점에는 보석이 총 N개 있다. 각 보석은 무게 Mi와 가격 Vi를 가지고 있다. 상덕이는 가방을 K개 가지고 있고, 각 가방에 �www.acmicpc.net #include #include #include #include #inclu.. 2020. 8. 7.

티스토리툴바