행그

Goal 정렬 알고리즘 중 Merge Sort 에 대해 알기 Merge Sort의 장· 단점 시간 복잡도 이해하기 자바로 구현할 줄 알기 Merge Sort (합병 정렬) 알고리즘 분할 정복(divide and conquer) 방법 : 작은 2개의 문제로 분리하고, 각각을 해결한 후, 결과를 다시 모아 원래의 문제를 해결한다. 설명 하나의 리스트를 두개의 균등한 크기로 분할한다. 더 이상 분할이 불가능 할때까지 (배열의 크기가 1일 때까지) 계속해서 분할한다. 분할된 부분 리스트를 순차적으로 정렬한다. 정렬된 부분 리스트를 합쳐 전체를 정렬시키는 방법. 구체적 용어 설명 분할(Divide) : 2개의 배열로 분할한다. 정복(Conquer) : 부분 배열을 정렬한다. 순환 호출을 이용해서 분할 정복을 반복..

Goal 정렬 알고리즘 중 Quick Sort 에 대해 알기 Quick Sort의 장· 단점 시간 복잡도 이해하기 자바로 구현할 줄 알기 Quick Sort (퀵 정렬) 알고리즘 ★분할 정복(divide and conquer) 방법 작은 2개의 문제로 분리하고, 각각을 해결한 후, 결과를 다시 모아 원래의 문제를 해결한다. 설명 리스트 안에 한 요소를 선택 - 선택한 요소를 피벗(pivot)이라고 한다. pivot을 기준으로 작거나 큰 요소의 위치를 옮긴다. pivot 기준으로 왼쪽 : pivot 보다 작은 요소 pivot 기준으로 오른쪽 : pivot 보다 큰 요소 pivot을 제외한 왼쪽 list와 오른쪽 list를 재 정렬한다. 분할한 부분 리스트(왼쪽, 오른쪽) 에 대해 다시 pivot을 정한다...

Goal 정렬 알고리즘 중 Insertion Sort 에 대해 알기 Insertion Sort의 장· 단점 시간 복잡도 이해하기 자바로 구현할 줄 알기 Insertion Sort (삽입 정렬) 알고리즘 "순서대로 뽑고, 적당한 위치에 삽입" 배열의 모든 요소를 왼쪽의 모든 요소들과 비교하여 지정 자리에 자료를 삽입하면서 정렬하는 알고리즘. 아래 예시를 통해 이해해 보자. 기억★ 두번째 data 부터 시작할 것 PASS 1 - 왼쪽 값과 오른쪽 값을 비교한다. 왼쪽 데이터 값과 오른쪽 데이터 값(처음 상태: 두번 째 data 값)을 비교한다. 왼쪽 데이터 값이 더 크다면, 오른쪽 값과 비교한다. 왼쪽 데이터 값이 존재하지 않을 때까지, 비교 후 삽입 반복 왼쪽에 데이터가 더이상 존재하지 않는다면, 현재 상..

Goal 정렬 알고리즘 중 Bubble Sort 에 대해 알기 Bubble Sort의 장· 단점 시간 복잡도 이해하기 자바로 구현할 줄 알기 Bubble Sort (버블 소트) 알고리즘 두개의 값을 계속 비교해 나아가면서 값을 정렬시키는 알고리즘이다. 아래 예시를 통해 이해해 보자 PASS 1: 왼쪽 값과 오른쪽 값을 비교한다. 왼쪽 값이 오른쪽 값보다 더 크다면, 두 개의 값을 바꾼다. PASS 2: 다시 배열의 처음으로 가서 이를 계속 반복한다. Bubble Sort (버블 소트) 의 장 · 단점 장점 : 구현이 단순하다. 단점 : 가장 왼쪽에서 가장 오른쪽으로 이동하기 위해서는 배열의 모든 요소들과 교환이 이루어져야한다. 교환하는 것보다 이동 작업이 더 많기 때문에 거의 쓰이지 않는다. Bubble..

Goal 정렬 알고리즘 중 Selection Sort 에 대해 알기 Selection Sort의 장· 단점 시간 복잡도 이해하기 자바로 구현할 줄 알기 Selection Sort (선택 정렬) 알고리즘 데이터 중에서 가장 작은(가장 큰) 데이터를 선택해 현재의 데이터와 위치 교환하는 방식 아래 예시를 통해 이해해 보자 PASS 1 - 주어진 배열 중에서 최솟값을 찾는다. PASS 2 - 현재 위치 값과 Min 값을 SWAP 한다. 가장 작은 데이터 (Min)값이 배열의 맨 앞자리로 이동했다. 그렇다면 배열의 첫번째 데이터는 최솟값 고정이므로 현재 위치(ptr) 를 다음 index로 이동시킨다. PASS 3 현재 위치를 다음 index 로 이동시키고, 남은 데이터들 중에서 다시 Min 값을 찾는다. PAS..