밝은 미래

2012년 code jam round 1A를 읽고 문제 풀이에 대해 생각 까지만 해본 내용들 정리.

http://code.google.com/codejam/contest/1645485/dashboard

Problem A. Password Problem

password를 typing 하다가 말고, 아 틀렸나? 하고 생각이 들 때,

1. 계속 typing을 하는 것이 낫나

2. 지우고 typing을 하는 것이 낫나

3. enter 쳐버리고, 처음부터 다시 typing하는 것이 낫나

기대값을 구하기.

첫 번째 문제라서 그나마 쉬운 편이다. 알고리즘이랄 것이 많이 없고, 구현만 잘하면 된다. 내가 구현하면 2.5시간 쯤 걸릴 것 같다. ^^;;

문제 examples에서 계산 방법을 다 설명으로 써놨더라고.

그런데, 막상 구현을 하다보면 막힐 수도 있다. 경우의 수에 따라서 probability와 keystrokes 값을 각각 구해야 하는데, 이 경우들을 어떻게 정의해야 좋을지 막막할 수 있다.

막연히 다차원 배열로 생각하자면, 이미 입력한 keystrokes 개수에 따라서 차원이 마구 늘어나니 힘들다.

1차원 배열이라고 생각하되, 각 경우의 수에 맞는 값을 하나씩 정의하는 것이 좋겠다. 그렇다면, 각 경우의 수를 어떻게 나열하느냐가 관건인데, 각자 프로그래밍 하기 좋은 방법으로 한 가지 원칙을 설정해서 나열하면 되겠다.

그 중 가장 이해가 잘 가는 방법은 2진수를 그대로 사용하는 것이다. keystrokes가 맞는지 안맞는지를 각 자릿수 bit로 생각하면, 2^n만큼 숫자의 2진수 안에 빼곡히 index를 채워넣을 수 있다.

index를 정의했다고 해서 배열을 사용하면 large input 은 통과할 수가 없다. small input은 통과하게 해놨나보다.

배열을 만들어두지 않고, 각 경우의 값을 dynamic하게 계산하는 것이 좋겠다.

계산하는 것도 모든 index에 대해서 계산하면 large input을 통과할 수가 없다. 시간이 부족해서.

겹치는 것들은 한 번씩만 계산한다.

probability를 계산할 때는 1 bit의 개수가 동일한 것들에 대해서 한 번씩만 계산한다. 이건 어떻게 알아내지? bit를 shift해가면서 세야 하나?

keep typing 하는 경우에 대한 keystrokes 계산은 특정 2^n-1 숫자보다 큰 경우와 그렇지 않은 경우로 나눠서 한 번씩만 계산한다.

m번 backspace 하는 경우 계산은 2^n-1보다 작은 경우와 그렇지 않은 경우로 나눠서 한 번씩만 계산한다.

2진수 계산 연습과 확률 계산 연습을 조금씩 해 놓으면 좋겠다.

한편, google solution에는 엄청 간단한 수식으로 풀 수 있다고 써 있는 것 같다. ^^;;

Problem B. Kingdom Rush

다음 문제도 크게 어렵지는 않을 것 같다. 내가 구현하면 2+2시간은 걸리겠지만 ㅋㅋ.

greedy한 방법으로 풀면 되지 않을까 생각한다. 그렇게 해봐서 안되면 망하는 거고.

무조건 별점 2개짜리 먹기부터 다 채운다. 가능한 것부터 아무거나.

끝나면, 별점 1개짜리 중 먹을 수 있는 것을 먹어본다.

계속 반복해도 도달할 수 없는 것이 없게 되면 Too bad.

나중에 google solution을 봤더니, 다행히 greedy algorithm으로 푸는 게 맞다고 하네. ㅎㅎ.

그렇다면야, 2시간이면 풀 수도 있었겠다.

Problem C. Cruise Control

이 문제 풀이 방법까지는 생각도 못했다. 

나는 문제를 읽는 것도 하나 당 15분 이상씩 걸리고, input, output 처리만 1시간은 걸리는데, 문제를 15분 만에 푸는 괴물들은 도대체 뭐지..

