Heecheol's blog

문제 https://www.acmicpc.net/problem/14502 14502번: 연구소 인체에 치명적인 바이러스를 연구하던 연구소에서 바이러스가 유출되었다. 다행히 바이러스는 아직 퍼지지 않았고, 바이러스의 확산을 막기 위해서 연구소에 벽을 세우려고 한다. 연구소는 크 www.acmicpc.net 풀이 처음에는 벽을 어디에 세워야 바이러스가 최소한으로 퍼질지 고민을 오래했다. 근데 벽의 개수가 반드시 3개이고 n과 m이 큰 숫자도 아니기때문에 일단 모든 경우를 구해보기로 했다. 우선, 0인 위치를 전부 찾아서 3개로 만들 수 있는 모든 조합을 구했다. 다음으로 각 조합별로 실제로 벽을 세워 각각 BFS를 돌려 확인했다. 각 경우마다 안전범위를 구하는 것은 직접 하나하나 확인하지 않고, 처음에 구했..

문제 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..