본문 바로가기

백준

백준 2096 내려가기 조금 쉬워보이는 것을 잡았다. 이해하기도 나쁘지 않고, 왠지 그림도 있어서 있어보인다. 문제는 쉽다. N*3 게임 판에서 한칸씩 내려가는데, 바로 밑이나 바로 밑과 붙어있는 칸만 갈 수 있다. 각 칸은 점수가 있고, 그 점수의 합이 최대가 되는것, 최소가 되는 것을 찾으면 된다. 처음 접근은 dp[N][N] 으로 정의해서 dp[i][j] = i 번째 줄에서 j번째 줄까지 최대값을 저장하려고 했다. 근데 이렇게 접근을 하면, 맨 마지막 줄에서부터 역순으로 탐색을 해야하고, 역순으로 탐색을 하는 도중에 어디 칸을 밟았는지도 저장을 따로 했어야 했다. 심지어 최소값 저장 DP, 최대값 저장 DP를 따로 저장해야 했다. 머리를 뜯다가 질문글을 슬쩍 슬쩍 봤는데, 좀 신기했다. 내가 접근했듯이 밑에서부터 한칸한칸.. 더보기
백준 11066 파일 합치기 오랜만이다. 역시 DP 문제이다. 처음 접근했을때는 어 이거 저번에 풀었던 행렬 곱셈 순서랑 너무 비슷한데? 해서 최대한 풀이를 보지 않고 접근해보았다. 일단 dp[i][j] 배열은, i번째 장에서부터 j번째 장 까지 합친 비용의 최소값이다. 추가로, sum[i] : 0 ~ i번째 원소까지 누적합을 저장하는 배열도 선언해준다. 그럼 이제 몇개의 예시를 돌려보자. dp[i][i] = sum[i] - sum[i - 1] dp[i][i+1] = sum[i + 1] - sum[i - 1] dp[i][i+2] = min(dp[i][i] + dp[i+1][i+2], dp[i][i+1] + dp[i+2][i+2]). 만약 1~10 장의 합치는 개수를 구하고 싶으면(dp[1][10]), dp[1][1] + dp[2][.. 더보기
백준 1520 내리막 길 오늘도 DP 문제이다. 2차원 지도를 입력으로 받아 0, 0 위치에서 N - 1, M - 1 위치까지 경로가 몇개 있는지 찾는 문제이다. DP 없이 그냥 문제 푼다고 생각하면 DFS를 써서 탐색을 돌려버릴 것 같다. 하지만 맵 크기가 작은 편이 아니라 그렇게 돌리면 Timeout이 발생할 가능성이 크다. 처음에 DP 접근을 dp[i][j] = 0, 0에서부터 i, j 까지 경로의 수 라고 생각을 해봤는데 생각을 아무리 해봐도 잘 답이 나오지 않았다. 그러고 한번 뒤집어 접근을해봤다. dp[i][j] = i, j 에서부터 N-1, M-1 까지 경로의 수로 생각을 하고 접근을 했다. 이 방향이 더 좋았던 것 같다. 그리고, dp 배열을 채우는 과정은 DFS로 흘러가게 된다. 현재 픽셀에서, 다음 픽셀을 찾고.. 더보기
백준 11049 행렬 곱셈 순서 어제에 이어 오늘도 DP 접근 문제이다. 이 문제도 학교 알분시간에 한번 다뤘었던 기억이 나는데 꼭 항상 학교에서 한것은 했다는 그 사실만 기억나고 내용은 기억이 나지 않는다... 하하하... DP 문제에서 관건은 문제가 쪼개지는지, 그 문제들의 합이 전체 해가 되는지인것같다. 만약 이 조건이 만족한다면 DP적 접근을 해보는게 좋을 것 같다. 해당 문제는 어떤 특정 부분의 최소값이 전체 최소값의 부분을 차지한다. 따라서 DP적 접근을 하는게 좋아보인다. DP 배열은 dp[i][j]일때, i번째 행렬부터 j번째 행렬까지 곱의 최소횟수를 의미한다. 처음 초기화는 전부 0으로 하고, 이웃한 배열끼리의 곱은 무조건 고정되어있으므로, 0~N-1 배열까지 이웃한 값을 채워줄 수 있다. 이후로는 저번 문제들과는 다르.. 더보기
백준 12865 평범한 배낭 역시 DP 접근 문제이다. 처음 접근은 2*물건의 수 DP 배열을 만들어 물건마다 넣고빼고를 적어두고 다음 물건을 볼 때 두 조건 중 max값을 사용하면 되지 않을까? 싶었는데 머리로 몇번 돌려보니 너무나도 쉽게 전체 탐색이 안되는구나... 하며 고민했다. DP 배열은 물건의 수*가방의 무게 크기로 생성한다. DP[i][j] 는, i 번째 물건까지 사용했을때, j무게 가방에 넣을 수 있는 물건 최대 가치이다. 처음 행은 당연히 첫번째 물건을 넣는 경우이고, 한번 값이 들어가기만 한다. 이후로는 모든 물건을 순회(현재 물건 무게 : curWeight, 현재 물건 가치 : curValue)하면서 DP를 채우게 된다. 매 물건마다 가방 크기를 1씩 늘리면서, 현재 가방 크기가 현재 물건을 넣을 수 있으면 저번.. 더보기
백준 9251 LCS 추석 연휴 끝나고 DP를 해보려고 잡은 문제이다. DP의 개념은 살짝 알고 있고, 관련 문제도 몇 번 푼 적이 있지만 제대로 좀 훑고 싶었다. Dynamic Programming은 문제를 푸는 과정에서 계속 부분부분 정답을 기록해가며 문제에 대한 해답을 풀어가는 방식이라고 생각한다. 근데 이게 나중에 보고 나면 아...~ 하는데 접근하기가 너무 어려운 것 같다. 이번 문제는 두 문자열이 있고, 그 문자열들의 부분 수열 중 가장 긴 공통 부분 수열의 길이를 찾는 문제이다. 처음 DP 쓰고 어 문자열~ 하고 접근했을 때, 1차원 배열을 선언해서, 먼저 받은 문자열을 쭉 스캔하면서 거기 기준으로 다른 문자열 어떤 위치까지 만들 수 있는가를 저장하는 방식으로 작성했다. 근데 아무리 생각해도 그렇게 접근하게 되면.. 더보기
백준 2473 세 용액 바로 이전에 푼 문제보다 조금 쉬운 문제이다. 저번 문제는 3명의 합이 0인 개수를 구하는 문제였고, 이번에는 합의 절대값이 최소인 것만 찾으면 된다. 정말 간단하다. 투 포인터 방향은 쉽게 잡았다. 문제도 유사해서 문제에서 제공하는 테스트케이스는 돌아가게 쉽게 만들었다. 문제는, 악마는 디테일에 있다는 것. 생각없이 int로 만든것을 보고 long long으로 바꿨다. 그래도 특정 %에서 틀렸습니다가 나왔다. 문제질문 보면 다양한 사례가 있더라. int - long long 범위 문제도 많았고, 중간에 특성값 계산할때 절대값 연산을 하는게 편한데 그때 abs() 함수에서 문제가 발생한 사례도 있었다. 컴파일러 구현체마다 std::abs가 아닌 그냥 abs를 int abs(int , int) 이렇게 받을.. 더보기
백준 3151 합이 0 오늘은 좀 쉬운거 잡고 오전에 다른거 해야지 했는데 예상보다 날 많이 괴롭혔다 이 문제가. 투 포인터를 사용하는 나쁘지 않은 편한 문제이다. 처음 보았을 때 정렬을 해두고 어떤 한 원소를 고정해두고 나머지 원소들을 투 포인터로 탐색하며 조합을 찾으면 좋겠다고 생각했다. 처음에는 선정한 한 개를 빼고 나머지들에서 투 포인터 탐색을 구현했다. 그렇게 되니 막 중복으로 찾고 난리가 나더라. 다시 생각해보니 어떤 원소 하나를 정하고 그 다음것부터 마지막까지만 계산하면 되는 문제였다. 그렇게 짜고 나니, 같은 값의 원소가 많이 있을 수 있다는 점이 걸렸다. L과 R이 가르키는 원소가 조합을 만족할 때, 우리는 두가지 상황에 빠진다. 하나는 두 원소가 값이 같을 경우. 이 때는 해당 값이 몇개 있는지 확인하고, k.. 더보기

티스토리툴바