dp
-
프로그래머스 Lv.3) 등굣길 (DP)알고리즘/프로그래머스 고득점 Kit 2020. 6. 4. 14:45
등굣길 코딩테스트 연습 - 등굣길 계속되는 폭우로 일부 지역이 물에 잠겼습니다. 물에 잠기지 않은 지역을 통해 학교를 가려고 합니다. 집에서 학교까지 가는 길은 m x n 크기의 격자모양으로 나타낼 수 있습니다. 아래 그림은 m = programmers.co.kr 풀이 전에 풀었던 방법과 오늘 푼 방법이 같다. 다만, 차이점이 있다면 처음에는 map을 생성하고, 모든 길을 1로 적어뒀다. 그런 뒤에, 입력받은 웅덩이 위치를 0으로 표시하고, 웅덩이에 막힌 길을 0으로 표시했다. 맵이 완성되면 맵을 돌면서 갈 수 있는 방법을 더해가며 답을 구했다. 오늘 푼 풀이도 위와 같다고 보면 된다. 처음부터 dp 배열을 생성하고, 웅덩이만 -1로 표현해줬다. 그리고 dp를 돌면서 위와 왼쪽 길이 웅덩이인지 아닌지만 ..
-
프로그래머스 Lv.3) N으로 표현 (DP)알고리즘/프로그래머스 고득점 Kit 2020. 6. 3. 18:30
N으로 표현 코딩테스트 연습 - N으로 표현 programmers.co.kr 풀이 고득점 Kit의 DP에 있는 문제다. 예전에 풀었을 때, DP로 풀지 않고 DFS로 풀었기 때문에 DP로 풀고자 했지만, 실패했다. 그래서 검색을 해봤더니 4중 for문을 돌리면서 답을 찾는 글들만 보였다. 좌표를 탐색하는 시뮬레이션 문제가 아닌 이상은, 4중 for문이 가독성이 더 떨어지고 이해하기 힘들다는 주관적인 의견이다. 물론, 머리가 좋으신 분들은 이해하시는데 문제가 없겠지만, 나같은 사람들이 범접할 수 있는 영역이 아닌 것 같았다. DFS의 방법은 만들 수 있는 모든 수를 가지고 4칙 연산을 진행하는 것이다. 문제의 조건에 따라 문자 N 사용 횟수가 8이 넘어가면 -1을 반환하기 때문에, DFS가 가능했다. 또한..
-
프로그래머스 Lv.3) 거스름돈알고리즘/프로그래머스 2020. 5. 29. 18:27
거스름돈 코딩테스트 연습 - 거스름돈 Finn은 편의점에서 야간 아르바이트를 하고 있습니다. 야간에 손님이 너무 없어 심심한 Finn은 손님들께 거스름돈을 n 원을 줄 때 방법의 경우의 수를 구하기로 하였습니다. 예를 들어서 손님께 5�� programmers.co.kr 풀이 정말정말정말정말 어려운 문제라고 생각한다 주관적으로. n이 100,000 화폐가 100이나 되는 문제기 때문에 dfs로는 풀 수 없다. 가능한 방법이 있다면 알고싶다.. 내가 알고있는 선에서는 풀 수 없었다. 그래서 DP로 풀어야한다는 생각이 들었는데 점화식이 감이 잡히지 않았다. 정말 오랫동안 생각하고 수식을 짜보려 해도 보이지 않았다. 그래서 다른 분의 해설을 보기로 했다. 거스름돈이 0원인 경우 경우의 수가 1이라는데, 문제 ..
-
프로그래머스 Lv.3) 멀리 뛰기알고리즘/프로그래머스 2020. 5. 29. 18:11
멀리 뛰기 코딩테스트 연습 - 멀리 뛰기 효진이는 멀리 뛰기를 연습하고 있습니다. 효진이는 한번에 1칸, 또는 2칸을 뛸 수 있습니다. 칸이 총 4개 있을 때, 효진이는 (1칸, 1칸, 1칸, 1칸) (1칸, 2칸, 1칸) (1칸, 1칸, 2칸) (2칸, 1칸, 1칸) (2칸, 2�� programmers.co.kr 풀이 dp 문제이고, 피보나치 문제임을 바로 눈치챘다. 바로 1차원 배열을 만들어서 제출했는데, 1번 문제가 틀렸다고 나왔다. 피보나치 문제가 아닌가? 생각에 다시 문제를 꼼꼼히 봤으나 피보나치가 맞았다. 문제점을 모르겠어서 질문하기 탭을 확인했는데, n만큼 배열을 만들면 메모리 초과가 뜬다는 것이었다... 충격.. 최대 n이 고작 2000인데 메모리 초과가 난다.. 아무튼 그래서 변수 두개..
-
프로그래머스 Lv.3) 보행자 천국알고리즘/프로그래머스 카카오 2020. 5. 27. 22:57
2017 카카오코드 예선 보행자 천국 코딩테스트 연습 - 보행자 천국 3 3 [[0, 0, 0], [0, 0, 0], [0, 0, 0]] 6 3 6 [[0, 2, 0, 0, 0, 2], [0, 0, 2, 0, 1, 0], [1, 0, 0, 2, 2, 0]] 2 programmers.co.kr 풀이 DP 문제임을 눈치 챘고, DP로 풀기위해 노력했다. 하지만, 눈치챈 것 이상도 이하도 아니었다. DP임을 알고도 어떻게 해야할지 감이 안잡혔기 때문이다.. 처음에는 2차원 배열 DP를 만들어 x축과 y축이 각각 0인 좌표들에 통행 금지 표지판을 만나기 전까지 1을 저장해주었다. (y=0일 때, x를 증가하면서 저장, x=0일 때, y를 증가시키면서 저장) 하지만, 나중에 회전 불가 표지판을 만날 때 어떤 경로..
-
프로그래머스 Lv.2) 피보나치 수알고리즘/프로그래머스 2020. 5. 21. 16:36
피보나치 수 코딩테스트 연습 - 피보나치 수 피보나치 수는 F(0) = 0, F(1) = 1일 때, 1 이상의 n에 대하여 F(n) = F(n-1) + F(n-2) 가 적용되는 수 입니다. 예를들어 F(2) = F(0) + F(1) = 0 + 1 = 1 F(3) = F(1) + F(2) = 1 + 1 = 2 F(4) = F(2) + F(3) = 1 + 2 = 3 F(5) = F(3) + F(4) = programmers.co.kr 풀이 피보나치를 배열을 통해 푸는 방법과, 1234567로 나눈 나머지 값을 저장 및 return한다는 것 이외는 특별하게 신경써야하는 부분이 없다. 혹시 피보나치를 구현하는데 어려움을 겪는 분이 있다면, 피보나치를 배열로 풀기 전에 재귀를 통해 푸는 방법을 먼저 익히는 것을 ..
-
프로그래머스 Lv.2) 가장 큰 정사각형 찾기알고리즘/프로그래머스 2020. 5. 19. 23:01
가장 큰 정사각형 찾기 코딩테스트 연습 - 가장 큰 정사각형 찾기 [[0,1,1,1],[1,1,1,1],[1,1,1,1],[0,0,1,0]] 9 programmers.co.kr 풀이 DP를 이용해 이 문제를 풀었다. Top-down을 이용해서 풀었고, board를 돌면서 어떠한 점이 1이라면 그 점을 기준으로 왼쪽, 왼쪽 상단, 상단 세 점의 최소값을 찾아 1을 더해줬다. 이후에 max값을 갱신했고, 탐색이 끝난 후에는 max값의 제곱을 리턴해주었다. 1. board의 모든 점을 탐색한다. 2. board가 1이라면 해당 점을 기준으로 좌측, 좌측 상단, 상단 세 점의 최소값을 찾는다. 2.1 최소값에 +1을 해주어 해당 점에서 만들 수 있는 정사각형의 최대 크기를 저장해주었다. 3. 2번이 끝난 후 m..
-
프로그래머스 Lv.2) 땅따먹기알고리즘/프로그래머스 2020. 5. 19. 22:40
땅따먹기 코딩테스트 연습 - 땅따먹기 땅따먹기 게임을 하려고 합니다. 땅따먹기 게임의 땅(land)은 총 N행 4열로 이루어져 있고, 모든 칸에는 점수가 쓰여 있습니다. 1행부터 땅을 밟으며 한 행씩 내려올 때, 각 행의 4칸 중 한 칸만 밟�� programmers.co.kr 풀이 나를 좌절하게 만든 문제였다... 분명 DP를 활용하는 문제임을 눈치챘고 유사한 문제도 풀어냈었는데, 검색과 자동완성 기능 없이 풀어야한다는 생각이 들어서 그랬을까 못풀었다. 그래서 프로그래머스에서 제공하는 문제의 해답 영상을 봤다. 마지막 행의 4개의 x에 대해 bottom-up 방식으로 dp를 진행하는 것이었다.. 분명 이렇게 풀었던 dp문제가 있었던게 기억났다. 생각보다 간단했다.. 로직 1. 행의 길이와 x의 개수(4..