이건 풀기를 시도하더라도 생각해야 할 조건도 종종 생길 것 같다. 차 길이 등.

동시에 같은 거리에 2개 이상의 차가 없는지만 계산하는 방법이 있겠다. 

1초마다 모든 차를 이동해가면서 simulation해봐도 small input은 풀 수 있을지도 모르겠다. 보장 못하지.

simulation하는 경우는 backtracking까지 하는 거면 더 어렵겠다. 차가 모두 앞으로 등속이동을 하니, backtracking이 필요 없을 것 같기도 하다. 딱 한 경우만 나오겠네.

차 3개씩의 모든 set에 대해서 같은 시각에 같은 위치에 있는지를 검사해볼 수도 있겠다. large input까지는 안되겠지?

google solution 을 읽다가 깨달았는데, 차가 추월할 때, 옆으로 순식간에 이동하더라도 그 순간 양측에 차가 없어야 된다는 조건을 구현에 넣기가 쉽지 않았을 것 같다.

아, 해설도 열라 기네. 해설을 읽고 풀으라고 해도 5시간 이상 걸리겠다.

영어 공부부터 해야 할 판.

http://project.oss.kr/sub01/sub01.php

중간 혜택도 많아지고 있다.

전체참가자
  · KT에서 참가하는 모든 팀에게 개발기간동안 ucloud Sever 무료 지원
  · 기술력 향상을 위한 기술세미나, 멘토링 등 개발자대회에서 진행하는 모든행사에 참여 기회 부여
   (전액 무료 지원)
  · 공개SW역량프라자에서 프로그램 개발을 위한 기술테스트 및 라이선스 검증 지원
  · 회의 및 개발공간 지원
  · 산출물 접수팀에게는 정보통신산업진흥원장 명의의 2012 공개SW개발자대회 참가확인증 부여

국제부문은 해외 거주 외국인만 되나보다.

국제부문

시상 전체

접기

일반부문

등    급		학생 부문				일반 부문
		지정과제		자유과제		지정과제		자유과제
		팀수	부상	팀수	부상	팀수	부상	팀수	부상
대상	지식경제부 장관상	1팀 1000만원				1팀 1000만원
금상	정보통신산업 진흥원장상	1	500만원	1	500만원	1	500만원	1	500만원
은상	한국공개SW협회 협회장상	1	300만원	1	300만원	1	300만원	1	300만원
동상	기업상	4	200만원 이하현물	4	200만원 이하현물	4	200만원 이하현물	4	200만원 이하현물
KT ucloud상		1팀 700만원

베스트업그레이드부문

등    급	팀    수	부    상
정보통신산업진흥원장상	1	500만원

활용부문

등    급		팀    수	부    상
대상	지식경제부 장관상	1	상패
금상	정보통신산업진흥원 원장상(개인)	1	300만원
	정보통신산업진흥원 원장상(기업)	1	상패

국제부문

등    급		팀    수	부    상
대상	지식경제부 장관상	1	USD 8,000
금상	정보통신산업진흥원 원장상	1	USD 5,000
은상	한국공개SW협회장상	1	USD 3,000

 

접기

itunesu 에서 받아볼 수 있었는데, dvd highlights 만 담겨 있는 거였다.

전체는 책을 사야 볼 수 있나?

Brain Rules: DVD Highlights 25:22 10. 5. 13. Medina, John Seattle Pacific University Course - Group - Brain Rules: DVD Highlights - Seattle Pacific University > Brain Rules > Brain Rules: DVD Highlights

제목이 수업 제목 같아서 받았는데,

공부하기에 안좋은 영상이어서 지우기.

이제 UC Davis, Imperial College London 공식 영상은 받지 말아야지.

Neuroscience UC Davis Neuroscience http://deimos3.apple.com/WebObjects/Core.woa/Feed/ucdavis-public-dz.4554663396.04554663398

The Cell Imperial College London A podcast series on The Cell http://deimos3.apple.com/WebObjects/Core.woa/Feed/imperial-ac-uk-public-dz.5939022047.05939022049