안녕

0. 문제 링크 https://school.programmers.co.kr/learn/courses/30/lessons/68936 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 1. 풀이 방법 Divide and Conquer 방식을 사용했고, 트리 내에서는 반복문을 사용하여 문제를 해결하였다. 첫 번째 숫자인 bef와 반복문에서 나오는 숫자가 다를 경우 압축이 불가능하므로, 해당 트리를 사등분하여 재귀를 호출했다. 사등분 한 쿼드 트리를 모두 호출한 이후에는 return을 함으로써, 반복문을 바로 종료했다. -> 트리를 사등분하면 더 이상 볼 필요가 없..

다들 이항 계수 아시죠? \(\binom{n}{k} = \frac{n!}{k!(n-k)!}\)입니다. 이때 n!를 계산하기 매우 힘드므로, 재귀 관계식을 이용하여 다음과 같이 정리할 수 있습니다. \(\binom{n}{k}=\left\{\begin{matrix} \binom{n-1}{k-1}+\binom{n-1}{k} & 0

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..

가능하다면 다음 두 가지 경우에 대해서는 분할 정복을 피해야 합니다. instance of size N is divide into two or more instances each almost size n. 크기가 n인 사례가 거의 n에 가까운 두 개 이상의 사례로 분할될 때 이렇게 분할하면 지수 시간 알고리즘이 나옵니다. instance of size N is divied into almost n instances of size n/c, where c is a constant 4개로 쪼갰는데, 다시 4번의 재귀할 때, 혹은 2개로 쪼갰는데, 2번 재귀할 때 이렇게 분할하면 \(n^{\Theta(nlgn)}\)의 알고리즘이 나옵니다. 만약 피보나치수열을 재귀적인 방법 즉, 분할 정복을 이용해서 문제를 해결..

만약에 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 : 큰 정수의..

from os import sep import sys input = sys.stdin.readline count = 0 def mmult(n, a, b, c): # 단순 행렬 곱셈 for i in range(n): for j in range(n): for k in range(n): c[i][k] += a[i][j] * b[j][k] # += 해줘야함. 그냥 =를 하면 마지막으로 들어가는 값으로만 치환됨 def partition(n, a, a11, a12, a21, a22): # 행렬 분할 for i in range(n): for j in range(n): a11[i][j] = a[i][j] a12[i][j] = a[i][j + n] a21[i][j] = a[i + n][j] a22[i][j] = a[i ..

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의 중간 값보다 크다면 중간 위치를 기준으로 오른쪽 리스트를 탐색한다...