본문 바로가기

프로그래머스

프로그래머스 도둑질 프로그래머스 코딩테스트 연습의 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개와.. 더보기

티스토리툴바