목록알고리즘/C++ (56)

수학과의 좌충우돌 프로그래밍

[C++] BAEKJOON 10830 행렬 제곱

https://www.acmicpc.net/problem/2740 2740번: 행렬 곱셈 첫째 줄에 행렬 A의 크기 N 과 M이 주어진다. 둘째 줄부터 N개의 줄에 행렬 A의 원소 M개가 순서대로 주어진다. 그 다음 줄에는 행렬 B의 크기 M과 K가 주어진다. 이어서 M개의 줄에 행렬 B의 원소 K개가 차례대로 주어진다. N과 M, 그리고 K는 100보다 작거나 같고, 행렬의 원소는 절댓값이 100보다 작거나 같은 정수이다. www.acmicpc.net 행렬을 제곱하는 문제입니다. B 범위가 100,000,000,000 까지 이기 때문에 곱셈을 여러 번 한다면 시간복잡도에 걸리게 됩니다. 따라서 행렬에 대해서 분할 정복을 통해서 제곱을 수행합니다. 그리고 행렬의 곱셈을 하는 함수 matrixMul와 단위..
알고리즘/C++ 2019. 9. 10. 20:21
[C++] BAEKJOON 11049 행렬 곱셈 순서

https://www.acmicpc.net/problem/11049 11049번: 행렬 곱셈 순서 첫째 줄에 입력으로 주어진 행렬을 곱하는데 필요한 곱셈 연산의 최솟값을 출력한다. 정답은 231-1 보다 작거나 같은 자연수이다. 또한, 최악의 순서로 연산해도 연산 횟수가 231-1보다 작거나 같다. www.acmicpc.net 동적계획법 중 top-down 방식을 사용했습니다. dp[i][j] 는 i 부터 j 까지의 행렬을 곱하는 연산의 최솟값 으로 정의하였습니다. i, j 가 인접해있다면, 즉 1 차이가 난다면 두 행렬의 곱셈을 직접 계산해주고 인접해있지 않다면 부분으로 쪼개 각각을 계산해준 후, 계산한 결과인 두 개의 행렬의 곱셈은 직접 계산해주었습니다. #include #include using n..
알고리즘/C++ 2019. 9. 8. 15:16
[C++] BAEKJOON 11066 파일합치기

https://www.acmicpc.net/problem/11066 11066번: 파일 합치기 문제 소설가인 김대전은 소설을 여러 장(chapter)으로 나누어 쓰는데, 각 장은 각각 다른 파일에 저장하곤 한다. 소설의 모든 장을 쓰고 나서는 각 장이 쓰여진 파일을 합쳐서 최종적으로 소설의 완성본이 들어있는 한 개의 파일을 만든다. 이 과정에서 두 개의 파일을 합쳐서 하나의 임시파일을 만들고, 이 임시파일이나 원래의 파일을 계속 두 개씩 합쳐서 소설의 여러 장들이 연속이 되도록 파일을 합쳐나가고, 최종적으로는 하나의 파일로 합친다. 두 개의 파일을 www.acmicpc.net 동적계획법을 사용하여 문제를 해결하였습니다 . 그 중에서도 top-down 방식입니다. dp[i][j] 는 i 부터 j 까지의 파..
알고리즘/C++ 2019. 9. 7. 22:40
[C++] BAEKJOON 1520 내리막길

https://www.acmicpc.net/problem/1520 1520번: 내리막 길 여행을 떠난 세준이는 지도를 하나 구하였다. 이 지도는 아래 그림과 같이 직사각형 모양이며 여러 칸으로 나뉘어져 있다. 한 칸은 한 지점을 나타내는데 각 칸에는 그 지점의 높이가 쓰여 있으며, 각 지점 사이의 이동은 지도에서 상하좌우 이웃한 곳끼리만 가능하다. 현재 제일 왼쪽 위 칸이 나타내는 지점에 있는 세준이는 제일 오른쪽 아래 칸이 나타내는 지점으로 가려고 한다. 그런데 가능한 힘을 적게 들이고 싶어 항상 높이가 더 낮은 지점으로만 이동하여 목표 지 www.acmicpc.net 동적계획법을 사용한 문제입니다. dp[i][j] 을 (i,j) 에서 시작해서 (N,M) 까지 가는 경로의 수 라고 정의하였습니다. 이 ..
알고리즘/C++ 2019. 9. 7. 21:15
[C++] BAEKJOON 2293 동전 1

