백준 11053번 동적 계획법(Dynamic Programming)으로 풀 수 있는 문제이다. 11053번: 가장 긴 증가하는 부분 수열 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이 www.acmicpc.net 문제는, 수열 A에서 이를 어떻게하면 가장 긴 부분 수열로 나열할 수 있고, 이의 길이를 출력으로 보여주는 문제이다. 처음 문제의 풀이 과정을 생각할 때, 너무 단순하게 생각했다. 왜 이 문제를 DP을 이용해서 풀어야하는지 몰라서 소팅을 실행하고 중복된 숫자만 제거해서 최종적으로 남은 숫자의 ..

백준 2217번 그리디 알고리즘(Greedy Algorithm)을 통해 풀이하는 문제이다. 정답률이 높았던만큼 큰 고민없이 쉽게 풀 수 있던 문제였다. 문제는 N(1 ~ 100,000)개의 로프가 있다. 여기서 로프를 이용해서 중량이 w인 물건을 들어올릴 수 있는데 로프를 병렬로 연결해서 물체를 들어올리면 (w/로프의 개수)의 중량으로 들 수 있다. 여기서 로프를 사용해서 들 수 있는 최대 중량을 구하는 것이 문제였다. 문제의 답을 찾는 과정을 생각하는 것이 크게 어렵지 않았다. 각 로프가 버틸 수 있는 중량이 주어지는데 주어진 중량 중에 가장 버틸 수 있는 중량이 적은 로프가 버틸 수 있는 무게가 로프 몇개일 때, 가장 큰지 찾으면 됐다. 우선 각 로프가 버틸 수 있는 크기를 오름차순으로 정렬하고 찾아..

백준 2156번 동적 계획법(Dynamic Programming)으로 풀 수 있는 문제이다. 문제를 읽어보면, 포도잔의 개수가 N개 있고, 이를 선택하여 마실 수 있다. 그러나 조건이 있다. 연속해서 위치한 3잔을 모두 마실 수는 없다. 여기서 가장 많은 양의 포도주를 마실 수 있는 양은 얼마인지 구해야한다. 점화식을 생각하게 되었고, 이전에 풀어봤던 문제 유형이랑 비슷해서 방법을 떠올리는 건 쉽게할 수 있었다. 그러나, 하나 사소한 부분에서 실수로 return문을 적지 않아 '왜 틀렸지...'하며 시간을 조금 낭비했다. DP로 풀기 위해선 점화식을 세우는게 중요한데, 우선 초기 조건을 잘 확인해서 풀어야한다. N이 1, 2, 3일 때를 나누어서 초기 조건을 세웠다. if (N == 1) { System..

백준 1912번 동적 계획법(Dynamic Programming)으로 풀 수 있는 문제이다. 1912번: 연속합 첫째 줄에 정수 n(1 ≤ n ≤ 100,000)이 주어지고 둘째 줄에는 n개의 정수로 이루어진 수열이 주어진다. 수는 -1,000보다 크거나 같고, 1,000보다 작거나 같은 정수이다. www.acmicpc.net 먼저 문제를 보고 시작하면, n개의 정수로 이루어진 수열을 입력으로 받는다. 그리고 이 중 몇 개의 수를 선택해서 모두 더한다. 이 중 가장 크게 나올 수 있는 수를 찾는 문제이다. 여기서 주어진 조건은 꼭 연속된 수를 선택하여야한다. 여기서 처음 문제를 풀 때, 실수를 하였던 부분은 N개의 숫자를 연속으로 선택해서 합이 가장 큰 수를 선택하여야하기 때문에 모든 경우의 수를 더하는..

백준 14502번 DFS, BFS를 같이 사용해야 풀 수 있는 문제이다. 문제를 보게 되면, N * M 인 직사각형의 연구소가 있다. 여기서 연구소 각 칸은 1 * 1의 크기를 가지며 빈 칸, 벽으로 이루어진다. 여기서 일부의 칸에는 바이러스가 존재하게 되고 바이러스는 상하좌우로 퍼져나갈 수 있다. 그러나 벽이 존재하는 칸으로는 퍼지지 못한다. 여기서 꼭 벽 3개를 세워서 가장 바이러스가 감염되지 않는 칸을 많이 나오게 하는 수를 찾는 문제이다. 연구소 문제로 처음에 벽을 어떻게 3개를 세워야할까 긴가민가해서 고민을 많이 했던 문제다. 다른 사람의 방법을 보기 위해 검색을 좀 해봤고,, 그 결과, 벽을 세우기 위해선 결국 DFS을 통해 완전 탐색이 필요하다는 것을 알게 됐다. 이후, 느낌을 알았고 세워진..

백준 2178번 기본적인 BFS 문제이다. 일단 문제를 확인하게 되면, (1, 1)에서 (N, M)까지의 배열상태를 나타내는 int형 배열이 주어지고 (1, 1)에서 시작해서 (N, M)까지 가는데 가장 최소의 길로 갈 때, 지나쳐 온 칸의 수를 세어주는 문제이다. 여기서 조건이 주어지는 것은 미로에서 1인 칸만 이동할 수 있고 0인 칸은 이동할 수 없다는 것이다. 일단 알고리즘을 풀 때, BFS로 풀게되는 경우는 최소라는 단어가 들어갔으면 BFS로 접근하여 풀이법을 생각합니다. 보통 그렇더라구요... 이 문제는 기본적인 BFS문제이기 때문에 풀이법은 보통의 BFS 풀이하는 방법과 동일합니다. 추가되는 것은 지나쳐 온 칸의 수를 카운트하기 위해 별도의 배열을 하나 더 두는 것 밖에 없습니다. 우선 소스코..