처음에는 매우 충격적이었으나,


처음에는 매우 충격적이었으나,
점점 볼 영화가 별로 없다는 것을 알게 되고…
결국은 해지…
한국에서 정식 서비스 안해서 이리저리 불편하게 봐야한다는 점과, (적절한) 컨텐츠의 부재가 해지를 결정하게 됐다.
그래도 사용해 본 것이 돈이 아쉽거나 하진 않았음으로 성공적인 경험..

토요일 근황

오랜만에 토요일을 알차게 보낸 관계로 글을 남겨본다.

7시 기상

그래. 아무리 주말이라고 해도 늦어도 이 시간에는 눈이 떠진다.
오늘은 민지 결혼식이 있는 날이고, 구글 코드잼 날이기도 하네.
8시까지 코드잼 준비나 하고 있으면 되겠다.

8시 코드잼 시작

ㅎㅎ 드디어 시작이다. 등록하고 1달정도 기다린 것 같긴 한데~,
우선 문제는 총 4개고 1번은 연습문제인지, large셋이 별도로 없다.
ㅇㅋ!
40분동안 2번 문제까지 해결.
3번 문제 풀어야지.

9시 아이들 기상.

집이 시끄러워진다. 아...정말..집중이 안되는구만..
와이프가 애들이랑 뽀로로파크에 가잔다......
시간을 계산해본다. 뽀로로파크 2시간, 점심 1시간 왕복 40분.
약 4시간 정도 걸릴 것 같고, 이 정도면 10시에 출발하면 결혼식에 늦지 않고
다녀올 수 있을 것 같다. 콜.
아이들 준비시켜달라고 하고, 나는 3번 문제 마무리..
3번 문제까지 풀면 우선 다음 라운드는 넘어가니까, 3번까지 풀면 오늘 하루 편하게 살겠다.

10시 3번 문제 못풀다.

아아..어떤 예제 케이스가 안되는지 잘 모르겠다.
게다가 뽀로로파크를 더 늦게 갔다가는 결혼식도 못가겠다.
우선은 여기서 접고 뽀로로파크로 이동.

12시반 뽀로로파크에서 탈출

공연 1개, 마술쑈 및 비누방울 1개, 뽀로로 기차, 그리고 볼풀장에서 놀다보니 2시간이 휙 지나갔다.
다행히 아이들은 뽀로로파크에서 나올 생각인데, 허기져한다. 아침도 제대로 안먹고 오전부터 놀아댔으니
당연히 그러겠지. 밥 먹으러 식당으로 고고..

1시반 식사를 마치고 집으로.

아이들과 와이프를 먹이고, 정리하고 나오니 1시반이다.
다행히 아이 둘 다 집으로 이동하는 차에서 골아떨어졌다.
그나마 마음 편하게 집을 떠날 수 있겠군.
아이들을 침대에 눕히고 서울로 이동.

2시50분 결혼식장으로..

연구실 사람들로부터 전화가 오기 시작한다.
주말이라서 그런지 생각보다 길이 막힌다. 그래도 티맵 덕분에 일찍 온 것 같기도 하다.
오랜만에 만난 반가운 사람들, 옛 모임의 경조사는 이런 점이 좋다.
이럴 때 아니면 한 자리에게 모이기가 쉽지 않으니까..
다들 한 해 한 해 지나면서 조금씩 바뀌는 것이 보인다. 좋은 부분도 있고 아쉬운 부분도 있고..

5시 다시 집으로..

역시 집으로 가는 길도 막힌다. 티맵이 이번에는 또 다른 길을 알려준다.
원래 가던 길이 그만큼 막히겠거니...하고 알려주는대로 간다.
오고 가는 길이 다 다르다보니, 티맵이 맞을까라는 생각도 든다.
티맵에 대한 신앙심이 약해진 모양이다.
그래도 아직까진 그가 알려주는대로 행동해본다.
집까지 50분 걸림.

6시 다시 코딩.

3번 문제를 풀다가 갔었으니, 다시 들어가본다.
음. 3번 문제의 제출율보다 4번 문제의 제출율이 더 높다.
방향 선회해서 4번 문제에 도전한다. 1, 2, 4 번 문제의 제출율이 약 90% 정도 된다.
헐, 얼핏봐도 80%는 통과하겠다 싶다.
광성 주임이 다 통과한다는 이야기가 뻥이 하나도 안섞인 것이구나...라는 생각을 해본다.

6시 20분 무한도전 한다.

토요일은 무한도전 봐야지.
재미있다.!! 레이싱이라니..난 게임으로 밖에 해본적이 없지만, 분명히 매력적인 활동이다.
기회가 되면 정말 리얼한 게임을 해보고 싶다. 실제 해보고 싶진 않고..

