본문 바로가기

코딩공부66

(c++) 동적계획법 BOJ 2629번: 양팔저울 https://www.acmicpc.net/problem/2629 2629번: 양팔저울 첫째 줄에는 추의 개수가 자연수로 주어진다. 추의 개수는 30 이하이다. 둘째 줄에는 추의 무게들이 자연수로 가벼운 것부터 차례로 주어진다. 같은 무게의 추가 여러 개 있을 수도 있다. 추의 무 www.acmicpc.net 문제 개요 배낭 문제와 동일한 냅색(KnapSack) 문제 중 하나이다. 배낭 문제는 물건을 넣기, 물건을 안 넣기 두 개로 나누었는데 양팔 저울 문제는 세 가지로 나눈다. 추를 안 올리기 왼쪽에 추 올리기 오른쪽에 추 올리기 왼쪽 저울에 비교할 추가 올라간다고 생각하면 왼쪽에 추를 올릴 경우 비교할 추 무게를 더해주면 되고 오른쪽에 추를 올릴 경우는 비교할 추 무게를 빼주면 된다. // 안 넣기 .. 2024. 1. 23.
(c++) 동적계획법 BOJ 1520번: 내리막 길 https://www.acmicpc.net/problem/1520 1520번: 내리막 길 여행을 떠난 세준이는 지도를 하나 구하였다. 이 지도는 아래 그림과 같이 직사각형 모양이며 여러 칸으로 나뉘어져 있다. 한 칸은 한 지점을 나타내는데 각 칸에는 그 지점의 높이가 쓰여 있으 www.acmicpc.net 문제 개요 현재 위치보다 작은 상하좌우로 이동할 수 있는 것으로 재귀를 이용하여 시작 위치에서 끝 위치까지의 거리를 계산하면 되는 문제이다. 현재 위치보다 다음 위치가 작을 경우 현재 위치에 값을 더해주는 것으로 코드를 짜보았다. 함수에는 x, y가 끝 위치와 같다면 1을 리턴해주는 조건을 달아서 시작 위치인 (0, 0)에서 결괏값이 저장되도록 한다. 코드 위치 이동같은 경우 구현 문제와 마찬가지로 미.. 2024. 1. 22.
(c++) 동적계획법 BOJ 11049번: 행렬 곱셈 순서 https://www.acmicpc.net/problem/11049 11049번: 행렬 곱셈 순서 첫째 줄에 입력으로 주어진 행렬을 곱하는데 필요한 곱셈 연산의 최솟값을 출력한다. 정답은 231-1 보다 작거나 같은 자연수이다. 또한, 최악의 순서로 연산해도 연산 횟수가 231-1보다 작거나 같 www.acmicpc.net 문제 개요 재귀를 이용한 메모이제이션을 사용하는 동적 계획법 문제이다. 나름대로 점화식을 만들어보면 $$ M[i][j] = min(M[i][j], M[i][k]+M[k+1][j]+D(i,k,j)) $$ 문제의 예제로 주어진 (5, 3), (3, 2), (2, 6)들의 최솟값을 구하려면 각 경우가 1번째, 2번째, 3번째라고 했을 때 1 * (2 * 3), (1 * 2) * 3 이렇게 .. 2024. 1. 21.
(c++) BOJ 12865번: 평범한 배낭 https://www.acmicpc.net/problem/12865 12865번: 평범한 배낭 첫 줄에 물품의 수 N(1 ≤ N ≤ 100)과 준서가 버틸 수 있는 무게 K(1 ≤ K ≤ 100,000)가 주어진다. 두 번째 줄부터 N개의 줄에 거쳐 각 물건의 무게 W(1 ≤ W ≤ 100,000)와 해당 물건의 가치 V(0 ≤ V ≤ 1,000) www.acmicpc.net 문제 개요 동적 계획법에서 유명한 문제인 배낭 문제이다. 일반적으로 푼다면 전체 2^n 의 경우의 수가 나오는데 물품을 가져갈지, 가져가지 않을지 두 가지 중에서 가치합이 큰 경우를 골라주는 알고리즘을 구현하면 된다. 물품을 가져가지 않을 경우 pack(남은 용량, 물품 수 +1) 물품을 가져가는 경우 pack(남은 용량 - 선택 .. 2024. 1. 19.
(c++) BOJ 9251번: LCS https://www.acmicpc.net/problem/9251 9251번: LCS LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다. 예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다. www.acmicpc.net 문제 개요 LCS(최장 공통 부분 수열) 문제는 https://ko.wikipedia.org/wiki/%EC%B5%9C%EC%9E%A5_%EA%B3%B5%ED%86%B5_%EB%B6%80%EB%B6%84_%EC%88%98%EC%97%B4 최장 공통 부분 수열 - 위키백과, 우리 모두의 백과사전 위키백과, 우리 모두의 백과사전. 최장 공통 부분수열 문제는.. 2024. 1. 18.
(c++) LIS BOJ 2565번: 전깃줄 https://www.acmicpc.net/problem/2565 2565번: 전깃줄 첫째 줄에는 두 전봇대 사이의 전깃줄의 개수가 주어진다. 전깃줄의 개수는 100 이하의 자연수이다. 둘째 줄부터 한 줄에 하나씩 전깃줄이 A전봇대와 연결되는 위치의 번호와 B전봇대와 연결되는 www.acmicpc.net 문제 개요 문제만 보면 LIS를 어떻게 이용할지 감이 안 잡히는데 겹친다는 개념을 생각해보면 답이 나온다. 전봇대는 오름차순 순서대로 두 개가 세워져있고, 그 사이 전깃줄이 있는 형태이다. 전깃줄이 겹치려면 아래의 경우를 만족해야 한다. 왼쪽에 있는 숫자가 작은 것이 연결되어있는 오른쪽 숫자가 더 클 경우 ex) 1 - 4, 2 - 1 겹침 왼쪽 전봇대가 정렬되있는 순서대로 오른쪽 전봇대에 연결된 숫자를.. 2024. 1. 18.

티스토리툴바