안녕

Description 우리 교재의 Chapter 2, Exercise 42번 (p. 94)을 풀어보자.이 문제는 분할정복의 대표적인 문제로, 트로미노 타일링 문제로 널리 알려져있다.단, 이 실습과제에서 트로미노 타일의 번호는 트로미노를 놓는 순서로 정한다.예를 들어, 다음과 같은 트로미노 퍼즐은 아래와 같은 순서로 트로미노를 놓는다. Input 첫 번째 줄에 n, row, col이 주어진다.n은 n*n 트로미노 퍼즐 보드의 크기이다. (2의 거듭제곱 수라고 가정해도 된다.)row, col은 구멍의 행과 열이다. 0 <= row, col <= (n - 1) Output 트로미노를 놓는 순서대로 타일에 번호를 부여한 보드를 출력한다.구멍 타일의 번호는 0으로 한다. Sample Input 1..

만약에 8개의 원소를 가지고 있는 리스트를 정렬해야 한다고 가정해봅시다. 이때도 \(\Theta(nlgn)\)인 merge sort가 \(\Theta(n^2)\)인 exchange sort보다 좋을까요? 아마 작은 분할일 때는 오히려 exchange sort가 좋지 않을까요? merge sort가 더 좋다고 말하는 것은 n이 무한대로 갈 때의 얘기입니다. 오히려 n이 작으면 작을수록 다른 알고리즘이 더 좋을 때가 있습니다. 이때 나오는 것이 Threshold, 임계값입니다. 1. 임계값이란? 분할 정복 알고리즘이 A이고, 대체 알고리즘이 B라고 합시다. 계속해서 분할하다 보면 어느 순간부터 B가 더 좋아질 때가 있습니다. 바로 위의 sorting이 예시입니다. 이때, 대체 알고리즘이 더 좋아지는 시점이 ..

만약 하드웨어의 저장 공간을 넘어서는 숫자들의 연산을 해야 한다면 어떻게 해야 할까요? 이 경우에 유일한 대안은 소프트웨어적으로 숫자들을 표현하고 처리해야 합니다. 방법은 숫자들을 하나씩 쪼개서 배열에 넣는 방법이 있습니다. 이때 배열에는 역순으로 넣어야 합니다. 1. 알고리즘 및 코드 우선 긴 숫자를 쪼개 봅시다. \(u\,=\,x\times10^m+y\) \(v\,=\,w\times10^m+z\) 일 때, \(uv\, =\, \left (x \times 10^m + y \right )\left ( w\times10^m+z \right )\) 이고, 이는 \(xw\times10^{2m}+(xz+wy)\times10^m+yz\) 입니다. 이것을 통해 쉽게 계산할 수 있습니다. Problem : 큰 정수의..

1. 행렬 곱셈에 대한 간단한 소개 예전의 글에서 구한 행렬 곱셈의 시간 복잡도는 \(T(n)\,=\,n^3\)이었습니다. 왜냐? 두 개의 행렬에 대해 A의 행, B의 열을 곱해야하기 때문입니다. A의 n개의 행에 대해서 B는 \(n^2\)번을 곱해야하기 때문입니다. 하지만 Strassen씨는 시간 복잡도가 \(n^3\)보다 더 빠른 알고리즘을 개발했습니다. 2. Strassen's Algorithm에 대한 소개 행렬 A) \(\begin{bmatrix}a_{11}&a_{12} \\a_{21}&a_{22} \\\end{bmatrix}\) 행렬 B) \(\begin{bmatrix}b_{11}&b_{12} \\b_{21}&b_{22} \\\end{bmatrix}\) 행렬 C) \(\begin{bmatrix}..

1. 알고리즘 및 코드 Problem : 오름차순으로 주어진 리스트를 정렬 Input : 양의 정수 n, 리스트 S Output : 오름차순으로 정렬된 리스트 S 알고리즘) 1. pivot을 기준으로 나눈다. 2. 나눈 pivot의 왼쪽, 오른쪽을 재귀적으로 다시 적용한다. 3. 리스트를 더 이상 나눌 수 없을 때까지 반복한다. (원소가 1개 이하로 남았을 때) 생각의 흐름) pivot은 리스트의 맨 앞을 넣는다. pivot을 기준으로 나누면 되는데, j에 low 위치를 넣고, i를 low + 1의 위치부터 high까지 넣는다. 그러면 for문으로 i를 돌리고, 이때 S[i]가 pivot보다 작으면 j에 1을 더하고, i 위치와 j 위치를 swap한다. 쭉 반복하면 결국 최종적으로 j의 위치가 pivot..

1. Binary Search의 알고리즘 및 코드 분할 정복의 기본은 재귀이기 때문에 반복문이 아닌 재귀를 통해서 binary search를 하겠습니다. 반복문을 통한 binary search는 앞 글을 참고해주세요. Problem : 원소가 n개인 (오름차순)정렬된 리스트 S안에 검색하려는 수 x가 있는가? input : 양의 정수 n, 정렬된 리스트 S, 검색키 x output : x의 위치, 만약 없다면 -1를 반환 알고리즘 구상) 1) x와 S의 중간 값과 비교해 같다면 그대로 끝 2) 만약 다르다면 두 가지 방법을 이용한다. 2.1) x가 S의 중간 값보다 작다면 중간 위치를 기준으로 왼쪽 리스트를 탐색한다. 2.2) x가 S의 중간 값보다 크다면 중간 위치를 기준으로 오른쪽 리스트를 탐색한다...

1. 분할 정복이란? 분할 정복은 이름에서 볼 수 있듯이 말 그대로 분할 정복입니다. 분할 정복의 접근법) 1. divides an instance of a problem into two or more smaller instances. 2. if they are too large to be sorved, they can be divided into still smaller instances 3. if solutions to them can be obtained readily, these smaller solutions can be combined into original solution 즉, 문제를 두 개 이상의 instance로 쪼갠다. 그래도 instance가 여전히 크면 또 쪼갠다. 만약 분할한 i..