회사 일을 하면서는 알고리즘에 대해 그리 고민을 많이 안하게 되는 듯.. 그래서 찾아서 해야하는 알고리즘 공부
결론만 말하면…(
톺아보기)
주변의 많은 이들이 이직시장에 나가서 고군분투하는 모습을 보면서 알고리즘의 중요성(?) 아니 알고리즘과 너무 멀리 떨어져있는 내 자신을 발견함. 이런 걱정을 해소하기 위한 작은 움직임으로 주변 사람들이 보는 코딩 테스트 문제를 가지고 알고리즘 고민을 시작함. 그 과정에서 고민하게 된 문자열 알고리즘에 대한 고민과 나름의 해결과 잡다부리 한 생각을 정리한 글
이미지 출처: 인프런
프로그래밍과 알고리즘을 뗄레야 뗄 수 없는 관계다. 사실 이름만 거창하지 사실상 모든 코드가 어떤 문제를 해결하려는 목적을 가지고 설계된 ‘알고리즘’ 이라 생각 할 수 있다.
현실(AS-IS)
프로그래밍을 처음 배우던 시절에는 취직을 위해 필수라고 생각해서 알고리즘 스터디를 했었다. 그때는 백준 알고리즘에서 문제를 보고 여러명이서 정해진 시간동안 푸는 식으로 스터디를 진행했었다. 자바를 갓 배운 입장에서 사실상 알고리즘을 제대로 공부했다기 보다는 스터디원 중 빼어난 1인의 하드캐리를 지켜보며 알고리즘에 ㅇ정도 느꼈던 거 같다. 강남에만 스터디가 즐비한 것에 갑갑함을 느끼고 OKKY에 직접 ‘강서구 알고리즘 스터디’ 모집 글을 올리고 6명으로 구성된 알고리즘 스터디를 구성했었던 혈기 왕성하던 시절이 그립…
취직을 한 이후에도 알고리즘에 대한 막연한 동경에 사로잡혀 종만북이나, 기타 도서관에 있는 알고리즘에 대한 책들을 빌려봤지만, 사실 읽을때는 그런줄 알지만(못이해하겠는 것도 많았고) 실제로 일을 하면서 알고리즘을 적용할 일은 그리 많지 않았다. 머신러닝을 통한 기능이 필요했던 이미지분석을 위해 opencv로 이미지가공하고 tensorflow를 경험해봤지만 이는 알고리즘을 짠다기 보다는 대량의 데이터를 통해서 결과를 예측하는 수준이었…
코드를 효율적으로 짜는데 집중하는 정도에서 타협했고, 프론트엔드에 집중하게 되면서 점점 알고리즘에 대한 갈증을 잃어가고 있었다. 클라이언트단에서 부하를 많이 견디는 코드는 최대한 지양하자는 1차원적인 생각에… 요즘 핫한 기술들을 경험하고 싶다는 생각에 알고리즘에 대한 고민을 등한시 했었다.
하지만, 최근 감사하게도 주변 지인들의 이직 준비와 이직 소식을 들으면서 알고리즘에 대해 다시 한번 생각해볼 수 있는 기회가 생겼다.
주말(Weekend)
코딩 테스트 문제를 받았고, 한번 훑어보니 음… 이거 이러저러케 하면 되겠는데? 하는 가닥이 보였고, 잠깐 짬을 내서 한번 풀어나 보자 싶었다.
그렇게 금요일 밤에 나혼자 산다를 보는 와이프 옆에서 맥북으로 놀이를 시작했다. 나는 그러지 말았어야 했나?
대충 코드를 짰고, 이를 가지고 원하는 결과를 받았다. 하지만 너무 Brute Force Algorithm이었다.(진짜 과제는 처리해야하는 데이터 양이 많아서 Brute Force 방식으로는 효율성이 극심히 떨어지는 문제가 있었다.)
그래서 이것 저것 알고리즘들을 검색해보고 적용할 수 있는 것들을 읽어보고 이해해보고 적용해보고 하다보니 새벽 3시가 됬다.
찝찝했지만, 그렇게 침대에 누워서 계속 더 나은 답을 찾다가 토요일에 일어나자마자 하다가 아들래미랑 놀다가 다시 생각나면 잠깐 종이에 끄적여보고,
밥먹다가 또 끄적여보고 도서관가서 책빌릴때도 괜히 수학적 사고에 대한 분야에서 이것저것 살피다가,
주일이 되었고 교회 갔다가 아버지 생신파티하고 집에 돌아가서 생각해본 걸 이것저것 해봤고 그렇게 주말을 떠나 보냈다. 주말이 내게로 들어온건가?
결론(Conclusion)
결론은 좋았다. 오랜만에 뭔가의 해결책을 오래도록 끈덕지게 고민해볼 수 있었다. 이런 일이 많으면 좋겠다. 이글은 그렇게 성지글이 되는데..는 아니길
사실 알고리즘에 대해 조금이라도 고민을 해본 사람에게는 크게 어렵지 않은 문제일수도 있지만 어떻게 하면 이를 더 효율적으로 해소할 수 있을까에 대해 계속 고민하는 건 좋은 거 같다.
누군가 말했다. ‘프로그래밍에는 모두가 동의하는 최적의 답이 반드시 존재한다고’
특정 회사의 코딩 테스트 문제이기 때문에 뭐 함부로 유출할 수는 없지만 대략의 내용은 다음과 같다.
읽는 여러분도 고민해 보시길..?
문제
- 랜덤으로 생성되는 임의의 문자 생성기가 있다.
- 그 문자 생성기에서 생성된 1만개의 문자를 유사성을 기준으로 가장 유사한 문자쌍의 목록을 보여줘라.
- 필터를 추가해서 특정 문자를 선택하면 해당 문자를 포함한 문자한 가장 유사항 문자쌍의 목록을 보여줘라.
문제를 좀더 간단하게 하기 위해서는 문자의 종류와 중복가능성, 갯수 등을 조절하면 난이도는 확 줄어들 수 있겠다.
일반적인 문자열 비교 알고리즘은 다양하겠지만 가장 유명한건 Edit Distance라고도 불리는 ‘Levenshtein distance’ 알고리즘이다.
간단히 개념만 설명하면,
A라는 문자묶음과 B라는 문자묶음를 비교하면서 가장 조금 편집해서 서로를 동일하게 만들 수 있는 점수(최소 편집 거리)를 구하는 방식이다.
편집이란 개념은 우리 모두 알듯이 추가(Add), 편집(Edit), 삭제(Delete)하는 방식을 모두 포함한다.
고민해보시길~ 알고리즘만 찾아보고 이를 가지고 직접 이것저것 시도하면서 즐거움을 누려보시길(나처럼 주말을 날리시길)
끗
나는 저 편집 거리 알고리즘을 사용하지 않았다. 문제에 걸맞는 접근이 아니었기에… 그래서 직접 알고리즘을 고민해서 만들었다. 사실 알고리즘을 만들었다고 하기도 뭐하지만, 비교의 과정에서 발생하는 정보들을 재활용할 수 있는 방법을 계속 고민했고, 그 과정을 최소화할 수 있도록 했다. 1만개 데이터를 상호 비교하고 이를 유의미한 결과로 내는데 길게는 80초에서 짧게는 20초정도 걸렸다. js 기준… 해당 과제는 프론트엔드에서 이를 구현하는 과제였기에 나는 프론트엔드에서 작업한 코드도 작성하다가 분석만 담당하는 Express 서버를 하나 띄워두고 일을 전달하고 작업을 하도록 했다. 프론트엔드의 기술력 + 알고리즘적 문제해결 능력에 대해 묻는 질문이지 않았나 싶다.