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

전쟁을 하러 가면서 총을 안가져 가는 격이지만

혹시 시험을 보러 갔는데 완전탐색을 풀 수 있는 문제가 나왔고

코드가 기억나지 않더라도 끝까지 물고 늘어져야 합니다.

 

많은 문제가 ~하는 경우는 몇 가지인가? 라고 묻기도 하지만

~하는 최대 값은 얼마인가? 라고 묻는 경우가 많이 있습니다.

(실제도 경우의 수보다 최대/최소값이 더 중요합니다.

  ~과제를 하는데 최소 얼마가 필요합니다. 라고 해야지

  "몇가지 방법이 있는데요.""라고 하면

  "이런.. 그래서 어떤 것이 최소냐고?" 라고 하겠죠.)

 

이럴때 순열/조합/중복순열/중복조합을 꼭 확인하고 풀어야 하는 경우도

있지만 중복순열로 풀면 되는 경우가 많이 있습니다.

 

왜냐하면 중복순열이 나머지를 다 포함하기 때문이죠.

 

그리고 모두 몇개를 고르는 것이 모르면 어려운데

(for문을 몇번 쓰는지 모르기 때문에)

예를 들어 항상 8개를 고른다고 하면 8중 for 문을 쓰면 됩니다.

for (a1=1;a1<=8;a1++)

  for (a2=1;a2<=8;a2++)

    ......

 

재귀 이런것 몰라도 이렇게 8중 for문 쓰면 그게 8개를 뽑는 중복순열입니다.

 

어차피 온라인저지는 코드를 보지 않기 때문에 답만 맞으면 되지

어떤 함수를 썼는지는 중요하지 않고 창피한 것 이런거 없습니다.

 

조합으로 풀 수 있는 것을 중복순열로 풀면 몇배의 실행시간이 더 걸리겠지만

답이 같은 경우가 많이 있습니다.

(아닌 것도 분명 있습니다.그러니 꼭 도구(외운 기본 코드)를 가지고 시험장에 가야죠.)

 

 

그리고 조합의 경우는 "바이너리 카운팅"이라는 방법으로 쉽게? 구할 수 있습니다.

재귀 같은 것 없습니다. 

(재귀를 이해 못하시겠으면 이렇게라도 하시면됩니다.)

 

비트연산을 이용하는 것인데 코드도 있고 하니 아래를 참고하세요.

http://dumpsys.blogspot.kr/2015/03/algorithm-binary-counting-power-set.html

 

많은 경우가 완전 탐색 문제이니 모든 경우의 수를 찾는,

즉, 순열/조합/중복순열/중복조합/(복합) 중 어떤 것인지를 빨리 알아내는 것이 중요합니다.

 

 

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