Daeseok's Blog

Algorithm 문제 풀기(TopCoder, Hackerrank)

 다양한 사이트에서 알고리즘 문제를 풀고 만들어진 코드를 github project 로 올리고 있다. 아직 많이는 풀지 못했지만,

언젠가는 다양한 문제를 많이 올릴 수 있기를...

https://github.com/SolvingProblems/Code4Algorithm/tree/master/Daeseok.Youn

[Google Codejam] Qualification Round 2014-Cookie Clicker Alpha

문제 link : https://code.google.com/codejam/contest/2974486/dashboard#s=p1

Magic Trick 에 이어 두번째 문제, Magic Trick 에 비하면 난이도가 있지만 쉬이 풀수 있는 문제이다.

이 문제의 결론은 X 값으로 주어진 cookie 의 개수를 가장 빠른 시간에 만들 수 있도록 하고 그 시간을 답으로 갖게 하는 것이다.

3 가지의 input 이 주어지는데,

C : farm 을 하나 만들 수 있는 cookie 의 개수

F : farm 하나 당 cookie 생산량

X : 최종으로 만들어야 하는 cookie 의 개수

문제의 link 를 보면 예제가 나와있다.

예제를 보면, 초기 cookie 생산량은 초당 "2" 이다.

가정 C = 500.0, F = 4.0, X = 2000.0

1. cookie 0개에서 부터 초당 2개씩 cookie 가 생산된다.

2. 250초 뒤에, 500개의 cookie 가 생산되고 farm 하나를 구입할 수 있다. 구입하게 되면 초당 4개의 cookie 를

생산하는 farm 을 만들 수 있다.

3. farm 을 하나 만들자. 그렇다면 보유하고 있던 cookie 의 개수는 0이 되고 초당 cookie 의 생산량은 6개가 된다.

4. 다음 farm 을 만들 수 있는 cookie 500개를 초당 6개씩 생산하였을 때, 83.3333333 초가 된다.

5. 83.333333 초 뒤에 farm 을 하나더 만들자. 그러면 다시 보유하고 있던 cookie 의 개수는 0이되고, 초당

10개의 cookie 생산량을 갖게된다.

6. 다음 farm 을 만들 수 있는 시간은 50초가 된다.

7. 3번째 farm 을 만들자. 다시 보유하고 있던 cookie 는 0이 되고, 생산량은 14개가 된다.

8. 생산량 14개에서 다음 farm 을 만들 필요는 없다. 왜냐 하면 이 이후의 생산량 증가는 2000개에 도달하는 시간이 점점 커진다. 이제 2000 개를 만들어 보자. 그러면 142.8571429 초가 걸린다.

총 시간은 250 + 83.3333333 + 50 + 142.8571429 = 526.1904762 초가 답이 된다.

앞서 쓴데로, C, F, X 가 input으로 주어지고 결과는 소수점 8자리에서 반올림하여 7자리를 만들면 된다.

중요한 점은,

farm 을 만들 것인지 만들지 않고 그냥 cookie 생산을 할 것인지 결정해야 하는 순간이 있다. 7번에서 8번으로 넘어갈때.

이것은 전 단계에서 X 까지 cookie 를 생산하여 걸린 시간과 현재 단계에서 farm 을 만들지 않고 cookie을 target 까지 생산한 값을 비교하여 전 단계에서 시간이 더 짧게 걸렸다면 farm을 만들지 않고 X 값까지 cookie 만든 시간을 return 하면 될 것이다.

코드를 보자.

def CalculateCookies(cookies, extra, target):
        cookieGen = 2 # default cookie
        if cookies > target:
                return target/cookieGen

        farmTime = 0.0
        prevEndTime = farmTime + target / cookieGen
        totalTimeFarm = 0.0

        while True:
                totalTimeFarm = totalTimeFarm + \
                                cookies / (cookieGen + extra * farmTime)
                farmTime = farmTime + 1.0
                currentEndTime = totalTimeFarm + \
                                 target / (cookieGen + extra * farmTime)

                if prevEndTime < currentEndTime:
                        break;
                prevEndTime = currentEndTime

        return prevEndTime

if __name__ == "__main__":
        testcases = input()
        for caseNr in xrange(1, testcases + 1):
                cookies, extra, target = map(float, raw_input().split())

                timeForCookies = CalculateCookies(cookies, extra, target)
                print "Case #%d: %.7f"% (caseNr, round(timeForCookies, 8))

코드가 간단하다. 계산만 잘하면 풀수 있는 문제일 것이다. 

[Google Codejam] Qualification Round 2014-Magic Trick

문제 link : https://code.google.com/codejam/contest/dashboard?c=2974486

Google Codejam 이 시작되었다. 참가는 하지 않았지만, 하나씩 풀어 보려고 노력중이다.

