Heecheol's blog

문제 https://www.acmicpc.net/problem/11054 11054번: 가장 긴 바이토닉 부분 수열 첫째 줄에 수열 A의 크기 N이 주어지고, 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ N ≤ 1,000, 1 ≤ Ai ≤ 1,000) www.acmicpc.net 풀이 전깃줄문제에서 배웠던 LIS문제였다. 우선, 나는 주어진 입력에서 각 원소별로 LIS 길이를 구해서 result에 넣어주었다. 해당 숫자까지 다시 반복문을 통해 오름차순의 길이를 구해주었다. max를 이용해 현재 값과 이전의 값의 1을 더한 값을 비교해주었다. 바로 1을 더한 값으로 바꿔주지 않은 이유는 단순하게 작은 숫자만 확인하는 것이 아니라 오름차순이기때문에 result[j] + 1의 값과 비교를 해..

문제 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 풀이 knapsack이라는 유명한 문제라고한다. 문제와 똑같이 가방 안에 물건을 넣을 때, 최대 무게를 넘지 않고 최대의 가치를 구하는 문제이다. 풀이를 이해하기가 쉽지 않아서 자료를 많이 찾아봤던 것 같다.(내 머리가 모자라다는걸 다시 한 번 느낄 수 있었음) 일단 이 문제는 knapsack 문제 중에서도 0/1 knapsa..

문제 https://www.acmicpc.net/problem/2156 2156번: 포도주 시식 효주는 포도주 시식회에 갔다. 그 곳에 갔더니, 테이블 위에 다양한 포도주가 들어있는 포도주 잔이 일렬로 놓여 있었다. 효주는 포도주 시식을 하려고 하는데, 여기에는 다음과 같은 두 가지 규 www.acmicpc.net 풀이 보자마자 계단오르는 문제와 비슷하다고 생각해서 똑같이 풀었지만 바로 틀렸었다. 계단 문제는 1칸 또는 2칸을 반드시 올라가면서 끝까지 올라가야하는 문제였다. 연속해서 세 계단을 올라갈 수 없다는 조건과 연속으로 놓여있는 세 잔을 모두 마실 수 없다는 조건만 보고 같다고 판단하여 풀었던 것인데, 생각해보면 비슷하지만 다른 문제였다. 이 문제의 경우는 1잔 또는 2잔을 반드시 마셔야하는 것이..

문제 https://www.acmicpc.net/problem/11053 11053번: 가장 긴 증가하는 부분 수열 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이 www.acmicpc.net 풀이 이전에 풀었던 전깃줄 문제에서 배웠던 LIS를 직접적으로 알 수 있는 문제였다. 가장 긴 증가하는 부분 수열을 구하기만 하면 되므로 max값을 출력해주면 된다. import Foundation let n = Int(readLine()!)! var numbers = readLine()!.split(separat..

문제 https://www.acmicpc.net/problem/2565 2565번: 전깃줄 첫째 줄에는 두 전봇대 사이의 전깃줄의 개수가 주어진다. 전깃줄의 개수는 100 이하의 자연수이다. 둘째 줄부터 한 줄에 하나씩 전깃줄이 A전봇대와 연결되는 위치의 번호와 B전봇대와 연결되는 www.acmicpc.net 풀이 이 문제를 처음 봤을 땐, 어떻게 dp로 풀어야하는지 전혀 감이 안왔다. 그래서 검색을 해보니 LIS와 관련이 있다고했다. LIS란 최장 증가 부분 수열이라는 의미로, 말그대로 배열 안에서 증가하는 부분 수열중 가장 긴 수열을 의미한다. 예를 들어, [1,4,5,3,8,6,9]라는 arr배열이 있을 때 최장 증가 부분 수열은 [1,4,5,6,9]를 나타낸다. LIS를 구할 때 dp가 사용되는 ..