archive

- 그래프 알고리즘에서 배운 DFS를 빼고는 백트래킹을 이야기할 수 없음, DFS는 백트래킹의 골격을 이루는 알고리즘 ! - 깊이 우선 탐색 (DFS)의 방식으로 탐색하는 모든 방법을 이야기한다. - 탐색을 하다가 더 갈 수 없으면 왔던 길을 되돌아가 다른 길을 찾는다고 해서 이런 이름이 붙었고, 백트래킹은 주로 재귀적으로 구현한다. -백트래킹 알고리즘마다 DFS에서 조금씩 변형은 일어나지만 모두 DFS의 범주에 속하며, 백트래킹 알고리즘이 상태 공간 트리를 명시적으로 만드는 것은 아니지만 알고리즘의 진행 과정은 상태 공간 트리의 루트에서 시작해서 DFS 방식으로 탐색해나가는 것이다. ** 그 전에 그래서 백트래킹이 뭔데? 백트래킹 알고리즘이란 퇴각 검색이라고도 불리며 이는 한정 조건을 가진 문제를 풀려..

**그리디 알고리즘 -=근사 알고리즘 (현재의 최적해가 전체의 최적해를 보장하지 않음) -그리디 알고리즘은 최적해가 보장되는 조건에서만 사용해야함, 이는 다음과 같음 (1) 현재의 선택이 미래의 선택에 영향을 주지 않는다 (2) 부분의 최적해가 모이면 전체의 최적해가 된다 (최적 부분 구조 조건, Optimal Subtructure) -ex) 서울-대전-부산 : 서울과 대전 사이의 거리를 구하는 것이 대전과 부산 사이의 거리를 구하는 것에 영향을 주지 않을 뿐만 아니라, 서울-대전의 최소거리와 대전-부산의 최소거리, 즉 부분의 최적해가 모이게 되면 전체의 최적해를 보장한다. -이 두 가지 조건을 만족하기 위해서는 정렬이 핵심임 ! -ex) 회의실 배정 -> 언제 끝나느냐가 중요함, 가장 빨리 끝나는 회의..

1. 전형적인 그리디 알고리즘의 구조 -눈 앞의 이익만 추구하는 알고리즘을 총칭해서 그리디 알고리즘 (Greedy Algorithm)이라고 한다. -그리디 알고리즘은 대부분의 경우 뛰어난 결과를 도출하지 못하지만 드물게 최적해를 보장하는 경우가 있다. -그리디 알고리즘은 최적화 문제를 대상으로 한다. ** 최적해, 最適解, optimal solution 선형 프로그래밍에서 제약 조건을 충족시키는 가능한 해 (解) 중 목적 함수 값을 최대 또는 최소로 만드는 값. -최적해를 찾을 수 있으면 그것을 목표로 삼고, 찾기 어려운 경우에는 주어진 시간 내에 그런대로 괜찮은 해를 찾는 것을 목표로 삼는다. -아래는 전형적인 그리디 알고리즘의 구조이다. do 가장 좋아 보이는 선택을 한다 until (해 구성 완료)..

1. 어떤 문제를 동적 프로그래밍으로 풀이하는가? -동적 프로그래밍 : 큰 문제의 해답에 작은 문제의 해답이 포함되어있고, 이를 재귀호출 알고리즘으로 구현하면 지나친 중복이 발생하는 경우에 이 재귀적 중복을 해결하는 방법이다. - 피보나치 수열이 가장 대표적인 예시 -피보나치 수열을 재귀로 표현하면 다음과 같다 fib(n): if(n=1 or n=2): return 1 else return fib(n-1)+fib(n-2) -위와 같은 재귀적 알고리즘은 간명하지만 때때로 엄청난 비효율을 초래할 수 있으며, n의 피보나치 수를 구하는 앞의 재귀적 알고리즘은 지수 함수에 비례하는 시간이 들게 된다. -이것은 호출 결과를 한 번만 구해 저장해두었다가 나중에 사용만 하면 될 것을, 매번 호출함으로써 비효율이 발생..

1. 힙 정렬 (Heap sort) - 합 정렬은 대표적인 우선순위 큐인 힙 자료구조를 사용하는 정렬 알고리즘이다. -지금까지 소개한 정렬 알고리즘들이 모두 주어진 배열 자료구조 위에서 정렬한 것에 반해, 힙 정렬은 힙 자료구조를 사용해서 정렬 -[힙의 정의] -힙은 다음 두 조건을 만족해야 한다 : 완전 이진 트리 구조를 사용해야 한다, 모든 노드는 값을 갖고, 자식 노드 값보다 크거나 같다. -조건들을 만족하면 우선순위가 가장 큰 원소가 루트에 자리하게 된다 -[힙의 구성] - 2. 기수 정렬 -기수 정렬(Radix Sort)는 원소들이 모두 상수 k개 이하의 자릿수를 가진 자연수와 같은 특수한 경우에 (자연수가 아닌 제한된 길이를 가진 알파벳 등도 해당함) 사용 가능한 알고리즘이다. -우선 가장 낮..

1. 병합 정렬 -병합 정렬은 일단 입력을 반으로 나누고, 전반부와 후반부를 각각 독립적으로 정렬한다. -마지막으로 정렬된 두 부분을 합쳐서, 즉 병합하여 정렬된 배열을 얻는다. -전반부와 후반부를 정렬할 때에도 역시 반으로 나눈 다음 정렬해서 병합한다. -크기만 절반으로 줄어들었을 뿐 원래의 정렬 문제와 성격이 똑같다는 것을 알 수 있다. -요약하면, 병합 정렬은 자신에 비해 크기가 반인 문제를 두 개 푼 다음, 이들을 병합하는 작업을 재귀적으로 반복한다. - 이를 코드로 구현하게 되면, tmp[]라는 빈 배열을 하나 형성하고 경쟁을 하여 변수 하나씩 빈 배열에 옮긴다 -병합 정렬의 수행 시간은 최악, 최선, 평균 모든 경우에 O(n log n)이다. ** 스위칭 병합정렬 -이론적으로 보면 병합 정렬은..