*매우 주관적인 견해임을 밝힙니다. 정답은 없으니까...
안녕하세요. F-lab에서 오프라인으로 코딩테스트 스터디를 진행하면서 다른 분들보다 조금이라도 문제를 많이 푼 경험이 있어, 삽질을 한 경험을 공유드려 이제 막 코테, 언어, 자료구조 공부를 시작하시는 분들에게 조금이나마 저와 같은 실수를 하지 않기를 바라는 마음에 글을 작성하게 되었습니다.
백준과 프로그래머스 문제를 합쳐 700문제 가까이 풀었습니다. 정말 많이 푼 것 같지만 저는 작년에 카카오 공채, 소마 2 차코테, 이베이 등등 수많은 코테에 떨어진 경험이 있습니다.
Q) 왜 떨어졌을까요?
A) 문제만 많이 풀면 될 줄 알았고, 알고리즘의 원리나 자료구조에 대해 정확히 파악을 하지 못하고 무작정 생각과 동시에 코드를 작성하려고 했습니다.
그러면 코테 공부 어떻게 해야 하면 좋을까?
문제 하나를 예시로 들면서 설명을 해드리겠습니다. 문제를 읽어보고 어떻게 풀지 잠깐 생각을 해보시면 좋을 것 같습니다.
생각을 해보셨을테니까 여러분들은 이 문제를 어떻게 풀려고 하셨나요?
글을 읽고 계시니까 머릿속으로만 생각을 하셨을 것 같습니다. 그 생각들을 노트에 적으면서 풀려고 많이 노력하셨나요?
그렇게 하지 않으셨다면 코드작성보다 먼저 노트에 본인의 생각을 정리하면서 1. 논리적인 흐름을 완성하려고 시도해 보세요.
저 같으면 노트에 아래와 같이 표현을 했을 것 같습니다.
그 전에 제한사항으로 N, K 가 최대 10만으로 주어졌으니 2중 for 문으로 접근하는 논리는 배제하고 생각을 해볼 수 있겠네요!
O(10만 * 10만) = O(100억) 이 되므로 10초가 걸리는 연산이 되어버리겠네요. O(1억) = 1초 라고 생각하면 될 것 같습니다.
그림을 보면 그래프의 모양이 그려졌습니다. 그렇다면 여기서 어떤 알고리즘을 써야 할까요?
동생의 위치를 탐색해야 하니까 "그래프 탐색을 위한" 알고리즘 BFS/ DFS를 생각해 볼 수 있을 것 같습니다.
우선 DFS로 탐색을 해본다고 가정을 하면 맨 위 3초에서 동생의 위치를 찾겠지만 해당 지점이 최단임을 보장하지는 못할 것 같습니다.
그러면 BFS로 탐색을 한다면 2초에 동생의 위치를 찾게 되고 해당 지점이 가장 빨리 찾는 지점이 될 것 같습니다.
논리적 흐름이 완성되었으니 2. 어떤 자료구조가 필요할까요? BFS는 보통 선입선출 방식인 Queue 자료구조를 사용하니까 해당 방법으로 구현하게 되면 자연스럽게 먼저 들어온 것이 먼저 나가게 되니까, 가까운 지점부터 탐색을 하게 되겠네요.
3. 시간복잡도를 계산을 하면 문제에 주어진 제한시간 2초라서 O(N * 3 [방향])으로 O(30만)이라서 안정적으로 풀 수 있을 것 같습니다. 이제 4. 코드를 작성하시면 됩니다.
정리해 보면
1. 논리적 흐름 완성하기
2. 필요한 알고리즘, 자료구조 선택
3. 시간복잡도 계산 (검증)
4. 구현
흐름이 완성되지 않고 잘못된 방법으로 코드를 먼저 구현을 한다면, 그 코드가 제대로 통과되지 못할 경우에 잘못된 방법으로 짠 코드만 바라보게 되어 시야가 좁아져 다른 방법을 떠올리기 되게 어려울 겁니다.
지금은 BFS/DFS 의 예시로 들었는데 모든 문제에 해당 방법을 적용 시킬 수 있습니다.
단, 알고리즘의 이론을 처음 공부할때 해당 알고리즘의 원리가 무엇인지, 어떤상황에 쓰이는지 정확히 숙지를 한다면 논리적흐름을 완성하는데 정말 많은 도움이 될 것입니다. 이론이 지루하다면 먼저 해당 알고리즘의 기본문제 3개정도 풀어보면 감을 숙지하기 좋습니다.
처음에 이 방법대로 연습을 하게되면 코드작성을 늦게해서 문제를 풀지 못하는게 아닌가? 라고 생각이 들수있습니다. 사실 논리적 흐름이 완성되고 검증되면 코드 구현은 얼마 걸리지 않습니다.
따라서 위의 흐름대로 연습을 해보는 것을 적극 권장 드립니다.
자료구조 공부, 언어 공부는 코테 공부하면서 같이 할 수 없을까?
여기서 말하는 공부방법은 처음에는 정말 시간이 오래 걸리는 공부방법이지만 기억 속에 많이 남게 되는 공부방법이라 생각합니다.
예시를 하나 가져오겠습니다. 코딩테스트를 풀다 보면 정렬을 정말 많이 사용합니다.
Arrays.sort();
Collections.sort();혹시 두 정렬방법의 차이를 알고 계신가요?
간단하게 생각하면 배열과 컬렉션의 차이라고 생각할 수 있을 것 같습니다.
틀린 대답은 아니지만, 어떤 방법으로 구현되어 정렬이 되고 시간복잡도는 얼마나 나오는지 궁금하지는 않으셨나요?
문제를 많이 푸는 것도 좋지만, 더 나아가서 꼬리를 무는 생각을 하는 과정도 중요하다고 생각합니다.
내부를 보면 Dual-Pivot Quicksort 를 사용한다고 적혀있습니다. 모든 데이터 셋에서 O(n log(n)) 을 보장하기 때문이라고 적혀있습니다.
[꼬리] 그렇다면 왜 Quicksort 를 사용하지 않은 이유는 무엇일까?
-> Quicksort 는 최악에 상황에서 O(n^2)의 성능을 내기 때문에 Dual-Pivot Quciksort 보다 좋지 못합니다.
[꼬리] 그럼 Collection.sort() 도 내부적으로 QuickSort 를 사용할까?
-> 직접 확인을 하러 가겠습니다.
-> 내부적으로 list.sort를 사용하여 구현하고 있습니다. 들어가 보겠습니다.
-> List에서 제공하는 default 메서드 sort를 보니 TimSort를 사용한다고 적혀있습니다.
[꼬리] 그렇다면 왜 Collection 은 Dual-pivot quick sort 를 사용하지 않았을까? TimSort는 무엇일까?
-> Dual-pivot quick sort는 primitive data types(int, doulbe) 에 적합하고 효율적이기 때문입니다.
반면 Timsort는 Merge sort와 insertion sort를 합친 정렬 알고리즘으로 정렬되는 데이터의 특성에 맞게 조정하여 최적의 성능을 제공할 수 있습니다. 최악의 경우 O(n log(n)) 을 보장하는 알고리즘입니다.
[꼬리] Timsort는 어떤 점이 좋을까?
-> 네이버 D2 발표자료를 참고하면 CPU의 참조지역성(Locality of reference) 원리를 잘 만족하도록 구현이 되어 있음을 알 수 있습니다.
땅굴을 파면서 오다보니 운영체제 까지 도달했습니다. 평소 CS에 흥미를 느끼지 못했다면 이런 부분에서 흥미를 느낄 수 있지 않을까요.
[꼬리] 돌아와서 Sort 메서드를 보니 Comparator를 매개변수로 받는데 Comparator는 뭘까?
-> 함수형 인터페이스로 1개의 추상메서드를 갖는 인터페이스를 지칭합니다.
[꼬리] 1개의 추상메서드를 갖는다고 했는데 스크롤을 내려보니 3개의 메서드가 있습니다. 왜일까요?
-> 해당답을 모르신다면 이 부분 부터는 직접 찾아보시면 좋을 것 같습니다.
코테를 공부하다 정렬에 대해서 알아보려 했는데 스스로에게 왜? 라는 질문을 던져보니 CS 레벨까지 공부 할 수 있습니다.
여태 눈으로만 공부하던것이 실제로 이렇게 활용되어 구현이 되었구나 더 흥미도 느낄 수 있습니다.
이렇게 땅굴을 파는 학습을 한다면 특정 자료구조를 선택했을 때 어떻게 구현되어 있는지, 어떻게 동작하는지 잘 알고 있기 때문에 선택의 근거가 더 명확해질 것입니다. 코테뿐만 아니라 실제 작업할 때도 이와 같은 사고가 큰 도움이 될 거라 저는 생각을 합니다.
시간은 오래 걸리지만 이렇게 공부를 하면 다시 돌아와도 빠르게 익힐 수 있기 때문에, 점점 더 가속도가 붙으면서 공부를 할 수 있을 거라고 생각을 합니다.
이 방법의 단점이 있다면 정말 많은 땅굴을 파다가 적당히 끊어내기 어려울 때가 있습니다. 시간과 비용이 많이 들어가는 작업이기에 스스로 적절하게 끊는 판단하는것도 중요합니다.
맨 처음 말한 것처럼 공부방법에는 답이 없다고 생각을 하며, 제가 많은 삽질과 배움을 통해 터득한 방식입니다.
좋은 점들만 가져가셔서 저보다 더 좋은 학습방법을 만들어 초반에 올바른 방향으로 나아가도록 하셨으면 하는 생각에서 이 글을 작성하게 되었습니다.
긴 글을 읽어주셔서 감사합니다.
Contact : audrn6689@gmail.com
'끄적끄적' 카테고리의 다른 글
| [소소한 팁] 인텔리제이 Commit 창 분리 되었을때 해결 방법 (2) | 2022.11.28 |
|---|---|
| 2021년 회고 (0) | 2021.12.31 |