문제 정보 프로그래머스 문제 링크 난이도 : level 4 해결 방법 현재까지 확인한 idx 번째 집에서 털 수 있는 돈의 최댓값을 dict 에 key-value 형태로 저장했습니다. 집 사이의 간격은 최대 3칸이 될 수 있어서 헷갈렸는데 ( 아래 이미지에 고뇌의 흔적이 보입니다. ) 현재까지 확인한 이라는 조건이 붙기 때문에 방범장치가 영향을 줄 수 있는 2칸만 확인하면 됩니다. 점화식으로는 아래와 같이 나타낼 수 있습니다. newDp = max(memoization1[idx - 1], memoization1[idx - 2] + money[idx]) 그리고 첫 번째 ( idx 값으로는 0 ) 집을 털지 여부를 판단하기 위해 selZero 라는 변수로 판단했습니다. 첫 번째 집을 털게 되면 마지막 집을 ..

문제 정보 프로그래머스 문제 링크 난이도 : level 3 해결 방법 왼쪽 위 (1, 1) 부터 오른쪽과 아래로만 이동할 수 있는 최단거리 문제로 중학교(?) 교과 과정에서 많이 풀던 경로 문제입니다. 왼쪽 위부터 갈 수 있는 경우의 수를 표시하면서 왼쪽과 위의 경우의 수를 순차적으로 합산하여 구현할 수 있습니다. 그래서 Dynamic Programming 알고리즘을 사용해 구현했습니다. 처음 구현할 때는 두 가지 문제점이 있었는데 첫 번째는 중간에 웅덩이가 있을 경우 지나가지 못하는 경우를 중복으로 세서 물 웅덩이가 많을 경우 음수로 나와버리는 경우를 발견했는데 물 웅덩이에서의 경로의 수를 0 으로 세팅하여 해결했습니다. 두 번째는 위에서 기술했듯이 예전 교과 과정에서 많이 풀던 방식으로 인해 생긴 문..

문제 정보 프로그래머스 문제 링크 난이도 : level 3 해결 방법 1. 문제에 명시된 대로 거쳐간 숫자의 합이 가장 큰 경우를 찾기 위해 Top-down 방식의 DP 를 사용하여 구현했습니다. 제출하니 시간이 많이 초과되어 다른 방법의 풀이를 시도했습니다. 2. 모든 경로를 반복해서 수행하지 않도록 특정 경로까지의 최대 값을 triangle 배열에 update 했습니다. 짧은 경로는 금방 구할 수 있기 때문에 Bottom-up 방식으로 구현했습니다. 소스 코드 # 시간초과 def solution(triangle): answer = 0 answerList = [] def dp(depth, curSum, idx): curNum = triangle[depth - 1][idx] curSum += curNum..

문제 정보 프로그래머스 문제 링크 난이도 : level 3 해결 방법 노드 사이에서 관계를 가지고 있으므로 자료 구조는 그래프를 사용하고 탐색하는 방법은 BFS 혹은 DFS 를 사용하여 풀 수 있습니다. 해당 문제에서는 모든 공항을 방문해야 하므로 DFS 를 사용했습니다. 소스 코드 function solution(tickets) { let answer = []; const visitedList = []; const visited = new Array(tickets.length); const vAirport = []; visited.fill(false); const dfs = function(tickets, cur, depth){ // 종료조건 if(depth == tickets.length){ vAir..

문제 정보 프로그래머스 문제 링크 난이도 : level 3 해결 방법 노드 사이에서 관계를 가지고 있으므로 자료 구조는 그래프를 사용하고 탐색하는 방법은 BFS 혹은 DFS 를 사용하여 풀 수 있습니다. 해당 문제에서는 단어를 변환할 수 있는 최소 단계를 구해야 하므로 BFS 를 사용합니다. DFS 를 사용할 경우 최소 단계를 발견하더라도 다른 경로를 모두 탐색해야 최소 단계임을 보장할 수 있기 때문에 비효율적이기 때문 입니다. 소스 코드 function solution(begin, target, words) { let answer = 0; // target 이 words 에 없는 경우 if(!words.includes(target)){ return answer; } // 방문여부 초기화 const vi..