본문 바로가기

알고리즘44

최대 공약수와 최소 공배수 알고리즘 유클리드 호제법은 두 수의 최대 공약수는 큰 수에서 작은 수를 빼가며 어느 한 쪽이 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.
[BOJ] 백준 1700번: 멀티탭 스케줄링 https://www.acmicpc.net/problem/1700 1700번: 멀티탭 스케줄링 기숙사에서 살고 있는 준규는 한 개의 멀티탭을 이용하고 있다. 준규는 키보드, 헤어드라이기, 핸드폰 충전기, 디지털 카메라 충전기 등 여러 개의 전기용품을 사용하면서 어쩔 수 없이 각종 전 www.acmicpc.net 요즘 그리디에 너무 약해서 그리디 문제를 풀던 중 골머리를 앓았던 문제에 대하여 포스팅합니다. 이 문제는 각 전기용품의 사용 순서가 k개 주어지고 멀티탭이 n개 구멍이 있을때 주어진 전기용품을 순서대로 사용하면서 플러그를 뽑는 최소횟수 구해야 합니다. 가장 처음에 든 생각은 멀티탭을 모두 사용하고 있으며 다음 전기용품이 멀티탭에 꼽혀있지 않은 경우, 즉 플러그를 하나 뽑아야되는 시점에서, 꼽혀있는.. 2020. 8. 7.
[BOJ] 백준 11049번: 행렬 곱셈 순서 https://www.acmicpc.net/problem/11049 11049번: 행렬 곱셈 순서 첫째 줄에 입력으로 주어진 행렬을 곱하는데 필요한 곱셈 연산의 최솟값을 출력한다. 정답은 231-1 보다 작거나 같은 자연수이다. 또한, 최악의 순서로 연산해도 연산 횟수가 231-1보다 작거나 같� www.acmicpc.net 행렬 곱셈 순서에 따라 연산량이 적어지는데 잘 생각해보면 (a b) (b c) 차원인 두 행렬을 곱할 때 a * b * c 의 연산횟수가 필요하다. 즉 가운데 b가 큰 순서대로 먼저 곱하는것이 횟수를 줄일 수 있다. 하지만 당장 b가 큰것을 줄이는 순서가 최종적으로 최적의 방법이 아닐 수 있기 때문에 구간 s~e 에서 모든 연산을 수행해봐야 한다. DP[s][e]를 s 번째 행렬과 .. 2020. 8. 6.

티스토리툴바