8시 다시 코딩.

문제 해법이 틀린 경우는 디버깅하기도 쉽지 않다. 게다가 지금처럼 답이 주어지지 않았을 경우는 더욱 더.
incorrect가 뜰 때마다 다시 해법을 돌아본다. 내가 지금 맞게 풀고 있는건가..?
3-4번의 문제 해법을 변경해서 겨우 correct 휴..이제 3번만 남은 건데....
3번 안풀어도 우선은 통과니 쉬어볼까?

10시 탑코더 오픈 등록

지난주에 했어야 했는데 갑작스러운 서버 다운으로 연기된 탑코더 오픈을 등록했다.
선착순 2500명이니까, 10시부터 등록 시간 맞추어 등록을 한다.
이제 1시까지 잘 버티면 되겠네...

다음날 4시

잠들었다. ;;;; 아.....허무하네.....
어제 너무 빡센 하루를 보내서 그런가..
어제 있었던 일 정리나 해야지.. 하면서 지금 글을 쓰고 있다.

글을 쓰면서도 탑코더 오픈 참가하지 못한 것이 못내 아쉽다.

Code Review 교육을 들으면서

원래 교육을 듣는 취지는..

올해의 첫 교육을 들었다. 작년과 달리 (작년에는 상반기에 있는 교육을 말도 안되는 이유로 못가고, 하반기에는 일에 치어서 못가고) 상반기 교육을 듣게 되었다.
소속 팀이 변경된 점이 가장 크지 않을까 생각한다. 작년에는 정말 말도 안되게 작은 데모 가지고 못갔는데...
올해의 목표 중에 하나를 프로그래밍 스킬 향상에 두었기 때문에 교육도 관련 교육으로 채웠다.
사실 전공과 관련된 것은 거의 세미나 형식밖에는 안되고, 그걸로 현업에 크게 도움도 안되서 전공 외의 축을 만들었다.
남들은, 프로그래밍은 어짜피 그거 잘하는 사람들이 하면 되고, 너는 이론이나 신경쓰라고 하지만...
그렇게 하기에 주변에 프로그래밍 잘하는 사람이 존재하는 것도 아니라서;;;; (그런 이야기를 할 때는 적어도 그런 지원이 많던가..ㅎㅎ)
그리하여 프로그래밍 교육을 받으러 갔다. 그것도 코드 리뷰..
사실 말로만 들으면 코드 리뷰는 특별한게 하나도 없다. 코드 적용하기 전에 리뷰를 잘 보자. 그래야 코드도 좀 정리가 되고 버그도 없지 않겠냐는..
지극히 당연한 이야기지만, 지극히 지켜지지 않는 부분에 대한 교육이었다.

생각보다 얻는게 많았던 교육

