[Algorithm] 수제 버거 장인 (SW Expert Academy – 3421)

By | 2018-08-14

출처

  • https://www.swexpertacademy.com

난이도

  • (하) – 중 – 상 – 최상 – 풀지 못함

문제 (항상 대략적인 설명만 작성합니다. 문제는 위 출처에서 확인하세요)

  • 여러 개의 재료를 사용하여 햄버거를 만들려고 한다. 하지만, 같이 사용하면 안되는 재료의 종류가 주어질 때 총 만들 수 있는 햄버거의 가짓수를 계산하는 문제이다.
  • SW Expert Academy의 경우 문제 공개를 하면 안 된다고 되어있어서 상세히 문제를 설명하지 않았다. 상세한 내용은 위 사이트에서 확인 부탁합니다.

후기

  • 처음에 읽고 모든 가짓수를 계산하기 위해서 Recursive 함수와 Cache (메모이제이션)을 사용하여 문제를 풀려고 생각해보았다. 하지만, 구현 방법이 바로 머리에 생각나지 않아서, 단순히 For Loop을 사용하여 모든 가짓수를 계산하는 코드를 작성했다.
  • 총 N개의 재료가 주어질 때 총 만들 수 있는 햄버거의 개수는 0부터 1 << N (1을 N 번 Shift 한 결과)까지이다. 이중 특정 재료가 들어간 햄버거를 제외하고 싶은 경우 &(And) 연산을 통하여 해당 Bit가 동시에 켜져 있는 경우를 제외하였다. 다행히 해당 방법으로 간단히 문제를 해결 할 수 있었다.
  • 생각보다 문제는 쉽게 풀렸는데 역시나 제일 빠른 코드 대비 성능이 상당히 느리다. 본 문제는 분명히 수학적으로 쉽게 접근하는 방법이 있는 것 같다. 제일 빠른 답안의 경우 대략 1ms 이내에 결과를 계산하는 것 같다. 역시나 알고리즘을 잘하기 위해서는 수학적 지식이 많이 필요한 것 같다.

코드 (본 문제 부터는 코드를 Github에 업로드 할 계획입니다. 주소: https://github.com/mkblog-cokr/algorithmCode)

  • For Loop을 사용하여 모든 경우의 수를 계산하는 코드
  • 실행 시간: 167ms (제일 빠른 코드 대비 대략 167배 (1ms) 느림)

 

Leave a Reply

Your email address will not be published. Required fields are marked *