멱집합 알고리즘 멱집합은 한 집합의 모든 부분집합을 뜻합니다. 원소 a,b,c를 갖고 있는 집합의 모든 부분 집합은 (a, b, c, ab, ac, bc, abc + 공집합)으로 총 8가지 입니다. 탐색 (재귀, 브루트포스) 알고리즘 문제를 풀때 멱집합을 구하는 방법을 종종 사용하게 됩니다. 모든 부분집합의 경우의 수를 구하는 과정은 다음과 같습니다. 첫번째 원소가 포함이 되는가? 혹은 안되는가?→ 두번째 원소가 포함이 되는가? 혹은 안되는가? → . . . → N번째 원소가 포함이 되는가? 혹은 안되는가? 그래서 원소의 갯수가 N인 집합의 모든 부분집합의 갯수는 2^N개가 됩니다. 아래는 주어진 집합의 모든 부분집합을 출력하는 (java)코드입니다. 핵심부분은 위에서 설명한대로 n번째의 원소가 포함이 ..
재귀란 어떤 사건이 자기 자신을 사용하여 정의 될 때 재귀적(recursive)라고 합니다. 대표적인 예로 팩토리얼이 있습니다. (팩토리얼의 10!는 10x9!로 설명할 수 있다.) 재귀는 스택이다. 재귀 알고리즘이 어렵다고 느껴지는 이유 중 하나는 사람의 머리로 컴퓨터가 실행하는 재귀적 행동을 따라 갈 수 없기 때문입니다. 재귀 알고리즘을 보다 쉽게 상상하려면, 같은 함수가 호출 되는 것이 아니라, 복사된 함수가 호출 된다고 생각합니다.함수의 호출을 상상 할때는 스택(stack)으로 합니다. 함수 호출의 원리는 결국 스택으로 진행됩니다. 함수가 호출되면 기존 함수 스택 위에 호출된 함수가 쌓이게 되고, 더 이상 쌓을 함수(스택)이 없게 되면 위에서부터 차례대로 실행하게 됩니다. 재귀 알고리즘 문제 풀이..