프로그램을 배웠으나 알고리즘 시험을 봐야 한다면. #10

오늘은 꼭 온라인 시험이 아니더라도 해당되는 실행 시간 관련 이야기를 해보겠습니다.

 

러시아 페인트공 알고리즘이라는 것이 있습니다. "조엘 온 소프트웨어" ( http://book.naver.com/bookdb/book_detail.nhn?bid=1528741 ) 라는 책에 나오는 많이 인용되는 이야기입니다. 한번만 해도 되는 일을 반복해서 하는 것에 대한 우화입니다.

(우리 일상도 그렇고 우리가 짠 프로그램도 그렇고)

 

시험을 볼 때 일단 구현을 해서 원하는 답이 나와도 제한 시간을 초과하면 온라인저지 시스템에서 Timeout이 걸립니다.

물론 신입사원 레벨에서는 좀 넉넉히 주겠지만 암튼 걸리는 경우가 많이 있습니다.

(어제 예를 든 1), 2), 3) 모두 해당되지만 특히 2), 3)에 많이 해당됩니다.)

 

이럴 때는 아래와 같은 경우가 있습니다.

1) 알고리즘의 복잡도 (O(10^n 처럼)가 높은 경우

2) 가지치기를 안한 경우

3) 반복 계산을 하는 경우

 

1) 알고리즘의 복잡도 (O(10^n) 같은 높은 경우

   알고리즘 능력과 많이 관계가 있습니다. 복잡도가 낮게 짤 수 있을 수록 알고리즘 실력이 뛰어난 것이죠.

   (O(n^3) 로 풀던 것을 O(n^2)로 풀면 시간이 많이 줄어들겠지요. 몇 개 안되면 효과가 적지만)

   이건 당장 어쩔 수 없습니다. 계속 공부 하다 보면 효과적인 방법을 생각할 수 있게 되겠지요.

2) 가지치기를 안한 경우

   완전탐색(DFS/BFS)등에서 원하는 답을 얻었거나 더 이상 할 필요가 없음에도 계속 하는 경우가 있습니다.

   이럴 때는 가지치기만 확실히 하는 것 만으로도 실행 시간이 많이 줄어듭니다.

3) 반복 계산을 하는 경우

   예를 들어 외판원 문제 (TSP, https://ko.wikipedia.org/wiki/%EC%99%B8%ED%8C%90%EC%9B%90_%EB%AC%B8%EC%A0%9C )같은 문제를 풀 때 순회 순서를 정하고 거리를 구해 보는데 순회 순서를 바꿀 때 마다 거리를 다시

   구하면 시간이 많이 걸립니다. 그런데 모든 장소에서 모든 장소까지를 미리 계산해 table을 만들어 사용하면 순회 순서만 정해지면

   총 거리는 매번 모든 위치를 계산할 필요가 없이 표를 보고 쉽게 계산이 됩니다.

   위에 러시아 페인트공이 바로 이렇게 반복해서 하는 작업이 있지요.

   또, 문자열 뒤에 문자열을 계속 추가하는 것도 대표적인 예입니다.

 

문제를 풀 때 반복 계산하는 것을 찾게 되면 속도도 빨라지고 완전탐색으로 할 때 

Momoization ( https://ko.wikipedia.org/wiki/%EB%A9%94%EB%AA%A8%EC%9D%B4%EC%A0%9C%EC%9D%B4%EC%85%98 )을 자연스럽게 구사하게 되고 한계를 느끼면 Dynamic Program로 연결이 됩니다. 처음 부터 DP를 공부하면 알고리즘 공부 포기하게 되요.

 

사실 이것은 어떻게 하던지 답은 맞았으나 시간초과일 때 사용해야 하지만

반대로 생각해 보면 시간초과가 되면 답이 맞았는지도 모르고 이렇게 하는 습관이 있어야

평소에도 실행 시간이 짧은 코드를 만들 수 있습니다.

 

다 적어 놓고 편집하는 것이 아니라서 번호만 붙었지 순서가 뒤죽박죽입니다.

 

다음 편에는 최대/최소를 구할 때 많이 사용하는 완전탐색에 대해 생각해 보겠습니다.

 

아래는 삼성 SW 검정 시험 (S직군이 보는) 관련 글인데

총 4등급 중 상위 2등급에 관한 글이지만 아래 부분은 시험을 보는 방법에

대한 것이 참고가 될 것입니다.

http://hongjun7.tistory.com/129

 

#삼성_소프트웨어_역량_테스트