python에는 너무 유용한 내장 함수가 많이 있는데, 그 중에서도 경우의 수를 구할 때 사용되는 내장 함수를 다뤄보겠다. 경우의 수는 전체 탐색이 필요한 알고리즘 문제에서 은근 자주 쓰이므로 기억해둘 것! 경우의 수를 구할 땐 itertools라는 모듈을 활용한다. import itertools 순열 서로 다른 n개 중에서 r개를 '순서'대로 나열하는 경우의 수 # 배열 ['1','2','3','4'] 중에서 서로 다른 원소 두 개를 순서대로 나열하는 경우의 수를 출력한다. itertools.permutations(['1','2','3','4'], 2) 중복순열 중복 가능한 n개 중에서 r개를 '순서'대로 나열하는 경우의 수 # 배열 ['1','2','3','4'] 에서 중복 가능한 원소 두 개를 순서..
[Algorithm] 동적 계획법(dynamic programming)
복잡한 문제를 간단한 여러 개의 문제로 나누어 푸는 방법 동적 계획법은 부분 문제를 풀고 결과를 저장한 후, 다음 부분 문제를 푸는 과정에서 저장된 결과를 사용한다. 그렇기 때문에 문제가 '최적 부분 구조'와 '중복되는 부분 문제'를 갖고 있다면 동적 계획법으로 해결이 가능하다 최적 부분 구조 : 답을 구하기 위해서 했던 계산을 반복해야 하는 문제의 구조 상향식 접근을 사용하는 것이 중요! 메모이제이션 프로그램이 동일한 계산을 반복할 때 이전에 계산한 값을 메모리에 저장하여 동일한 계산의 반복 수행을 제거해 프로그램의 실행 속도를 빠르게 하는 기법이다. 예제 - 최장 증가 부분열 주어진 리스트에서 '최장 증가 부분열'을 찾아보자. 최장 증가 부분열이란, 증가하는 순서대로 숫자를 고른 부분열의 길이가 최대..