Keep the Experience Natural, Easy, Light

#1 알고리즘#1-1 개요while(문제 해결 안 됨) { 현 시점 가장 좋아 보이는 선택}눈 앞의 이익만 추구(= Greedy(탐욕스러운, 욕심 많은))하는 방식의 접근법을 말한다. 위 코드의 형식을 갖추기만 하면 그리디 알고리즘이라 부를 수 있다. 즉 구체성이 낮은, 추상적인 알고리즘이다. #1-2 최적해(最適解, optimal solution)주어진 문제를 가장 효과적으로 해결하는 최상의 답 또는 해결 방법을 의미한다. #1-3 Yes/No 문제와 최적화 문제예를 들어, "어떤 조건 A를 만족하는 원소 B가 집합 C에 존재하는가?"라고 묻는 문제를 Yes/No 문제라고 한다. 반면 "어떤 조건 A를 만족하는 원소 B의 최솟ㆍ최댓값은 얼마인가?"라고 묻는 문제 즉, "최적해는 얼마인가?"라고 묻..

#1 그래프의 탐색 깊이 우선 탐색 - 위키백과, 우리 모두의 백과사전위키백과, 우리 모두의 백과사전. 깊이 우선 탐색 깊이 우선 탐색의 애니메이션 예시 깊이 우선 탐색( - 優先探索, 영어: depth-first search, DFS)은 맹목적 탐색방법의 하나로 탐색트리의 최근에 첨가ko.wikipedia.org그래프의 각 정점을 한번씩 방문할 필요가 있다고 해보자. 그 방문의 방법에는 크게 2가지 방법이 있다. 하나는 깊이 우선 탐색이다. 또 다른 하나는 너비 우선 탐색이다. 본 게시글에서는 깊이 우선 탐색법을 다룬다. (너비 우선 탐색에 대해서는 이 게시글에서 다룬다) #2 알고리즘원래라면 순서도를 통해 알고리즘을 소개하고 코드로 넘어가는 편이 이해하기 좋지만, 그래프 탐색 알고리즘은 그냥 코드부터..

#1 그래프의 탐색 너비 우선 탐색 - 위키백과, 우리 모두의 백과사전위키백과, 우리 모두의 백과사전.ko.wikipedia.org그래프의 각 정점을 한번씩 방문할 필요가 있다고 해보자. 그 방문의 방법에는 크게 2가지 방법이 있다. 하나는 너비 우선 탐색이다. 또 다른 하나는 깊이 우선 탐색이다. 본 게시글에서는 너비 우선 탐색법을 다룬다. (깊이 우선 탐색에 대해서는 이 게시글에서 다룬다) #2 알고리즘원래라면 순서도를 통해 알고리즘을 소개하고 코드로 넘어가는 편이 이해하기 좋지만, 그래프 탐색 알고리즘은 그냥 코드부터 보는 게 오히려 이해가 더 빠르다고 생각한다. 다만, 인접 배열 (Adjacency Array)의 지식에 대해서는 알고 있어야 한다는 전제 하다. 여기서 사용할 인접 배열은 이 게시글..

#1 그래프#1-1 그래프그래프는 현상이나 사물을 정점(Vertex)와 간선(Edge)로 표현하는 것이다. 정점은 어떤 개체를 나타내고, 간선은 그 개체들 간의 관계를 나타낸다. 위 그림은 각 정점(도시)을 항공편(간선)이 잇는 모습을 표현한 예이다. n개의 정점 집합 V와 이들 간에 존재하는 간선의 집합 E로 구성된 그래프 G를 G = (V, E)로 기술한다. #1-2 가중치가 없는 그래프 vs 가중치가 있는 그래프간선에는 가중치를 줄 수 있다. 항공편으로 비유하자면, 운항비가 가중치가 된다. 가중치가 없는 그래프를 가중치가 있는 그래프처럼 생각할 수도 있다. 모든 가중치를 1로 보면 된다. #1-3 무향 그래프 vs 유향 그래프항공편은 반드시 양방향적이지는 않다. 예를 들어 런던에서 파리를 갈 수 있..

#1 알고리즘#1-1 정의동적 프로그래밍을 한 줄 요약하면 중복의 제거다. 정적(static)이라는 개념과 반대되는 개념으로서, 동적(dynamic)이라는 단어가 이름에 붙었다. 확실히 static이 붙을 만한 작업은 아니지만, 그렇다고 많은 단어들 중에 굳이 dynamic가 붙을 필요 또한 없다. '동적', ' dynamic'이라는 이름은 동적 프로그래밍의 (중복의 제거라는) 핵심을 직관적으로 이해하지 못하게 만든다. 하지만, 관례적으로 이미 굳어진 이름이라 앞으로도 쓰일 것이라는 사실은 안타까우면서도 분명하다. #1-2 종류동적 프로그래밍은 이와 같이 2가지 방식으로 나뉜다. #1-3 상향식(Bottom-up) 접근 [백준] 17626 - Four Squares#1 알고리즘 123 123 재귀 함수가..

