항해99 2주차(2021.3.8 - 3.14) WIL - 알고리즘에 푹 빠지기.

이번주는 알고리즘!

이번주는 항해99 2주차 + 3주차 2일째까지 과정으로, 알고리즘 문제를 풀면서 알고리즘 지식과 풀이 테크닉을 익히는 주였다. 익숙하지 않은 이론이 많았고 배워야 할 테크닉도 많고 어려운게 많아서 애를 먹기도 했지만, 이전까지 생각하는 방식이 비효율적이라는 것도 깨닫게 되고 답이 나오는 생각법으로 바꿔야겠다는 통찰도 얻었고, 신박한 풀이를 내가 생각해 내기도 하고 남들의 좋은 풀이를 배우기도 하면서 지적인 즐거움도 느끼게 되는 주였다. 가장 좋았던 것은, 앞으로 내가 목표로 하는 '남들의 문제를 해결해주는 사람'이 되기 위해서 문제해결 방식을 끊임없이 길러야겠다는 목적의식을 갖게 되었다는 것이다. 그래서 답에 이르게 되는 수학적 사고방식을 체화하는 것이 목표다. 앞으로 다른 프로젝트를 하면서도 틈틈히 챙겨야겠다. 그러기 위해서 운영진도 알고리즘 주차가 아니라도 매주 문제를 내준다고 하니, 걱정은 없다. 

이전까지 알고리즘 경력(?)

이전에 나는 알고리즘 책 한권을 다 떼본적이 있다. 알고리즘 경력(이라고 하기도 뭣하네)은 이게 전부다. 

이승찬님이 지은 모두의 알고리즘 with 파이썬

작년 어느 시기에 알고리즘을 한번 파고 싶어서 이 책을 처음부터 끝까지 보면서 소개된 문제들과 코드들을 실습해보고 문제도 풀어본 적이 있다. 지금와서 생각해보면 이게 얼마나 잘 한 일이었는지, 나한테 큰 칭찬을 해주고 싶다. 왜냐면 이 책을 봤기 때문에 기본적인 테크닉은 알고 있으니, 이번 알고리즘 주차에서 낮은 난이도의 문제에도 쩔쩔매게 되어서 멘탈을 잡는다고 에너지를 쓰지 않아도 되었기 때문이다. 

알고리즘 입문자에게는 아주 적절한 책이다. 다른 알고리즘 책처럼 너무 두꺼워서 기가 죽지도 않고, 설명도 쉽다.

처음 본 백준

운영진이 이번에는 백준에서 나온 문제를 풀거라고 했는데, 근데 '난 백준이 뭐지?' 했다. 이렇게 어리둥절하고 있으니 예전에 내가 투자회사에 인턴으로 들어갔을때 느낌이었다. 공대 대학원생이던 나에게는 거기 직원들이랑 대표들이 아무렇지 않게 말하던 IR(알아 보니 Investor Relations이고 뜻은 투자 유치를 위한 활동이란다. 나만 저 원어에서 저 뜻을 바로 알아차리지 못한거 아니지? 하여간 듣는 사람의 이해도를 생각하지 않고 자기 이해도에 맞게 단어를 지으면 저런 아리송한 말을 만들게 된다)이니 투심이니 투자 용어들이 너무 생소했다. 공돌이던 나에게 IR이란 적외선(InfraRed)였으니까. 그때도 내가 은어같은 용어들을 알아보고 적응했듯이, 여기 업계 용어들도 내가 알아보고 익숙해져야겠다는 생각이 들었다. 사회에 나와서 경험해보니, 뉴비라고 그런 용어들을 친절하게 알려주고 대화를 시작하는 사람은 '없었으니까'. 다만 나는 상대가 이해하는 언어를 쓰면서 소통에 있어 차별화 된 사람이 되고자 한다. 

 

백준은 이렇게 생겼다. 

www.acmicpc.net/

Baekjoon Online Judge

메인페이지 : 온라인 프로그래밍 문제 풀이 사이트라고 소개하고 있다

 

이렇게 알고리즘 문제가 제시되고,

 

풀이를 제출하면 이렇게 정답/오답 판별을 해준다.

 

예전에 나는 백준과 비슷한 사이트를 본 적이 있다. 바로 '프로그래머스'라는 사이트에서 알고리즘 문제를 난이도 별로 풀게 했던 걸 보고 지나친 적이 있다. 백준은 프로그래머스 사이트의 일부로 있는 알고리즘 문제 풀이를 주력으로 하는 사이트라는 생각이 들었다.

