Development Artist

도입 백준 단계별 풀기 DFS와 BFS 일곱 번째 문제이다. DFS와 BFS DFS - Root Node 혹은 다른 임의의 Node에서 이어진 Branch를 완벽하게 탐색하고 다른 이어진 Branch로 넘어가는 방법. 한 방향으로 계속 가서 끝을 마주하면 다른 방향으로 설정해서 마찬가지로 진행. - Stack 또는 Recursive함수로 구현. - 시간 복잡도 : 인접 리스트는 $O(V+E)$ 인접 행렬은 $O(V^2)$ // 접점(V), 간선(E) BFS - Root Node 혹은 다른 임의의 Node에서 이어진 Branch들의 바로 하나 건너 있는 Node들을 먼저 탐색. - Queue로 구현 - 시간 복잡도 : 인접 리스트는 $O(V+E)$ 인접 행렬은 $O(V^2)$ // 접점(V), 간선(E) ..

도입 백준 단계별 풀기 그리디 알고리즘 네 번째 문제이다. 그리디 알고리즘 그리디 알고리즘(탐욕 알고리즘)이란, 문제를 해결하는 과정에서 그 순간순간마다 최적이라고 생각되는 결정을 하는 방식으로 진행하여 최종 해답에 도달하는 문제 해결 방식이다. 특징 - 1. 최적성의 원리 : 주어진 문제에 대한 최적해가 분할된 부분 문제의 최적해로 구성된다는 원리. - 2. 최적 해 보장 불가 - 3. 효율성 개선 그리디 알고리즘 수행절차 1. 해 선택 : 부분 해 집합에 추가 다음 항목 선택 현재 상태 최적화 기준 만족 여부 확인 2. 적합성 검증 : 새로운 부분 해 집합 조건 여부 확인 현재 집합이 해가 될 가능성 검사 3. 해 검증 : 신규 구성 집합이 해인지 검사 문제가 아니면 1번으로 돌아가서 반복 풀이 1...

도입 백준 단계별 풀기 그리디 알고리즘 첫 번째 문제이다. 그리디 알고리즘 그리디 알고리즘(탐욕 알고리즘)이란, 문제를 해결하는 과정에서 그 순간순간마다 최적이라고 생각되는 결정을 하는 방식으로 진행하여 최종 해답에 도달하는 문제 해결 방식이다. 특징 - 1. 최적성의 원리 : 주어진 문제에 대한 최적해가 분할된 부분 문제의 최적해로 구성된다는 원리. - 2. 최적 해 보장 불가 - 3. 효율성 개선 그리디 알고리즘 수행절차 1. 해 선택 : 부분 해 집합에 추가 다음 항목 선택 현재 상태 최적화 기준 만족 여부 확인 2. 적합성 검증 : 새로운 부분 해 집합 조건 여부 확인 현재 집합이 해가 될 가능성 검사 3. 해 검증 : 신규 구성 집합이 해인지 검사 문제가 아니면 1번으로 돌아가서 반복 풀이 1...

도입 백준 단계별 풀기에서 분할정복 아홉 번째 문제이다. (참고로 1725번 문제와 결을 같이한다. 1725번의 경우는 스택을 이용해 푼다.) 풀이 1. 어떤 히스토그램에서 가장 왼쪽과 가장 오른쪽을 변으로 하는 가장 큰 직사각형의 높이는? 그 히스토그램에서 가장 높이가 낮은 막대를 높이로 하는 직사각형이 가장 크다. 2. 그렇다면 높이가 가장 낮은 막대를 히스토그램의 왼쪽(0번째)부터 m번째 막대라고 한다면, 우리는 m의 왼쪽과 m의 오른쪽으로 나눌 수 있다. 그렇다면 하나의 히스토그램에서 임의의 n개의 히스토그램으로 분할할 수 있다. 코드 #include #include #include using namespace std; typedef long long LL; vector h; // height v..

도입 백준 단계별 풀기에서 분할정복 여덟 번째 문제이다. 풀이 1. n이 매우 크다. - 점화식으로 푸는 DP 방법 = $O(N)$ -> 비추천 - 행렬로 변환한 풀이법(행렬 거듭제곱) - $O(M^3 * logN)$ -> 사용 2.1. 점화식을 행렬로 변환해보자. 2.2. 여기서 f1 과 f2 는 1이다. 그리고 거듭제곱 결과의 2x2 행렬을 a b c d로 치환하면 2.3. $F_{n+2} = a+b$ 이고 $F_{n+1} = c+d$가 된다. 2.4. 이제 $F_{n}$을 구해보자. n에 n-1을 대입한다. 그렇다면 n-1의 거듭제곱을 구하고 2번째 행의 2개 값을 더해주면 된다. 3. 곱셈 연산자 오버로딩을 사용한다. c++에서는 '연산자 오버로딩'을 찾아보면 더 자세한 내용들이 많을 것이다. p..