교육은 왜 코드 리뷰를 해야하는가 부터 시작해서 실제 코드 리뷰 사례
코드 리뷰 시스템등에 대한 소개가 있었다. 처음에는 익숙한 이야기들이었지만, 뒤로 갈수록 실습이 많아서 좋았다.
몇몇 분들은 교육을 쉬는 시간으로 여기지만 그러지 못하도록 실습이 있는 것이 얼마나 좋았는지..
관련된 내용으로 2개의 실습이 있었다.
1. 짝 프로그래밍
짝 프로그래밍은 두 명이서 페어가 되어, 한 명은 드라이버, 한 명은 네비게이터가 되어서 문제를 해결하는 것인데,
시간을 정해놓고 역할을 바꿔가면서 진행을 했다. 문제는 스파이럴 박스...그림이 durl 처럼 숫자를 배열할 예정인데,
좌측상단에서부터 시작을 하며 1부터 숫자를 증가시키면서 주어진 박스 사이즈에 맞게끔 만들면 된다. 여기에 추가로 X라는 포인트들이 주어지는데, 이 점은 만나면 방향을 시계방향으로 꺾어서 진행하는 것으로 제약한다.
뭐 말로 하니까 역시 쉽지 않군..
암튼, 방향 설정과, 갈 수 있는데까지 가보기, 두개를 묶어서 재귀로 돌렸다. 문제는 이 것을 두 명이 공유를 하면서
코딩을 해야 하는데, 같이 짝이 된 분은 이런 프로그래밍이 익숙치 않은 분이어서, 생각을 공유하는데 많은 시간이 걸렸다.
2. 팀 프로젝트
팀 프로젝트로는 워드 카운트를 짜는 거였다. 8천라인의 영어 소설이 주어지고, 이를 알아서 파싱해서
알아서 카운트 하고 알아서 출력까지...1초 안에
이번에는 짝 프로그래밍을 했던 페어 2개를 묶어서 팀으로 만들었다.
git/gerrit 연습을 위해서 진행한 프로젝트긴 한데, 뭐 머지할 때, 생각해서 업무를 나누었다.
우선 입출력 / 저장하는 부분...가만..입력이야 워드 단위로 받는다 하더라도 출력하는 부분은
저장할 때 자료구조를 어떤 것을 쓰느냐에 따라서 다르겠구나?
그럼 이것도 저장하는 부분에서 잡아줘야겠네..
그래서 약간 불균등하게 업무 배분이 되었지만, 입력 / 저장, 출력으로 나뉘었다.
당연히 나는 저장, 출력 부분...을 맡았다. 아무도 안맡으려고 한 것도 있고;;
딱히 어려울 것 같지도 않아서...
어라? STL을 쓰면 안된다고?;; 이러면 이야기가 달라지는데...
1초 안에 나오려면 계산량을 막쓰면 안되겠다는 생각이 들었다.
다행히 강사가 힌트를 준다.
자료 구조는 다이나믹 어레이나, 링크드 리스트, 바이너리 트리 중에 써보세요
음.. 다이나믹 어레이는 신규 단어 저장하는데는 O(1)이 들겠지만, 기존 단어는 O(n)이 들겠군.
링크드 리스트도 마찬가지일테고...
바이너리 트리는 둘다..O(logn)이면 되겠구나. 출력할 때 더 귀찮아 지겠지만..
ㅇㅋ 바이너리 트리로 선택.
덕분에 바이너리 트리를 한번 짰다.;;;전자과에서는 절대 구경도 할 일이 없었던 내용을..
암튼, 자료구조형을 정하고 나니, 훨씬 후월하게 작업이 되었다. 사실 바이너리 트리 구조였기 때문에
기존에 있는 단어인지를 확인 하면서 없으면 바로 추가가 가능했기 때문에 코드가 더 간결해졌다.
확실히 머리속에서 복잡해지면 코드로는 간결해질 수 있는 것 같다.
암튼, 다른 자료구조를 선택한 팀보다는 일찍 끝낼 수 있었고, 덕분에 순위권.
실습 외에도 git / gerrit을 사용해볼 수 있었던 점이 개인적으론 좋았다. git의 경우 예전에 libav할 때 다뤄봤는데,
회사에서는 svn만 쓰고 있어서 개인적으로 쓰는 것 외에는 사용할 일이 없었다. 다른 사업부에서는 사용하고 있다곤 하는데,
왜 이렇게 전파가 느린건지 우린 아직도 svn..ㅎㅎ gerrit도 구경할 일이 없고 말이다.
다행히 연구소 품질 파트에서 git 전환 유도를 위해 신청한 과제에 대해 git/gerrit을 설치해주는데, 미리 신청해서 받아만 놓고
잘 사용하지 못하고 있었다. 사용법도 모르고 ㅠ.ㅠ.
그런데 이번에 실습을 하면서 git/gerrit을 다뤄봐서 좋았다. 개인적으로는....이 것만 따로 만들어서 동영상 강의를 올려도 좋을 것 같은데,
내 욕심일려나....

그리고 손코딩으로 얻은 점을 확인할 수 있었던 교육

교육에 오신 분들은 다 그렇듯이, 신입에서부터 지긋한 분까지...다양한 계층이 모인다.
물론 다 개발자 트랙을 타고 있는 분들이 나타나시는데, (나도 그랬듯이) 본인의 생각들을
코드로 내려놓는데 어려움을 많이 겪는다. 가장 힘들어 했으면서 공감했던 부분은 뭔가 꼬리는 잡았는데,
머리 속에서 풀어내지 못하면서 돌고 도는 것이다.
이걸 이용해서 어떻게 해보면 될 것 같은데..
문제는 어떻게가 머리 속에서 풀리려면 연습이 필요하고, 이걸 쉽게 끄집에 내는 것이
손코딩이었던 것 같다. 이번에도 2개의 문제를 접하면서 내 생각도 정리할 겸, 같이 하는 분에게 전달도 할 겸,
연습장에 슥 슥 써 나갔던 부분이 크게 도움이 되었다. 문제를 받고 내가 생각하는 방향이 잡혔음에도 우선은
같이 하는 분의 생각을 확인하고자 의견을 이야기하지 않고 있었는데, 이러한 내용을 밖으로 끄집어 내는 것이 쉽지 않으셨던 모양..
틀리면 어떻게 하지라는 불안감도 있겠지만, (사실 이건 손코딩으로 많이 내려놓게 되었다. 쓰다보면 틀린 것 투성이라서..ㅎㅎ)
아무래도 코딩은 키보드로 하는 것이지 손으로 하는 것이 아니라는 관념 때문에,
펜과 종이 앞에서는 시간이 멈춘 듯한 광경을 많이 보았다. 우리 뿐만 아니라, 다른 팀에서도....