https://www.acmicpc.net/problem/2293 2293번: 동전 1 첫째 줄에 n, k가 주어진다. (1 ≤ n ≤ 100, 1 ≤ k ≤ 10,000) 다음 n개의 줄에는 각각의 동전의 가치가 주어진다. 동전의 가치는 100,000보다 작거나 같은 자연수이다. www.acmicpc.net 동적계획법을 활용한 문제입니다. dp[i] 를 i 원에 대해서 주어진 동전으로 만들 수 있는 경우의 수라고 정의했습니다. 처음에는 동전을 하나만 사용하여 계산할 수 있는 경우의 수를 채우고, 이를 활용하여 동전 2개를 사용했을 경우, 3개, 4개 … 다음과 같이 늘려나가게 됩니다. 주어진 문제의 예시 처럼 1,2,5 원으로 10원을 만들려고 한다면 10원을 만드는 경우의수 = 9원까지의 경우의 수(..
알고리즘/C++ 2019. 9. 6. 21:48
[C++] BAEKJOON 2156 포도주 시식

https://www.acmicpc.net/problem/2156 2156번: 포도주 시식 효주는 포도주 시식회에 갔다. 그 곳에 갔더니, 테이블 위에 다양한 포도주가 들어있는 포도주 잔이 일렬로 놓여 있었다. 효주는 포도주 시식을 하려고 하는데, 여기에는 다음과 같은 두 가지 규칙이 있다. 포도주 잔을 선택하면 그 잔에 들어있는 포도주는 모두 마셔야 하고, 마신 후에는 원래 위치에 다시 놓아야 한다. 연속으로 놓여 있는 3잔을 모두 마실 수는 없다. 효주는 될 수 있는 대로 많은 양의 포도주를 맛보기 위해서 어떤 포도주 잔을 선택해야 할지 고 www.acmicpc.net 동적계획법으로 접근하였습니다. dp[i] 에 대해 i 번 째 포도주 까지에 대해 최대로 마실 수 있는 포도주의 양 이라고 정의했습니다..
알고리즘/C++ 2019. 9. 6. 20:59
[C++] BAEKJOON 10942 팰린드롬?

https://www.acmicpc.net/problem/10942 10942번: 팰린드롬? 총 M개의 줄에 걸쳐 홍준이의 질문에 대한 명우의 답을 입력으로 주어진 순서에 따라서 출력한다. 팰린드롬인 경우에는 1, 아닌 경우에는 0을 출력한다. www.acmicpc.net 일반적으로 팰린드롬을 판별하기 위해서는 맨 앞과 맨 뒤, 앞에서 두번째와 뒤에서 두번째 … 다음과 같이 비교해봐야 하므로 O(N) 의 시간복잡도가 걸립니다. 이 문제 같은 경우에는 질문이 M 개이므로 전체 시간복잡도는 O(MN) 이 됩니다. 이 때 M 의 범위가 1 ≤ M ≤ 1,000,000 이므로 시간초과에 걸리게 됩니다. 이를 해결하기 위해서 동적계획법 으로 접근하였습니다. 길이가 1 인 경우 길이가 1인 경우에는 앞에서 읽던 뒤..
알고리즘/C++ 2019. 9. 6. 12:05
[C++] BAEKJOON 1890번 점프

https://www.acmicpc.net/problem/1890 1890번: 점프 문제 N×N 게임판에 수가 적혀져 있다. 이 게임의 목표는 가장 왼쪽 위 칸에서 가장 오른쪽 아래 칸으로 규칙에 맞게 점프를 해서 가는 것이다. 각 칸에 적혀있는 수는 현재 칸에서 갈 수 있는 거리를 의미한다. 반드시 오른쪽이나 아래쪽으로만 이동해야 한다. 0은 더 이상 진행을 막는 종착점이며, 항상 현재 칸에 적혀있는 수만큼 오른쪽이나 아래로 가야 한다. 한 번 점프를 할 때, 방향을 바꾸면 안 된다. 즉, 한 칸에서 오른쪽으로 점프를 하거나, 아래로 www.acmicpc.net 처음에는 bfs 나 dfs 를 생각하기 쉬운 문제지만 dp 를 사용해서 해결해야하는 문제입니다. dp 배열을 생성하여 각 원소는 해당 지점까지..
알고리즘/C++ 2019. 9. 6. 02:19
Prev 1 2 3 4 5 6 Next

티스토리툴바