1182번: 부분수열의 합 첫째 줄에 정수의 개수를 나타내는 N과 정수 S가 주어진다. (1 ≤ N ≤ 20, |S| ≤ 1,000,000) 둘째 줄에 N개의 정수가 빈 칸을 사이에 두고 주어진다. 주어지는 정수의 절댓값은 100,000을 넘지 않는다. www.acmicpc.net IDEA 공집합을 제외한 모든 부분 집합의 원소의 합을 계산해보는 문제다. 하나만 고르는 경우, 둘을 고르는 경우, 이렇게 따로따로 생각하면 어떻게 접근해야할지 좀 막막한데 백트래킹의 원리를 생각해보면 모든 경로를 탐색하고, 매 탐색마다 탐색 중인 정점의 수치를 더해주고 되돌아갈 때 더했던 값을 다시 빼주면 1~N개까지의 원소를 갖는 모든 부분 집합을 한번씩 탐색할 수 있다. CODE using System; class Pro..

12100번: 2048 (Easy) 첫째 줄에 보드의 크기 N (1 ≤ N ≤ 20)이 주어진다. 둘째 줄부터 N개의 줄에는 게임판의 초기 상태가 주어진다. 0은 빈 칸을 나타내며, 이외의 값은 모두 블록을 나타낸다. 블록에 쓰여 있는 수는 2 www.acmicpc.net IDEA 브루트포스 문제는 복잡한 생각을 할 필요가 없어서 좋다. 한 때 재밌게 하던 2048 게임을 구현하는 문제다. 모든 가능성을 탐색해서 원하는 결과를 뽑아내면 된다. 탐색 과정에서 이전 과정을 기억해두고 되돌아가 다른 경로를 탐색할 수 있도록 하는 것이 관건이다. N * N 크기의 배열을 스택에 담아 탐색 과정을 관리하도록 했다. 처음에는 N * N 배열을 매개변수로 하는 재귀 호출로 구현했다. 그런데 매개변수로 받아온 데이터는..

2580번: 스도쿠 스도쿠는 18세기 스위스 수학자가 만든 '라틴 사각형'이랑 퍼즐에서 유래한 것으로 현재 많은 인기를 누리고 있다. 이 게임은 아래 그림과 같이 가로, 세로 각각 9개씩 총 81개의 작은 칸으로 이루 www.acmicpc.net IDEA 아주 오래전 군복무 중에 도전했던 문제다. 한창 재귀호출에 대해 (어설프게) 공부하고 있을 때 였는데 백트래킹이라는 것을 연습해보려 몇문제 덤벼들었다가 뼈도 못추린 적이 있었다. 그 때는 대강 이런 알고리즘을 생각했던 것 같다. 1. 입력을 받는다. 동시에 빈칸의 수를 센다. 2. 모든 칸을 순차적으로 확인한다. 3. 빈칸이라면 경우의 수를 파악한다. 4. 만약 한 가지 경우의 수만 있다면 그 칸을 채운다. 5. 아니라면 다음 칸을 확인한다. 6. 끝까..