이 문제는 처음 시작하는 사람들에게 자신감을 줄 수 있는 문제가 아닌가 한다. :-)

문제의 내용을 요약하면,

마술사가 1~16까지의 수가 적힌 카드를 갖고 4X4 로 무작위(사실 마술사가 트릭을 쓴다는 내용이다. 실제 무작위가 아님)로 배열한뒤 지원자가 선택한 카드가 무엇인지 맞추는 문제이다.

Rule 과 함께 예제를 들면,

1. 마술사가 1~16 까지 숫자를 4X4로 놓는다.

1 2 3 4
5 6 7 8
9 10 11 12
13 14 15 16

2. 지원자가 원하는 숫자가 어느 열에 있는지 물어본다.

예를 들어 지원자는 7을 생각했고 마술사에게 "2"열이라고 답해준다.

3. 마술사가 카드를 썪어 다시 한번 놓게된다.

1 2 5 4
3 11 6 15
9 10 7 12
13 14 8 16

4. 그럼 지원자는 "3" 열이라고 마술사에게 얘길 하고, 마술사는 지원자가 생각한 숫자 7을 말해주면 된다.

이는 마술사가 1번째와 2번째 카드 배열시 "Trick"을 써 지원자의 생각한 숫자를 맞추는 것이다.

(이런걸 속을 수 있나.. 지원자도 말하면서 눈치를 챌듯..)

이렇게 정상적인 case 만 있는 것은 아니다. 지원자가 실제 위의 예제에서 마술사가 2번째로 카드를 배열했을 때

3열이라고 답해야 하지만, 2열이라고 답하게 되었다면 "Volunteer cheated!" 출력하고,

마술사가 2번째 배열에서 5,6,7,8 을 다른 열로 분리를 해야 하는데, 하나이상 같은 열에 놓게 되어 맞출수 없는 경우에는

"Bad magician!" 이라고 출력하면 이 문제는 완전히 풀수 있게 된다.

문제 link 를 가면, Sample case 가 잘 나와있다. 

일단 Google Codejam 은 input data file을 제공한다. 이 파일을 받아서 code의 input으로 사용하면된다.

input 파일의 한라인씩 읽는다고 했을때,

첫번째 배열에서 지원자가 말한 열(5, 6, 7, 8) 을 저장해놓고 다음 배열에서 말한 (9, 10, 7, 12)를 단순 비교한다

만약

1. 같은 숫자가 하나 라면, 그 값을 return 한다.

2. 같은 숫자가 2 이상 4 이하라면 "Bad magician!" 을 return 한다.

3. 같은 숫자가 하나도 없으면 "Volunteer cheated!" 를 return 한다.

끝.

파일을 첨부하는데 문제가 있어, code를 붙여 넣는다.

def checkCards(first, second):
    sameCount = 0
    sameNum = ""

    for num in range(0, len(first)):
        for snum in range(0, len(second)):
            if first[num] == second[snum]:
                sameCount = sameCount + 1
                sameNum = first[num]

    if sameCount == 1:
        return sameNum
    elif sameCount > 1 and sameCount <= 4:
        return "Bad magician!"
    elif sameCount == 0:
        return "Volunteer cheated!"

    # never reach hear with data from codejam
    return "error"

if __name__ == "__main__":
    testcases = input()
    LineOfCardsFirst = []
    LineOfCardsSeconds = []
    for caseNr in xrange(1, testcases + 1):
        for num in range(0,2):
            selectRow = raw_input()
            #print "selected Row : ", selectRow
            for row in xrange(0, 4):
                if row == int(selectRow) - 1:
                    if (num == 0):
                        LineOfCardsFirst = map(int, raw_input().split())
                        #print "LineOfCards : ", LineOfCardsFirst
                    else:
                        LineOfCardsSeconds = map(int, raw_input().split())
                        #print "LineOfCards : ", LineOfCardsSeconds
                else:
                    raw_input()
 

[Algorithm] Python 배우기

CodeChef, TopCoder, Google Codejam 등 Algorithm Contest 를 하는 site 들이 많다. 내 개인적인 생각으로는 앞서 말한 세개의 site 에서 제공하는 문제를 푸는 것에 있어 언어(C++, Java, Python 등)가 그렇게 중요하진 않다고 생각한다.

그래서 제가 선택한 것은 Python. 아주 배우기도 좋고 Algorithm 문제를 푸는데 적합한(물론 C++/JAVA 도 괜찮다-개인적인 생각이다.) 언어인 것 같아 선택했다. Python는 CodeChef 와 Google Codejam 에서는 지원을 하고 있고, 내가 덤벼볼수 있는 초급문제가 많은 CodeChef 에서도 Python 의 기본적인 function 으로 풀 수 있다. 

