이 글은 7월26일~ 8월6일 2주일동안 자료구조와 알고리즘을 배우며 회고한 글입니다.
간단한 느낀점
약 2주간의 자료구조와 알고리즘 수업이 끝이 났다. 사실 자료구조와 알고리즘에 대해선 학교에서도 수업으로 배운적이 있었지만, 이렇게 기업의 코딩테스트를 위해 문제들을 유형화 시켜서 문제를 풀어본적은 처음이라 익숙치 않아 어려우면서도 직접 구현하고 풀이 과정을 들으면서 재미있었던 시간이었다.
배운 내용
2주간 배운 알고리즘의 카테고리는 다음과 같다.
- 문자열과 해싱
- 1,2차원 배열탐색
- 스택, 큐, 덱
- 투포인터, 슬라이딩 윈도우
- 그리디
- DFS, BFS
- 트리, 이분검색
- 동적계획법
- 최단거리, Trie
문자열과 해싱
문자열과 해싱의 경우 강사님한테 배운것은 문제에서 요구하는 조건을 해결하기 위해 JavaScript에서 제공하는 map이나 set과 같은 자료형들을 사용하여 문제를 푸는 방법에 대해서 그 노하우를 알게 되어서 많이 도움이 되었던 것 같다.
1,2차원 배열탐색
1, 2차원 배열탐색은 말 그대로 배열을 탐색하면서 문제에서 요구하는 답을 도출하는 것인데, 어떠한 방식으로 접근을 하면 좋을 지, 그동안 잘 쓰지 않았던 while문이나 앞으로도 세어보고 뒤에서부터도 세어보는 여러가지 방법들에 대해서 많이 배웠다.
스택, 큐, 덱
스택과 큐, 덱과 관련해선 문제에서 괄호가 나오거나 후위식 연산과 같은 문제 해결방법의 특성에 따라 사용하는 경우와 사용하지 않고 푸는 경우에 대해서 잘 파악해야 할 것 같다. 스택, 큐, 덱을 이용하면서 각각의 자료구조의 특성에 대해서 좀 더 잘 알게 되었다.
투포인터, 슬라이딩 윈도우
이 투포인터와 슬라이딩 윈도우 방식으로 기존에 문제를 풀어본 적이 없고, 사용하는 방법을 몰라서 이중 for문의 방식으로 풀어왔었다. 그러나 이 기법을 사용하여(lt와 rt) 시간복잡도를 훨씬 단축시키는 방법에 대해서 알았고, 아직은 익숙하지 않지만, 좀 더 익숙해질 수 있도록 다른 문제들을 풀면서 사용을 많이 해봐야겠다.
그리디
그리디 기법또한 말로는 많이 들어왔지만 어떠한 경우에 사용해야하는 지, 잘 몰랐는데 그리디 유형의 문제들을 보다보니 특정 조건에서 그 순간 최적의 조건을 선택하여 최종적인 답에 도달하는 것으로 알 수 있었고, 이 또한 문제를 풀면서 그리디 기법에 익숙해 질 수 있도록 많이 연습해야겠다.
DFS, BFS
DFS, BFS의 경우 미로찾기와 같은 대표적인 문제들을 몇몇 봐왔지만 미로가 아닌 조합이나 수열찾기의 경우에도 사용하는 것을 알았다. 또한 DFS를 트리를 그리는 것처럼 재귀를 통해 계속 트리의 레벨까지 내려가 찾는 방법으로 머리속에 기억하니까 되게 신박하면서도 잘 이해가 되었고, DFS와 BFS에 대해서 좀 더 자세히 알게 되며, 어떻게 사용을 하면 좋을 지 잘 알게되는 시간이었다.
트리, 이분검색
수업에서는 트리보다는 이분검색를 많이 풀었었는데, 특정 조건이 주어졌을 때, 최대한, 최소한으로 하는 답을 도출할 때 기존 for문 만으로는 시간복잡도가 크게 증가하지만 이 이분검색을 통해 시간복잡도를 줄이면서 답을 빠르게 도출할 수 있다는 방법을 알게되어서 재미있었다.
동적계획법
동적계획법 또한 학교나 인터넷에서 DP, 다이내믹 프로그래밍으로 많이 들어는 왔었지만 정확히 어떻게 사용하는 지 몰랐는데 수업을 들으면서 가장 중요한 dp배열의 정의를 어떻게 세우는게 좋을 지 대략적인 느낌을 알게되고, 몰랐던 부분을 채울 수 있어서 배우면서 좋았던 것 같다. 또한, knapsack문제들을 보면서 이 또한 dp를 이용하여 접근하고, 중복이 아닌 경우에 거꾸로 dp배열을 채우는 방법으로 해결하여 풀이를 보면서 되게 신기해 하면서도 나중에 이러한 문제가 나왔을 때, 나도 생각할 수 있을 정도로 성장했으면 좋겠다는 생각을 하였다.
최단거리, Trie
최단거리의 경우 앞에 배운 dp를 이용해 문제를 풀었고, 플로이드 와샬 알고리즘에 대해서도 배우며 결국 이 또한 Dp의 한 유형임을 알고 어떤 식으로 접근해야 되는 지 알게되었다. 마지막으로 자동완성이라는 문제를 풀면서 Trie구조를 사용하였는데 이 새로운 자료구조를 알게되고 이용하면서 어떠한 경우에 이러한 자료구조를 사용할 지 생각해보는 시간이 되었다.
앞으로의 계획
2주 동안 알고리즘을 배우면서 매일 데일리 퀴즈를 볼 때에는 그날 배운 유형의 문제가 나왔기 때문에 그 유형을 생각하면서 접근하면 크게 어렵지 않게 문제를 풀 수 있었다. 그러나 마지막에 위클리테스트에서는 이 문제가 어떠한 유형인지 알 수 없었고 자신이 어떠한 방법을 사용하여 문제를 풀지 생각해내야 했는데 이러한 부분이 아직 알고리즘을 많이 풀어보지 않아서 미숙한 것 같다.
따라서 백준과 같은 알고리즘 문제들을 푸는 사이트에 가서 문제들을 많이 보고, 풀어보면서 문제를 보면 "아! 이러한 방법으로 풀면 되겠구나" 라는 생각이 금방금방 나올 수 있게 유형화 시킬 수 있는 나만의 데이터를 많이 쌓아야 겠다는 생각이 들었다.
마지막으로 얼마안된 시간이지만 2주동안 가르쳐주신 김태원 강사님 감사합니다.😀