도입 백준 단계별 풀기에서 분할정복 일곱 번째 문제이다. 풀이 1.1. 행렬의 거듭제곱을 어떤식으로 할 것인가! 정사각형 행렬 A를 13번 거듭제곱을 한다고 가정해보자. A의 제곱부터 차례차례 A를 곱하는 방법이 있다. 하지만, 이렇게 하지 않는다. $A^{13}$이 $(A^6)^2*A$ 으로 표시할 수 있고, 여기서 $A^6$을 알고 있다면? 제곱연산을 2번만 하면 된다. 1.2. 지수가 홀수인가, 짝수인가. 홀수라면 $(A^k)*A$ 일 것이고, 짝수라면 $(A^k)^2$ 으로 표현할 수 있다. 1.3. 13을 2진법으로 표현해보자. $1101_2$ 이다. MSB로 계산을 한다. (LSB아님) 1일 때는 홀수로 계산하고 0일때는 짝수로 계산. 1 - $(A^0)^2*A$ = $A$ 1 - $(A^1)..

도입 백준 단계별 풀기에서 분할정복 여섯 번째 문제이다. 링크는 아래와 같다. www.acmicpc.net/problem/2740 2740번: 행렬 곱셈 첫째 줄에 행렬 A의 크기 N 과 M이 주어진다. 둘째 줄부터 N개의 줄에 행렬 A의 원소 M개가 순서대로 주어진다. 그 다음 줄에는 행렬 B의 크기 M과 K가 주어진다. 이어서 M개의 줄에 행렬 B의 원소 K개 www.acmicpc.net 풀이 1. 행렬을 어떻게 받을 것인가, 2차원 배열로 받겠다. 행과 열을 표현할 수 있기 때문이다. 2. 곱셈을 어떻게 할 것인가! 행렬의 곱셈을 다들 배웠다고 가정을 하겠다. 다음 그림 처럼 곱셈 로직을 짜겠다! 예를 들어서 2x3 크기의 행렬과 3x2 행렬을 곱셈하면 2x2행렬이 결과로 출력된다. Why? 첫 번..

백준 단계별 풀기에서 분할정복 다섯 번째 문제이다. 링크는 아래와 같다. www.acmicpc.net/problem/11401 11401번: 이항 계수 3 자연수 \(N\)과 정수 \(K\)가 주어졌을 때 이항 계수 \(\binom{N}{K}\)를 1,000,000,007로 나눈 나머지를 구하는 프로그램을 작성하시오. www.acmicpc.net 절대 단순한 문제가 아니다. 설계를 어떻게 하느냐에 따라 연산의 성능이 확연히 차이가 난다. 방법은 3가지가 있다. 1. 점화식을 이용한 방법 -> O(N^2)으로 시간 초과 2. 이항계수의 정의를 활용한 방법 2.1. 확장 유클리드(호제법) 2.2. 페르마 소정리 우리는 확장 유클리드 알고리즘과 페르마 소정리를 이용하고자 한다. (실제 백준 추천 알고리즘) 일..

백준 단계별 풀기에서 분할정복 네 번째 문제이다. 링크는 아래와 같다. www.acmicpc.net/problem/1629 1629번: 곱셈 첫째 줄에 A, B, C가 빈 칸을 사이에 두고 순서대로 주어진다. A, B, C는 모두 2,147,483,647 이하의 자연수이다. www.acmicpc.net 1. 시간복잡도를 생각해 보아야 하는 문제이다. 단순히 a^n 하면 시간 복잡도는 얼마인가? O(n)이다. 시간 복잡도가 무엇인가? 어떤 프로그램 또는 알고리즘이 수행하는데 소요되는 시간을 보여주는 것이라고 볼 수 있다. $$2^n > n^3 > n^2 > n*logn > n > logn > 1$$ 순이다. 여기서 분할정복 메커니즘을 활용한 알고리즘을 사용하면 O(log n)의 복잡도의 알고리즘으로 문제를..

백준 단계별 풀기에서 분할정복 세 번째 문제이다. 링크는 아래와 같다. www.acmicpc.net/problem/1780 1780번: 종이의 개수 N×N크기의 행렬로 표현되는 종이가 있다. 종이의 각 칸에는 -1, 0, 1의 세 값 중 하나가 저장되어 있다. 우리는 이 행렬을 적절한 크기로 자르려고 하는데, 이때 다음의 규칙에 따라 자르려고 한다. www.acmicpc.net 1. 분할정복 문제는 재귀함수의 활용이다. 분할정복 첫 문제를 해결하니, 두 번째 문제도 그렇고 이번 문제도 그렇고 굉장히 쉽게 해결하였다. 앞선 문제들이 배열 0과 1의 두 가지 변수만을 사용했다면, -1, 0, 1의 3가지 변수를 설정하고 접근하면 된다. 그리고 기존의 정사각형을 4등분 한것을 바탕으로, 이번에는 9등분을 하면..