문제를 풀 때 왜 완전 탐색부터 고려해야될까요?
그리고 완전 탐색은 어떻게 연습하면 좋을까요?
차근차근 살펴봅시다.
완전 탐색을 위해서는 크게 3가지 훈련이 필요합니다.
- 완전 탐색부터 떠올리는 연습
- 탐색 공간을 계산하는 연습
- 탐색을 구현하는 연습
완전 탐색부터 어떻게 떠올릴 수 있을까요?
완전 탐색을 떠올리기 전에 가장 중요하게 해야할 일이 2가지 있습니다.
- 문제의 목표를 명확하게 알아야합니다.
- 어떤 값을 구해야하는지 아는 상태다.
- 문제의 조건을 빠짐없이 알아야합니다.
- 값을 구하는데에 펼쳐진 상황을 이해한 상태가 된다.
위 2가지 작업을 통해 문제 상황에 대한 전체 경우의 수 파악을 합니다.
어떤 문제의 목표가 최댓값을 구해야한다면,
최댓값을 어떻게 구할지에 집중하는 것이 아닌
모든 상황을 어떻게 구해서 그 중 최댓값을 구할지에 집중해야합니다.
그렇다면 주어진 상황을 자세하게 들여다 볼 필요가 있겠죠?
예를 들어, 다음과 같은 상황이 있을때 전체 상황이 무엇일지 생각해봅니다.
- 동전을 던지는 상황이라면
- 앞면 or 뒷면
- 스위치가 있는 상황이라면
- 켜기 or 끄기
- 수식에 괄호나 연산자를 끼워넣는 상황이라면
- 추가 or 삭제
- 숫자가 N개 있는데 K개를 통해서 M을 만들어야한다면
- 각 숫자에 대해 뽑는다 or 안뽑는다
- nCk
- 격자판에서 이동한다면
- 이동할 칸 수 + 이동할 방향
- 테트리스 게임이라면
- 블록 모양 + 회전 횟수 + 착지 할 열 번호
치킨이 눈 앞에 있다면먹는다 or 먹는다
트와이스Yes or Yes
문제 상황을 분석하는 절차는 다음과 같습니다.
- 문제 조건을 모두 기록합니다.
- 조건 간 종속/독립 관계를 따져봅니다.
- 독립 조건 내에 발생하는 종속 상황을 모두 기록합니다.
- 각 독립 조건을 조합합니다.
최종적으로 문제에 주어진 모든 상황을 알 수 있습니다.
탐색 할 공간이 어떻게 생겼을까요?
모든 상황을 알게되었다면, 해당 상황을 그렸을 경우 생기는 공간의 크기를 알아야합니다.
공간의 크기를 통해 탐색하는데에 걸리는 시간을 예상할 수 있기때문입니다.
또한, 공간 중 어떤 부분을 건드려야 시간 효율을 쉽게 얻을 수 있을지 알 수 있기때문입니다.
앞에서 말씀드린 예제의 탐색 공간을 계산해봅시다.
- 동전, 스위치, 삽입여부
- 2개, True False
- 만약 동전이 N개 라면?
- 2N
- N = 2
- 00, 01, 10, 11
- N개 중 K를 골라야하는 상황
- nCk
- 격자판 상황
- 부딪힌다 or 겹친다 or 튕긴다 or 지나간다
- 한 번의 이동에 발생할 수 있는 4개 상황
- 테트리스
- 블록 모양이 4개, 회전 방향이 동서남북, 열의 개수 10개
- 4 x 4 x 10
- 만약 내려올 블록이 N개라면?
- N x 4 x 4 x 10
- 만약 내려오는 블록 순서가 중요하다면?
- N! x 4 x 4 x 10
- 블록 모양이 4개, 회전 방향이 동서남북, 열의 개수 10개
탐색 공간을 계산하기 위해서는 문제의 조건을 정확하게 파악하는 작업이 필요합니다.
각각의 조건을 변수와 상수로 만들어서 수치화하는 작업이 있어야 계산할 수 있기 때문이죠.
탐색 공간은 문제에서 주어진 조건에 따라 크기가 달라집니다.
조건을 빠짐없이 기록하지 않으면, 그만큼의 공간을 탐색하지 못하므로
예외가 발생할 확률이 높겠죠?
탐색 공간을 알기 전 문제의 조건을 정확하게 파악하고 분석하는 일이 먼저입니다.
그 이후 탐색 공간을 계산하는 일은 어렵지 않기때문이죠.
어떻게 공간을 모두 둘러볼까요?
이제 둘러볼 공간에 대해 완전히 알았으니, 탐색할 일만 남았습니다.
무식하고 쉽게 모든 공간을 살펴보려면 어떻게 해야할까요?
앞선 단계에서 조건을 명확하게 정의해뒀다면, 탐색하는 코드를 작성하는 일도 매우 간단합니다.
각각의 변수(동전, 모양, 방향, 번호)에 대해 반복문을 돌리면 구현이 가능합니다.
동전 1개
동전이 하나 있을때는 나올 수 있는 가짓수는 2개입니다.
2개를 탐색하는데에 코드 2줄이면 가능하겠죠?
동전 = 앞면, 동전 = 뒷면
혹은 반복문으로 작성 할 수도 있습니다.
for(i=0~1){} //0: 앞면, 1:뒷면
동전 N개
만약 동전이 N개라면 2N의 탐색 공간이 필요했습니다.
2N을 풀어서 쓰면 2를 N번 곱한 식과 동일합니다.
N번 반복해서 2를 곱한 작업으로 볼 수 있으므로, 반복문을 N번 돌리면 가능하겠죠?
각각의 동전(i번 동전)에 대해 앞면, 뒷면을 확인한다고 생각할 수 있습니다.
for(i=1~N){동전 = 앞면, 동전 = 뒷면}
테트리스
테트리스의 경우에 블록 모양이 N개, 회전 방향이 M개, 열의 개수 K개인 경우는 다음과 같습니다.
블록 모양 1, 회전 방향 1, 열 번호 1
블록 모양 1, 회전 방향 1, 열 번호 2
블록 모양 1, 회전 방향 1, 열 번호 ...
블록 모양 1, 회전 방향 1, 열 번호 K
블록 모양 1, 회전 방향 2, 열 번호 1
블록 모양 1, 회전 방향 2, 열 번호 2
블록 모양 1, 회전 방향 2, 열 번호 ...
블록 모양 1, 회전 방향 2, 열 번호 K
블록 모양 1, 회전 방향 ..., 열 번호 1
블록 모양 1, 회전 방향 ..., 열 번호 2
블록 모양 1, 회전 방향 ..., 열 번호 ...
블록 모양 1, 회전 방향 ..., 열 번호 K
블록 모양 1, 회전 방향 M, 열 번호 1
블록 모양 1, 회전 방향 M, 열 번호 2
블록 모양 1, 회전 방향 M, 열 번호 ...
블록 모양 1, 회전 방향 M, 열 번호 K
각 상황이 1부터 N,M,K까지 반복되는 모양을 볼 수 있습니다.
따라서, 반복문을 통해서 구현해주면 됩니다.
for(i=1~N){ for(j=1~M){ for(k=1~K){ }}}
정리
완전 탐색을 "완전"의 부분과 "탐색"의 부분으로 나눠서 살펴봤습니다.
"완전"의 경우, 문제에 주어진 조건들로 인해 생기는 모든 상황 완전히 알아보기
"탐색"의 경우, 완전한 공간을 반복문 이용해 탐색하기
문제를 푸실때 완전 탐색부터 해야하는 이유는
주어진 상황에 대한 모든 탐색 공간을 알고 있는 상태에서
모든 공간을 탐색하는 방법을 생각해봐야
문제를 온전히 파악하고, 올바르게 해결할 수 있기때문입니다.
모든 공간을 탐색할 필요없이
특정 부분만 탐색을 해도 문제가 해결될 수 있습니다.
모든 공간을 모르는 상태에서 특정 부분을 탐색하는 방법을 떠올리기
모든 공간을 아는 상태에서 특정 부분을 탐색하는 방법을 떠올리기
문제를 해결하는데에 엄청나게 큰 차이가 존재합니다.
모든 공간을 모른다는 말은
문제를 올바르게 이해하지 못한 상태와 동일하고,
해당 상태에서 문제를 해결하는 행위는
다른 문제를 해결하는 행위와 동일합니다.
그로 인해, 많은 디버깅과 예외를 맛보게 될 것입니다.
모든 공간을 모르는 상태에서 특정 부분을 탐색하는 방법을 떠올리기
vs
모든 공간을 아는 상태에서 특정 부분을 탐색하는 방법을 떠올리기
=
내가 만든 문제 풀기
vs
내 눈 앞의 문제 풀기
=
맞왜틀
vs
맞았습니다!!
다음 시간 예고
탐색 구현 설명 중 빠진 내용인
반복문으로 완전 탐색을 못하는 경우에 대해 살펴보겠습니다.
