개발 정보/Data Structure (6) 썸네일형 리스트형 [Sorting Algorithms] Quick Sort (퀵 정렬) Sorting Algorithm의 끝판왕이 등장했다.정말 정말정말정말정말정말 꼭 알아둬야 한다. 실제로 이놈 덕을 본 적이 있다.온라인 알고리즘 문제풀이 사이트에서 어떤 문제를 풀던 중, 해결 과정에서 정렬이 필요한놈을 만났다.여기서 시간초과 오답이 꼭 발생하게 됐는데, 정렬을 Quick Sort로 바꿔 드디어 정답으로 인정됐다.실제 Youtube 동영상 이나 많은 참고 글을 보면 얼마나 효율적이고 빠른지 나와있지만, 직접 체감하기는 그리 쉽지 않다.하지만 이 문제를 풀어보면서 그 위력을 느꼈다.웬만한 알고리즘 문제에서 정렬이 필요할 땐 꼭 Quick Sort를 사용해야 할 것이다.그렇지 않으면 시간초과에 걸릴 확률이 매우 높다!! 참 얼마나 빠르면 이름까지 퀵소트일까 싶다.하지만 간단하게 알고리즘만 살.. [Sorting Algorithms] Merge Sort (합병 정렬) 필기시험에서 나를 괴롭혔던 바로 그놈이다.아직도 그때만 생각하면 이불킥중. Merge Sort는 분할정복법, 재귀를 떠올리면 된다.커~~다란 배열을 반씩 반씩 쪼개서 조각조각 정렬을 한 뒤 합치는 정렬법이다.쉽게 말해 분할 - 정렬 - 병합 세 단계로 나뉜다. Merge Sort에는 딱히 Target Index라고 칭할만한 대상이 없다.일단 쪼개는게 우선, 그리고 이를 정렬하고 다시 병합하는 과정에서 Target Index가 필요하다.결국, Merge Sort 구현의 핵심은 '병합'에 있다. 기준은 크기(길이)가 1이면 Sorted 상태로 간주한다.쪼개는 과정은 재귀호출로 해주면 되기 때문에 구현이 매우 쉽다.[0][1][2][3][4][5][6]53171194Array's Size / 2 의 크기로 쪼.. [Sorting Algorithms] Bubble Sort (버블 정렬) 사실 포스팅을 Bubble 정렬부터 하려고 했다.워낙 정렬법이 명확하고 간단해서 많은 Sorting중에 내가 가장 먼저 깨우친 알고리즘이기 때문이다.(Insertion Sort가 Bubble 스럽게 동작하기도 하고..) 여튼 Bubble Sort는 Bubble의 특성을 생각하면 된다.이름에 관해서는 다들 알아서 유추하는 것 같다.뭐 거품이 연달아서 붙어있는것처럼 생각하면 된다는 사람도 있고,버블이 위로 송송 떠오르는 모습을 상상하라는 사람도 있고.....뭐 썩 와닿진 않지만 그렇다고 한다.그냥 뭔가 정렬 알고리즘을 보면 버블버블한 느낌(?)이 들긴 한다. Bubble Sort는 Target Index인 나를 다음 Index와 비교해 자리를 찾아가는 정렬법이다.그 찾아갈 자리는 다음 Index가 나보다 큰.. [Sorting Algorithms] Insertion Sort (삽입 정렬) 이론에만 몰두하다보면 항상 겪는 문제가 있다.바로 머리로는 되는데 실제 구현에서 '어.. 이거 어떻게 해야되지..?'라고 멘붕에 빠지는 경우가 가끔 있다.나에겐 Insertion Sort가 그랬다. 이론적으로 Insertion Sort는 Target Index인 나를 적절한 위치에 삽입하는 것이다.그 적절한 위치는 왼쪽 Index가 모두 나보다 작은 위치이다.오른쪽 Index를 고려하지 않는 이유는, - 오른쪽은 정렬되기 전의 Index들이며 - 정렬하는 동안 순차적으로 나와 왼쪽 Index들만 비교할 것이기 때문이다. 나의 위치는 0번째 index부터 시작해 1회전을 끝낼때마다 1씩 증가한다.[0][1][2][3][4][5][6]531711943 < 5 이므로 자리를 교환한다.35171194------.. [Sorting Algorithms] Selection Sort (선택 정렬) 처음에는 Selection과 Insertion을 구분하지 못했다. (이게 다 겉핥기로 공부하면 이렇게 된다.) 각 정렬 알고리즘은 모두 이름을 보면 대부분 그 방법을 유추할 수 있다.Selection Sort는 말 그대로 Index 중 하나를 선택해 나와 자리를 바꾸는 것이다.(정렬 대상인 Target Index를 나라고 표현하겠다.) 그 선택의 대상은 최솟값(minimum)이다. 나의 위치는 0번째 index부터 시작해 1회전을 끝낼때마다 1씩 증가한다.[0][1][2][3][4][5][6]53171194 13571194----------------------------------------- 1회전 끝 ------------------------------------------예를 들어, 주어진 위의.. [자료구조] Sort (Selection, Insertion, Bubble, Merge, Quick) - 다섯 가지 기본 정렬 알고리즘 Selection Sort (선택 정렬)Insertion Sort (삽입 정렬)Bubble Sort (버블 정렬)Merge Sort (합병 정렬)Quick Sort (퀵 정렬) 어느 기업 신입공채 필기시험에서 정렬 관련 문제가 나온적이 있다. 각 정렬 알고리즘별로 방법과 그 과정을 이해하고 있으면 누구나 쉽게 해결할 수 있는 보너스 수준의 문제였다.너무나도 쉽게 문제를 풀던 중 'Merge'라는 아이가 눈에 들어왔다.순간 '이게 뭐더라?'라는 생각이 들었고, 잠시 당황했지만 침착하고 뒤의 문제부터 해결한 뒤 다시 돌아와그 단어를 한참 쳐다봤다.결국 그놈을 이해하지 못하고 시험을 마쳤다.(심지어 Merge라는 단어의 뜻만 알아도 풀 수 있었을 거다.) 이런 기본적인 문제도.. 이전 1 다음
