알고리즘 기초 - 완전탐색

이 글은 학회 회원 랑이집사님의 허락을 받아 에브리타임 게시글을 그대로 가져왔습니다.

 

원래 아주 중요한 배열을 이용한 코딩 스킬을 올리려고 했는데, 내용이 너무 길어질것 같기도 하고 그 내용은 코드를 많이 보여드려야 하는데 에타에 적긴 쉽지 않을것 같아서 우선 미뤘습니다. 알아두면 코딩이 훨씬 간단해지니 다음에 방법을 찾아서 적어보도록 할게요!

코딩 테스트, 대회, 취미 등 알고리즘을 공부하는 이유는 여러가지가 있겠지만 처음 공부할 때 어떤 알고리즘부터 해야할지 막막하실거에요. 백트래킹, 동적계획법, DFS, BFS, 그리디 등 검색하면 여러 알고리즘이 나오지만 전 우선 처음 시작했으면 완전탐색부터 잡아야 한다고 생각합니다.

컴퓨터는 1초에 약 1억번의 연산을 합니다. 그리고 대부분의 문제는 시간제한이 최소 1초 이상입니다. 그럼 문제를 풀 때 컴퓨터한테 1억번의 연산은 시켜도 된다는 뜻인데, 그렇게 많은 연산이 가능하다면 문제를 푸는 방식이 꼭 사람처럼 복잡하지 않아도 되는거 아닌가 하는 생각을 할 수 있습니다.

 

http://boj.kr/14568

위 문제를 보시면 사탕을 나눠주는 규칙이 있습니다. 정답이야 어떤 수식 하나로 구할 수도 있을것 같아요. 하지만 이건 사람이 푸는 방식이고, 컴퓨터는 아래처럼 풀 수 있습니다.

택희, 영훈이, 남규가 사탕을 (1,1,1)개씩 가져간 경우 문제의 조건을 만족하는지, (1,1,2)개씩 가져간 경우 문제의 조건을 만족하는지, (1,1,3)개씩 가져간 경우 문제의 조건을 만족하는지,...(100,100,100)개씩 가져간 경우 문제의 조건을 만족하는지

위의 모든 경우를 살펴본 뒤 조건을 만족하는 경우의 수를 세면 약 100*100*100=100만번 연산으로 정답을 구할 수 있습니다.

간략한 코드

for(i=1;i<=100;i++)
for(j=0;j<=100;j++)
for(k=0;k<=100;k++)
if(i+j+k==n && i >= j+2 && k % 2 == 0)
cnt++


일반적인 수학 문제를 푸는 것과 알고리즘 문제를 푸는 것에는 이런 차이가 있다는걸 인식하고, 컴퓨터의 연산 수를 이용해 문제를 쉽게 푸는 것이 알고리즘 공부의 첫단계라고 생각합니다.

한문제만 더 볼게요.

http://boj.kr/15734

왼발잡이, 오른발잡이, 양발잡이 선수가 있는데 양발잡이 몇명을 어느쪽에 배치하는게 좋을지 골라야 합니다. 수식 생각중이시면 멈추시고, 양발잡이를 배치하는 모든 경우를 확인할 수 있다는걸 생각하셔야 합니다.

양발잡이 a명 중 왼발잡이 쪽으로 0, 1, 2, 3..., a명 보내고 나머지를 오른발잡이 쪽으로 보내는 경우를 다 살펴봅시다.
만약 입력이 7 7 7로 들어온다면 아래 경우를 모두 보는겁니다.

양발잡이 0명을 왼발잡이 쪽으로, 나머지 7명을 오른발잡이 쪽으로 보내는 경우 - (7,14)명이 됩니다.
양발잡이 1명을 왼발잡이 쪽으로, 나머지 6명을 오른발잡이 쪽으로 보내는 경우 - (8, 13)명이 됩니다.
...
양발잡이 7명을 왼발잡이 쪽으로, 나머지 0명을 오른발잡이 쪽으로 보내는 경우 - (14, 7)명이 됩니다.

간략한 코드

for(i=0;i<=a;i++)
{
left = l + i;
right = r + a - i;
if(answer < min(left, right))
answer = min(left, right);

//사실 아래처럼 한줄에 적는 경우가 많습니다
//answer = max(answer, min(l + i, r + a - i));
//min, max, abs를 잘 사용하면 코드가 짧아지고 가독성이 좋아지는데 이건 나중에 따로 다룰게요.
}


알고리즘 공부를 처음 하시는 분들이 이 글을 보시고 컴퓨터로 문제를 푸는게 사람이 푸는 것과 어떻게 다른지 약간이라도 감을 잡으셨길 바라고, 이런 컨셉으로 풀어볼만한 간단한 문제들 몇개 남겨두겠습니다.
제 코드도 공유해드리고 싶은데 어떻게 드려야 할지 잘 모르겠네요.. 좋은 아이디어 있으시면 댓글 남겨주세요.

http://boj.kr/2875

http://boj.kr/6131

http://boj.kr/16283

http://boj.kr/16561

http://boj.kr/17945

http://boj.kr/2503