구프의 메모장

여기서 살펴볼 알고리즘은 Backtracking Branch&Bound 두 개이다. Backtracking은 DFS, 깊이 우선 탐색이고, Branch&Bound는 좀 다른데, 이 알고리즘들은 NP-완전 문제의 근사해가 아닌 최적해를 탐색하기 위한 방법들이다. 1. Backtracking PS를 하다보면 DFS알고리즘으로 접하기 쉬운 백트래킹이다. 백트래킹을 이용해 해를 구할 수 있는 문제의 종류는 다음과 같다. - 최적화 문제 (Optimization) : 최소,최댓값을 구하는 문제 - 결정 문제 (Decision) : 해의 존재 여부를 구하는 문제 일반적으로 백트래킹은 트리 구조에서, 가장 왼쪽 가장 깊은 트리부터 오른쪽으로 모든 트리를 탐색하는 방식이라고 생각하면 쉽다. 대충 이런식으로 모든 트리를..

DP 다음에는 사실 정렬이지만, 정렬은 너무 많이 본거기도 하고, https://kgwdiary.tistory.com/16 여기에도 작성한 적이 있기 때문에, 일단 생략하고, 다른 과목들까지 모두 하고나서 시간이 남는다면 정렬도 다시 써보기로 했다. 그래서 정렬을 넘기고 다음 챕터인 근사 알고리즘에 대해 알아보자. 근사알고리즘은 다항식시간안에 답을 구할 수 있다고 보장할 수 없는 이른바 'NP-문제'에서 근사해를 구하기 위한 알고리즘이다. NP-문제에서 다항식 시간안에 해를 구하려고 하기 때문에, 최적해가 아닌 근사해를 구하는 것이 특징이다. 이 챕터에서 다루는 문제는 - 여행자 문제 (TSP) - 정점 커버 (Vertex Cover) - 통 채우기 (Bin Packing) - 작업 스케줄링 (Job S..

DP는 Dynamic Programming, 동적 프로그래밍을 의미한다. '동적'이라는 말이 들어가서 뭔가 움직일 것 같은 느낌이 있는데, 딱히 그런건 없다. 기본적인 DP 방식은, 문제를 작은 여러개의 문제로 나눈 뒤, 작은 문제들의 값을 이용해 원래 문제의 값을 찾아가는 일종의 Bottom-up 방식의 알고리즘이다. Dynamic Programming의 대표적인 문제들로는 - Floyd-Warshall - Matrix Chain Multiplication - Minimum Edit Distance - 0-1 Knapsack - Coin Change 와 같은 문제들이 있다. 이 글에서는 이 5문제들에 대해 알아볼 것이다. 1. Floyd-Warshall Floyd-Warshall 알고리즘의 이름은 개발..

1장 알고리즘(Algorithm)이란 단어는 알 콰리즈미라는 페르시아의 수학자에게서 유래되었다고 알려진다. 최대 숫자 찾기(순차 탐색) : 앞부터 순서대로 탐색하여 가장 큰 수 찾기 임의 숫자 찾기(이진 탐색) : 절반씩 나눠가면서 찾기 ( 단 정렬된 데이터 ) 동전 거스름돈 문제(그리디 알고리즘) : 큰 수부터 가능한 한 최대로 가지기 한 붓 그리기 문제 : 현재 점으로 돌아오는 사이클 찾기 가짜 동전 찾기 문제 : 3그룹으로 분할하여 찾기 독이 든 술단지 문제 : 이진수처럼 해서 찾기 2장 ① 유클리드의 최대 공약수 찾기 알고리즘 A B A mod B 24 14 10 14 10 4 10 4 2 4 2 0 위와 같이 A, B, A mod B로 3열 행을 만든 뒤, B값과 A mod B를 다음 행의 A,..