알고리즘!/Dynamic Programming33 [C/C++] 백준 12015: 가장 긴 증가하는 부분 수열2 (O(logn) 알고리즘) ㅣhttps://www.acmicpc.net/problem/12015 12015번: 가장 긴 증가하는 부분 수열 2 첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ Ai ≤ 1,000,000) www.acmicpc.net 풀이! 이 문제를 기존의 11503: 가장 긴 증가하는 부분 수열 푼 방식으로 풀 경우에는 해결이 불가능하다. 그 이유는 11503 문제의 알고리즘은 시간복잡도가 O(n^2)로 구현해도 해결이 가능했지만 이 문제는 수열의 크기가 10^6이므로 똑같이 시간복잡도가 O(N^2)가 되어 시간초과가 발생하게 된다. 그렇기 때문에 새로운 아이디어를 생각해야한다. 일단 가장 기본적인 알고리즘은 11503 .. 2023. 10. 14. [C/C++] 1562: 계단 수 https://www.acmicpc.net/problem/1562 1562번: 계단 수 첫째 줄에 정답을 1,000,000,000으로 나눈 나머지를 출력한다. www.acmicpc.net 이 문제를 10844: 쉬운 계단 수처럼 모든 경우의 수를 배열에 저장하여 풀려고 한다면 메모치 초과가 날 것이다. 그렇기 때문에 메모리 아끼면서 Dynamic Programming을 해결하기 위한 방법으로 비트마스킹을 이용하면 된다. 이 문제는 사실 10844 문제를 비트마스킹으로 풀기만 하면 되기 때문에 자세한 알고리즘은 아래 포스팅을 참고하면 된다! https://donggul-godsang.tistory.com/67 [C/C++] 10844: 쉬운 계단 수 https://www.acmicpc.net/problem.. 2023. 10. 11. [C/C++] 백준 1504: 특정한 최단 경로 (다익스트라 풀이) https://www.acmicpc.net/problem/1504 1504번: 특정한 최단 경로 첫째 줄에 정점의 개수 N과 간선의 개수 E가 주어진다. (2 ≤ N ≤ 800, 0 ≤ E ≤ 200,000) 둘째 줄부터 E개의 줄에 걸쳐서 세 개의 정수 a, b, c가 주어지는데, a번 정점에서 b번 정점까지 양방향 길이 존 www.acmicpc.net 풀이!!! 다익스트라 알고리즘! 다익스트라를 제대로 구현을 한 상태라면 사실 쉽게 풀 수도 있다. 다익스트라를 4번에서 6번 사용을 한다면 최단거리를 1부터 N까지 V1과 V2를 거치면서 최단거리를 구하면 된다. 이 문제에서 한번 이동했던 정점을 다시 이동할 수 있다는 것은 다익스트라를 여러번 사용할 때 같은 정점을 지나도 된다는 것이지 한번의 다익스트.. 2023. 9. 30. [C/C++] 백준 17404: RGB 거리 2 https://www.acmicpc.net/problem/17404 17404번: RGB거리 2 첫째 줄에 집의 수 N(2 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 각 집을 빨강, 초록, 파랑으로 칠하는 비용이 1번 집부터 한 줄에 하나씩 주어진다. 집을 칠하는 비용은 1,000보다 작거나 www.acmicpc.net 하나 주의해야 할건 첫번째 칠한 집과 마지막으로 칠한 집의 색깔이 같으면 안되는것이다. 그렇기 때문에 기존의 DP로 문제를 풀게 된다면 이 조건을 만족시키기에 쉽지 않다. 따라서 여기서 생각해야하는건 첫번째로 칠할 집의 색깔을 정하고 나서 for문을 3번 돌며 각각의 경우세어 모든 집을 칠하는 비용의 최솟값을 구해야한다. 즉 dp[0][1]로 시작했을 때는 dp[1][.. 2023. 9. 28. 이전 1 2 3 4 5 ··· 9 다음
