알고리즘/알고리즘 개념

[알고리즘 개념] 순열 조합 부분집합(순조부~)

자바로 알고리즘을 풀면서 순조부에 대해서 깊게 공부해야했습니다... (파이썬은 api가 있지만 자바는 없기 때문에) 순조부를 공부하면서 자신이 없던 재귀도 공부하구,,, 의외로 문제 풀때 개념이 많이 쓰이더군용.. 그런 문제만 풀어서 그른가 아무튼 핵심 개념에 대해서 글을 써보겠습니다. 순열(Permutation) 서로 다른 n개 원소 중 r개를 뽑아서 한 줄로 나열하는 것. nPr 쉽게 예제를 통해 말하면 3명 중에서 회장 1명, 부회장 1명을 뽑는다면 (a,b) (a,c) (b,a) (b,c) (c,a) (c,b) 이런 식으로 뽑을 수 있는데 중요한 포인트는 a,b != b,a 입니다. (조합과 다른 큰 특징) 예시 코드 private static void permutation(int cnt) { /..

[알고리즘] 다이나믹 프로그래밍 (DP) 이해하기

다이나믹 프로그래밍(동적계획법)이란? - 큰 문제를 풀기 위해서 작은 문제를 풀어 나가는 방식이며, 작은 문제에서 반복이 없다는 것이 특징입니다. -> 분할 정복 기법과 다른 결정적인 차이 또한 하나의 문제를 단 한 번만 푸는 알고리즘 다이나믹 프로그래밍 조건 1. 큰 문제를 작은 문제로 나눌 수 있다. 2. 작은문제에서 구한 정답은 이것을 포함한 큰 문제에서도 동일한 정답이다. 이러한 조건때문에 시간 복잡도를 훨씬 줄일 수 있습니다!!! 어떻게 구현할까요?? 메모이제이션(Memoization) 기법 활용 말 그대로 메모하는 기법입니다. 작은 문제 계산된 결과값을 배열을 사용해서 저장하고, 나중에 큰 문제에서 동일한 계산을 요구할 때 배열의 저장된 값을 불러오는 것입니다. -> dp 리스트 초기화해서 안..