안녕하세요 오늘은 부분집합에 대한 간단한 설명 및 구현 코드를 통해 코드로 수학시간에 배웠던 부분집합을 새롭게 느껴보려고 합니다. 부분집합 (Powerset) 학창시절 수학의 정석을 펼치면 늘 1단원에 있던, 집합 저희는 모두 1단원 반복문에 갇혀 나오지 못한 경험이 있으니 집합에 대해서 다들 알고 계시겠죠? 부분집합은, literally 어떤 집합의 부분들에 대한 집합입니다. 나만의 라면 레시피를 만든다고 가정해보겠습니다. 들어갈 수 있는 재료는 다음과 같습니다. {치즈, 계란, 대파, 새우, 홍합} 이제 이 재료들의 부분집합을 계산한다면, 각 재료들에 대해 들어가는 경우와 들어가지 않는 경우를 나누어 2*2*2*2*2 = 32 그럼 이제 32가지의 집합들을 출력하는 코드를 구현해보겠습니다. 반복문을 ..
재귀함수
안녕하세요 오늘은 백트래킹에 대한 포스팅을 작성해보겠습니다. 목차 1. 백트래킹 기법 2. DFS와의 차이점 3. 대표적 문제예시 4. N-Queen 코드 한 줄 요약 백트래킹은 모든 후보 검사가 아니다, 즉 완전탐색이 아니다. 1. 백트래킹 기법 어떤 노드의 유망성을 점검한 후 에 유망하지 않다고 결정되면 그 노드의 부모로 되돌아가 다음 자식 노드로 간다. 가지치기(pruning): 유망하지 않는 노드가 포함되는 경로는 더 이상 고려하지 않는다. 2. 백트래킹과 DFS와의 차이 출발하는 경로가 해결책으로 이어질 것 같지 않으면 더 이상 그 경로를 따라가지 않음으로써, 시도 횟수를 줄인다. 깊이 우선 탐색이 모든 경로를 추적하는데 비해 백트래킹은 불필요한 경로를 조기에 차단할 수 있다. N! 가지의 경우..
