알고리즘 (3) 썸네일형 리스트형 순열 구현 순열 순열은 기본적으로 재귀 함수로 구현할 수 있다. 10!을 구한다고 하자. 10!=10*9!이므로 10!을 구하기 위해선 9!을 구해야하고 9!=9*8!...이므로 9!를 구하기 위해선 8!을 구해야하므로... 재귀적이라 할 수 있다. 코드는 다음과 같다. void perm(char[] list, int i, int n) { //list의 i번째부터 n번째 인덱스에 해당하는 요소 출력 if (i == n) { for (int j = 0; j 그래프 탐색 DFS, BFS 정리 1. BFS(너비 우선 탐색) - 가장 가까운 노드들 먼저 탐색, 레벨 순으로 탐색 - 큐로 구현 BFS 왜 사용 ? 1. 최단 경로(가중치 x) 구할 때 사용. 목적지를 찾자마자 최단 경로임이 보장되어 탐색을 종료함. 왜 최단 경로? - 2178 미로찾기 BFS 일일이 분석해보면 왜 최단경론지 알 수 있삼 - 또는 아래 증명 참고 https://velog.io/@kasterra/%ED%95%B5%EC%8B%AC-%EC%9E%90%EB%A3%8C%EA%B5%AC%EC%A1%B0-%EA%B7%B8%EB%9E%98%ED%94%84-%EC%B5%9C%EB%8B%A8-%EA%B2%BD%EB%A1%9C-%ED%83%90%EC%83%89 2. 재귀를 통해 시스템 스택을 사용하는 DFS에 비해 queue를 사용하기 .. DP 동적 프로그래밍 느낌 정리 dp는 이런 느낌의 문제다 정리 1. f(10)을 구하는 문제=f(9), f(8)을 구하는 문제로 바꿀 수 있. 2. 초기값을 구할 수 있. f(0)=0,f(1)=1 핵심 ! - 반복문이나 재귀 호출로 해결 - 먼저 구한 해를 저장하고 다음에 써야(메모제이션) + 메모제이션할 때 보통 2가지 유형으로 나뉘는 듯 1) dp[n] : n을 포함하는 최대 길이 2) dp[n] : n까지 왔을 떄 최대 길이 이전 1 다음
