뚝딱햄 탈출기

접근 방식처음에는 diffs의 최댓값을 maxLevel로 설정하고, 이를 1씩 줄여나가며 숙련도의 최솟값을 구하려 했다.즉, 완전 탐색(Brute Force)을 이용해 문제를 해결하려 했다.diffs의 최댓값을 maxLevel로 설정하려고 한 이유는 이 값 이상으로 maxLevel을 설정하면 무조건 제한 시간(limit) 내에 모든 퍼즐을 해결할 수 있기 때문이다. (추가 시간 없이 해결되기 때문)따라서 diffs의 최댓값 이상의 값을 maxLevel로 설정해야 하는데, 반환값은 숙련도의 최솟값이므로 diffs의 최댓값을 maxLevel로 설정한다.그러나 위의 방법은 최악의 경우 300억번의 연산이 필요하다.diffs[i] = 100,000, diffs.length = 300,000, limit = 1인..

순열이란? 서로 다른 n개의 원소에서 r개를 중복없이 순서를 고려하여 선택하거나 나열하는 것. [1, 2, 3]에서 2개를 중복없이 순서를 고려하여 선택 및 나열한다면 [1, 2], [1, 3], [2, 1], [2, 3], [3, 1], [3, 2] 이다. (조합은 순서를 고려하지 않고 선택 및 나열하는 것. 위와 같은 예시에서 조합을 구한다면 [1, 2], [1, 3], [2, 3]) JavaScript로 순열 구현하기 1. 선택할 원소 개수 r이 정해져 있을 때 ref: https://www.youtube.com/watch?v=0tcgYHU8IIs function permutate(arr) { const results = []; // DFS const dfs = (i, arr) => { // ba..

[프로그래머스][level 3] 베스트앨범 접근 방식 입력값이 두 배열 genres와 plays로 나뉘어 들어오지만, 두 배열의 같은 인덱스를 가진 값들은 하나의 노래에 대한 값이다. 따라서 한 객체에 노래에 대한 정보들을 모아야겠다고 생각했다. 먼저 Object에 노래의 고유번호(= 인덱스), 장르, 재생 횟수를 담는다. 반환값인 베스트앨범의 첫 번째 기준은 '속한 노래의 재생 횟수가 많은 장르 먼저 수록' 이므로 장르별로 해당 장르 노래들의 재생 횟수를 모두 더하고, 총 재생 횟수를 기준으로 장르를 내림차순 정렬해야겠다고 생각했다. 베스트앨범의 두 번째 기준은 '장르 내에서 많이 재생 횟수가 많은 노래 수록' 이다. 장르별로 속한 노래들을 재생 횟수를 기준으로 내림차순 정렬해야겠다고 생각했다. 장르를..

다이나믹 프로그래밍?다이나믹 프로그래밍이란 하나의 문제를 단 한 번만 풀도록 하는 알고리즘이다. DP와 다르게 분할 정복은 동일한 문제를 다시 푼다.예를 들어 피보나치 수열을 분할 정복을 통해 푼다면 특정 숫자를 구하기 위해 그 n-1와 n-2 에 계속 접근한다.즉, 반복적인 데이터 계산이 발생한다.DP 사용할 수 있는 경우큰 문제를 작은 문제로 나눌 수 있다.작은 문제에서 구한 정답은 그것을 포함하는 큰 문제에서도 동일하다.위의 조건을 만족할 때 다이나믹 프로그래밍을 사용하면 효율적으로 문제를 해결할 수 있다.다이나믹 프로그래밍이란 큰 문제를 작게 나누고, 같은 문제라면 한 번만 풀어 문제를 효율적으로 해결하는 알고리즘 기법이다. 문제를 풀 때, 주어진 문제가 다이나믹 프로그래밍 유형임을 파악해야한다...