CodeChef
Alogrithm 연습을 위한 site 를 소개하려 한다.
어쩌다 Google Codejam 을 알게 되었는데, 문제를 몇개 열어 풀어보려고 시도를 했지만 어떻게 접근을 해야 하는지 조차 생각해내지 못해 좌절(?)을 맞게 되었다. 그래서 여기저기 Community 도 돌아다녀보며 사람들이 어떻게 이런 Competition을 준비하는지에 대한 내용을 보게 되었다. 그 중 TopCoder 라는 곳을 먼저 알게되었는데, 오래동안 준비해왔던 단체라 볼 수 있는 자료도 많고 java applet 을 통해 Web 환경에서 algorithm test 를 할 수 있도록 만들어 놓았다.(나중에 posting 하겠다.) 하지만 단점이라고 굳이 짚자면 지원되는 language 가 4개 밖엔 없었고(C++, java, C#, Visual basic) 내가 하고 싶어한 python은 아직 준비중이 었던 것이다. 또 하나는 algorithm 문제를 쉬운 것, 혹은 어려운 것만 모아 두지 않아 찾아보고 할만한 것(?)만 시도 해봐야 하는 것이다. 이 사이트도 나중에 도전을 해봐야 겠지만 지금은 조금 무리인 듯 해서 다른 site 를 찾던 중에 CodeChef를 찾은 것이다.
URL : http://ww2.codechef.com
이 사이트의 가장 큰 장점은 다양한 language 를 지원하는 것과 나이도별(easy, medium, hard, challenge, peer) 문제를 모아둔 것이다. 물론 Algorithm test 중 과정에서 실패한 항목에 대한 출력을 안해준다는 것이다. 그래서 내가 어떤 input 값에 대한 output 이 잘못되었는지 스스로 확인해봐야 하는 것이 문제이다.(TopCoder 는 이런 것들을 확인해준다)
하는 방법은 간단하다.
1. Site 에 접속하여 가입을 한다.
- 가입 후 확인 메일이 오는데, 확인 메일에서 link를 따라가면 password 를 설정 할 수 있다.
- 또한 facebook 계정과 연동이 되어 그냥 해도 될 듯 했지만 연동하지 않았다.
가입이 완료 되었다면,
2. Practice ==> Easy 문제를 보자
위 그림에서 박스로 되어 있는 부분으로 가서 "Easy" 클릭
3. 진입
이와 같이 문제와 Sucessful Submission 개수 및 정확도 등을 보여준다. 맨 위에 있는 문제는 "Easy" 중에서도 어려운 문제인 듯 하다. 푼사람이 많지 않으니.. ㅎㅎ
그래서 맨 아래에서 부터 풀어 올라와면 좋을 듯!!!
4. 한문제를 풀어보자.(미리 풀어봤으니)
Holes in the Text 라는 주제의 문제를 풀어보자(아래에서 7번째에 있다. )
물론 영어라는 압박(?) 있지만 걱정말자 Example 만 잘 보면 그냥 문제의 의도를 알수도 있다. 아니면 이 문제의 답변글을 살펴 보셔도..
암튼 문제를 간단히 요약하면 주어진 문자열에 영문자(대문자만)에 있는 구멍(?)의 개수가 몇개인지 찾는 문제이다.
(예를 들어 "A" 는 구멍이 1개, "B" 는 2개, C, E, F 이런 녀석은 구멍이 없는 문자다)
Example로 나온 "CODECHEF" 는 구멍이 "O"와 "D" 에 하나씩 2개가 있는 것이다.
사실 이런 문제는 문자가 구멍이 몇개 있을 것이라는 규칙 같은 것이 없다.(Table 을 만들어 줘야 할 것이다.)
5. 내 개인 컴퓨터로 문제를 열심히 풀어 Example에 나온 input 과 output 에 맞도록 작성한다.
(Python으로)
alphaHoles에 A~Z 순서로 hole의 개수를 미리 적어 놓는다.
그리고 input으로 들어오는 문자열에서 문자를 하나씩 꺼내 'A' ascii 값을 빼준다.(65) 그렇게 되면 정확히 alphaholes table에 각 문자에 맞는 hole 개수 값을 갖고 올 수 있다. 그리고 다 더 해서 출력해주면 끝~
6. code를 만들었으니 확인해봐야 겠다.
문제 아래를 보면, "SUBMIT" 이라는 버튼이 있다. 클릭하자
(SUBMIT 버튼 위에 보면 지원되는 language 와 Time limit 같은 것은 확인하자.)
SUBMIT 을 click 하면,
위에서 처럼 창이 뜬다 여기에 code를 넣고 맨아래 Submit 을 클릭하면 되는데 그전에 자신이 사용할 language를 선택해야 한다. python을 선택하고 code를 넣겠다.
위에 처럼 code를 붙여 놓고 맨아래의 submit button을 클릭하면 된다. 그럼 progressbar 가 나오고 정상적으로 완료되면 Accept 가 되는 것이다.(이미 submit을 한번 했으므로 이 화면은 제외하겠다.)
그리고 나중에 나의 Code를 다시 보려면,
문제 제목 옆에 보면 "MY SUBMISSIONS" 라는 버튼이 있다. 클릭하면 내가 했던 Submit 을 모두 볼수 있다(한번에 성공했다면 하나밖에 없겠지만 여러번 했던 경우에 모두 볼 수 있을 것이다.)
미리 code test를 local에서 하고 넣는 것이라 compile 오류는 없겠지만 대게 Time limitation에서 걸린다. 시간을 짧게 요하는데 빨리 끊내지 못하고 시간을 끌면 Fail 난다.
이런 식으로 하나씩 하면 된다. 물론 막히거나 어려운 점이 있을 것으로 예상된다. 그렇다면 다른 사람이 이미 성공한 소스를 참조를 해보자. 다른 사람 소스에 너무 의존하는 것보다 자신이 하는 것이 좋지만 너무 어렵다면 참조를 하는 것도 좋을 듯하다. 문제가 많으니 처음엔 참조하더라도 나중에는 그냥 쉽게 풀수 있지않을까 한다.
내가 10개정도 풀었는데 Easy 문제는 10~20분정도면 충분히 풀수 있을 것으로 본다. 하나씩 풀고 공유할 알고리즘이 있다면 써보도록 하겠다.