Facebook Hacker Cup 2015 Round 1

우리나라 시간으로 2015년 1월 18일 (일) 새벽 3시부터 라운드1이 열렸다.

예선에서 한 문제를 맞춰 라운드1에 왔다. 빨리 푸는 순서로 다음라운드로 올라가는줄 알고 새벽 3시에 일어날 생각하고 있었는데

다행히 순위 관계없이 동점자 모두 진출 규칙이라 아침에 일어났다. 

바로 카페로 가서 풀이 시작.. 한 문제라도 풀 수 있을까? 걱정했지만 생각보다 많이 풀렸다.

1. Homework

주어진 숫자 범위 내에 정해진 소수 갯수를 약수로 갖는 숫자가 몇 개인지를 판단하는 문제다.

결국 소수 구하는 문제인데 입력 크기를 보면 그때 그때 구하는건 무리다. 

조건에 맞게 캐시를 만들어놓고 계속 캐시를 이용하도록 했다.

관련 알고리즘: 아리스토테네스의 체

코드: https://github.com/xgate/competition/blob/master/hackercup/2015/R1/Homework.cpp

2. Autocomplete

사전에 입력하고 찾고, 그 다음 단어 입력하고 찾고 하는 방식으로 자동완성 시키는 기능을 구현하란다.

사전에 단어들은 하나씩 추가 되므로 입력이 늘어날 수록 후보군이 많아지게 된다.

입력크기도 상당하기 때문에 모든 문자열을 들고 있기에는 힘겨워보였다.

결국 알파벳을 하나씩 물고 트리구조를 가지는, 이 문제에 적합한 트라이를 만들어 풀었다. 

최대길이 문자열도 처리가 가능할지 해봤는데 에러없이 통과해서 바로 서밋!

관련 알고리즘: Trie

코드: https://github.com/xgate/competition/blob/master/hackercup/2015/R1/Autocomplete.cpp

3. Winning at Sports

stress free / stress full 두 가지 승리조건이 존재한다.

stress free: 내가 항상 이기다가 결국 이긴다.

stress full: 상대가 최종득점에 도달하기 전까지는 내가 앞서갈 수 없다.

모든 경우의 수를 다 따져보자니 막막하다.

모든 경우의 수, 그 중 겹치는게 있지 않을까? 그래서 메모리를 사용하기로 했다. 

dp[승점][실점] = dp[승점-1][실점] + dp[승점][실점-1]

관련 알고리즘: 동적계획법

코드: https://github.com/xgate/competition/blob/master/hackercup/2015/R1/Winning.cpp

4. Corporate Gifting

매니저가 받은 선물을 상사에게 선물할 수 없는 조건으로 모든 선물 비용을 구하는 문제.

사실 해결책이 잘 생각나지 않아서 패스했다. 밤도 늦었고.. 

최종 스코어는 이렇게..

75점 이상만 라운드2로 올라갈 수 있어서 이번에는 여기까지..

다음에는 라운드2까지 가보고싶다.

라운드1 문제

https://www.facebook.com/hackercup/problems.php?round=344496159068801

문제풀이

https://www.facebook.com/notes/1047761065239794