아니 이게 왜 됨? (백준 1067) (Feat. Pragma)

1년 전에 이동(백준 1067) 문제를 처음 접했을 때 시간복잡도를 생각하지 않고 막 구현해서 시간초과가 났던 기억이 있었습니다. 그때는 코딩에 막 입문했던 시기라 FFT가 뭔지도 몰랐기도 하고, 시간복잡도를 고려하는 습관도 잘 없던 시기라 그냥 맞왜틀만 외치고 있었습니다.

 

결국 이동 문제를 버리게 되었습니다. FFT를 써먹을 일이 있겠냐는 마인드로 1년 넘게 그 문제를 안 건드렸었는데...

저희 학교에 푸리에 변환을 공부한 친구가 있어 그 친구와 함께 FFT를 공부하고 오랜만에 다시 한 번 이 문제를 건드려보았습니다. 

 

여러 온라인 소스들도 다 찾아가보면서 FFT의 코드 한 줄 한 줄을 최대한 이해하려해보고, 좀 더 수학적인 측면으로도 접근하기 위해 카라추바 알고리즘도 공부해보았습니다. (뭐 결국에 이 문제 풀 때 사용하지는 않았다만)

 

그렇게 학교에서 약 1달간 FFT만 죽도록 알아보며 결국 1년만에 1067번 이동을 드디어 풀게 되었습니다.....만

다른 분들은 FFT를 어떻게 구현했는가 보려고 다른 분들 코드도 찾아보고 그랬는데 희안하게 FFT를 구현안하고도 푸신 분들이 꽤 있더라구요. 어떻게 그게 가능한거지

 

FFT를 사용하지 않고 푸신 분들은 Pragma를 이용해서 시간을 간추린 것으로 보였습니다. 저도 평소에 pragma를 쓰긴 썼었으나, 단순히 코드 속도가 빨라진다는 거만 알았지 정확한 원리는 모르고 있었습니다. 아무리 빨라봤자 이게 얼마나 빨라지겠어라고 생각했었지만, FFT 문제를 뚫는 것으로 이것이 얼마나 빠른 것인지 깨닫게 되었습니다. 지금까지는 대회 알고리즘 유형들만 공부하고 그랬었는데, 이걸보고 정확히 프로그램이 어떤 식으로 돌아가는지, 혹은 언어 별 특징이라던지 그런 것도 공부하는 게 엄청 중요하다는 사실을 느끼게 되었습니다. 

3시간 전 코드가 FFT써서 푼 것, 39분 전 코드가 pragma만 써서 푼 것

 

혹시나 이 글을 읽으신 분들 중에 pragma의 원리를 잘 아시는 분이 계신다면 댓글 한 번만 부탁드리겠습니다. 제가 알고리즘 위주로만 공부했다보니, 프로그래밍 언어의 기본, 컴파일의 원리 등을 잘 모르기 때문에 직접 구글에 검색해서 찾아보았으나 혼자 이해를 하는데에는 무리가 있었습니다. 

 

오늘도 코딩에게 벽을 느끼네요. 벽을 만날 때마다 갈 길이 멀다는 느낌도 있지만, 몰랐던 것을 알 때마다 그 재미와 성취감도 있어서 코딩에 맛 들린 것 같습니다. 

 

곧 있을 IGCSE 시험 때문에 많이 바빠져서 백준 문제 코드 풀이나 해설을 잘 안올렸었는데, 나중에 FFT를 조금 더 공부하여 타인에게 완벽하게 설명해줄 수 있는 실력이 되었을 때 이 문제도 한 번 올려보도록 하겠습니다.