교육 초반에 쓰다가 한동안 보이지 않았었는데, dfs나 bfs와 결합된 알고리즘에서 많이 사용되어 잊어버리지 않기 위해 다시 정리하기로 했다 순열(Permutation = nPr) = n*n-1*n-2* ... * n-r+2 * n-r+1 = n부터 r개만큼 곱하기 - 서로 다른 n개의 수들 중 r개를 순서를 맞춰 뽑음 - 출발지, 도착지를 선택하면 이동 경비를 최소로 사용하면서 모든 도시를 여행하는 경우 - 릴레이 계주 선수 4명 중 3명을 뽑는다 = ₄P₃ 예시 코드 - input, numbers, isSelected 사용 int N = 4; // 주어진 N개의 수 int R = 3; // 뽑으려고 하는 수 R int[] input = new int[N]; // input에 N개의 숫자 넣기 int[..

메모이제이션(memoization) - 컴퓨터 프로그램을 실행할 때 이전에 계산한 값을 메모리에 저장해서 매번 다시 계산하지 않도록 하여 전체적인 실행속도를 빠르게 하는 기술 - 추가적인 메모리 공간이 필요하다 - 재귀 함수 호출로 인한 시스템 호출 스택을 사용하게 되고 실행 속도 저하 또는 오버플로우가 발생할 수 있다 재귀 if(n=N && memo[n]==0) memo[n] = DP(n-1)+DP(n-2); return memo[n]; 동적계획법(Dynamic Programming) 그리디 알고리즘과 같이 최적화 문제를 해결하는 알고리즘 먼저 작은 부분 문제들의 해들을 구하고 이들을 이용하여 보다 큰 크기의 부분 문제들을 해결하여, 최종적으로는 원래 주어진 문제를 해결하는 알고리즘 설계 기법 재귀(하..

long min = 0; long mid = 0; while(min 찾고자 하는 값보다 큰 수가 있는 첫 번째 인덱스 if(count >= num) max = mid; else min = mid + 1; } 기본 틀만 잘 알면 활용할 수 있는데 그게 어렵다......