알고리즘,PS

https://www.acmicpc.net/problem/14002 14002번: 가장 긴 증가하는 부분 수열 4 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이 www.acmicpc.net 문제 풀이 이전에 포스팅했던 LIS 알고리즘에 + 추척 까지 해줘야 하는 문제이다. (이전 포스팅 참고 : https://katastrophe.tistory.com/39?category=956141 ) 1. DP 풀이 최종적으로 나온 부분 수열의 길이 값을 ans 라고 하면 각 구간마다 길이를 저장해놓은 DP배열의 ..

https://www.acmicpc.net/problem/1365 1365번: 꼬인 전깃줄 첫 줄에 전봇대의 개수 N(1 ≤ N ≤ 100,000)이 주어지고, 이어서 N보다 작거나 같은 자연수가 N개 주어진다. i번째 줄에 입력되는 자연수는 길 왼쪽에 i번째 전봇대와 연결된 길 오른편의 전봇대가 www.acmicpc.net 문제 풀이 전깃줄이 서로 꼬여야 하지 않아야 하므로 가령 , 4 -> 1 번 전봇대로 가는 선을 제거해야 꼬이지 않는다. 즉 , 반대쪽의 전봇대의 번호가 증가하는 수열의 형태면 꼬이지 않으므로 LIS 알고리즘을 통해 해결해야한다. LIS에 대한 이전 포스팅에서 해결방법이 3가지가 있다고 했는데 , 문제에서 조건을보면 N의 갯수가 10만개가 넘어간다. N^2 이상의 시간복잡도를 가지는..

https://www.acmicpc.net/problem/11722 11722번: 가장 긴 감소하는 부분 수열 수열 A가 주어졌을 때, 가장 긴 감소하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 30, 10, 20, 20, 10} 인 경우에 가장 긴 감소하는 부분 수열은 A = {10, 30, 10, 20, 20, 10} www.acmicpc.net 문제 풀이 LIS(LDS) 풀이는 3가지다. 1. 완전탐색으로 푸는경우 => 시간복잡도 O(n^3) 2. DP => O(N^2) 3. 이진탐색 => O(nlongn) 완전탐색인 경우 for문을 이용한 단순 반복이므로 생략 DP로 접근 할 경우 , 부분 중복 되는부분을 찾아 최적화 시켜야한다. 2중 for문( 바깥쪽 i , ..

https://www.acmicpc.net/problem/12865 12865번: 평범한 배낭 첫 줄에 물품의 수 N(1 ≤ N ≤ 100)과 준서가 버틸 수 있는 무게 K(1 ≤ K ≤ 100,000)가 주어진다. 두 번째 줄부터 N개의 줄에 거쳐 각 물건의 무게 W(1 ≤ W ≤ 100,000)와 해당 물건의 가치 V(0 ≤ V ≤ 1,000) www.acmicpc.net 문제 풀이 KnapSack 이라는 굉장히 유명한 다이나믹 프로그래밍 유형의 문제이다. 그리디 접근이 왜 안되는가 .. ? 가방에 넣는 순서를 무게순 혹은 가치순이라고 가정을 해보면 1. 무게순으로 일단 넣어서 무게합이 11이 되고, 가치합이 12가 되었다. 그런데 바로 뒤에 무게11짜리 가치 100짜리가 있는 경우가 생겨버렸다. =..

https://www.acmicpc.net/problem/2293 2293번: 동전 1 첫째 줄에 n, k가 주어진다. (1 ≤ n ≤ 100, 1 ≤ k ≤ 10,000) 다음 n개의 줄에는 각각의 동전의 가치가 주어진다. 동전의 가치는 100,000보다 작거나 같은 자연수이다. www.acmicpc.net 문제 풀이 동전의 배열을 coins[] 라고 하고 , 만들고 있는 갯수의 합의 결과를 dp[] 라고 하면 dp[k] 를 만들기위해 이전의 결과값을 더해줘야 한다. 기준을 conis[] 로 해서 반복문을 돌리면 coins[1] 일때 1~k원 까지 모두 체크 , coins[2] 일때 1~k원 가지 모두 체크 .. 이런식으로 해서 coins[n] 일때 모두 체크해서 기존의 dp 배열에 계속해서 추가해주면..

https://www.acmicpc.net/problem/11057 11057번: 오르막 수 오르막 수는 수의 자리가 오름차순을 이루는 수를 말한다. 이때, 인접한 수가 같아도 오름차순으로 친다. 예를 들어, 2234와 3678, 11119는 오르막 수이지만, 2232, 3676, 91111은 오르막 수가 아니다. 수 www.acmicpc.net 문제 풀이 앞 자리 기준으로 자리 수가 늘어날때마다 추가로 들어간다고 생각하면 된다. 점화식은 다음과 같다 => dp[i][j] += dp[i-1][k]; i : 자릿수 j : 현재 자릿수의 0~9 k : 이전 자릿수의 0~9 그런데 이전 자릿수의 모든 수가 들어가는 것이 아닌 k

https://www.acmicpc.net/problem/1932 1932번: 정수 삼각형 첫째 줄에 삼각형의 크기 n(1 ≤ n ≤ 500)이 주어지고, 둘째 줄부터 n+1번째 줄까지 정수 삼각형이 주어진다. www.acmicpc.net 문제 풀이 밑으로 진행 할 수록 , 최대한 값이 높게 나오게 합산하면서 내려오는 방식이다. 예제 입력처럼 주어진다면 "바로 위" 혹은 "왼쪽 위" 에서 값을 받아 내려올 수 있으므로 점화식은 => arr[i][j] = arr[i][j] + Math.max(arr[i-1][j],arr[i-1][j-1]); 이다. 하지만 왼쪽끝이나 오른쪽 끝에서는 둘 중에 큰 값을 받는것 대신 하나만 선택할 수 있으므로 그 조건만 추가하면 된다. 1 2 3 4 5 6 7 8 9 10 11..

https://www.acmicpc.net/problem/1149 1149번: RGB거리 첫째 줄에 집의 수 N(2 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 각 집을 빨강, 초록, 파랑으로 칠하는 비용이 1번 집부터 한 줄에 하나씩 주어진다. 집을 칠하는 비용은 1,000보다 작거나 www.acmicpc.net 문제 풀이 첫 번째 집을 무슨 색으로 칠 하느냐에 따라서 결과가 달라지고 이전 집과는 다른 색을 칠해야 하므로 그리디로는 접근이 불가능하다. 만약 i 번째 집을 R로 색칠 하고 싶다고 가정을 하자. 그럼 i-1 번째 집은 R이 아니어야 한다. => i-1 번째집을 [G 로 색칠 했을때 총비용] 과 [B 로 색칠 했을때 총 비용] 중 작은 것을 선택 해야한다. 이런 식으로 하면..