본문 바로가기

알고리즘

백준 15686 치킨 배달 구현 문제를 풀어보자고 해서 잡은 문제이다. 2D 지도를 입력받고, 치킨 집 중 M개를 선택해 각 집에서 가장 가까운 치킨집 거리들의 합 최소값을 구하면 되는 문제이다. 구현 문제기도 하고, 맵 크기도 50 * 50 = 2500개 셀이라 크지 않아서 전체 탐색으로 구현했다. 처음 맵 입력을 받을 때, 집 위치와 치킨집 위치를 각 벡터에 저장한다. 탐색하는 공간은 전체 치킨집 중에서 어떤 특정한 치킨집들을 선택하는 경우를 비트마스킹으로 탐색했다. 전체 탐색 공간의 수는 2^치킨집의 수 이다. 하지만 이 경우 중에서 선택한 치킨집의 수가(1의 수가) M개인 경우만 사용한다. 각 경우에서는 집을 순회하면서 그 집에서 가장 가까운 치킨집의 거리를 더해나간다. 가장 가까운 치킨집 거리 역시 각 치킨집을 모두 돌면.. 더보기
백준 7579 앱 알고리즘 스터디에서 친구가 가져왔던 문제이다. 0-1 Knapsack문제 유형을 보고 잡은 문제라는데, 좀 어려웠다. 그냥 0-1 knapsack 문제로 생각하면, 배낭크기를 메모리로 따져서 col에 M개 열을 만들어 해볼까 했는데 메모리의 최대값이 10000000이라 배열으로 선언을 할 수 없을 것 같다. 그럼 어떻게 할까...? 친구가 풀다가 솔루션을 확인했는데, 그 방식이 너무 신기했다. col을 다른 값을 사용해서 채우는 방법이 있더라. 이 문제 같은 경우에는, col에 cost를 넣어둬 문제를 해결했다. 따라서 dp[i][j] = i번째 앱까지 봤을때, j비용으로 얻을 수 있는 메모리의 크기가 된다. dp 배열의 내용을 한번 보자, [0] [1] [2] [3] [4] [5] [6] [7] [8].. 더보기
백준 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차원 배열을 선언해서, 먼저 받은 문자열을 쭉 스캔하면서 거기 기준으로 다른 문자열 어떤 위치까지 만들 수 있는가를 저장하는 방식으로 작성했다. 근데 아무리 생각해도 그렇게 접근하게 되면.. 더보기

티스토리툴바