나는개발자니까

6.1 도입 '무식하게 푼다'는 말은 컴퓨터의 빠른 게산 능력을 이용해 가능한 경우의 수를 일일이 나열하면서 답을 찾는 방법을 의미합니다. 이렇게 가능한 방법을 전부 만들어 보는 알고리즘을 완전 탐색 (exhaustive search)이라고 부릅니다. 완전 탐색을 쓰면 어떻게 쉽게 푸는 방법이 없을까 고민할 필요 없이, 무식하지만 훨씬 간편하게 문제를 풀어낼 수 있습니다. 완전 탐색은 더 빠른 알고리즘의 기반이 되기도 하기 때문에 완전 탐색에 대해 잘 익혀둘 필요가 있습니다. 6.2 재귀 호출과 완전 탐색 재귀 호출 우리가 들여다보는 범위가 작아지면 작아질수록 각 조각들의 형태가 유사해지는 작업을 많이 볼 수 있습니다. 예를 들어 완전히 같은 코드를 반복해 실행하는 for 반복문 같은 것이 있습니다. 이..

5.1 도입 간단할 때는 직관적으로 알고리즘을 설계할 수 있지만, 문제가 복잡해지면 이 알고리즘이 문제를 제대로 해결하는지를 파악하기 까다로워집니다. 단위 테스트를 이용해 여러 개의 입력에 대해 프로그램을 실행해 보고 그 답을 점검할 수 있지만, 결국 이 알고리즘이 존재 가능한 모든 입력에 대해 정확하게 동작한다는 사실을 증명할 수 없습니다. 알고리즘을 공부해야 하는 이유 1. 증명이 알고리즘을 유도하는 데 결정적인 통찰을 담고 있기 때문입니다. 결정적으로 알고리즘의 필요한 깨달음이 증명에 담겨 있는 경우가 많습니다. 2. 다른 알고리즘들의 증명을 공부하다 보면 나중에 자신이 설계한 알고리즘의 정당성을 더 쉽게 증명할 수 잇습니다. 이번 Chapter 5에서는 알고리즘의 증명을 이해하기 위한 수학적 기법..

1. 알고리즘의 시작 효율적인 알고리즘을 만들기 위해선 알고리즘의 속도를 측정할 수 있어야 한다. 알고리즘의 속도를 알 수 있어야 더 좋은 알고리즘인지 판단할 수 있기 때문이다. 알고리즘의 속도를 측정하는 방법으로는 각각을 프로그램으로 구현한 뒤 같은 입력에 대해 두 프로그램의 수행 시간을 측정하는것이다. 하지만 단순이 동일한 입력으로 어떤 알고리즘이 빠르다는 것을 단정지을 수 없다. 첫번째, 프로그램의 수행 시간은 사용한 프로그래밍 언어, 하드웨어, 운영체제, 컴파일러 등 여러 요소들이 영향을 미친다. 두번째, 다른 입력값에 대한 프로그램의 수행 시간을 반영할 수 없다. 앞에서 동일한 입력으로 어떤 알고리즘이 빠른지를 판단한다고 했는데, 그 동일한 입력값이 다른 값으로 바뀐다면? 입력의 크기나 특성에 ..

기수 정렬 (Radix Sort) 다른 정렬은 많이 들어보았는데 기수 정렬은 생소하다! 기수 개념 : ?? 기수 정렬 (radix sort) : 낮은 자리수부터 비교하는 정렬 알고리즘이다. 비교 연산을 하지 않아 정렬 속도가 빠르지만 데이터 전체 크기에 기수 테이블의 크기만한 메모리가 더 필요하다. 1. 기수만큼 큐를 이용해 저장공간을 생성한다. 2. 데이터의 1의 자리가 같은 숫자들끼리 저장공간에 넣는다. 3. 저장공간에 저장된 데이터를 순서대로 꺼내 기존 데이터에 덮어쓴다. 4. 데이터의 10의 자리를 기준으로 저장공간에 넣는다. 5. 마지막 자리수까지 정렬의 기준이 될 자리수를 늘리며 정렬한다. (이미지 찾는중...) 기수 정렬 (Radix Sort)의 시간 복잡도 기수 정렬은 데이터의 삽입과 추출..