어쨌든, 백준은 알고리즘의 늪이기도, 지옥이기도, 풀면 큰 희열을 주는 천국이기도 하다. 마치 양자역학적으로 보면 전자와 빛은 파동이기도 하고 입자이기도 하듯이 알고리즘의 상반된 면이 공존하는 곳이다.

알고리즘 학습에서 나의 궁극적인 목표

나는 아래 영상에 나오는 분이 가르치는 수학 풀이법을 지향하고 있다.  이분은 조봉한 박사님이자 수학 교육 업체 '깨봉수학'의 대표로, 대학원생 시절에 제1회 세계로봇축구대회에 나가 초대 우승도 하고 국민은행과 하나은행에서 높은 자리에 있으면서 국내 온라인 금융 시스템을 발전시키고, 삼성화재 부회장까지 오른 후덜덜한 인물이다. 이 분이 이런 어마어마한 성취를 한 원인은 자신의 수학적 사고 철학인 '무시-변화-관계' 라고 생각한다.  이 분에 관한 기사를 읽어 보면 친구들이 보기에 매일 당구나 치고 노는 것 같은데, 순식간에 과제를 제출하고 좋은 점수를 받아 신기 했다고 한다. 

www.youtube.com/watch?v=q2R_g5q2pdw

운영진 대장 범규님이 소금물 문제를 언급하자 그날 바로 올라온 소금물 문제 풀이 영상ㅋㅋㅋ

정말 신박한 문제 풀이인데, 꼭 한번 보길 권한다.

소금물 농도 문제랑 속도 구하기 문제가 왜 같은 문제인지 통찰을 얻을 것이다.

항해99 과정 이후에 이 분이 운영하는 온라인 수학 교육을 들을 계획이다.

조봉한 박사님의 수학 철학은 '무시', '변화',' 관계'다.

이분이 정의하는 무시, 변화, 관계는 다음과 같다

• 무시 : 디테일을 무시하여 핵심을 빠르게 파악하는 힘

• 변화 : 변화를 파악하고 패턴화해 미래를 예측하는 힘

• 관계 : 사실이나 현상을 관계로 보고 연결해 새로운 사실을 발견하는 힘

백준 문제를 많이 풀면서 저 세가지 철학이 정말 유용하다는 것을 알게 되었다. 겉으로 보기엔 어떻게 풀어야 하는지 갈피를 못 잡는 문제도 '농도'니 '강을 건너'니 '색칠하는데 드는 돈이 얼마'니 하는 디테일을 걷어내면 무슨 문제인지 핵심과 본질이 보여 풀이법을 세울 수 있다. 변화와 관계는 말할 것도 없다. 이 세가지 철학으로 접근하면 문제가 더 쉬워진다는 걸 백준을 풀면서 체험했다. 

지금은 인공지능시대, 머신러닝 시대, 4차 산업혁명시대다. 이 시대에 필요한 인재는 '해결하고자 하는 문제의 핵심을 빠르게 파악해서 해결 방법을 찾고 이에 필요한 논리 구조를 세워서 자신만의 해결 프로그램을 효율적으로 설계할 줄 아는 능력을 지닌 인재'이다. 다른 말로 이 사회가 목놓아 부르짖고 기업에선 눈에 불을 켜고 찾는 '창의적 문제해결 능력'이고 이 능력을 키우는데 수학만한 학문이 없다. 하지만 지금까지 우리가 배워온 수학은 대형, 대량화 된 산업현장에 필요한 표준 인재를 대규모로 공급하는데 적합하다. 말이 좋아 표준 인재지, 스스로 생각해서 참신한 문제해결법을 제시할 능력이 있는 사람보다 이미 나와 있는 공식에 숫자만 넣고 풀 줄 아는 아는 인간계산기들 정도면 공장에 투입해서 일 시키기에 충분했다는 뜻이다.  하지만 인공지능 시대에는 그 정도 능력으로 하는 일은 지치지도 않고 한치의 계산실수도 없는 인공지능 탑재 기계가  대신해서 다 해버릴 수 있게 되었다. 그래서 이런 시대에는 인간만이 가질 수 있는 고유 능력을 키워야 하는데, 무시-변화-관계의 힘이야 말로 인공지능이 못하고 인간만이 가질 수 있는 고유 능력이다. 더 와닿게 말하자면, 무시-변화-관계의 힘을 기른 인간만이 문제해결 과정을 설계해서 인공지능을 부려 먹으면서 문제를 해결 할 수 있는 것이다. 