그럼에도 아직 갈 길이 멀었다는 생각이...

몇 번의 손코딩을 참여하면서 이런 부분은 확실히 늘었다고 단언할 수 있다.
예전 같았으면 나도 그냥 어떻게 하지...손 놓고 있다가 시간만 흘렀을테니까 말이다.
또는 되지도 않는 접근법으로 우선 IDE만 만지작 거리고 있었을 것이다.
생각해보면 짧은 시간동안 많이 늘었다. 그럼에도 아직 멀었다는 생각이 든 점은
팀 프로젝트에서 강사의 힌트가 없었다면 난, 바이너리 트리 방식으로 접근을 했을까 하는 점이다.
그도 그럴 것이 바이너리 트리 저장 구조를 이번에 처음;;; 들었다. 자료 구조도 들어본 적이 없으니까;;;
STL로 가져다 썼으면 썼지..딱히;;
이런 것들은 협업에 충분히 적용이 가능한 부분인데, 이제 알았다는 것이 아쉬웠고,
실제 STL로 가져다 쓰는 것 외에도 내부를 알 필요가 있다는 것을 강하게 느끼는 기회였다.
요즘 C++을 해보자고 겉 멋들어 있었는데, 다시 낮은 레벨로 갈 수 있는 전환점이 되었다.

기타

아, 정말 이번 교육은 강사님들이 정말 좋았다. 내용도 내용이지만, 강사분 두분의 성격이 너무 좋았다.
아니, 좋아보였다. (또 저 뒤에 어떤 모습이 숨어 있을지는 모르겠지만 ㅋㅋ) 만약 안에 숨은 모습이 무섭더라도
겉에 모습이 저 정도라면 같이 일 해보고 싶다는 생각이 들 정도였으니 말이다.
이틀이면 짧은 시간이었지만, 사람에게 좋은 인상을 주는데는 부족함이 없는 시간이라는 것을 느꼈다.
나도 저럴 수 있으면 좋겠다.
내가 접하는 사람들도, 저 사람과 일하고 싶다. 는 생각이 들 정도로
업무도, 그 외에 부분도 잘해야겠다는 생각이 들었다.

SRM 615 Div 2 level 2

문제는 다음과 같다.
어떤 아이가 T회만큼 뛸 수 있는데, 한번에 B만큼 뛰거나 1만큼 뛸 수 있다. 그럴 때, D에 도달할 수 있을지 없을지?를 구하는 문제이다.
모든 값들은 1,000,000,000보다 작은 자연수로 제한된다.
음..어떻게 하면 될까..다 돌려보면 되겠군.?
그렇다. 경우의 수를 다 돌려보면 결과가 나온다. 그런데 최악의 경우 경우의 수는 매번 두가지 분기가 발생하니까 2^1,000,000,000번 루프를 돌아야 한다. 절대 안되겠군..이 방법은 패스...
..
..
음 생각해보니,
매 경우의 수를 다 해볼필요는 없겠다. 어짜피 1번째 B만큼 뛰고 2번째 1만큼 뛰나, 1번째 1만큼 뛰고 2번째 B만큼 뛰나 똑같잖아? 즉, 경우의 수가 아니라, B를 몇번 뛰었을 때만 체크하면 되겠다. 그러면 최악의 경우 1,000,000,000번 루프를 돌리면 되니, ㅇㅋ 이건 좀 나올만 하겠다.
...
...
...
땡 오답.
시간 초과...
아씨;; 파이썬으로 짜서 그런가?
이미 점수는 날라갔지만 열받잖아. C++로 짜봐야지.
..
..
통과..
..
..
이런 걸 (어떤 언어로는 통과할 수 없는 문제)를 문제라고 내다니..짜증나게;;;!!!! 흥
...
...
...
몇 일이 지나고 오늘 에디토리얼을 봤다.
본 이유는 단 하나.
ㅋㅋㅋ 파이썬으로 푼 인간은 없겠지?
...
...
..
왠 걸? 에디토리얼이 파이썬이다.
뭐야..이건..

최종적인 방법은 이렇다.
뭐 접근법은 큰 범주에서 맞았다.
순서는 상관없이 B를 몇번 뛰었는지만 카운트하면 된다.
즉,

x * B + (T - x) = D