머지 정렬 (Merge Sort) 머지 정렬 : 원소가 저장되어 있는 배열을 계속 나눠서 길이가 1인 배열을 만들고 정렬하면서 합치는 알고리즘이다. (머지 정렬 = 병합 정렬 = 합병 정렬 모두 같은 말이다.) 머지 정렬 (Merge Sort)의 시간 복잡도 머지 정렬은 이진 트리 형태로 나누기 떄문에 가질 수 있는 최대 깊이는 log n이다. 각 원소별로 합쳤으므로 시간 복잡도는 O(nlogn)이다. 머지 정렬 (Merge Sort)의 구현 public class Main { public static int[] src; public static int[] tmp; public static void main(String[] args) { src = new int[](1, 9, 8, 5, 4, 2, 3, ..

힙 정렬 (Heap Sort) 힙 트리 구조 (Heap Tree Structure)를 이용하여 정렬하는 방법이다. (최대힙 트리나 최소힙 트리를 사용한다.) 1. 내림차순일 경우 데이터를 최대힙으로 구성하고 오름차순일 경우 최소힙으로 구성한다. 2. 최대힙의 경우 루트노드는 해당 트리에서 항상 최대값을 가지고 있으므로 삭제를 반복하면 다음 최대값이 루트노드가 되어 최종적으로 내림차순 정렬이 된다. 3. 반대로, 최소힙의 경우?? 힙 정렬 (Heap Sort)의 시간 복잡도 힙 생성 알고리즘의 시간 복잡도는 O(log N)이다. 전체 데이터의 갯수가 N개이므로 시간 복잡도는 O(N * log N)이다. 힙 정렬 (Heap Sort)의 구현 import java.util.Arrays; import java...

퀵 정렬 (Quick Sort) 퀵정렬 : ?? (말그대로 퀵 정렬은 빠른 정렬 알고리즘이라는 뜻입니다.) 퀵 정렬 (Quick Sort)의 동작 1. 배열의 가장 왼쪽의 숫자를 피벗(pivot)값으로 두고 피벗(pivot)을 기준으로 2개의 배열로 나눈다. 2. 피벗을 기준으로 피벗 왼쪽에는 피벗보다 작은 숫자, 오른쪽에는 피벗보다 큰 숫자를 배치한다. 3. 피벗을 제외한 왼쪽 배열과 오른족 배열을 다시 퀵 정렬을 수행한다. 퀵 정렬 (Quick Sort)의 구현 public class QuickSort { public static void main(String[] args) { int[] arr = {6, 9, 20, 3, 5, 10, 7, 11, 15, 1}; quickSort(arr); } pub..

버블 정렬 (Bubble Sort) 버블 정렬 : 데이터 집합을 순회하면서 집합 내의 이웃 요소들끼리의 교환을 통해 정렬을 수행한다. (데이터를 정렬하는 과정이 마치 물 깊은 곳에서 일어난 거품이 수면을 향해 올라오는 모습과 비슷하다고 해서 버블 정렬이다!!) 1. 현재 배열과 다음 배열이 숫자 크기를 비교하여 더 큰 숫자를 오른쪽에 배치한다. 2. 숫자 크기 비교하여 배치가 완료된 숫자를 제외한 나머지 숫자를 1번과 같은 과정을 거친다. 3. 2번 과정을 반복한다. 글로 이해하려고 하면 어렵지만 직접 그려보면 개념과 코드가 금방 이해된다! 버블 정렬의 시간 복잡도 버블 정렬의 구현 public class BubbleSort { public static void bubbleSort(int[] a) { b..