[Day-Warm-up] 손코딩과 알고리즘

CS-Basic 페이지 에 따라 어제(23일)과 오늘 학습의 일부를 정리용을 기록한다. 우선 9월 까지는 Warm-up 기간으로 생각하고 편안하게 임한다.

몸풀기로 ACM-ICPC의 기본문제 1000, 1001을 C++, Java, C로 처리했다.  풀었다고 하기 민망한 간단한 예제로, 온라인 저지를 어떻게 쓰는지 감을 익히는 정도라고 생각했다.

한 가지, Java로 구현할 때 IDE 도움 없이 손코딩 하면서 입력을 받기 위한 Scanner 클래스를 사용하자니 어떤 클래스를 import하는지 생각이 안났다. 확인하니 java.util.Scanner를 import해야 한다. 그동안 너무 IDE의 편한 인텔리센스 기능에만 의존한게 아닌가 생각이 든다. 어렵지 않으니 Java Scanner에 대해서 간단히 복습해 두자

문제 난이도가 번호 순으로 올라가겠지 하고 1002번을 이어서 시도했다. 문제의 핵심은 두 원을 교차하는 점의 개수를 구하는 것이라 파악은 했지만 끝내 어제와 오늘 일부의 시간을 할애하고도 풀지 못했다. ㅠㅠ;

처음에는 단순하게 두 원의 교차관계를 생각하고 “R-r < d < R + r” (여기서R,r은 서로 다른 두원의 반지름, R이 큰 값, d는 두 원의 중심 사이의 거리) 에 해당하면 2를 반환시키고, R+r =d 이면 1, 아니면 0을 반환시키는 단순한 코드를 작성했다. 그러나 당연히 실패!

좀 더 생각해 보니 두 원의 관계가 저렇게 단순한 경우만 있는 것이 아니라는 것을 알았고 위와 같은 방법으로는 문제를 풀 수 없다는 것을 깨달았다. 이 때부터 기나긴 삽질의 시작…

algorithm study

전략을 바꿔 두 원의 방정식을 가지고 근의 개수를 구하는 방법으로 변경했다. 그러나 여기서 새로 봉착한 장애물은 문제의 조건이 가로세로 좌표가 -10000에서 10000으로 제한되어 있다는 점이다. 결국 GG를 ㅠ

복잡한 심경에 바로 다음 문제 1003 도전. 피보나치 수열을 응용한 문제였다.  피보나치 수열을 재귀로 풀되 base 케이스가 되는 0 또는 1이 몇번 나오는지를 카운트하는 문제.

나 또한 재귀적으로 접근해서, 0과 1의 사용빈도를 보관할 변수를 전역변수로 두고서 함수가 재귀적으로 돌면서 0과 1이 나타나면 카운트를 올리게 해서 문제를 풀었다.

답은 맞았지만 개선의 여지가 없을까하고 다른 사람들의 답을 좀 뒤져보려고 했더니… 아하 여기에도 문제에 제약조건이 있었다. 입력 조건이 40이하였다. 그러고 보니 어떤 분이 아예 for문으로 40까지 다 계산하고 나서 입력에 맞는 값을 출력하는 방식으로 구현해 놓은 것을 확인했다.

어제와 오늘의 연습을 통해서 어떤 식으로 문제를 접근해야 할지 조금 감이 온다.

어제 저녁에 “알고리즘 문제 해결 전략” 첫부분을 읽으면서 문제풀이의 과정을 6단계로 설명한 것(23p)이 앞으로의 학습에 도움이 될 것 같다.

  1. 문제를 읽고 이해한다.
  2. 문제를 익숙한 용어로 재정의한다. (추상화)
  3. 어떻게 해결할지 계획을 세운다.
  4. 계획을 검증한다.
  5. 프로그램으로 구현한다.
  6. 어떻게 풀었는지 돌아보고, 개선할 방법이 있는지 찾아본다. (회고)