제주 탈출 일지

알기쉬운 알고리즘 2장 연습문제를 공부한 내용을 정리하였습니다. 틀린 점이나 피드백이 있으시다면 언제든지 답글로 달아주시면 감사하겠습니다. 1. 360과 96의 최대공약수를 나눗셈을 이용한 유클리드 알고리즘으로 구하라. G(A, B) = G(B, R) 이다. ( A / B = 몫....R(나머지) ) G(360, 96) = G(96, 72) G(96, 72) = G(72, 24) G(72, 24) = G(24, 0) = 24 따라서 360 과 96의 최대공약수는 24이다. 2. 유클리드의 최대공약수 mod 연산 알고리즘의 시간복잡도를 O-표기로 표현하라. Euclid(a, b) 입력 : 정수 a,b; 단 a >= b >= 0 출력 : 최대공약수(a, b) if (b == 0) return a return..

알기쉬운 알고리즘 1장 연습문제를 공부한 내용을 정리하였습니다. 틀린 점이나 피드백이 있으시다면 언제든지 답글로 달아주시면 감사하겠습니다. 1. 최대 숫자 찾기에 대한 알고리즘과 다른 알고리즘을 생각해보자. - 순차 탐색 모든 숫자에 대해서 처음부터 끝까지 카드의 숫자를 하나씩 비교하면서 가장 큰 숫자를 찾는다. - 정렬 모든 숫자를 오름차순, 내림차순으로 정렬해두면 한쪽 끝에 있는 숫자가 최소 혹은 최대일 것이다. 2. 여러 장의 숫자 카드 중에서 가장 큰 수와 가장 작은 수를 동시에 찾기 위한 알고리즘을 생각해보자. - 순차 탐색 1번과 동일하게 처음부터 끝까지 숫자를 비교하며 가장 큰 수와 작은 수를 찾는다. - 정렬 1번과 동일. 3. 보간탐색(Interpolation Search)이 어떤 방식의..

DFS(깊이 우선 탐색) DFS는 파고들 수 있을 만큼 계속 파고들다가 더 파고들곳이 없을때까지 탐색을 진행하고, 그 후 이전으로 되돌아가 다시 탐색을 시작. 1. 첫번쨰 노드를 방문처리. 2. 노드에 대한 작업을 진행. 3. 현재 노드와 연결되어 있으면서 방문하지 않은 노드를 dfs로 검사.(재귀적) 4. 2,3을 모든 노드를 탐색할 때까지 반복. #include using namespace std; bool visited[9]; //노드의 방문 여부. vector graph[9]; // DFS 함수 정의 void dfs(int x) { // 현재 노드를 방문 처리 visited[x] = true; cout n >> m; // 2차원 리스트의 맵 정보 입력 받기 for (int i = 0; i < n;..

재귀 알고리즘의 복잡도를 구하는 방식은 3가지가 있다. 1. 반복대치 2. 추정 후 증명 3. 마스터 정리 1. 반복대치 반복대치로 복잡도를 구하기 위해서는 먼저 점화식을 구한다. factorial(n) { if(n =1) return 1; return n * factorial(n-1); } 이 식은 다음 점화식으로 나타낼 수 있다. T(n) = T(n-1) + a (a는 자기호출이외의 수행시간) 그리고 T(1) = c * 2^n + 1 이므로, 따라서 T(n) >= Ω(2^n) 가 성립한다. 3, 마스터 정리 마스터 정리는 T(n) = aT(n/b) + f(n) 형태의 점화식에 적용할 수 있다. f(n) / h(n)을 구하는데, h(n)은 n^(logb a) 형태이다. 만약 h(n)이 f(n)을 압도한..

점근적 표기법 : 변수의 크기가 충분히 큰 경우에 변수가 커짐에 따라 함수가 증가하는 비율을 표현하는 방법 이 표기법은 계수가 중요하지 않다. n.이 커짐에 따라 계수의 영향은 미미해지고, 점근적 표기에서 계수를 무시하는 이유이다. 1. 세타 표기법(θ) θ(f(n))은 점근적 증가율이 f(n)과 일치하는 모든 함수의 집합. ex) 5n^2 + 4n = θ(n^2) 여기서 "=" 기호는 같다는 표현이 아닌 포함된다로 사용된다. 2. 빅오 표기법(O) O(f(n))은 점근적 증가율이 f(n)을 넘지 않는 모든 함수의 집합 ex) 5n^2 + 4n = O(n^2) ex2) 7n = O(n^2) 최고차항의 차수가 f(n)과 일치하거나 그보다 더 작은 함수의 집합. O-표기는 함수의 점근적 상한을 나타낸다. 3..