algorithm

https://www.acmicpc.net/problem/13305 13305번: 주유소 표준 입력으로 다음 정보가 주어진다. 첫 번째 줄에는 도시의 개수를 나타내는 정수 N(2 ≤ N ≤ 100,000)이 주어진다. 다음 줄에는 인접한 두 도시를 연결하는 도로의 길이가 제일 왼쪽 도로부터 N-1 www.acmicpc.net C++로 작성한 백준 문제 13305번 주유소에 대한 문제 풀이다. 실버 3 문제이고, 그리디 알고리즘이 문제를 푸는데 필요한 주요 지식이다. 문제 설명 문제 어떤 나라에 N개의 도시가 있다. 이 도시들은 일직선 도로 위에 있다. 편의상 일직선을 수평 방향으로 두자. 제일 왼쪽의 도시에서 제일 오른쪽의 도시로 자동차를 이용하여 이동하려고 한다. 인접한 두 도시 사이의 도로들은 서로 ..

https://www.acmicpc.net/problem/11399 11399번: ATM 첫째 줄에 사람의 수 N(1 ≤ N ≤ 1,000)이 주어진다. 둘째 줄에는 각 사람이 돈을 인출하는데 걸리는 시간 Pi가 주어진다. (1 ≤ Pi ≤ 1,000) www.acmicpc.net C++로 작성한 백준 문제 11399번 ATM에 대한 문제 풀이다. 그리디 알고리즘과 정렬 이 문제를 푸는데 필요한 주요 지식이다. 문제 설명 문제 인하은행에는 ATM이 1대밖에 없다. 지금 이 ATM앞에 N명의 사람들이 줄을 서있다. 사람은 1번부터 N번까지 번호가 매겨져 있으며, i번 사람이 돈을 인출하는 데 걸리는 시간은 Pi분이다. 사람들이 줄을 서는 순서에 따라서, 돈을 인출하는데 필요한 시간의 합이 달라지게 된다. ..

https://www.acmicpc.net/problem/11047 11047번: 동전 0 첫째 줄에 N과 K가 주어진다. (1 ≤ N ≤ 10, 1 ≤ K ≤ 100,000,000) 둘째 줄부터 N개의 줄에 동전의 가치 Ai가 오름차순으로 주어진다. (1 ≤ Ai ≤ 1,000,000, A1 = 1, i ≥ 2인 경우에 Ai는 Ai-1의 배수) www.acmicpc.net 풀이 가장 기초적인 그리디 알고리즘 문제다. 동전을 가장 적게 가져가기 위해서는 , 큰 금액의 동전이 최대면 된다. 즉, 일단 총금액에서 최대의 동전을 가져갈 수 있을 만큼 가져가고, 그다음 크기의 동전을 가져갈 수 있을 만큼 가져가고.. 이걸 반복하면 된다. 예를들어 1260원이 있다 치면 500원으로 최대개수인 2개 가져가고, 2..

https://www.acmicpc.net/problem/2293 2293번: 동전 1 첫째 줄에 n, k가 주어진다. (1 ≤ n ≤ 100, 1 ≤ k ≤ 10,000) 다음 n개의 줄에는 각각의 동전의 가치가 주어진다. 동전의 가치는 100,000보다 작거나 같은 자연수이다. www.acmicpc.net 풀이 2차원 배열을 사용하는 dp로 접근했다. 가능한 돈의 경우의 수를 동전별로 따로 접근한다. 행에는 동전, 열에는 목표하는 원을 만들고, 그에 따라 가능한 경우의 수를 할당하였다. 배열의 열을 i라고 하고, 현재 사용하는 동전 행을 j라고 하자. 그리고 현재 n원 짜리 동전으로 계산하고 있다면 다음과 같은 점화식이 나온다. dp [i][j]=dp [i-1][j]+dp [i][j-n] 현재 dp에..

https://www.acmicpc.net/problem/9251 9251번: LCS LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다. 예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다. www.acmicpc.net 풀이 문제를 풀기 위해서는 주어진 2개의 문자열 중 하나를 기준으로 잡아 생각해야 한다. 여기서는 그 문자열을 기준문자열, 그렇지 않은 문자열을 비교문자열이라고 하겠다. ACAYKP가 여기서는 기준문자열, CAPCAK가 비교문자열이다. 기준문자열의 길이만큼 dp 배열을 만든다. 즉 배열 칸이 의미하는 것은 각 번째의 문자를 말한다. 문자열 A C A Y..

https://www.acmicpc.net/problem/11054 11054번: 가장 긴 바이토닉 부분 수열 첫째 줄에 수열 A의 크기 N이 주어지고, 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ N ≤ 1,000, 1 ≤ Ai ≤ 1,000) www.acmicpc.net 풀이 이 문제를 보고 가장 먼저 생각난 것은 바이토닉 수열의 중앙점이다 S1 ... SN-1 > SN에서 Sk를 말하는 것이다. Sk를 어디로 S1~SN 중 어디로 할지 정하고, S1~SK에서 나오는 증가하는 부분수열의 개수+ SK~SN에서 나오는 감소하는 부분수열의 개수를 K 값에 따라 비교해 최댓값을 출력하면 된다. 2023.06.11 - [algorithm/dp] - [백준] 11053번:..

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차원 배열을 사용해서 풀면 된다. 열은 무게를, 행은 몇 번째 물건까지 넣었는지 표시하고, 테이블의 각 자리에 가치를 저장한다. 냅색문제에서 물건을 대할때 선택지는 2가지다. 물건을 넣던가 혹은 그렇지 않던가. 1. 그래서 물건을 넣지 않을 거면 이전 행에서 그대로 할당받고 2. 물건을 넣..

https://www.acmicpc.net/problem/2565 2565번: 전깃줄 첫째 줄에는 두 전봇대 사이의 전깃줄의 개수가 주어진다. 전깃줄의 개수는 100 이하의 자연수이다. 둘째 줄부터 한 줄에 하나씩 전깃줄이 A전봇대와 연결되는 위치의 번호와 B전봇대와 연결되는 www.acmicpc.net 풀이 결국 전깃줄끼리 꼬이지 않게 하려면 어떻게 하야할까? 전깃줄들을 A에서 B로 간다는 관점으로 바라보자. A에서 시작하는 점을 1~10까지 오름차순으로 정렬할 때. 그 줄에 대응하는 B 역시 오름차순으로 정렬되면 된다. 문제에서는 (A,B) 형태로 입력을 받는다. 그렇다면 A와 B를 pair형태로 저장하고, A를 기준으로 정렬한다. 그리고 A를 기준으로 정렬한 페어쌍에서 B부분만 추출해, 몇 개가 빠..