밝은 미래

 

 

http://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-046j-introduction-to-algorithms-sma-5503-fall-2005/video-lectures/

 

http://en.wikipedia.org/wiki/Interval_tree

 

 

 

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시간 이상 걸리겠다.

영어 공부부터 해야 할 판.

이런 대회에 참가하려면 미리 준비해둘 것이 있다.
이왕이면 착실하게 준비해보면 좋겠다.
1.5년 동안 반절 만들고,
다음 1.5년 간 나머지를 만들어야지.
공부는 별개로 skiena 강의를 보면서 해야겠다.
 

1년 안에
general input parser tool 을 만들어야겠다.
grammar를 입력하면 data를 import해주는 tool

언어는 뭘로 선택할까
잘 통용되는 것은 java이겠다.
언젠가, ruby interpreter를 공부할 꺼라면, ruby를 공부해보는 것도 좋겠지만, 저 위 준비물을 다 만들 자신이 없네.
그리고, ruby 등은 통용이 안될 때도 있다.
중간 결과를 조작할 수 있는 interpret 언어가 좋기는 하겠는뎅.

합격점이 35점밖에 안됐었는데, 그것도 모르고 너무 무리했었다.
보통의 algorithms도 large input도 엄청 빨리 실행할 수 있는데, 그것도 모르고 너무 무리했었다.
괜히 위축돼 있었네.

http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=29&page=show_problem&problem=36
에는 설명이 좀 있네.

그런데, 결국 실패했다.
program judge 입맛을 맞춰주고 싶지도 않다.
지금 정석으로 나가기에는 시간이 아까워..

이것 저것 다 시도해보다가 code만 섞였다. c로 썼다가, c++로 썼다가..

lec02 동영상을 41분 봐도 도움되는 말은 "큰 수, 작은 수" 순서 case를 조심하라는 말밖에 안나온다.

계속 틀렸다는 메시지만 받으니, optimize하고 싶지도 않다 T_T

// PcSkienaTry.cpp : 콘솔 응용 프로그램에 대한 진입점을 정의합니다.
//

//#include "stdafx.h"
//
//
//int _tmain(int argc, _TCHAR* argv[])
//{
// return 0;
//}

#include <iostream>

int CalculateCycle(int nStart)
{
 long long i = nStart;
 long long nCycle = 0;

 while (i > 1)
 {
  if (i % 2 != 0)
   i = i * 3 + 1;
  else
   i /= 2;

  nCycle++;
 }

 return nCycle+1;
}

int main()
{
 long long nFrom, nTo;
 long long i = 0;

 while ( std::cin >> nFrom >> nTo
  )
 {
  long long nCycle = 0;
  long long nMaxCycle = 0;

  unsigned long int nStart = 0;
  unsigned long int nEnd = 0;

  if (nFrom < nTo)
  {
   nStart = nFrom;
   nEnd = nTo;
  }
  else
  {
   nStart = nTo;
   nEnd = nFrom;
  }

  long long i = nStart;
  for (; i <= nEnd; i++)
  {
   nCycle = CalculateCycle(i);
   if (nCycle > nMaxCycle)
    nMaxCycle = nCycle;
  }

  

  std::cout << nStart << " " << nEnd << " " << nMaxCycle << std::endl;
 }

 return 0;
}

 

Programming Challenges 사이트는 다음과 같습니다.

http://www.programming-challenges.com

UVa 사이트는 다음과 같습니다.

http://uva.onlinejudge.org