케이스윔의 개발 블로그

문제수열 S가 어떤 수 Sk를 기준으로 S1 Sk+1 > ... SN-1 > SN을 만족한다면, 그 수열을 바이토닉 수열이라고 한다.예를 들어, {10, 20, 30, 25, 20}과 {10, 20, 30, 40}, {50, 40, 25, 10} 은 바이토닉 수열이지만, {1, 2, 3, 2, 1, 2, 3, 2, 1}과 {10, 20, 30, 40, 20, 30} 은 바이토닉 수열이 아니다.수열 A가 주어졌을 때, 그 수열의 부분 수열 중 바이토닉 수열이면서 가장 긴 수열의 길이를 구하는 프로그램을 작성하시오.문제 출처: 백준 온라인저지(https://www.acmicpc.net/problem/11054) 풀이가장 긴 증가하는 부분 수열, 가장 긴 감소하는 부분..

문제건물 순서 규칙이 주어지고, 해당 규칙에 맞춰서 건물을 지을 때 특정건물을 가장 빨리 지을 때까지 걸리는 최소시간을 알아내는 프로그램을 작성하시오.문제 출처: 백준 온라인저지(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방향에서 오는 모든 경우를 구할 수 있겠다는 생각이 들었습니다..

문제우리는 어떤 올바른 괄호열 X에 대하여 그 괄호열의 값(괄호값)을 아래와 같이 정의하고 값(X)로 표시한다. 1. ‘()’ 인 괄호열의 값은 2이다.2. ‘[]’ 인 괄호열의 값은 3이다.3. ‘(X)’ 의 괄호값은 2×값(X) 으로 계산된다.4. ‘[X]’ 의 괄호값은 3×값(X) 으로 계산된다.5. 올바른 괄호열 X와 Y가 결합된 XY의 괄호값은 값(XY)= 값(X)+값(Y) 로 계산된다.예를 들어 ‘(()[[]])([])’ 의 괄호값을 구해보자. ‘()[[]]’ 의 괄호값이 2 + 3×3=11 이므로 ‘(()[[ ]])’의 괄호값은 2×11=22 이다. 그리고 ‘([])’의 값은 2×3=6 이므로 전체 괄호열의 값은 22 + 6 = 28 이다.여러분이 풀어야 할 문제는 주어진 괄호열을 읽고 그 ..

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

문제N과 수열이 주어질 때 부분 수열 중에서 가장 합이 큰 것을 구하시오.문제 출처: 백준 온라인저지(https://www.acmicpc.net/problem/11055) 풀이전에 풀었던 가장 긴 증가 부분 수열(https://kswims.tistory.com/152) 문제와 거의 비슷합니다. 이전 문제는 길이를 구해야했다면 이번엔 합으로 dp배열을 추가해나갑니다. i번째 값이 들어왔을 때 i-1번째부터 쭉 내려가며 i번째 값보다 작은 숫자이면서 dp의 값을 가장 큰 값을 택해서 dp[i] = 해당값+num[i]를 해주면 됩니다. 코드https://github.com/kswim/Algorithm/blob/master/DP/11055.cpp

문제 3×N 크기의 벽을 2×1, 1×2 크기의 타일로 채우는 경우의 수를 구하시오.문제 출처: 백준 온라인저지(https://www.acmicpc.net/problem/2133) 풀이저번에 이 문제를 풀려했던적이 있는데 점화식을 세우지 못해서 포기했던 문제였습니다. N이 홀수인 경우에는 0이 된다는 점과 타일의 위치에 따라 규칙을 알 수 없는 특수한 케이스로 점화식을 세우지 못했었습니다. 그러다 bitmasking을 공부하며 관련 문제들을 풀다가 이 문제도 해당분류에 속함을 알 수 있었습니다. dp[i][000~111] 과 같이 표현을 할 수 있고 이는 i-1번째까지 다 채워졌다고 했을 때 i-1번째의 행에 채워진 타일을 bit로 나타냅니다. 다 채워지지 않은 경우를 000, 다 채워진 경우를 111,..

문제 상근이는 20병의 맥주를 가지고 있고 50미터에 한 병씩 마시며 목적지에 도착해야한다. 출발지와 목적지 사이에 맥주를 파는 편의점이 주어질 때 상근이가 페스티벌에 도착할 수 있는지 구하는 프로그램을 작성하시오.문제 출처: 백준 온라인저지(https://www.acmicpc.net/problem/9205) 풀이처음에 문제를 봤을 때는 주어지는 좌표도 너무 넓어서 50으로 나눠서 관리를 해줄지.. 등의 생각이 많이 드는 문제였는데 하나의 힌트로 쉽게 해결할 수 있는 문제였습니다. 편의점을 통해서 그래프를 그리는 것입니다. 처음에 20병으로 시작하게되고 어느 편의점을 들리던지 먹은만큼 맥주를 살 수 있기 때문에 편의점에 들리게 되면 20병으로 다시 채워집니다. 남은 병수와 관계없이 20병안으로 편의점을 ..