인데, 이게...루프를 돌릴 필요가 없다.
이유인 즉슨...
x로 정리를 하면,

x(B - 1) + T = D
x = (D - T) / (B - 1)

이렇게 되고, 이 조건만 체크하면 된다. 우선,
x는 자연수 라고 했으니까 (D - T) % (B - 1) == 0을 만족해야 하고, 또한 양수여야 하니까 D - T >= 0도 만족해야 한다. 마지막으로 x는 T를 넘을 수 없다.
결국 (D - T) / (B - 1) <= T....
이 세가지 조건을 만족한다면,
표현 가능하다.
당연히, 루프 따위 없이 파이썬에서 아주 빠르게 동작.
ㅠ.ㅠ
킁...앞으로 열심히 공부해야겠다.
머리도 좀 빨리 빨리 돌리고 말이다.

파이썬으로 푼 사람이 22명이나 된다. 물론 다른 언어에 비해서는 성공률이 낮은 편이지만..그래도 다 돌려보지 않은 사람이 그만큼 많다는 거고, 그 짧은 시간에 머리가 그렇게 돌아간 사람이 그만큼 많다는 것이다.

공부해야겠다.!!!!!

손코딩

아, 시간 잘 간다.
책도 읽을 것이 많고, 할 일도 많다보니
글을 쓰는 일에 등한시 하게 된다.
정확히는 블로그에 글을 쓰는 일을 등한시 하고 있다.
손코딩에서도 매번 후기를 작성해서 공유하고 있으니, 글을 안쓴다고 하기엔 좀 그렇고....
그래서 오늘은 한달 전과 마찬가지로,
다시 손코딩.. :)

여러마리의 고양이가 일직선 상에 놓여 있고, 저희는 그 고양이들의 위치[정수 좌표]를 알고 있습니다. 이 고양이는 딱 한번 X 칸 만큼 움직일 수 있습니다. 왼쪽이나, 오른쪽이나 상관은 없고, 반드시 고양이들은 X칸만큼 1회 움직여야 합니다. 이동 후에 맨 오른쪽의 고양이와 맨 왼쪽 고양이 간의 거리가 가장 짧은 경우에 대해, 그 거리를 반환하면 됩니다. 예를 들어, 고양이가 다음과 같이 배치되어 있습니다. (-3, 0, 1) 그리고 X는 3이라고 하면, (0, -3, -2)로 움직여서 고양이간의 최대 거리가 3인 경우가 가장 짧은 경우가 됩니다. 고양이는 50마리까지 가능하고, 좌표는 정렬되지 않은체 -100,000,000 ~ 100,000,000까지 위치할 수 있고 X는 100,000,000까지 가능합니다. 모든 경우를 다 해보는 것은 어렵겠지요. 생각만해도 250에 해당하는 케이스를 확인해야하니까 말입니다. 바깥에 존재하는 고양이를 넣어가면서 거리가 짧은 것으로 고르는 것도 어렵습니다. 생각지도 않은 예외 케이스가 발생합니다. 분명히 지금 고양이를 왼쪽으로 옮기는 것이 짧은 거리로 가는 것인데, 최종적으로 보면 오른쪽으로 옮기는 것이 더 짧은 거리를 가지는 경우도 나옵니다. (이 경우 때문에 다들 맨붕에...) 이 문제는 생각보다 간단하게 풀릴 수 있습니다. 이 문제를 간단하게 만드는 점은 바로 이겁니다. 최소를 만들기 위해서 오른쪽 이동과 왼쪽 이동이 만나는 점은 1회면 족하다 입니다. 예를 들어보면, X가 3이고 주어진 고양이 배치가 [1, 3, 5, 7, 11, 13]인 경우가 [1, 3, 9, 11, 21, 23] > > > > < < 로 이동하면 됩니다. 물론 아래와 같은 경우도 되겠지요. > > < > < < 이런 경우 X에 따라서 위에보다 더 큰 경우가 나오거나, 동일한 경우가 나옵니다. 즉, 최소 거리는 오른쪽 이동과 왼쪽 이동이 만나는 점이 1회인 경우를 다 살펴보면 그 안에 존재한다는 겁니다. 사실 생각해보면 간단한데 글로 쓰니 어렵군요;; 그래서 고양이 5마리가 정렬되어 있다고 하면,ㅡ <<<<< ><<<< >><<< >>><< >>>>< 인 경우만 확인하면 됩니다. 체크하면 되는 경우의 수가, worst case로 250이라고 생각했던 것에서 50으로 줄어들지요. 이정도면 풀어볼 수 있겠습니다. 코드는 다음과 같습니다. import math,string,itertools,fractions,heapq,collections,re,array,bisect,random class TaroFriends: def getNumber(self, coordinates, X): c = sorted(coordinates) result = list() for i in xrange(len(c)): bound = list() for j in xrange(i): bound.append(c[j] + X) for j in xrange(i, len(c)): bound.append(c[j] - X) result.append(max(bound) - min(bound)) return min(result)

