본문 바로가기

dp

백준 1562 계단 수 비트마스킹 문제이다. 근데 또 보니까 DP 문제이다... 으... DP... 이걸 어떻게 구현을 해야하나... 하다가 DFS로 탐색을 돌까 했는데, 탐색 수가 너무 많이 나와 솔루션 나오기 전에 내 복장부터 터질것 같아 그만 뒀다. 머리 쥐어 뜯다가 좀 검색을 해봤다. DP를 사용한 해결 방법이 대부분이었다. 그 중에는 DFS에 DP를 붙인 것도 있고, 단순히 for를 사용하면서 탐색을한 방법도 있었다. 그 중 for 문을 사용한 BFS탐색이 더 마음에 들어 코드를 보면서 다시 짜봤다.. 일단 DP 배열을 선언한다. dp[i][j][b] = 현재 자리수가 i이고, 마지막으로 사용한 숫자가 j이면서 사용한 숫자의 상태가 b 비트마스크일때, 가능한 계단 수 이다. 이제 이걸 i와 j, b를 늘리면서 배열을 .. 더보기
백준 1126 같은 탑 DP 문제를 슥 보다가 오우 문제 짧네? 하고 한번 잡아봤다. 근데 플은 괜히 플이 아니더라... 하하... 처음 접근했을때, dp[i]를 i 높이로 탑을 쌓을 수 있는 조건으로 접근했다. dp[i]는 벡터였고, dp[2]는 2 높이를 만들 수 있는 블럭들 상태들을 저장하고 있었다. 루프 돌면서 이전 조합에 지금 블럭을 or 해서 추가하고, dp[i]가 2 이상인 경우 중 최대값을 출력했다. 답은 나왔는데 예상보다 루프가 많아 시간 초과가 떴다. 시간 갈아넣었는데 시간초과가 나와 좀 더 생각해보다가 검색을 좀 해봤다. dp 배열을 진짜 신박하게 잡더라. dp[i][j] = i 번째 블럭까지 썼을때, 두 블럭 높이 차이가 j일 경우 두 탑 중 높은 것의 높이. 로 정의해둔다. 이렇게 되면, i와 j를 늘려.. 더보기
백준 2618 경찰차 좀 어려워 보이는 문제를 잡아봤다. 두 경찰차가 있고, 하나는 1,1에서 나머지 하나는 N,N에서 출발한다. 경찰차가 격자무늬 도시를 돌아다니며 사건들을 해결하는데, 그 과정에서 이동하는 최소값과 경로를 출력하는 문제이다. 처음에 그냥 답이라도 나왔으면 좋겠다 하고 각 사건마다 가장 가까운 경찰차를 이동하면서 문제를 풀었는데, 틀렸다. 당연히 그런게, 만약 두 경찰차가 모두 같은 거리에 떨어져 있으면 이 경우는 어떻게 할지 정의되지 않아 최적해 탐색은 물 건너간다... 머리 쥐어뜯다가 질문 게시판을 탐색해보고 DP 배열 감을 잡았다. dp[i][j] = 경찰차 1이 가장 마지막으로 i번째 사건을 했고, 경찰차 2가 가장 마지막으로 j번째 사건을 했을 때 이동 최소 거리로 정의를 하자. 이렇게 dp를 구성.. 더보기
백준 2098 외판원 순회 백준 문제를 다시 잡아봤다. DP문제에서 진짜 엄청 유명한 문제인 TSP를 풀어보고 싶어서 찾았다. 근데 진짜 TSP 키워드로 구글에서 검색하면 별의 별 곳 응용이 다 나오더라. 가장 많이 보이는게 경로 문제, 최근 드론 배달이 많이 연구 되고 있는데 그쪽 관련된 이미지가 많이 나오는 것 같다. 문제는 심플하다. 유향 가중치 그래프를 인접 행렬로 입력 받아서, 모든 노드를 방문하고 제 자리로 돌아오는 경로를 찾는 것 - 이 문제에서는 비용만 구하면 된다. 처음 접근은 DFS를 사용해서 DP에 저장해가면서 풀어보는 방식이었다. 직전 문제인 도둑질에서도 같은 접근 방법을 사용했었다. 근데 코드 구현 중, 탐색 중간에 되돌아가거나 다음 경로가 없을 때 너무 복잡해져서 엎었다... 그래서 이걸 어떻게 하나..... 더보기
프로그래머스 도둑질 프로그래머스 코딩테스트 연습의 DP 분류 마지막 문제이다. 뭔가 어디서 봤던 문제같긴 한데, 다시 생각해봤다. 근데 되게 머리가 아팠다. DP배열을 쓰고 어디서부터 어디까지 최적해를 찾아본다 했지만, 앞에서부터 찾아봐도 뒤에서부터 찾아봐도 답이 없었다. 집이 원형이 아니고 직선 형태로 배치되어 있다면 해당 접근이 괜찮아 보이는데, 맨 앞 칸과 맨 뒤 칸이 조건에 맞물려 있어 답이 없어보였다. 이렇게 해볼까 저렇게 해볼까 고민을 하다가, 질문들을 찾아봤다. 그 중에, DFS와 섞은 솔루션이 있어서 찬찬히 뜯어보면서 답을 작성해봤다. 일단 dp[i][b] 는 , 첫번째 집을 털었거나(b==true), 털지 않았을 때(b==false) i번째 집까지 털었을 경우 최대값을 의미한다. 첫번째 집을 털었을 경우, .. 더보기
프로그래머스 등굣길 프로그래머스의 DP 쪽 문제 세번째이다. 2D 지도가 주어지고, 1,1에서부터 최우하단 좌표까지 가능한 경로의 개수를 구하는 문제이다. 여기서, 특정 위치가 웅덩이가 될 수 있다. 해당 웅덩이는 경로에 포함될 수 없다(지나갈 수 없다). 움직이는 패턴이 상하좌우가 아니라, 오른쪽과 아래쪽으로만 움직인다는 제약조건이 있다. 이 제약조건이 있어서 DP를 사용해 문제를 풀 수 있다고 한다. 부분의 최적해가 전체 최적해에 포함이 되기 때문에 DP를 사용할 수 있다... 정말 코드에서 엄청난 삽질을 했다. 처음에는 dfs와 섞은 솔루션을 작성했다. 이 문제와 비슷하게 접근해서 작성했는데, 계속 문제가 발생했다... 정확도 체크는 어느정도 맞는데, 효율체크가 우수수수... 틀려 다른 방법을 찾아봤다. 그냥 위에서부.. 더보기
프로그래머스 정수 삼각형 저번 문제와 같이, DP 분류의 프로그래머스 문제이다. 머리속에서 좀 많이 생각을 해봤는데, 저번에 풀었던 문제와 아주 유사하게 접근할 수 있을 것 같다. 저번에 풀었던 문제는 dp 배열의 폭이 정해져있다면, 이번 dp 배열은 높이가 1 늘어날때마다 폭도 1 늘어난다. 그리고, 문제 지도는 피라미드 모양으로 되어있는데 이것을 왼쪽으로 챡 붙인 직각삼각형으로 생각하는게 머리속에서 문제를 푸는데 훨씬 도움이 된다. 저번 내려가기 문제에서는 폭이 정해져있고, 밑으로 내려가면서 그 자리에서 가질 수 있는 최대값/최소값을 저장하고 있었다. 이번 문제에서는 최소값이 없는 반면, 옆으로 한칸씩 증가한다. 따라서 DP 배열은 N*N 크기를 가진다. (마지막 row의 경우 N크기 이므로.) 그 외에, 각 셀을 채워주는것.. 더보기
프로그래머스 N으로 표현 프로그래머스에서 DP 문제를 찾아보고 나온 문제이다. 가장 쉬운 문젠데 역시 DP는 어렵다.... DP 배열은 dp[i] : i개의 숫자를 가지고 만들 수 있는 숫자 를 저장한다. 처음 DP를 초기화할때, 그 갯수만큼의 숫자를 저장해둔다. (예를 들어, dp[1] = 5, dp[2] = 55 ...) 그리고, 최대 8개까지 사용하는지 확인하는 것이므로, 8까지(사용 가능한 숫자 개수) 루프를 돌면서 dp 탐색을 한다. 만약 N = 5이고, 탐색하는 루프 수(숫자 개수)가 5이면, 5(op)5555 55(op)555 555(op)55 5555(op)5 이렇게 나눌 수 있다. 5를 1개 사용한 숫자들과 4개 사용한 숫자들의 연산 결과가 dp[5]에 추가되고, 2개와 3개의 연산, 3개와 2개의 연산, 4개와.. 더보기

티스토리툴바