케이스윔의 개발 블로그

문제건물 순서 규칙이 주어지고, 해당 규칙에 맞춰서 건물을 지을 때 특정건물을 가장 빨리 지을 때까지 걸리는 최소시간을 알아내는 프로그램을 작성하시오.문제 출처: 백준 온라인저지(https://www.acmicpc.net/problem/1005) 풀이처음엔 BFS를 써서 풀어봐야겠다! 라고 생각을 했는데 먼저 풀어본 친구가 BFS를 쓰면 시간초과가 난다고 알려주어서 고민을 했던 문제입니다. 그리고 떠오른 것은 topological sort였습니다. topological sort는 어떠한 사건이 선행되어야 다음 사건을 진행할 수 있는 관계들이 주어질 때 활용할 수 있는 방법입니다.(이후에 topological sort라는 포스팅을 통해 자세히 다뤄보도록 하겠습니다.) 이 문제에서도 2번, 3번 건물을 무조..

문제각 칸의 높이가 적인 지도가 주어질 때 제일 왼쪽 위 지점에서 출발하여 제일 오른쪽 아래 지점까지 항상 내리막길로만 이동하는 경로의 개수를 구하는 프로그램을 작성하시오.문제 출처: 백준 온라인저지(https://www.acmicpc.net/problem/1520) 풀이처음에 문제를 꼼꼼히 읽지 않고 오른쪽으로만, 아래쪽으로만 이동할 수 있도록 dp를 구현했었습니다. 그런데 문제에서 주어진 조건은 낮은 높이로 이동할 수 있는 모든 경우를 알아내야하기 때문에 지도상으로는 더 아래있는 칸에서 위로도 이동할 수 있는 경로가 있었습니다. 정렬을 써서 해야한다는 힌트를 얻었지만 어떻게 활용할지 생각이 나지 않았는데 큰 칸 먼저 dp의 값을 계산하면 4방향에서 오는 모든 경우를 구할 수 있겠다는 생각이 들었습니다..

문제두 문자열이 주어질 때 부분 수열 중 가장 긴 부분 수열의 길이를 구하시오.문제 출처: 백준 온라인저지(https://www.acmicpc.net/problem/9251) 풀이처음에 이 문제를 보고 잘 못풀 것 같다는 생각이 들어서 넘겨버렸었는데 다시 풀어보았습니다! 생각보다 쉬운 문제였는데 LCS알고리즘이란 말이 붇어있으니 어려워 보여서 못 풀었던 것 같기도..합니다. 이전에 풀었던 문제는 숫자의 배열이 주어지면 그것을 통해 가장 긴 증가 수열의 길이를 구하는 것이었는데 문자열을 통해서 공통된 부분을 찾는다고 접근하려니 어렵게 느껴졌습니다. 두 문자열을 쪼개어서 차례차례 생각을 하면 풀어나갈 수 있습니다. 만약 두 문자열이 'ABC'와 'ADB'라고 하겠습니다. 문자열을 첫번째문자부터 잘라서 보면 ..

문제1부터 N까지 마을이 있을 때 마을을 순회할 수 있는 최소비용을 구하시오.문제 출처: 백준 온라인저지(https://www.acmicpc.net/problem/2098) 풀이이 문제는 Bitmask를 사용해서 dp를 만들어 나가보려고 푼 문제입니다. 여기서는 모든 마을을 순회해야할 때 방문한 마을을 표시하기 위해 Bitmask를 사용해보았습니다. dp를 통해 문제를 풀기 위해 배열이 필요하고, Bitmask를 사용한다면 어느 마을을 방문했는지 알 수 있으므로 dp배열에서 바로 사용을 할 수 있게 됩니다. 1번 마을을 방문했다면 1이고, 2번 마을을 방문했다면 10, 3번 마을을 방문했다면 100, 세 마을을 전부 방문했다면 111로 표현할 수 있습니다. 이 때 특정한 i번째의 마을을 방문했는지 알려면..

문제N, L, R이 주어진다. N개의 건물을 왼쪽에서 보았을 때는 L개가 보이고 오른쪽에서 보았을 때 R개가 보이는 경우의 수를 구하시오.문제 출처: 백준 온라인저지(https://www.acmicpc.net/problem/1328) 풀이처음에 보자마자 너무 어렵다고 생각이 들었습니다! 그리고 아주 이상한 방법으로 많이 접근을 했습니다. 다이나믹 프로그래밍 카테고리에서 골랐기 때문에 dp로 풀어야겠다는 생각은 들었지만 점화식을 세울 수 없었습니다. 처음엔 1~N까지의 건물이 주어질 때 높이가 N인 건물을 고정시키면 왼쪽, 오른쪽으로 경우의 수를 쪼갤 수 있어서 그 방법을 통해서 시도해보려 했지만 너무 어렵고 무식한 방법이었습니다. 결국 다른 분들이 풀이한 것들을 보고 힌트를 얻어서 풀었습니다. N-1개의..

문제서쪽의 N개의 사이트, 동쪽의 M개의 사이트가 주어질 때 다리를 놓을 수 있는 경우의 수를 구하시오.문제 출처: 백준 온라인저지(https://www.acmicpc.net/problem/1010) 풀이꽤 간단한 문제인데 (혼자) 함정아닌 함정에 빠져서 1시간정도 걸린 문제입니다. 동쪽에 M개의 사이트로 N개의 다리를 놓는 경우의 수이고 모든 다리는 똑같이 생겼을 것이기 때문에 조합의 수와 같다고 할 수 있습니다. 처음에 생각을 하지 않고 풀었는지 이 문제가 dp일까? 하면서 조합을 구하는 공식 n!/k!(n-k)! 을 바로 적용해버렸습니다. 테스트케이스는 올바르게 나왔지만 신중히 제출하기 위해 질문검색을 찾아보니 바로 오버플로우가 나는 것을 알 수 있었습니다. N, M이 30이하이지만 30!만 해도 ..

문제N개의 원소를 가지는 수열이 주어졌을 때 가장 긴 증가하는 부분 수열의 크기를 구하시오.문제 출처: 백준 온라인 저지(https://www.acmicpc.net/problem/11053) 풀이DP를 통해 풀 수 있는 문제입니다. DP문제는 생각이나 구현면에서 다른 알고리즘에 비해 시간이 적게 걸린다는 장점이 있어서 요즘 공부를 하다가 집중이 안될 때 풀고 있는 중입니다! 풀이를 안적어도 될 정도로 간단한 문제들이 많지만 오랜만에 적어보겠습니다. 이 문제에서는 수열이 주어지고 가장 긴 증가하는 부분 수열을 구해야하기 때문에 두조건을 만족하는 경우 큰수가 dp배열에 저장될 수 있도록 했습니다. nums[i], dp[i] 라는 배열을 만들었고 nums에는 입력받은 값이 들어가있습니다. dp[i]의 값은 n..