Development Artist

도입 백준 단계별 풀기에서 분할정복 여섯 번째 문제이다. 링크는 아래와 같다. 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등분을 하면..

도입 백준 단계별 풀기에서 분할정복 두 번째 문제이다. 풀이 1. 앞의 '색종이 만들기' 문제와 유사하다. 재귀함수를 활용한다. 정사각형을 4개씩 쪼개면서 재귀함수를 호출하는 방식은 같으나, 출력에서 '('와 ')'를 해주어야 하는데 어디서 해야할까? 4개씩 재귀를 호출하는 곳에서 시작에서 '('를 해주고 재귀를 마칠때 ')'를 출력해주면 된다. 함수call의 특성에서 a라는 함수가 수행 되는 중 b라는 함수가 call이 되면 a 함수는 사라지는 것이 아니다. stack구조 처럼 생각하자. a함수 수행 중 b함수가 call이 되면 a함수는 stack에 push된다(대기한다). 그리고 b가 다 수행이 되면 a함수가 stack에서 pop되면서 이전의 수행지점을 찾아 그 이후부터 수행이 된다. 따라서, a함수..

백준 단계별 풀기에서 분할정복 첫번째 문제이다. 링크는 아래와 같다. www.acmicpc.net/problem/2630 18258번: 큐 2 첫째 줄에 주어지는 명령의 수 N (1 ≤ N ≤ 2,000,000)이 주어진다. 둘째 줄부터 N개의 줄에는 명령이 하나씩 주어진다. 주어지는 정수는 1보다 크거나 같고, 100,000보다 작거나 같다. 문제에 나와있지 www.acmicpc.net 1. 분할정복 문제는 재귀함수를 활용하는 것이다. 문제를 직면했을 때, 그것을 쪼개갠 작은 문제들을 해결한다면 그 문제들의 해결이 곧 그 문제의 해결이라는 것이다. 아래의 그림을 보자. 이번 문제에서 큰 사각형으로 바라본다면 사각형 안에 파란색, 하얀색 두가지가 섞여 있을 것이다. 하지만, 다음과 같이 쪼개고 쪼개다 보..

백준 단계별 풀기에서 큐,덱 일곱번째, 마지막 문제이다. 링크는 아래와 같다. www.acmicpc.net/problem/5430 5430번: AC 각 테스트 케이스에 대해서, 입력으로 주어진 정수 배열에 함수를 수행한 결과를 출력한다. 만약, 에러가 발생한 경우에는 error를 출력한다. www.acmicpc.net 1. 4가지를 입력 받는다, Testcase 개수를 우선적으로 받고, 각 Testcase 마다 RD연산 함수, 배열의 개수, 배열 3가지를 받는다. 일단은 배열을 어떤 타입으로 받을 것인지에 대한 고민이 필요하다. [x, y, z, q] 이런식으로 입력을 받아야 한다. 필자는 string으로 받아서 parsing을 통해 정수 배열로 만들어 줄 것이다. 일단 string으로 받게 되면 어떤식..

백준 단계별 풀기에서 큐,덱 여섯번째 문제이다. 링크는 아래와 같다. www.acmicpc.net/problem/1021 1021번: 회전하는 큐 첫째 줄에 큐의 크기 N과 뽑아내려고 하는 수의 개수 M이 주어진다. N은 50보다 작거나 같은 자연수이고, M은 N보다 작거나 같은 자연수이다. 둘째 줄에는 지민이가 뽑아내려고 하는 수의 위치가 www.acmicpc.net 1. deque를 활용한 문제이다. deque를 활용하면, 회전하는 큐를 구현할 수 있다. 2. 2번, 3번 연산을 하는 최소값을 구하려면, 우선 덱(deque)에서 빼내고자 하는 정수의 위치를 알 수 있어야한다. 그래야 2번 연산을 할지, 3번 연산을 할지 선택할 수 있기 때문이다. 처음에는 단순히, 덱의 사이즈를 반으로 나눠 구하고자 ..

백준 단계별 풀기에서 큐,덱 다섯번째 문제이다. 링크는 아래와 같다. www.acmicpc.net/problem/10866 18258번: 큐 2 첫째 줄에 주어지는 명령의 수 N (1 ≤ N ≤ 2,000,000)이 주어진다. 둘째 줄부터 N개의 줄에는 명령이 하나씩 주어진다. 주어지는 정수는 1보다 크거나 같고, 100,000보다 작거나 같다. 문제에 나와있지 www.acmicpc.net 1. Deque 라이브러리를 사용한다. 기본적으로 deque 라이브러리에서 제공하는 함수들이 지금 문제의 전부를 해결할 수 있다. en.cppreference.com/w/cpp/container/deque 해당 링크는 deque 라이브러리를 정리한 곳이다. #include #include using namespace ..

백준 단계별 풀기에서 큐,덱 네 번째 문제이다. 링크는 아래와 같다. www.acmicpc.net/problem/1966 18258번: 큐 2 첫째 줄에 주어지는 명령의 수 N (1 ≤ N ≤ 2,000,000)이 주어진다. 둘째 줄부터 N개의 줄에는 명령이 하나씩 주어진다. 주어지는 정수는 1보다 크거나 같고, 100,000보다 작거나 같다. 문제에 나와있지 www.acmicpc.net 1. priority queue를 사용한다. 일반 queue와 다른 점은 숫자를 push 할 때 자동으로 정렬을 해준다는 점이다. 1 2 3 4 순서대로 넣는다면, 4 3 2 1로 위치하게 된다. priority_queue.top()을 해보면 4가 먼저 나오는 것을 확인할 수 있다. 2. queue에 값을 넣을 때 pa..