하지만 python 도 따로 배우긴 해야한다. 다른 C++ 이나 JAVA를 다루어 보았다면 쉽게 접근하고 사용할 수 있을 것이다. 그리고 python 에서 제공되는 함수의 기능으로 검색하면 왠만큼 나온다. ^^

그래서 python 을 배우기 위한 추천하는 site는 http://www.learnstreet.com 이다.

browser 내에서 python code를 입력해보고 결과를 다 확인 할 수 있다는 장점이 있다. 

(eclipse, python 설치등이 필요없다!!)

어떻게 사용하는지 알아보자. 아래의 이미지가 너무 작아 세세히 보이지 않는다면 클릭하여 크게 보도록 합니다.

1. site 에 진입한다. Click ==> learnstreet

맛보기만 하려면 가입할 필요없지만, 끝까지 한번 해보고 어디까지 했는지 기록을 다 남기려면 가입하는 것이 좋다. 물론 가입은 Google/Facebook 등의 계정이 있다면 클릭 한번에 가입이 가능하다.

2. 가입

메인 페이지의 오른쪽 상단에 Sign in / Sign up 이 있다 아무거나 클릭해도 같은 page가 나온다.

난 Google 계정으로 로그인했다.

3. 배우려는 언어 선택

오른쪽 상단 로고 옆 "Courses" 를 클릭한다. 이사이트는 JavaScript/Python/Ruby 언어를 지원한다.

그중 Python을 선택해보자

4. Emulator(?) 같은 녀석이 나온다. 

시작한다고 얘기해주면서 화면 구성에 대한 설명을 해준다. (Next 를 눌러주자.)

설명을 차근차근 읽어보고 마지막 설명에서 Next 버튼이 비활성화 되면 Close 를 눌러주자.

5. 이제 하나씩 시키는 대로 풀어보자.

하나만 풀어보자. 오른쪽 까만 화면에 어떻게 하라고 지시가 나온다. 시키는대로 하나씩 하면 된다.

아래의 그림에서는 interpreter에 "Python" 이라고 입력해봐 라는 지시였고 그렇게 하면 바로 다음 문제가 나온다.

총 course 는 아래와 같다.

위의 course 대로 다 하게 되면 기본적인 것은 다룰 수 있다.

이렇게만 끝나는 site라면 추천하지 않는다. 간단한 project 를 할 수 있도록 도와준다.

왼쪽 상단 LearnStreet 오른쪽에 "Project"라는 탭으로 진입한다.

그러면 아래처럼 간단한 project 들이 보인다.

여기에 나오는 project 는 학습을 위한 것이다. code를 작성하고 수행하면 이미지에 반영이 되는 재미를 더해 집중을 할 수 있도록 만들어준다. 

이중 하나를 풀어보자.

나는 Project : Number Converter 라는 것을 선택했다.

시작 화면

이 project의 설명이 나온다. 설명을 보면 숫자를 입력했을 때 숫자를 로마자로 변경하는 것이다.(주어진 룰대로)

Start를 클릭하면

오른쪽 소스 view에 layout 이 나오고 이 함수내에 code를 구현하고 소스 view 왼쪽 하단에 "Run" 을 수행해주면 된다. (소스의 layout인 함수 내부에만 구현해서 원하는 값을 return 해주는 구조로 작성하면 된다.)

Course 를 잘 진행했다면 이것도 진행하는데 무리가 없을 것으로 생각된다.

완성이 되어 수행하면, 왼쪽화면에 결과를 알수 있도록 숫자를 입력하고 로마자로 변경(Convert 화살표 클릭)이 완료되면 OK

이런식으로 하나씩 하다보면 어느새 시간은 훌쩍지나 있고 기본기를 어느 정도 닦을 수 있다.

그리고 하는 과정에서 바로 입력하고 Run 수행하고 이것을 반복하는 것보다 소스 view 하단에 있는 "Scratchpad" 를 실행해서 소스를 작성하고 작성된 소스를 선 검토하는 것이 좋다. 

물론 Scratchpad는 함수 구현 및 호출부까지 작성해야 한다. 아래의 "scratchpad" 로 이동한 모습.

오른쪽 view에서 interpreter 로 바로 이용할 수 있고, 오른쪽에서 python으로 작성 후 사이에 있는 "체크"버트을 클리하면 interpreter console에서 결과를 알수 있는 구조이다. 

최대한 자세히 쓴다고 했으나 부족한 부분이 있을 수 있을 것이다. 어렵지 안은 UX 이니 차근차근 진행하시면 된다.  그다음 level 에 대한 내용은 좋은 방법이 있다면 포스팅을 할 것이다.

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분정도면 충분히 풀수 있을 것으로 본다. 하나씩 풀고 공유할 알고리즘이 있다면 써보도록 하겠다.