전체 글
기본 정렬(선택 정렬, 버블 정렬, 삽입 정렬)
목차 선택 정렬(Selection sort) 1-1. 선택 정렬이란? 1-2. 선택 정렬 구현 버블 정렬(Bubble sort) 2-1. 버블 정렬이란? 2-2. 버블 정렬 구현 삽입 정렬(Insertion sort) 3-1. 삽입 정렬이란? 3-2. 삽입 정렬 구현 시간복잡도 비교 1. 선택 정렬(Selection sort) 1-1. 선택 정렬이란? 자리가 정해져 있는 정렬 알고리즘이다. 주어진 배열이나 리스트에서 최솟값을 찾고 그 값을 맨 앞의 값과 위치를 바꾼다. 같은 방법으로 나머지 값들을 정렬한다. 아래에 8, 5, 1, 3, 6이 담겨 있는 배열을 선택 정렬로 정렬해보자. 우선, 제일 앞에 있는 8의 위치를 i라고 하고, j는 i다음 위치부터 존재하는 최솟값의 위치를 가져온다. 그리고 그 위치..
BOJ 2225 합분해
boj 2225 합분해 - 문제 링크 https://www.acmicpc.net/problem/2225 - 문제 해설 테이블 D[i][j]를 n이 i이고 k가 j일 때의 경우의 수라고 정의한다. 경우의 수를 어떻게 나눌지 잘 떠오르지 않아서 일단 n과 k에 따른 경우의 수를 작은 수부터 나열해보았다. 표로 나열해보면서 점화식을 유추해보자. 예를 들어 D[3][3]을 구한다고 해보자. 3을 3가지 수의 합으로 나타내는 경우는 0부터 3까지의 수를 2가지 수의 합으로 나타낸 것에다가 3이 되기위해 필요한 수를 더하면 된다. 0을 2가지 수의 합으로 나타낸 경우 : (0 + 0) 1을 2가지 수의 합으로 나타낸 경우 : (0 + 1), (1 + 0) 2를 2가지 수의 합으로 나타낸 경우 : (0 + 2), (..
BOJ 9461 파도반 수열
boj 9461 파도반 수열 - 문제 링크 https://www.acmicpc.net/problem/9461 - 문제 해설 첫 5항만 제외하고 나머지 항들은 전부 규칙을 따라 증가하는 형태이다. P(1)부터 P(10)을 보면 1, 1, 1, 2, 2, 3, 4, 5, 7, 9 이다. 길이가 3인 삼각형은 1과 2를 더해서 생기고, 길이가 4인 삼각형은 1과 3을 더해서, 길이가 5인 삼각형은 1과 4를 더해서 생긴다. D[i] = D[i-1] + D[i-5] 의 규칙을 따라 증가한다. 그러므로 1~5항을 따로 초기화해주고 나머지는 위 점화식을 따라 구해준다. - 코드 보기 #include using namespace std; int t; int n; long long P[105]; int main(voi..
BOJ 2133 타일 채우기
boj 2133 타일 채우기 n이 홀수일 때, 타일을 전부 채울 수 있는 방법은 없다. 그러므로 n이 짝수일 때만 살펴보면 된다. 테이블 D[i]를 n이 i일 때, 타일을 전부 채울 수 있는 방법 수라고 정의하자. 타일이 2칸일 때 채울 수 있는 방법의 수가 3가지인 것은 쉽게 알 수 있다. 그리고 힌트를 보면 4칸의 경우 2칸인 경우를 이용하지 않고 채우는 방법이 2가지가 있다는 것을 알 수 있다. 이 사실만으로 간단하게 점화식을 D[i] = D[i-2]x3 + D[i-4]x2 라고 하면 틀린다. 위의 사진을 보면, 타일이 2칸씩 늘어날 때마다 채우는 방식 2가지가 추가된다. 이를 바탕으로 점화식을 구현해보자. D[i] = D[i-2]x3 + D[i-4]x2 + D[i-6]x2 + ... + D[0]x..
BOJ 1699 제곱수의 합
boj 1699 제곱수의 합 수가 주어지면 그 수를 제곱수들의 합으로 표현할 때, 최소의 항 갯수를 구하는 문제이다. 모든 수는 1의 합으로 표현할 수 있기에 최대의 항 갯수는 입력된 수의 크기와 동일하다. 그러므로, 테이블 D[i]를 i를 제곱수의 합으로 표현할 때의 최소의 항 갯수라고 정의하면, D[i] = i 라고 초기 값을 지정해줄 수 있다. 최소의 항 갯수를 구하는 방법은 간단하다. i에서 i를 넘지 않는 제곱수를 빼면서 최소 항의 갯수를 변경해주는 것이다. 이를 점화식으로 나타내보자. D[i] = min(D[i], D[i - 제곱수]+1) 이때, +1을 해주는 이유는 제곱수에 해당하는 항 갯수를 더해주는 것이다. #include #include using namespace std; int n;..