Dynamic Programming - 손코딩

이번주 역시 Dynamic Programming 문제를 풀었습니다.

Dynamic Programming에 대한 개념은 이전 모임의 editorial을 참고해주시고...

Problem 1. Coins
동전셋(Coins)이 주어졌을 때, 임의의 금액(S)를 만들 수 있는 최소의 동전 갯수를 반환하라.
만들 수 없을 경우, -1을 반환.
S는 10,000 이하이고 len(Coins)도 10,000 이하로 제약합니다.

예제로는 다음과 같습니다.
ex1) S = 160, Coins = {10, 50, 100}
return: 3
ex2) S = 140, Coins = {10, 50, 100}
return: 5
ex3) S = 160, Coins = {50, 100}
return: -1

15회 P1. coins 문제와 유사하면서 P2. Roads 에서 사용했던 최소값 부분을 합친 문제로 봐도 무방할 것 같습니다.
다이나믹 프로그래밍을 설명하는 일환으로 state에 대한 이야기가 나왔습니다.
이전에 나왔던 것과 동일한 개념입니다만..
ex1을 state 로 설명을 하면
state(S)은 주어진 동전셋으로 표현 가능한 최소 동전로 정의를 하였습니다.
그러면 아래와 같이 정리가 되지요.
state(S) = 1 + min(state(S - Coins[0]), state(S - Coins[1]), ..., state(S - Coins[N-1]))
그럼 state(S)를 재귀의 형태로 만들면 끝.

code

  1. overflow 처리
    위의 코드에서는 파이썬이라서 그런 경우가 없습니다만,
    C++로 할 경우 ,INT_MAX로 잡아놓은 값에 대해 조심히 처리할 필요가 있습니다.
    지난주에 이어서 이번주에도 지적받았던 사항인데, INT_MAX에 +1 하는 순간 마이너스가 되어버리는..
    따라서, INT_MAX를 확인하고 아닐 경우에는 증가시키는 부분, 주의해야 합니다.

  2. 불필요한 최적화
    주석처리를 한 부분에 보면
    중간에 동전의 갯수가 0이면 그 이후에는 불필요하게 카운트할 필요 없이 루프를 끝내자
    고 생각하여 들어간 최적화 코드입니다.
    하지만, 실제로 그 이후에 들어가서 cache를 채우거나, 아니면 다음 루프에서 cache를 채우거나,
    어짜피 한번은 cache를 채우는 작업이 들어가기 때문에 크게 효용이 없었습니다.
    몇 번의 루프를 돌지 않는 경우가 발생할 수 있겠지만,
    a) 그를 위해서 분기문이 하나 생겼고, (그로 인해서 테스트 케이스 하나 늘어나고..)
    b) 코드를 읽는데 방해가 되네요. (저 if는 뭐지? 한 번 더 고민을 해야하는..)
    역시 반드시 필요한 경우가 아니면 구지 최적화를 -_- 하지 않는 것이 좋다는
    이야기에 맞는 케이스가 아닐까 합니다.

  3. 기타 재귀함수에서 확인점.
    재귀함수 코드를 완성하고 검증하는 부분에 대한 이야기가 있었습니다.
    리턴 가능한 부분을 정리하고 그에 대해서 잘 돌아가는지 확인하는 것입니다.
    위의 경우에는 0, x, MAX_VALUE 인데요. 이 리턴값들을 상위에서 잘 받아서 처리하는지,
    반대로 리턴하지도 않는데 상위에서 처리하는 부분이 있는지를 확인하는 것입니다.
    실수를 막을 수 있는 간단하면서도 좋은 방법입니다.

Problem 2. Paths
w, h 사이즈의 그리드가 존재합니다.
ex) w = 4, h = 4
(0,4) (4,4)
|-----|-----|-----|--|
| | | | |
| | | | |
|-----|-----|-----|--|
| | | | |
| | | | |
|-----|-----|-----|--|
| | | | |
| | | | |
|-----|-----|-----|--|
(0,0) (4,0)
그리고 막혀있는 라인이 주어집니다.
ex) w = 4, h = 4, bad = ("0 0 0 1", "2 1 2 2")
(0,4) (4,4)
|-----|-----|-----|--|
| | | | |
| | | | |
|-----|-----|-----|-----|
| | | |
| | | |
|-----|-----|-----|-----|
| | | |
| | | |
|-----|-----|-----|-----|
(0,0) (4,0)

