Code Diary Code Diary

내가 푼 알고리즘은 다음과 같다. ANS1에 최대길이 증가부분수열을 찾기 위해 번호를 저장한다. ANS2에는 반대로 최대길이 감소부분수열을 찾기 위해 번호를 저장한다. ANS에는 ANS1과 ANS2를 더한다. ANS의 최대값-1이 정답이 된다. 예를 들어 1 5 2 4 3 4 5 2 1이 들어왔으면 다음과 같다.

S와 ANS를 이중횡단하면서 자기보다 S가 작은 값중 ANS가 가장 큰 값 더하기 1 을 넣어준다. 말이 어려운데, 쉽게 말하면 10 20 10 30이면 20이 자기보다 작은 값 중에서 제일 크므로 30의 ANS값은 (2+1)=3이 된다.

L[1] = [1, 2, 3, 4, 5, 6, 7, 8, 9] L[i]는 L[i-1]에서 이어질 수 있는 경우의 수를 더해서 구한다. 예를 들어 0은 1에서부터 이어지게 되고 1은 0과 2에서 올 수 있다. 이제 동적프로그래밍이 익숙해지는 느낌이다.

해왔던대로 단계적으로 모아가는 알고리즘을 짰다. 이 코드를 예제를 돌려보자. 26, 40, 83 49, 60, 57 13, 89, 99 12번줄 반복문을 한번 돌려본다. 26, 40, 83 40+49(89), 26+60(86), 26+57(83) 13, 89, 99 끝까지 돌려본다. 26, 40, 83 40+49, 26+60, 26+57 26+57+13, 26+57+89, 26+60+99 L[2]중 최솟값인 26+57+13이 정답이 된다. 쉽게 말하자면, L[i][0]이란, i번째에 빨간색을 골랐을 때, 0부터 i까지 골라서 어떤 색깔을 골라 나올 수 있는 최솟값이 된다. 같은 방식으로 L[i][1], L[i][2]에는 i번째에 초록색을 골랐을 때의 최소, 파란색을 골랐을 때의 최소가 들어오게 된다. 그..

일단 동적프로그래밍을 사용하지 않고 반복문으로 짜보았다. i는 더할 문자열의 길이, j는 더할 문자열의 첫 인덱스이다. 예를 들어 N이 10이면 i = 1, j = 0 ~ 9 i = 2, j = 0 ~ 8 ~ i = 10, j = 0 이다. L[0], L[1], ~, L[9] L[0]+L[1], L[1]+L[2], ~, L[8]+L[9] ~ L[0]+L[1]+ ~ + L[9] 를 모두 비교해서 가장 큰 값을 찾는다. 결과는... 당연히 시간초과였다. 이 문제는 연속합이므로 사용할 수 있는 아주 좋은 풀이법이 있었다. 예를 들어 입력받은 수가 10 -6 3 -5 2 4 1 이면 먼저 10과 -6을 더한 4와 -6을 비교한다. 4가 더 크므로 -6을 4로 교체한다. 10 4 3 -5 2 4 1 4와 3을 더..

큰 문제를 한 번에 해결하기 어려울 때 재귀 등을 이용해서 작은 문제로 쪼개 해결하게 된다. 그런데 작은 문제들을 풀다보면 같은 문제들을 여러 번 반복해서 풀게 되는 문제점이 발생하는데, 동적 프로그래밍이란 반복되는 문제를 재계산하지 않고 값을 저장해놓고 다시 사용하는 기법을 말한다. 처음에는 예시 코드를 그대로 가져와 카운트를 넣어 모두 세보았다. C언어에서는 '이 x는 전역변수다'라고 선언해놓고 사용한다. 하지만 파이썬에서는 다르다. 외부에서 쓰던 변수x를 함수내에서 global x라고 하면 '그 x는 이 함수내에서만 사용하는 지역변수x가 아닌 전역변수 x다'라는 뜻이다. 이런 방식으로 하니 시간초과가 나왔다. 그래서 아예 생각을 바꾸어 하나하나 프로그램을 돌리지 않고 코드1, 2가 몇번 호출될지 간..

(n m)은 n!/{k!(n-k)!}이다. 처음에는 10이 2와 5를 곱한 값임을 이용해 하나씩 반복문으로 돌리며 (n m)에 2와 5가 몇개 들어있는지 파악해보았다. 하지만 시간초과가 나서 n>=m이므로 n!/m!을 m+1부터 n까지의 수를 모두 곱한 값으로 만들어 다시 짜봤다. 또 시간초과가 났다. 아무래도 n과 m에 큰 수가 들어올 수 있어서 반복문으로는 안될 것 같다. 아예 새로운 방법을 공부했다. 예를 들어 25!에 있는 2의 개수를 셀 때 25를 2로 나누어 몫(12)을 모두 변수 two에 담는다. 이 행동의 의미는 2, 4, 6, ---, 24를 한 번씩 센 것이다. 다시 이것을 2로 나누어 몫(6)을 two에 담는다. 이 행동의 의미는 4, 8, 12, ---, 24를 센 것이다. 또 2로..

예를들어 모자 2종류 상의 2종류 바지 3종류라면 (모자를 쓰는 2가지 경우 + 안쓰는 경우) = 3가지 경우의수로 이런 식으로 하면 3x3x4고 대신 모두 안쓰는 경우는 제외이므로 3x3x4-1을 하면 된다. 1. 각 의상의 이름을 리스트에 공백을 기준으로 나누어 받는다. 2. 리스트의 마지막 문자열로 어떤 의상인지 종류를 구분해 딕셔너리에 넣어준다. 3. 딕셔너리의 밸류값들을 리스트로 다시 만들어준다. (딕셔너리.values) 4. 모두 곱한 후 1을 빼준다.