#1 알고리즘#1-1어떤 원소를 기준으로 잡을 것이냐는 아무래도 상관없다. 여기에서는 각 배열의 맨 끝 원소를 기준으로 잡기로 한다.

혹시라도 기준을 대략적으로라도 원소들의 평균값에 가깝게 잡을 수 있는 조건이 존재한다면, 해당 조건을 이용해 기준을 잡게끔 응용할 수도 있을 것이다. 기준이 평균값에 가깝게 잡힐수록, 퀵 정렬의 성능이 좋아지기 때문이다. #1-2이 '분할(partition)'의 결과로 기준 원소의 자리가 최종적으로 결정되면, 그 원소는 앞으로의 모든 qucikSort() 재귀 호출에서 사용되지 않고 영원히 그 자리가 고정된다. 즉, 분할 한 번에 원소 하나가 정렬되는 것이다. #1-3 퀵 정렬 - 위키백과, 우리 모두의 백과사전위키백과, 우리 모두의 백과사전. 퀵 정렬(Quicksort..

#1 알고리즘#1-1 #1-2 #2 코드#2-1 자바public static void insertionSort(int[] array, int startIndex, int endIndex) { for(int maxIndex = (startIndex + 1); maxIndex = insertionDestination; i--) { array[i + 1] = array[i]; } array[insertionDestination] = temp;} #2-2 코틀린fun insertionSort(array: Array, startIndex : Int, endIndex : Int) { for(maxIndex : Int in (startIndex + 1)..endIndex) { ..

#1 알고리즘#1-1힙(heap)이라는 영어 단어의 사전적 의미는 쌓아 놓은 무더기다. 그리고 이 단어는 프로그래밍에서도 사용된다. 첫째로 메모리 영역에서, 둘째로 자료구조에서다. 이 둘은 서로 다른 개념이지만, 힙(heap)이라는 단어를 쓴 만큼 각각 힙의 사전적 의미와 관련된 내용이 있다. 메모리 영역에서의 힙은 무더기라는 뉘앙스를 풍긴다. 프로그램 수행 도중 그 크기가 변하지 않는 정적 할당과 달리 동적 할당은 필요한 만큼 크기가 무더기로 증가할 수 있기 때문이다. 자료구조에서의 힙은 '무더기'기 보단, 쌓임이라는 의미가 강조된다. 노드가 특정한 규칙을 지키며 차곡차곡 쌓이는 모습에서 힙이라는 이름이 붙었다. #1-2힙 정렬은 자료구조에서의 힙을 이용하는 정렬이다. 자료구조에서의 힙은 최소 힙과 최..

#1 알고리즘#1-1 #1-2 #1-3 #1-4 #1-5병합 정렬의 총 비교 횟수는, 최악의 경우 nlog2n이다 #2 코드#2-1 자바public static void mergeSort(int[] array, int startIndex, int endIndex) { // (startIndex  #2-2 코틀린fun mergeSort(array: Array, startIndex : Int, endIndex : Int) { // (startIndex , startIndex: Int, midIndex : Int, endIndex: Int) { // array에서 나뉜 'f'irst 부분을 순회할 인덱스 f var f = startIndex // f의 최댓값은 midIndex // ..

#1 알고리즘#1-1정렬 방식이 마치 거품이 수중에 있다가 수면 위로 보글보글 올라가는 모습과 비슷해서 버블 정렬이라고 이름 붙여졌다. 기본적인 버블 정렬은, 정렬 작업을 시작할 때 중간에 배열 이미 정렬된 상태여도 maxIndex가 1이 되는 마지막 반복까지 무의미한 순환을 계속한다. 이 문제점을 해결하기 위해 알고리즘에 한 가지 장치를 할 수 있는데, 그걸 향상된 버블 정렬이라고 부른다. #2-1반드시 n * (n - 1) / 2번의 비교를 하는 일반 버블 정렬에 비해, 향상된 버블 정렬은 비교 횟수를 최소 (n - 1)번까지 낮출 수 있다. #2 코드#2-1 자바public static void bubbleSort(int[] array, int startIndex, int endIndex) { ..