정렬별 시간복잡도를 생각해보자(Bubble Sort, Selection Sort, Insertion Sort, Quick Sort, Merge Sort, Heap Sort, Time Complexity)
Q. 정렬의 종류는 무엇이 있을까? 종류들을 나열하고, 간단하게 알고리즘에 대해서 설명하겠다. 오름 차순 정렬 기준으로 설명하겠다. 버블정렬 : 순차적으로 근접한 두 값을 비교하면서, 마지막에 거품(Bubble)처럼 하나의 값을 얻게 된다. 같은 과정으로 하나의 값들을 얻어보면 정렬할 수 있다. 선택정렬 : 선택정렬은 전체의 원소에서 가장 작은 값을 순차적으로 찾아가면서 정렬한다. 삽입정렬 : K번째 원소의 위치를 찾을 때, 1부터 K-1까지는 모두 정렬이 되어 있으므로, K -1번째부터 값을 비교하며 위치를 찾으면서 정렬한다. 퀵정렬 : 피벗을 선택하고, 피벗을 기준으로 왼쪽에는 피벗보다 작은 값이 오른쪽에는 피벗보다 큰 값이 오도록 한다. 재귀적으로 호출하며 모든 원소들을 정렬한다. 합병정렬 : 재귀..
Trie(트라이) 자료구조 정의, 예제 코드
2020 신입 개발자 카카오 블라인드 시험을 치다가, 문자열 처리에 대한 자료구조를 알게 되었다. Trie 자료구조에 대한 다음과 같은 모습으로 생겼다. 위에 보면, APPLE, LABLE, CABLE이라는 단어를 넣은 것이다. 왜 굳이, Trie 자료구조를 사용해야 하는지를 생각해보자. 특정 문자열을 벡터에서 순차적으로 탐색하면, 최대 문자열의 갯수만큼 걸리게 된다. 하지만 Trie 자료구조를 사용하면, 문자열의 길이만큼의 탐색 시간이 걸린다. 즉, 많은 문자열속에서 특정한 문자열을 찾기 위해서는 Trie만한 자료구조가 없다. Trie 자료 구조를 사용하지 않으면, 카카오 블라인드 2020 기출문제 효율성을 통과할 수 없게끔 설계되어 있다. Trie 자료 구조를 몰랐을 때 사용했던 방법은, 문자열을 일..
