문제 https://www.acmicpc.net/problem/1208 1208번: 부분수열의 합 2 첫째 줄에 정수의 개수를 나타내는 N과 정수 S가 주어진다. (1 ≤ N ≤ 40, |S| ≤ 1,000,000) 둘째 줄에 N개의 정수가 빈 칸을 사이에 두고 주어진다. 주어지는 정수의 절댓값은 100,000을 넘지 않는다. www.acmicpc.net 풀이 solved.ac 난이도: Gold 1 원소가 부분수열에 포함되는지 여부를 경우의 수로 생각해 보자. 포함되느냐 안되느냐인 두 가지 선택을 40개의 수에 적용하면 2^40 가지의 경우가 나온다. 2^40 = 1,099,511,627,776(약 1TB) 이므로 시간 안에 동작시킬 수 없다. 여기서 사용되는 기법이 양방향 탐색(Bidirectional..

문제 https://algospot.com/judge/problem/read/HANOI4 algospot.com :: HANOI4 하노이의 네 탑 문제 정보 문제 하노이의 탑은 세 개의 기둥에 꽂혀 있는 N개의 원반을 가지고 하는 게임입니다. N개의 원반은 크기가 모두 다르며, 게임의 시작 때는 그림과 같이 맨 왼쪽의 기둥 algospot.com 풀이 종만북 난이도: 중 재귀 함수 문제의 대표 격인 하노이 탑 문제에 기둥을 1개 더 추가하여 4개인 상태로 해결하는 문제이다. 이번 문제의 핵심은 각 기둥에 꽂혀있는 원판들의 상태를 어떻게 저장하느냐이다. 단순히 4개의 기둥들이 어떤 원판을 가지는지 stack을 사용하여 표현한다면 4개의 스택(각각의 기둥)을 가지는 구조체로 나타낼 수 있을 것이다. 1 2 ..