주어진 w, h, blk으로 (0, 0)에서 (w, h)까지의
최단경로의 수를 구하시오.
제약조건으로 w, h는 1 ~ 100, bad는 0개 ~ 50개까지 됩니다.
그리고 bad가 하나도 없는 상태에서 최대 W, h일 경우
200C100 을 가지게 됩니다만 이게 196자린가 그렇습니다.
문제에서는 2^63-1개까지 답이 나온다고 제한해놓았습니다.

이번 문제에서는 state를 아래와 같이 잡습니다.
state(m, n)은 (m,n)에서 (w, h)까지의 최단 경로의 수
그렇다면 아래와 같이 전개가 가능해집니다.
state(0, 0) = state(0, 1) if bad.count("0 0 0 1") == 0 else 0
+ state(1, 0) when bad.count("0 0 1 0") == 0 else 0

그럼 한단계를 더 내려가볼까요?

state(0, 1) = state(0, 2) if bad.count("0 1 0 2") == 0 else 0
+ state(1, 1) when bad.count("0 1 1 1") == 0 else 0
state(1, 0) = state(1, 1) if bad.count("1 0 1 1") == 0 else 0
+ state(2, 0) when bad.count("1 0 2 0") == 0 else 0

state(1, 1)이 겹치지 시작하네요. cache를 하면 되겠습니다.

code

  1. exit 조건이 cache 속으로
    재귀 함수를 작성할 때, 우선 exit 조건부터 고민하는데요
    이 문제에서는 m == w, n == h 일 경우에 1을 리턴하는 부분이 exit 조건으로 들어갑니다만,
    이 부분을 cache에 미리 넣어놨습니다.
    이러면 아무래도 비교 한번 더 안하고 넘어갈 수 있겠죠.

  2. (0,0)에서 출발이 아닌 (w, h)에서 출발
    위의 코드와 반대로 (w, h)에서 줄여나가는 방식으로 작성하신 팀이 있었습니다.
    이 경우에 exit 조건을 위해 w, h를 가지고 다니지 않고, 0, 0과 비교를 하면 되서
    코드가 조금 더 간결하게 표현 가능했습니다.
    (파이썬으로 했더니 이 경우에, 시스템 테스트에서 timeout 한번 나오네요 ㅜㅜ)
    (제약 조건이 나빠요. test case 2가 (w, h)에서 출발하도록 풀면 내부에서 2^63-1을 넘어가네요. 암튼;)


처음으로 editorial을 써봤는데,
생각보다 쉽지 않고 주저리 주저리 말이 많아진다.
게다가 어설프게 알고 있던 내용들이 적나라하게 드러나기까지 한다. (이것이 최대 장점이긴한데..)
그래도 이것저것 하다보니 2시간은 훌쩍..
휴우~ 생각보다 쉽지 않다…
그리고 이게 DP에 대해서 파는 것도 좋긴한데,
뭔가 원래 손코딩의 목적에서 내가 벗어나게끔 생각을 하는 것이 느껴진다.
원래 취지는 머리속에 있는 것을 끄집어 내어서 적어보고 그걸 코드로 바꾸는 과정인데,
코드로 바꾸는데 있어서 필요한 방식을 배우다보니 원래 목적이 약해지는 것 같은 느낌.
그만큼 기본기가 약하다는 말이긴 한데…유념해야겠다.

손코딩

아침에 와서 지난 날 작성했던 DP 코드를 만들어서 돌려봤다.

확실히 다시 한번 짜보니 조금 기억에 오래 남는 것 같다.

어제도 그런 감이 있었고...

캐시를 만들고 나서, recur에 대한 exit 조건을 작성하는데 있어서 명백한 부분은 init에서 캐시에 바로 넣어주는 것도 방법일 것 같다.

예를 들어 두번째 문제에서 w,h 포인트에 대한 캐시를 1로 설정해놓는 것처럼 말이다.

그럼 적어도 매번 w,h 포인트인지 체크하는 부분이 없어도 된다는 장점이 있다.

이번에 보면서 갑자기 생각이 안나서 찾아본 내용이 있다.

두번째 문제에서 보면 우선 블락이 하나도 없을 경우에 대해 경우의 수를 구하는 것인데, 이 부분에 대해서 어떻게 구하는지..까먹었다.-_-

기억이 안나더라.

그래서 이 부분을 찾아봤다.음..역시 간단헤..

(w + h)Cw

예를 들어 4,5 사이즈라면 9C4의 경우의 수가 발생한다.

