Week 09 알고리즘 공부 기록 [고속 푸리에 변환]

12.30 ~ 01.05

 

고속 푸리에 변환 (FFT)

 

이번주는 PintOS 프로젝트 2가 진행중이다. 다음주 화요일까지라 아직도 하고 있다.

목요일에 부스터샷 맞은 뒤 3일밤낮을 뻗어서 아무것도 못하다가 월요일이 되어 강의실에 오니, 프로젝트 2의 방대한 구현량과 난이도에 숨이 턱 막혔다. 매일매일 하고 있지만 일주일이 지난 아직까지도 반도 못했다는 느낌이 든다.

 

알고리즘에 많은 시간을 투자했다가는 멸망각이 보이는 상황이라 이번주는 전부터 익히기로 맘먹고 있었던 FFT 딱 하나만 파보기로 맘먹었다. 하루 날잡고 FFT 이론을 보고, 로직을 쭉 읽어가며 파이썬 코드로 구현해 라이브러리를 만들었다. 시작하기 전엔 쫄았지만 푸리에 변환 자체는 학부때 배웠던 거라 의외로 머리에 잘 들어왔던 것 같다.

그 후로는 하루에 몇문제씩 FFT 태그가 달린 문제를 풀기만 했다.

 

PS를 풀다보면 심화 알고리즘의 탈을 쓰고 있지만 이름만 들어도 엄청 유용해보이고, 몰랐다가는 개발자로서 인생을 손해볼것같은 알고리즘이 몇 있다. KMP나 아호코라식 같은 문자열 관련 알고리즘, 데이터관리의 효율에 직결되는 자료구조, 쿼리의 처리 효율을 높여주는 각종 로직과 테크닉 등. FFT도 그중 하나였는데, 늦게나마 배워서 기분이 좋다. 아직 깊게 응용할 실력은 안되지만, 기초를 배워둔것만으로도 언젠가 문제가 발생했을 때 'FFT를 쓰면 개선되겠다'라는 연상의 키가 되니 도움이 될 거라 믿는다.

 

다음주의 목표는 아호코라식이다. 여러개의 패턴을 트라이로 한데 묶어 이 트라이에 대해 KMP를 실행하여 텍스트에서 한번에 여러개의 패턴을 찾게 해주는 굉장한 알고리즘인데, 이것도 FFT처럼 검색하다가 개요를 본 순간부터 반드시 익혀야한다고 판단한 알고리즘이다. 그냥 배워두기만 해도 금지어 필터링 등등 실제 개발에서 온갖데에 응용할 수 있을거란 느낌이 든다.

 

여기까지 배우고 나면 꼭 배워야겠다고 점찍어둔 알고리즘은 다 배우게 되고, 아호코라식 몇문제를 풀면 목표였던 다이아도 아마도 찍을 것 같다. 이후에는 대재앙 핀토스 후반부가 기다리고있고 코테 준비도 해야하니 실전 위주의 S~G문제들을 풀며 문제해결력을 높일 생각이다.