목록분류 전체보기 (341)

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

[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 ··· 15 16 17 18 19 20 21 ··· 35 Next

티스토리툴바