Base/알고리즘5 퀵 정렬(Quick Sort) 퀵 정렬은 이름처럼 굉장히 빠른 정렬 알고리즘이라고 알려져 있다. 이번 글에서는 이런 퀵 정렬을 어떻게 구현할 수 있는지, 항상 빠르게 작동하는지, 어떤 장단점이 있는지 알아보고자 한다. 퀵정렬? 퀵 정렬은 우선 한 원소를 무작위로 골라 기준으로 삼고, 배열을 분할한다. 그리고 고른 원소보다 작은 것들은 앞쪽으로, 큰 것들은 뒤로 보낸다. 이렇게 배열을 계속해서 분할하고 또 분할하면, 결국 배열은 정렬된 상태가 된다는 것이 퀵정렬의 기본적인 아이디어이다. 배열을 분할하는 기준값을 보통 pivot이라고 하는데, 이 pivot값이 무엇이냐에 따라 시간복잡도가 달라지기도 하기 때문에 이 값은 굉장히 중요하다. 보통은 첫번째 원소를 pivot값으로 설정하지만, 상황에 따라서는 중앙값이나 마지막값으로 두기도 하고.. 2021. 6. 1. DFS(깊이우선탐색) / BFS(너비우선탐색) 그래프를 탐색하는 방법에 깊이 우선 탐색(DFS)과 너비 우선 탐색(BFS) 두 가지가 있다. 말 그대로 '깊이'를 우선시해서 탐색을 하는지, '너비'를 우선시해서 탐색하는 지에 차이가 있다. 아래 그림을 보며 어떻게 달라지는지 한번 비교해보자! DFS (Depth-First Search, 깊이 우선 탐색) 우선 DFS는 기본적으로 최대한 깊이 내려간 뒤에, 더 이상 갈 곳이 없을 때 옆으로 이동하는 탐색 방식이다. 스택(Stack)이나 재귀(Recurse)를 이용해서 구현 가능하다. 스택으로 구현할 때는 모든 노드가 중복없이 딱 한 번씩만 담겨야 하고, 재귀로 구현할 때도 노드 방문 여부를 반드시 체크해서 무한재귀에 빠지지 않게 주의해야 한다. DFS는 모든 노드를 방문하고자 할 때 주로 사용한다. 탐.. 2021. 1. 24. 선형 검색, 이진 검색 (단순 검색 알고리즘) 데이터들을 모아둔 곳에서 원하는 값을 가진 원소를 찾아내는 '검색 알고리즘'을 살펴보려고 한다. 먼저 가장 기본적인 접근 방법인 선형 검색, 이진 검색 두 가지를 알아보자. 선형 검색 (linear search) 선형 검색 알고리즘은 여러 개의 데이터가 들어있는 리스트에서 찾고자 하는 값이 나올 때까지, 처음부터 하나씩 차례대로 검색하는 알고리즘이다. 말 그대로 100개의 데이터 중 찾으려는 데이터가 100번째에 있다면 100개의 데이터를 다 확인해봐야 찾을 수 있는 것이다. 데이터 개수가 늘어날수록 시간도 당연히 오래걸리게 된다는 단점이 있다. 종료 조건 ✔️ Success : 검색할 값을 찾은 경우 if (array[index] === 찾는 값) ✔️ Fail : 검색할 값을 찾지 못하고 배열의 맨 .. 2021. 1. 9. 빅오(Big-O) 표기법 before... 복잡도 (Complexity) 복잡도는 알고리즘의 성능을 나타내는 척도인데, 시간 복잡도와 공간 복잡도로 나눌 수 있다. 시간 복잡도는 속도에 해당하는 알고리즘의 수행시간 분석결과를 말한다. 공간 복잡도는 메모리 사용량에 대한 분석결과를 말한다. 쉽게 설명하면 아래와 같다. ✔️ 시간복잡도 = 얼마나 오래 걸리는가 ✔️ 공간복잡도 = 얼마나 메모리를 차지하는가 빅오(Big-O) 표기법? 빅오 표기법은 알고리즘의 효율성을 평가하기 위한 분석 방법이다. 효율성의 판단 기준은 바로 위에서 설명한 시간 복잡도, 공간 복잡도이다. 보통 실행속도가 메모리 사용량보다 중요하기 때문에 성능을 판단할 때는 시간 복잡도에서 가장 영향력이 큰 부분을 따진다. 빅오 표기법은 기본적으로 '최악의 경우'를 가정.. 2021. 1. 9. 꼬리 재귀 (Tail Recursion) 재귀 자체도 머리 속에 과정을 떠올리려고 하면 굉장히 추상적이라 어렵게 느껴지는데 꼬리 재귀 개념까지 한번에 이해하려고하니 글을 읽는 것만으로는 잘 이해가 되지 않았다. 개발자 도구를 이용해 디버깅해보며 스택이 어떤 식으로 변하는 지도 살펴보고, 내 관점에서 이해한 바를 그림으로도 그려보기도 했다. 덕분에 꼬리재귀가 어떻게 스택오버플로우 문제를 개선할 수 있다는 건지 이해할 수 있었다. 하지만 아직 설명할 부분들이 좀 더 있는 것 같아 내용은 계속해서 수정, 보충할 예정이다. (잘못 알고있거나 보충할 내용이 있다면 알려주시면 감사하겠습니다🙏🏻) 재귀 (Recursion) 꼬리 재귀에 대한 이야기를 하기 전에 '재귀'가 뭔지, 그리고 일반적인 재귀의 위험성에 대해 먼저 간단히만 이야기하고 넘어가려 한다. .. 2021. 1. 8. 이전 1 다음 반응형
