뭐라도 남겨보자

넓이 우선 탐색(Breadth-Fisrt-Search) Breadth First Search. 흔히 줄여서 BFS로 쓴다. 한국어 표기는 넓이 우선 탐색 또는 너비 우선 탐색. 너비 우선 탐색은 트리나 그래프를 방문 또는 탐색하는 방법이다. 탐색 방법은 다음과 같다. 루트에서 시작한다. 자식 노드들을 [1]에 저장한다. [1]에 저장된 노드들을 차례로 방문한다. 또한 각각의 자식들을 [2]에 저장한다. [2]에 저장된 노드들을 차례로 방문한다. 또한 각각의 자식들을 [3]에 저장한다. 위의 과정을 반복한다. 모든 노드를 방문하면 탐색을 마친다. BFS는 갈림길에 연결되어 있는 모든 길을 한번씩 탐색한 뒤 다시 연결되어 있는 모든 길을 넓게 탐색하는 것을 볼 수 있다. DFS와의 가장 큰 차이로, 여러 갈..

동적 계획법 특정 법위까지의 값을 구하기 위해서 그것과 다른 범위까지의 값을 이용하여 효율적으로 값을 구하는 알고리즘을 동적 계획법, DP라고 한다. 쉽게 말해서 이전 계산까지의 결과를 활용하여 문제를 푸는 것이다. 그렇기 때문에 동적 계획법은 특정 답을 구하기 위해 같은 계산을 여러번 해야하는 데, 이는 최적 부분 구조(Optimal Substructure)의 문제를 푸는데 greedy algorithm을 사용하는 것 보다 큰 효과를 발휘한다. 접근 동적 계획법의 접근 방식은 원래의 문제를 작은 부분 문제들의 연속된 절차로 바꾸는 과정에서 분할 정복 알고리즘과 유사하다. 즉, 지금까지 쓴 글을 종합해보면 동적 계획법이란 최적 부분 구조를 지닌 중복된 하위 문제를 분할 정복으로 풀이하는 문제 해결 패러다..

그리디 알고리즘 그리디알고리즘, 욕심쟁이 알고리즘이란 "매 선택에서 지금 이순간 당장 최적인 답을 선택하여 적합한 결과를 도출하자"라는 모토를 가진 알고리즘이다. 그리디 알고리즘의 간단하게 설명 해보자면 마시멜로 실험으로 설명할 수 있다. 마시멜로 실험은 어린아이에게 마시멜로 1개를 주고 15분 동안 먹지 않고 참으면 2개를 주기로 하고 아동의 행동을 관찰했을 때, 기다리고 마시멜로를 받은 아이들과 그렇지 않은 아이들이 자라서 보여주는 성적과 학업성취도를 알아보는 실험인데, 만약 이 알고리즘으로 이 실험에 참여한다면 '당장 내 손에 있는 마시멜로 하나를 먹는다'라는 결과가 나오게 된다. 이 말은 곧 이 알고리즘의 한계이기도 한데 그리디 알고리즘은 매 선택이 '그 순간'에서는 최적이지만 종합적으로 봤을 때..

병합정렬 ‘존 폰 노이만(John von Neumann)’이라는 사람이 제안한 방법으로일반적으로 구현했을 때 이 정렬은 안정 정렬 에 속하며, 분할 정복 알고리즘의 하나 이다. 분할 정복(divide and conquer) 방법 문제를 작은 2개의 문제로 분리하고 각각을 해결한 다음, 결과를 모아서 원래의 문제를 해결하는 전략이다. 분할 정복 방법은 대개 순환 호출을 이용하여 구현한다. 리스트의 길이가 0 또는 1이면 이미 정렬된 것으로 본다. 그렇지 않은 경우에는 정렬되지 않은 리스트를 절반으로 잘라 비슷한 크기의 두 부분 리스트로 나눈다. 각 부분 리스트를 재귀적으로 합병 정렬을 이용해 정렬한다. 두 부분 리스트를 다시 하나의 정렬된 리스트로 합병한다. 병합 정렬(merge sort) 알고리즘의 구체..

버블정렬(Bubble sort) 버블정렬은 다른말로 제자리정렬(in-place sort)라고도 하며 말 그대로 별도의 저장공간 필요없이 본 배열안에서 정렬이 이루어진다는 장점이 있다. 버블정렬의 정렬방법은 0번째 인덱스에 커서를 맞추는 것(커서의 인덱스좌표를 i로 선언)으로 시작하여 1. i번째 인자와 인접한 인자(i+1)간의 값을 비교한다. 2. i번째가 더 크면 i+1번째 인자와 자리를 바꾼다. 3. i번째가 더 작거나 같으면 아무것도 하지 않는다. 4. 커서의 좌표, i를 1더해준다. 5. 해당 배열의 끝까지 1~3의 절차를 진행하는데 단 loop의 회차만큼 i는 배열 length에서 i를 뺀 만큼의 번째에 있는 값 까지만 비교한다. 6. 이 과정을 i가 length와 같게 될 때까지 진행한다. 같..

완전탐색(Exhaustive Search) 완전 탐색은 어떠한 문제를 풀기위해 사용하는 검색 알고리즘을 말하는데 이 방법은 주어진 모든 데이터를 하나하나 살펴보며 목표값을 찾아내는 알고리즘이다. 방법이 무식하기도하고 단순하여 'Brute Force'라고도 하기도 한다. 이러한 완전탐색을 하는데 사용하는 방법은 5가지로 주로 알려져 있다. Brute Force 순열(Permutation) 재귀(Recursion) 비트마스크(Bit Mask) 넓이탐색과 깊이탐색(BFS, DFS) 장점: 장점이라고 본다면 모든 데이터를 확인하는 것이기 때문에 "충분한 시간만 주어진다면" 못 푸는 문제가 없다는 것이다. 예를 들어 비밀번호가 6자리인 금고를 여는 문제를 brute force를 이용하여 해결할 때, 이 방법을 사..