사과를 먹을 땐 사과를 먹어요

Heap 힙의 조건 complete binary tree(완전 이진 트리)이며, heap property(min heap 또는 max heap)를 만족 동일한 데이터를 가진 여러개의 힙이 존재 가능 힙에서 각 노드의 위치 H(1..n) 루트 노드 : H(1) H(i)의 부모 : H(i/2) H(i)의 왼쪽 자식 : H(2i) H(i)의 오른쪽 자식 : H(2i+1) 힙은 일차원 배열로 표현 가능 A[0..n] 루트 노드 : A[0] A[i]의 부모 : A[(i-1)/2] A[i]의 왼쪽 자식 : A[2i]+1 A[i]의 오른쪽 자식 : A[2i]+2 Max Heapify (힙 정렬) 왼쪽과 오른쪽 자식 트리가 모두 max heap property를 만족하고, root만이 조건을 만족하지 않을 때, 이 트..

분할 정복법 기본적으로 순환(recursion)을 통해 해결 문제 해결을 위해 아래 세 단계를 거침 분할 : 해결하고자 하는 문제를 작은 크기의 동일한 문제들로 분할 정복 : 각각의 작은 문제들을 순환적으로 해결 합병 : 작은 문제의 해를 합하여 전체 문제의 해를 구함 Merge Sort (합병 정렬) 배열의 크기가 1이 될 때까지 분할 후 합병을 진행하며 정렬된 원래의 리스트 완성 (분할정복법) 구현 두 부분으로 나뉘어 정렬되어 있는 배열을 합쳐가며 정렬된 하나의 배열로 만드는 알고리즘 //이미 정렬된 인덱스가 p에서 q까지인 배열1과 q+1에서 r까지인 배열2를 합치면서 정렬하는 함수 private static void merge(int[] data, int p, int q, int r) { int ..

Selection Sort (선택 정렬) 최대 원소를 찾아 맨 오른쪽 원소와 자리를 바꿈 맨 오른쪽으로 이동한 원소를 무시한채로 위의 루프 실행을 반복 구현 크기가 큰 원소를 오른쪽부터 정렬 크기가 작은 원소를 왼쪽부터 정렬 위의 두가지 방식으로 구현 가능 public class Sort_selectionSort { private static int data[] = {7, 1, 3, 5, 9, 2}; //최대 원소를 맨 오른쪽으로 이동시키며 정렬 public static void selectionSortMax(int[] data, int length) { int max; //값이 최대인 원소 int temp; for(int i=data.length-1; i>0; i--) { //맨 오른쪽 원소부터 왼쪽에..

Maze 아래와 같은 구조의 미로를 나가는 길을 찾는 것이 목표 흰색은 지날 수 있는 길이며, 파란색은 막혀있는 벽 입구는 [0][0]이며 출구는 [N-1][N-1] 구현 무한 루프에 빠지지 않으려면 반드시 base case로 수렴해야함 이 경우에서는 이미 방문한 cell을 표시하여 무한 반복을 해결 public class Maze { /* * 현재 위치에서 출구까지 가는 경로가 있으려면 * 1) 현재 위치가 출구이거나 (base case) * 2) 이웃한 4개의 cell들 중 하나에서 현재 위치를 지나지 않고 출구까지 가는 경로가 있거나 (recursive) */ private static int N = 8; private static int [][] maze = { {0, 0, 0, 0, 0, 0, ..