Dev/Algorithms 썸네일형 리스트형 카탈란 수 Catalan number Python 구현 https://www.acmicpc.net/problem/10422 10422번: 괄호 ‘(‘, ‘)’ 문자로만 이루어진 문자열을 괄호 문자열이라 한다. 올바른 괄호 문자열이란 다음과 같이 정의된다. ()는 올바른 괄호 문자열이다. S가 올바른 괄호 문자열이라면, (S)도 올바른 괄호 문자열이다. S와 T가 올바른 괄호 문자열이라면, 두 문자열을 이어 붙인 ST도 올바른 괄호 문자열이다. (()())()은 올바른 괄호 문자열이지만 (()은 올바른 괄호 문자열이 아니다. 괄호 문자열이 주어졌을 때 올바른 괄호 문자열인지 확인하는 방법은 여러 www.acmicpc.net 이 문제를 풀면서 처음 알게된 수열이다. 뭐 위키피디아 같은데 보면 증명 다 볼 수 있는데, 코딩테스트에서 쓸 수 있을정도로만 알면 되니까.. 더보기 DP- 0-1 Knapsack (백준 12865 평범한 배낭) 문제 : 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 0-1 Knapsack 문제 0-1 Knapsack은 물건을 쪼갤 수 없기 때문에 DP로 풀어야 한다. DP 배열은 DP [N개의 물건까지 확인했을 때][물건의 무게] = 물건의 가치이다. 이때, i 번째까지 물건을 확인했을 때, j까지 담을 경우에는 dp [i][j] =.. 더보기 next_permutation Python 구현 def next_permutation(arr): i,j = len(arr)-1, len(arr)-1 while i>0 and arr[i-1]>=arr[i]: i-=1 if i==0: return False while arr[i-1]>=arr[j]: j-=1 arr[i-1], arr[j] = arr[j],arr[i-1] k = len(arr)-1 while i= arr[i] 가 되는 i 중 제일 큰 값을 찾는다. i 가 0 이 되면 [5,4,3,2,1] 같이 역으로 정렬되어있는 값이라 순열의 끝이라 False 를 반환한다. arr[i-1] >= arr[j] 가 되는 j 중 가장 큰 값을 찾는다. 이 때, 1 번에서 arr[i-1] >= arr[i] 를 찾았기 때문에 무조건 i 더보기 이전 1 다음
