케이스윔의 개발 블로그

문제각 칸의 높이가 적인 지도가 주어질 때 제일 왼쪽 위 지점에서 출발하여 제일 오른쪽 아래 지점까지 항상 내리막길로만 이동하는 경로의 개수를 구하는 프로그램을 작성하시오.문제 출처: 백준 온라인저지(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'라고 하겠습니다. 문자열을 첫번째문자부터 잘라서 보면 ..

문제릴레이션을 나타내는 문자열 배열 relation이 매개변수로 주어질 때, 이 릴레이션에서 후보 키의 개수를 return 하도록 solution 함수를 완성하시오.문제 출처: 프로그래머스(https://programmers.co.kr/learn/courses/30/lessons/42890) 풀이이 문제도 지난 하반기 때 못풀었었는데 그 당시 생각했었던 방법으로 새로 풀었습니다. 후보키는 유일성과 최소성을 만족해야하기 때문에 가능한 모든 조합을 구한 다음 각 조합이 유일성과 최소성을 만족하는지 그대로 구현해서 확인하면됩니다. 당시에는 그 모든 조합을 확인할 수 있을지에 대한 의문이 있어서 다른 문제를 먼저 풀었던 것 같은데 다시 풀면서 조건을 보니 최대 column의 수와 row 수가 작기 때문에 모든 ..

문제트리를 구성하는 노드의 x, y 좌표들이 주어질 때 규칙에 맞게 이진트리를 그리고 전위 순회와 후위 순회 결과를 출력하시오.문제 출처: 프로그래머스(https://programmers.co.kr/learn/courses/30/lessons/42892) 풀이이 문제는 지난번 하반기 채용 당시 풀어야했던 문젠데 못 풀었던! 문제였습니다. 오늘은 오랜만에 프로그래머스에 들어갔다가 이 문제를 골랐는데 풀 수 있는 방법이 떠올라서 풀었습니다! 처음에 이 문제를 봤을 때는 좌표가 x, y로 주어지는데 이진트리로 표현하기 위한 방법이 떠오르지않아서 못풀었는데 오늘은 우선순위큐를 이용하면 풀 수 있겠다는 생각이 들었습니다. y좌표가 높을수록, x좌표가 작을수록 우선순위큐를 만들어주면 가장 위에서 부터 차례대로 각 ..

문제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병안으로 편의점을 ..