알고리즘 중독자들, 알고리즘 프랙티스
안녕하세요.
매스프레소 R&D 검색팀 소속 리서치 엔지니어 Nutella 입니다.
알고리즘, 누군가에게는 헤어나올 수 없는 매력이지만 누군가에겐 hair 나올 수 없는 고민.
개발자라면 한번쯤 접해보았을 이 공부가 과연 실무적으로, 실용적으로 어떤 도움이 되는지 궁금하신 분들이 많으신 것 같습니다.
그 궁금증을 해결하고 싶은, 또 글로벌 1위 인공지능 검색 채팅 컨탠츠 플랫폼 킹왕짱 교육앱 콴다의 기술력을 살짝 엿보고 싶은 당신!
이 글을 읽어주세요 :)
먼저 홍보겸 간단한 (콴다 답게 Q&A 형식으로) 소개를 드리고자합니다.
Q. 알고리즘 프랙티스란?
A. 일상과 회사에서 마주치는 어려운 문제들도 척척 해결하는 독특하고 똑똑한 사람들의 Problem Solving 세미나입니다.
매주 자신의 지식과 풀이를 자랑하면서 상금 헌팅도 할 수 있는 기회를 가집니다! 인기가 없을 줄 알았던 괴짜들의 모임이 어느새 매프에서 가장 큰 학술 모임이되었습니다.
Q. 어떻게 시작되었나요?
A. 처음 시작은 R&D 연구소 벽이나 유리에 재미있는 문제를 적어놓고 토론을 하는 것이었습니다. 지금은 많은 인원을 감당하기 위해서, 실시간 채점이 되면 좋겠다는 피드백을 받아 온라인 저지 + 오프라인 풀이 세션로 옮겼습니다.
미래에는 사내 대회를 열거나 KPI 를 직접적으로 개선하는 문제에 대해 큰 상을 걸고 진행해보려 합니다
Q. 아무나 참여할 수 있나요?
A. 비개발자여도 Hello, World! 같은 쉬운 문제부터 단계별로 실력을 쌓을 수 있어요. 잘 모르겠더라도 고민과 시도를 채널에서 이야기하는 것으로 힌트를 얻어서 해결할 수 있어요.
Q. 참여하면 뭐가 좋나요?
A. 생각치도 못했던 다양한 풀이와 접근 방법을 들을 수 있어요.
뛰어난 동료 엔지니어들과의 질의응답, 챌린징 같은 상호작용 경험을 쌓을 수 있어요. 참여하다보면 자연스럽게 알고리즘의 달인이 된 자신을 발견할 수 있습니다. 그리고 상금은 덤!
자, 이제 크게 분야를 나눠서 어떤 문제들을 풀었는지, 실무에는 어떤 도움이 되었는지 적어보겠습니다.
(각각 Online Judge 사이트 백준(https://www.acmicpc.net/)의 문제의 링크를 참고해주세요.)
논리적 사고
Q. Fizz-Buzz 를 어떻게 만드나요?
A. 네! 저는 Deep-Leaning 을 활용해 보겠습니다.
https://joelgrus.com/2016/05/23/fizz-buzz-in-tensorflow/
↓문제 링크 ↓
https://www.acmicpc.net/problem/13410
https://www.acmicpc.net/problem/17073
깔끔하고 무결한 논리를 세우는 것만큼 개발자에게 흥미로운 것이 있을까요?
아무리 어려운 구현도 한두번, 혹은 몇번 해보다보면 쉽게 하고 있는 자신을 발견할 수 있습니다.
그러나 그러한 사고를 연습하지 않으면 Fizz-Buzz 에서도 헤맬 수 있겠지요. 알고리즘은 그런 점에서 아주 훌륭한 스승이자 도전적인 과제가 될 수 있습니다.
위의 문제는 대망의 첫번째 연습 문제였습니다.
구구단의 N단에서 K항까지의 결과를 뒤집어서 나온 수 중에서 가장 큰 수를 구하면 됩니다.…각자 풀이를 생각해보았으면 Integer 를 뒤집는 것이 핵심이라는 것을 알 수 있습니다.
하지만 일반적으로는 Integer 를 뒤집는 것이 익숙하지 않지요?
그래서 저는 string 으로 변환하여 그것을 뒤집고 다시 Integer 로 만들었습니다.
언뜻 비효율적일 수 있지만 주어진 범위의 입력을 처리하는 속도는 1ms 조차 되지 않습니다.
그런데도 C++ 라이브러리를 이용해 절차 그대로를 옮겨서 나쁘지 않았지요?
여기서 멈추지 않고 이러한 입력이 1억개 들어왔을때 같은 상상을 해보면 어떨까요.
범위가 작다는 것을 이용해 미리 뒤집는 테이블을 만들거나, 아예 입력으로 가능한 경우를 다 저장해놓는 것이 나을 수 있어요.
즉, 문제의 사이즈에 따른 여러 이론을 알고 있다면 편리합니다.
반면, 아래의 문제는 입력을 통해 Tree 를 꼭 만들어야하는가? 하는 물음을 담고 있습니다.
알고보면 연결된 원소의 수만 세면 답을 구할 수 있는 신기한 수학적 사실을 알 수 있습니다.
이건 여기까지만 말씀 드릴게요!
자료구조
Q. 왜 코카콜라는 균형잡힌 맛일까요?
A. Red-Black 이니까요?
↓문제 링크 ↓
https://www.acmicpc.net/problem/12789
https://www.acmicpc.net/problem/17082
면접썰을 듣거나 직접 면접을 보다보면 답답한 부분이 하나 생깁니다.
자료구조에 대한 이해가 부족하거나 어떻게 쓰는지 모르는 경우입니다.
(동료들이 저 농담에 웃지 못해도 답답합니다 ㅠ)
비교적 간단한 자료구조인 Queue, Stack, LinkedList, Array, Deque 등을 내부까지 깊숙히 알고있는 사람은 생각보다 드물었던 것 같습니다.
더 복잡한 자료구조인 RedBlackTree, HashTable 혹은 SegmentTree 는 말할 것도 없겠죠.
위의 문제는 Queue, Stack 을 알고 있는지 묻고 있는 것 같습니다.
자료구조를 올바르게 정했다면 다음과 같은 사실을 이용하면 됩니다.
한편, 아래의 문제는 힌트만 적어보겠습니다.
뽑힌 구간에 존재한 원소들을 MultiSet(Map) 저장하면 삽입, 삭제, 최대값을 구하는 시간복잡도가 모두 O(log N) 이겠지요?
+ 다만 두 주머니의 원소를 어떻게 뽑을지 정하는 Gridy Algorithm 을 하나 만들어야합니다.
TDD & Debugging
Q. 콴다에 코드를 찍어서 검색하면 반례를 보여주나요?
A. 그랬으면… (from 콴다 개발자)
↓문제 링크 ↓
https://www.acmicpc.net/problem/15671
https://www.acmicpc.net/problem/17081
개발을 하면서 종종 마주치는 복잡한 기획은 직장내 원두 떨어짐과 더불어서 일하는 사람에게 큰 스트레스를 줍니다.
가장 어려운 것은 이 프로그램이 과연 올바르게 작동하는지 알기 어렵기 때문이죠.
그런 점에서 Test Case 가 미리 있다면 또 본인이 만드는 것에 능하다면 한결 낫습니다.
가능한 입력들을 생각하면서 개발하는 것은 꽤 효율적이고 기능에 대한 이해를 돕습니다.
또, 그런 친구들은 디버깅은 어떻게 해야할까요?
이 모임에서는 수많은 왜 맞았는데 틀리지? 를 통해서 그리고 코드 리뷰를 통해서 실수를 발견하고 줄이게 됩니다.
놀랍게도 위 문제도 그러한 경우인데요.
(실제로 다른 참여자가 함께 연습하면서 겪은 스토리입니다.)
상하좌우(+ 대각선) 같은 규칙이 주어지고 그것들이 대칭적이라면 다음과 같은 배열을 만드는 것은 알고 있습니다.
그러나 저렇게 하면 마음대로 되질 않습니다.
어? 그런데 뭔가 이상하지 않나요?
바로 마지막 원소가 [-1, -1] 로 바뀌어야하는데 말이지요.
그 분은 10번을 보고 또 보고 제출해도 틀렸었는데 저는 한방에 찾았습니다.
(그래도 이 외의 다른 버그는 다 찾으셨다고..)
이런 것들은 남들이 보면 잘 보인다는 것이 진짜입니다!
또한 [-1, -1] 해당하는 Test Case 가 없었다면 쭉 맞다고 생각했을 수도 있겠네요.
아무튼 한번에 완벽한 코드를 짜는 능력이 있으면 좋겠지만 디버깅을 잘 하는 것도 충분히 바람직하겠습니다.
아래의 문제에 대한 저의 정답 코드는 6000Byte 가 넘어가네요.
객체지향이 고프신 분은 문제를 꼭 풀어보세요~
마무리
Q.매스프레소 RnD팀이 해결하고 있는 문제와 그에 사용되는 알고리즘들이 무엇인가요?
A. Problems: Fast Keyword Search, Document Similarity, Image, Image Region Separation, Questuib Clystering…
Algorithms: Aho-Corasick, Max Flow, Delaunay’s Triangulation, Flood Fill, Spectral Clustering, K-mins clustering…
수많은 회사들이 기술 지향 회사를 표방하고 있습니다.
그런 회사를 다닌 다는 것이 꼭 알고리즘과는 관계 없을 수 있습니다.
하지만 적어도 우리 회사의 RnD 팀 개인들은 알고리즘 전문가이고 더 전문가가 되고 싶어합니다.
하다못해 AI 엔지니어들이 DL 을 하려고해도 데이터를 순식간에 올바르게 가공하자하면 알고리즘이 필요하다고 증언해주셨습니다.
어쩌면 누군가에게는 일하고 사는데 하나도 도움이 안 될 수 있습니다.
그러나 단순한 취미로서도 함께할 수 있는 것이니까요!
이 점에서 알고리즘 프랙티스에서 공부하는 알고리즘은 하나라고 할 수 있습니다.
바로 모든 문제를 풀 수 있다고 알려진 파인만 알고리즘인데요.
함께 감상하면서 이만 마치겠습니다.
포기하지 마세요 :)
