백준풀때 궁금한 점이 있습니다

안녕하세요 백준 플래까지 했었던 사람입니다. 저도 비슷한 생각을 했었는데요, merge, quick 중 하나 잡아서 외워질 때까지 정의해서 사용하는 거 추천드립니다. 그 다음 다 외웠다 싶으면 내장 함수 쓰시구요. 이유를 말씀드리겠습니다. 1. 어찌되었든 정렬은 기본 알고리즘으로 아는 것에 의의가 있습니다. 알고 쓰는거랑 모르고 쓰는거랑은 다르니까요. 2. 또한, 위에 말씀드린 것들은 대표적으로 NlogN이 걸리는 알고리즘으로 시간복잡도 이해에 도움될 것입니다. 3. 그리고, 머지, 퀵 소트는 분할 정복 개념이 사용되어서 그 구조를 잘 익혀 두면 나중에 비슷한 문제(median of median, closest pair)를 이해하는데 도움이 될 것입니다. 질문자님께서 알고리즘 수업을 듣지 않으셨다면 나중에 들으실 때 큰 도움 되실거에요 제가 그랬거든요.

전 취준생에 골드1밖에 안되지만... 참고하시면 좋을 부분이 있습니다. 저도 많이 고민했던 부분인데, 앞서 말씀해주신 분들처럼 직접 구현해보면 당연 좋은부분이 많지만 현실적으로 재미없는 부분이라 진짜 꼼꼼히 하는 사람은 드문거 같아요. 하지만 공부 해두면 당연 도움되겠죠! 코테 측면에서 보면 구현 되어있는 라이브러리를 잘 쓰는게 더 중요하다고 보일 수도 있습니다. 하지만 생각보다 라이브러리가 효율적이지 않을 수도 있습니다. 내가 필요로한 부분보다 더 추가적인 변수와 메서드들이 잡혀있어 메모리가 부족해지거나 느려질 수 있습니다. 이런 부분들을 노리고 일부러 상용 라이브러리를 썼을때 터지는 문제들도 종종 본 것 같아요. 정확하진 않지만 java에서 스택 자료구조는 간단한 구조인데 라이브러리가 효율이 나빠서 꼭 직접 구현하라는 팁도 받은적 있습니다. 트리같은 링크드리스트 등도 전 웬만하면 직접구현하는 하려구해요. 잡설이 길었는데, 전 시간도 되시고 욕심이 있으면 직접 몇번 해보시는걸 강추드려요! 파이팅입니당🙂

백준을 푸는 것이 도움이 되긴 하지만 취업을 해보니 함수를 아는 것은 크게 상관이 없었습니다. 함수는 자기자신이 만들어 사용하게 되고 이를 정의하는데에 있어 쓰는 low level 코드에 사용하는 함수들은 구글링을 합니다. 또한, 래핑하여 가독성 좋게 코드를 구조적으로 설계하는 것이 중요합니다. 예를 들어 statemachine 구조라는 것이 있습니다. 먼저 간단한 프로젝트 하나를 정해 본인만의 함수로 구성하여 설계 해보시는걸 추천드립니다. 질문과는 좀 다른 답변이지만 입사한지 얼마 되지 않은 신입이로써 코드 공부에 있어 길을 제시해드리고 싶었습니다.

아마 sort가 문제의 대부분을 차지한다면 출제의도가 sort를 구현해보라는 것일 확률이 높습니다. 이런 문제가 면접에 나온다면 출제자에게 sort를 구현하라는 것인지를 직접 확인 해 보시면 됩니다.

개인적으로 머지소트는 구현해보는 게 좋은 것 같습니다. 다른 O(NlogN) 정렬 알고리즘인 퀵소트의 경우 이미 값이 정렬되어 있는 상황이라면 O(N^2)의 시간복잡도를 가질 수 있기 때문에 실제로 구현해서 사용하기는 살짝 비효율적인 면이 있지만 머지소트는 항상 O(NlogN)의 시간복잡도가 보장되고 정렬과정에서 메모리 상으로 비교적 가까운 변수들을 참조하여서 cache hit 면에서도 이득이기 때문이죠. 실제로 python에서 sort 함수의 내부구현을 보면 insertion sort와 merge sort를 혼합한 Tim sort라는 방식의 정렬 알고리즘을 사용하는데 머지소트와 같이 정렬 과정에서 기존 배열과 동일한 크기의 새로운 배열을 만들 필요는 없어서 메모리 낭비를 줄이고 참조 지역성을 개선하여 상수 부분을 최적화한 것으로 알고 있습니다.

제 개인적으로는 sort함수를 사용해서 푸는 것은 별 문제가 없다고 생각합니다