이 부분에 대해서 조금 더 친절히 설명을 하면 총 9번을 움직여야 하는데, 그중에서 우측으로 움직이는 경우가 4번인 경우...로 이해하면 되겠다.

그래서 9번 중에 4번이 우측인 경우,9번 중에 5번이 상측인 경우,로 보면 기억하기 쉽다.

그리고 이 부분을 정리하다보니 팩토리얼이 나왔는데,이 팩토리얼도, -_- 한줄로 짜는 역시,,, 파이썬....

reduce(lambda x, y: x*y, range(1,N + 1)

아, 훌륭하다. 파이썬의 미학은 이런 점이 아닐까...싶다.

저 문장 하나로 되? 이런?

kindle ebook Korean edition

몇 일전에 킨들 이북을 구매했다. 예전에 2권 정도 영문서적을 구매했었는데, 영 진도가 안나간다.

뭐 여전히..다 읽지 못한 상태로 되어 있다.

그러다보니 이북에 대한 호감이 떨어진 상태였는데, 우연치 않게 한글로 된 이북을 발견하고 구매했다.

130페이지 정도의 분량이었고 (아마존 예상치) 읽는데 이래저래 하루가 안걸린 것 같다. 아침 출근 시간, 점심시간, 저녁 퇴근 시간 정도 되니 다 읽었다.

내용에 대해서는 따로 정리를 하고....

이북이 정말 편했다. 우선, 눈이 편하기도 하거니와, 생각보다 일반 책이 글을 읽는데 편하지 않다는 베조스의 의견에 일부 동의할만큼 편하게 읽었다.

각 페이지마다 마킹할 필요도 없고,

페이지가 넘어갈까봐 잡고 있을 필요도 없고,

들고 다니기도 편했다.

그 외에 폰과 싱크로 인해 접근성이 좋은 점도 있었고...

물론 이북으로 읽기 편한 종류의 책이긴 했다. 일반 전공서적처럼 뒤적이면서 볼 수 있는 책에는 단점이 더 많을테지만, 휙휙~ 읽을 수 있는 책에서는 이북이 책보다 편하다고 느낄 수 있는기회였다.

아마존 이북이 한국에 진출을 하던가, 아니면 한국에 유력 이북업체에서 활용할 수 있는 좋은 이북기기(코보가 괜찮다고 하긴하던데..)를 구하면 정말 좋겠다는 생각이 들었다.

지금 당장은 킨들로 읽을 수 있는 (합법적으로) 이북이 얼마 없는데, 이걸 또 구매해야할까..라는 고민에 빠졌다. (처음 읽은 책의 속편이라...)

Evernote feedback

에버노트에서 뭔가 끄적이면 가깜 종성이 뒤로 튕겨나가는 현상이 있어서 피드백을 보내봤다.

사실 현상은 매우 오래되었는데, 되겠거니..되겠거니..기다렸는데 안되서 한번 보내봤다.

그런데, 이게 iOS 버그랜다...-_-;;

결론은 못고쳐요..

뭐 그거야 그렇다고 쳐도..

생각보다 에버노트 피드백이 그렇게 빠르다는 생각은 안들었어. 근 하루정도 걸린거 같긴하다. 빠르다면 빠른건데,....프리미엄은 더 빠를 것이라는 내 기대치가 높았을 수도 있고.

그러면서 iOS에서 버그가 영향을 안미치는 앱들을 소개시켜주긴 했는데, 크게 마음에 드는 앱들이 없긴 하다. 다들 가볍긴한데, 당장 작성과 검색이 앱으로 구분되다보니 불편하기도 하고..

빨리 해결되었으면 좋겠다.

-_- 애플 바보.

One click - 아마존 창립자 제프 베조스의 4가지 비밀

아마존 == 제프 베조스 공식에 걸맞게, 베조스에 대한 이야기와 아마존 이야기가 잘 버무려져있는 책이다.

이 책을 읽기 전에는 ET 같이 생긴 아저씨 정도로 알고 있었는데, 그를 이해하는데, 그리고 아마존을 이해하는데 큰 도움이 된 책이다.

다만, 특이하게도, 책을 읽는 초반에는 제프 베조스에 빠져버렸고, 중반에는 이 사람 뭐지?라는 눈으로 보게 되었고, 후반에는 과연..아마존이 앞으로도 잘 나갈까?라는 생각도 들 정도로 뭔가 느끼는 바가 드라마틱하다. :)

한 권의 책보다는, 아이템별로 쪼개서 연재기사 같이 봤다면 더 좋았을 것 같은 책.

제 3자가 보는 베조스임에도 너무 긍정적 시각으로만 나열된 것도 조금 몰입도를 떨어뜨리는 점