들어가기 앞서

왜 알고리즘 공부를 하는가?

1. 이미 나는 프로그래머스 문제들을 풀면서 알고리즘을 많이 풀었다. 지금 이글을 작성하는데도 포스팅만 60개 가까이 되어가고 있다. 레벨 0같이 쉬운것들은 정리를 안해놨는데 그것까지 검토해보면 150개 이상정도 문제를 풀었을 것이다.
   코테를 볼때 간단히 공부하려면 그래프 탐색과 그리디 알고리즘에 대해서만 알아도 코테 문제를 거의 풀수 있다고 하여서
   그리디에 대해 알아볼까 하다가 정리가 잘된 곳을 발견해서 공부도 할겸 정리하게 되었다.

2. 알고리즘을 많이 풀었지만 면접에서 알고리즘에 대한 이론에 대해 물어볼때는 전혀 답변하지 못하였다. 문제는 풀수 있는데 탐욕법, 기수 정렬, 등 용어에 대해서는 답변할수가 없어서 정리해보고자 한다. 그리고 정리를 하기 전에 한번 쭉 읽었는데 몇가지 정렬 방법에 대해 이런식으로 접근할수도 있구나 라는 접근법을 배울수 있어서 도움이 될것이라고 생각되어 정리를 하게 되었다.

3. 면접을 볼때 알고리즘 많이 푼것을 가지고 이렇게 할정도면 백엔드도 지식이 좀있는줄 알고 있다. 하지만 왜 알고리즘을 하게 되었냐면 현업을 할때에도 코드리뷰, 리팩토링 을 할때 내장함수 여럿을 가지고 변경한 바가 있다. map함수만 알고있을때 map만사용했는데 reduce라던지 filter 등 코드의 양도 줄일수 있었고 다른 사람들의 풀이를 보면서 새롭게 접근한 방식을 배우고 공부하면서 다양하게 접근할수 있는 방법을 배웠기 때문이다. 왜 공부하는지에 대해서 여러가지가 있지만 이것 때문에 알고리즘을 여태껏 풀어왔다고도 말할수 있을것 같다.

출처

공부는 제로초님의 사이트에서 알고리즘 정리를 깔끔하게 정리를 잘해둔것 같아서 보고 공부할수 있었다.
나는 이론 정도만 정리하고 코드로 설명해주셨는데 var로 문제를 풀어서 이를 let으로 적용할수 있을지에대해서 다시한번 	코드를 짜면서 검토해볼 생각이다. 

공식 주소는 이것이다. https://www.zerocho.com/category/Algorithm?page=2

우선 첫장이니 간단하게 자료구조의 기본과 복잡도에 대해서 정리해보도록 한다.

시간 복잡도

시간 복잡도는 알고리즘을 수행하는데 평균적, 또는 최악의 경우 얼마만큼의 시간이 걸리는지 보여준다.
복잡도는 주로 빅오 표기법을 사용해서 나타낸다.

주로
O(1),O(logN), O(N), O(NlogN), O(N^2), O(N^3), ..., O(2^N), O(N!) 이런 식으로 사용되고

오른쪽으로 갈수록 안좋은 알고리즘이다.

만약 100개를 정렬할 경우 로그(NlogN)의 경우에는 4.6초 N^2일 경우는 100초가 걸린다.
하지만 많은 자료일수록 더 걸린다.

그래프로 표현하면 아래와 같은데

기울기가 가파를수록 성능이 좋지 않다.

자료구조

자료구조는 데이터의 표현 및 저장 방법을 의미한다.
알고리즘은 그 저장된 데이터를 처리하는 과정이다.

배열이 자료구조 중 하나이다. 연결리스트, 스택, 큐 등이 있는데 자바스크립트의 배열은 이기능을 각각의 함수를 사용해서 표현할수 있다.

연결리스트는 여러개의 노드로 이루어져 있다. 각각의 노드는 데이터와 다음 노드가 무엇인지 알려주는 주소를 가지고 있다. 연결리스트는 새로운 데이터를 추가하거나, 위치를 찾거나, 제거하는 기능이 있어야 한다.

배열로 나타내면 배열[1,2,3,4,5] 에서 1,2,3,4,5가 데이터이고 인덱스로 위치를 말해준다.
각각 하나가 노드이고 인덱스가 주소인것 같다. push()함수와 slice()함수등 제거 및 삽입등의 기능을 가지고 있다.

제로초님의 사이트에서는 직접 자료구조를 만드는 것을 코드로 구현한것이 있다. 클래스로도 구현한것을 유튜브 강의로 봤었는데 더 공부하려면 어떻게 구현되는지 알아야 할것도 같다.

나는 클래스 같은것으로도 구현한것을 확인해서 한번 쭉 훑어보고 패스하였다.

출처 제로초님의 자료구조