나는 훗날 현업에서 일하게 될 때 고객이나 세상의 문제의 핵심을 빨리 파악해서 빨리 문제를 해결하는 인재가 되고 싶다. 그래서  지금 알고리즘 문제를 풀면서 무시-변화-관계의 힘을 기르는 것이 목표다. 

 백준에서 잘 알게 된 개념

이번에 알고리즘을 속성이지만 빡세게 공부하면서 확실하게 알게 되었어서 만족스러운 개념이 재귀와 동적프로그래밍이다. 재귀는 이전 계산 결과들의 바닥에 이를 때까지 이전 값들을 불러내면서 계산하는 과정이다. 쉽게 말해서 답을 구하기 위해서 이전에 했던 계산을 계속 반복하는 개념이다. 아래 개념도를 보면 이해할 수 있다.  설명은 이 그림 하나로 더 이상의 자세한 설명은 생략한다.

 

출처 : 파이썬 알고리즘 인터뷰

재귀 함수는 코딩식이 간단하다는 장점이 있지만 이전에 했던 계산을 몇번이고 반복하는 절차가 있기 때문에 시간 복잡도가 너무 크다. 예를들어 재귀함수로 구현한 피보나치 수열은 시간 복잡도가 O(n^2)이므로 시간이 너무 오래 걸리므로 100번째 항을 구하려고 하면 컴퓨터가 계산 결과를 출력하지 않고 오래동안 머물러만 있다. 정확히 말하자면 컴퓨터는 엄청난 계산량을 수행하느라 정신이 없는 상태고 메모리에 막대한 계산 결과들이 쌓여가고 있는 중이다. 이것이 심해지면 메모리가 더 감당할 수 없게 되는 '스택오버플로우' 상태가 될 수도 있다.

 

출처 : 파이썬 알고리즘 인터뷰

동적프로그래밍은 처음에 이 용어를 정한 사람이 '있어 보인다'라는 이유로 지은 이름인데, 그래서 실제 작동 원리를 이름에 전혀 담아 내고 있지 않다. 그래서 이름과 개념이 연관이 전혀 되지 않아서 처음 배우는 사람들은 헷갈리기 쉽다. 나는 이런걸 극혐하는 사람인데, 왜냐면 나는 소통하려면 상대가 이해하는 언어로 소통한다는 철학이 있기 때문이다. 다행히 이광근 교수님이라는 분이 '기억하며 풀기'라는 본질을 담은 쌈빡한 단어로 번역했는데, 이 용어를 쓰면 개념이 더 잘 이해가 된다.  앞으로 나는 '기억하며 풀기법'이라고 쓰겠다.

기억하며 풀기법은 쉽게 말해서 이전의 계산값을 재활용 하는 것이다. 이 재활용 개념이 어떻게 나온 것이냐면, '어느 문제를 더 작은 문제들의 모임(overlapping subproblem)으로 간주하고, 그 작은 문제들을 답들을 모아서 답을 만든다'에서 나온 것이다. 그래서 기억하며 풀기법에는 작은 문제들로 쪼개고 그 문제들의 답을 저장하는 절차(memoization. 메모에 중점을 둔 단어이므로 memorization이 아니다)가 반드시 있다. 작은 문제들은 한번만 풀게 되므로, 시간 복잡도는 작은 문제들의 수만큼만 비례하게 되어서 시간 복잡도는 O(n)이 된다. 그래서 피보나치 수열을 기억하며 풀기의 원리를 이용해 코드를 짜면 순식간에 결과가 나오게 된다.  

핵심을 찌르는 풀이법에 감탄을 금치 못했던 백준 두 문제의 풀이 코드

조봉한 박사님의 수학 철학중에서 '무시'라는 무기로 핵심과 본질을 포착해 문제를 간단히 해결해버린 코드를 보게 되었다. 그 문제들의 신박한 풀이 코드는 이 블로그의 '항해99_알고리즘 연습 중계' 카테고리에 작성해서 아래에 링크를 걸어 두었다. 

heo-dev-0229.tistory.com/8?category=931659

백준 1011번 Fly me to the Alpha Centauri : 파이썬으로 풀기

heo-dev-0229.tistory.com/9?category=931659

백준 2805번 나무 자르기 [파이썬]