백준 (8) 썸네일형 리스트형 [Baekjoon]12015.가장 긴 증가하는 부분수열2 Baekjoon #12015. 가장 긴 증가하는 부분 수열2 http://www.acmicpc.net/problem/12015 11053과 같은 문제이지만 N제한이 더 커서 O(N^2)의 방법으로 풀면 시간 초과가 난다. 따라서 O(NlogN) 방법으로 풀어야 한다. 이진 탐색을 활용한 lower bound 알고리즘을 사용했다. Lower Bound : 배열에서 찾고자 하는 값 k가 있을때 k보다 크거나 같은 값의 첫번째 인덱스를 리턴. 예) 배열 {1, 1, 3, 5, 6} 에서 k=1 일때 Lower Bound = 2(1보다 크거나 같은 값은 3이므로 3의 인덱스인 2를 리턴) 먼저 LIS를 저장할 빈 배열을 하나 생성하여 이를 갱신해나가면서 LIS를 구한다. 입력된 배열 a = {10, 20, 10.. [Baekjoon]11052.카드 구매하기(DP) Baekjoon#11052. 카드 구매하기http://www.acmicpc.net/problem/11052예전에는 붕어빵 판매하기 문제였는데 카드 구매하기 문제로 바뀐 것 같다. 문제를 읽어보니 내용만 다르고 문제에서 물어보는 것은 같은 것이었다. 카드 N개를 구매할 때 가장 비싸게 구매할 경우 가격 총합을 구하는 문제이다. 붕어빵 문제에서는 붕어빵 N개를 판매할때 최대 수익을 구하는 문제였다. 결국은 같은 말이다. 문제를 풀기 위해서 배열 d를 정의한다. d[n] : 카드 n개를 구매할 때 최대 가격 예전에 백준 알고리즘 인강을 들었을때 풀었던 방법을 참고했다. 1개를 살 때, 2개를 살 때, ..., n개를 살 때 각각 가격이 p[n]으로 다르다. 구매해야하는 총 카드의 개수가 n개이므로 먼저 1개를.. [Baekjoon]1699.제곱수의 합(DP) Baekjoon#1699. 제곱수의 합http://www.acmicpc.net/problem/1699수학적으로 좀 생각을 해봐야하는 문제였다. 어떤 자연수 n을 제곱수의 합으로만 나타낼 때 최소인 경우의 수를 구하는 문제이다. 예시는 문제에도 잘 나와있다. $$11=1^{2}+1^{2}+1^{2}+2^{2}+2^{2}$$ 11은 이렇게 5개의 합으로 나타낼 수도 있지만 이것이 최소인 경우는 아니다. $$11=1^{2}+1^{2}+3^{2}$$ 이처럼 3개의 제곱수의 합으로도 나타낼 수 있으므로 n이 11일때 답은 3 이다. 여기서 한가지 착각을 하기 쉬운데 나도 똑같은 생각을 했다. 제곱수의 합으로 나타낼 때 n보다 작은 가장 큰 제곱수를 사용하여 나타낼 때가 최소일 거라고 생각한것이다. 하지만 그렇지 .. [Baekjoon]2579.계단오르기(DP) Baekjoon #2579. 계단오르기 http://www.acmicpc.net/problem/2579문제를 처음 읽었을때 포도주 시식 문제와 비슷한 문제라고 느꼈다. 다른 점은 이 문제는 종점이 마지막 계단으로 정해져 있다. 마지막 계단을 n번째 계단이라고 하고 n번째 계단에 도착하는 방법을 생각해 보면 다음과 같다. 1. 바로 이전 계단을 밟지 않고 오는 경우.2. 바로 이전 계단을 밟고 오는 경우. 1에서 바로 이전 계단을 밟지 않고 왔다는 것은 전전계단은 반드시 밟았어야 한다.(1칸이나 2칸씩만 올라갈 수 있으므로 !! 이 경우 두칸을 올라온 것임). 1 에서 바로 이전 계단을 밟고 왔다는 것은 두 계단을 연속으로 밟은 것이므로 전전계단은 반드시 밟지 않았어야 한다. 빨간색칸이 밟지 않고 온 칸이.. [Baekjoon]11054.가장 긴 바이토닉 부분 수열(DP) Baekjoon#11054http://www.acmicpc.net/problem/11054LIS문제의 원리를 이용하여 풀 수 있는 문제 중 하나이다. LIS 문제 해결 방법은 이전 포스팅을 참고하자. 여기 처음에는 i번째 수까지는 증가 수열, i번째 수 이후 부터는 감소 수열을 이루는 방법으로 접근했다. 두 문제 모두 풀어본 다음에 이 문제를 접했기 때문에 그런 아이디어를 떠올렸는데 반복문을 돌때 i도 변하는데 이 때 배열 d에 저장되는 값에 문제가 있는 것 같았다. 내가 구현을 못한거 같기도 하다. 다른 사람들의 풀이는 대부분 양방향에서 LIS를 사용하는 방법을 사용했다. 의미상 내가 생각했던 방법과 같지만 구현하는데 있어서 더 쉬운 방법인것 같다. 배열 a, d는 LIS 문제와 같이 정의하고 다음과 .. [Baekjoon]11053.가장 긴 증가하는 부분수열(DP) Baekjoon #11053. 가장 긴 증가하는 부분 수열http://www.acmicpc.net/problem/11053 이 문제는 Longest Increasing Subsequence(LIS)로 유명한 문제라고 한다. 그 동안 풀었던 문제와는 다른 유형인 것 같아서 아이디어가 떠오르지 않았는데 유튜브에서 영상을 보고 바로 이해가 되어 풀 수 있었다. 이 영상이 도움이 되었다. 영상에서 설명한 방법은 시간복잡도가 O(n^2) 이다. 그런데 n이 100,000 이상일때는 이 방법으로 풀 수 없다. 시간 복잡도 O(nlogn) 인 방법이 있는데 이번 포스팅에서는 먼저 O(n^2)인 방법으로 풀고 이후에 따로 O(nlogn) 방법을 공부하여 포스팅 해야겠다. 먼저 배열 d를 정의하면 d[n] : 수열 a에.. [Baekjoon]9465.스티커(DP) Baekjoon #9465. 스티커http://www.acmicpc.net/problem/9465 처음에 문제를 보고 완전탐색으로 풀 수 있겠다고 생각했지만 알고리즘 분류에 DP로 되어 있어서 DP로 풀기로 했다. 완전탐색으로 풀어보고 비교해봐야겠다. 일단 DP를 이용해서 풀자. 문제에서 모서리를 공유하며 인접한 스티커는 뗄 수 없다고 했다. DP로 풀기 위해 N번째 열의 상태와 N-1번째 열의 상태를 비교하며 어떤 관계가 있는지 알아야 한다. 이렇게 스티커를 열로 분해하는 아이디어가 중요한것 같다. 먼저 스티커는 2Xn 이고 N번째 열이 표와 같은 상태일때 N-1번째에 올 수 있는 상태는 다음과 같다.(같은 행에 OO가 올 수 없음.)점화식을 세우기 위해서 배열 d를 정의한다. d[N][k] : 스티커.. [Baekjoon]2193. 이친수(DP) Baekjoon #2193. 이친수 http://www.acmicpc.com/problem/2193 개인적으로 오르막수나 쉬운 계단 수 문제보다 훨씬 쉽다고 생각했다. 이미 앞에 두 문제를 어떻게 접근하는지 알고 있어서 그런 것일 수도 있겠지만 코드 자체도 훨씬 간단하고 이해하기도 쉬웠다. 이 문제도 마찬가지로 배열d를 정의한다. d[N][k] : N자리 k로 끝나는 이친수 개수 (k=0, 1) 이 문제는 k에 올 수 있는 수가 0 또는 1 두 가지 경우이므로 생각해보기가 더 쉬웠다.먼저 N=1 일때 이친수는 0으로 시작할 수 없다고 했으므로 d[1][1] = 1 , d[1][0] = 0 으로 정의된다. 2자리부터 차근차근 생각해보면 다음과 같다. 1이 연속으로 나오면 안되기 때문에 1로 끝나는 N-1자.. 이전 1 다음
