Persistence

피보나치 수열 문제: 피보나치 수열에서 n번째 오는 값을 구하시오. e.g. n이 6일 때, 1, 1, 2, 3, 5, 8 ... 이므로 답은 8 재귀로 아래처럼 간단하게 풀 수 있으나, 이 방법은 O(2^n) 시간 복잡도를 가진다. def fib(n): if n == 1 or n == 2: return 1 return fib(n-2) + fib(n-1) 시간 복잡도를 생각하는 방법은, 아래와 같은 예시를 생각해보면 된다. 위의 피보나치 수열을 구하는 재귀와 밑의 코드의 시간복잡도는 비슷하리라 짐작할 수 있다. 하나의 n에서 두 개의 가지를 뻗어서 자기 자신을 재호출하고 있는 구조이기 때문이다. -1씩 깎이는 거나 -2씩 깎이는거는 나중에 가면 상수값이 되어서 빅오표기법에서는 의미가 없다. (이 영상 의..

스킬트리 문제 출처 - 프로그래머스 내가 푼 답 function solution(skill, skill_trees) { let arr = skill.split(''); let str, count = 0; for(let i = 0; i arr.includes(i)).join(''); if(str === skill.substring(0,str.length)) { count++; } } return count; } 처음에는 new RegExp를 쓰려고 용을 썼는데, 구현을 못해서 결국 그냥 filter로 했다. 다른 분들의 풀이를 보니 정..

쇠막대기 문제(스택) 문제 출처 - 프로그래머스 내가 푼 답 function solution(arrangement) { let count = []; let result = 0; for(let i = 0 ; i 0) { count = count.map(e => e + 1); } else if(arrangement[i+1] !== ')') { count.push(0); } } if(arrangement[i+1] === ')' && arrangement[i] !== &..

동적 프로그래밍 동적 프로그래밍은 제한 조건이 있을 때에 무언가를 최적화하는 경우 유용하다. 예를 들어 들어갈 수 있는 크기가 제한된 배낭에서, 값어치가 최대가 되도록 물건을 채우는 ''배낭 채우기'' 문제 같은 것이 그것이다. 동적 프로그래밍은 하위 문제가 서로 의존하지 않는 경우에만 사용할 수 있다. 예를 들어 배낭에 넣을 물건 - 책, 거울, 노트북 등 - 의 가치는 다른 물건들과 관계가 없다. 모든 동적 프로그래밍 답안에는 격자가 있다. 격자의 각 칸에는 최적화하고자 하는 값을 적는다. 배낭 채우기 문제의 경우 물건의 가치를 적는다. cell[i][j]의 최대값은 // i는 행, j는 열 1. 지금까지 구한 cell[i-1][j]의 값 중에서 가장 최대값이거나 2. 현..

문제 price는 가격이고, cash는 손님이 지불한 돈, cid는 현재 남아있는 잔고이다. cid의 예시는 다음과 같다. // Example cash-in-drawer array: // [["PENNY", 1.01], // ["NICKEL", 2.05], // ["DIME", 3.1], // ["QUARTER", 4.25], // ["ONE", 90], // ["FIVE", 55], // ["TEN", 20], // ["TWENTY", 60], // ["ONE HUNDRED", 100]] 돈의 단위는 다음과 같다. Currency UnitAmount Penny$0.01 (PENNY)Nickel$0.05 (NICKEL)Dime$0.1 (DIME)Quarter$0.25 (QUARTER)Dollar$1 (D..

문제 Nested array를 flatten하라 내가 푼 답 function steamrollArray(arr) { var flat = (arr) => arr.flat(); while(true) { if(arr.filter(i => Array.isArray(i)).length === 0) { break; } arr = flat(arr); } return arr; } Intermediate Solution function steamrollArray(arr) { let flat = [].concat(...arr); return flat.some(Array.isArray) ? steamrollArray(flat) : flat; } 나는 flat 메소드를 쓴 반면, 솔루션에서는 spread operator를 사..

SumPrimes 문제: 주어지는 숫자보다 작거나 같은 소수들을 모두 더한 값을 리턴하라 내가 푼 답 function sumPrimes(num) { var result = 0; function isPrime(n) { for(var i = 2; i { let m = n-1; while(m > 1 && m >= Math.sqrt(n)) { if(n % m === 0) { return false; m--; } return true; } }) return onlyPrimes.reduce..

집합 커버링 문제(set-covering problem) 근사 알고리즘 미국 50개 주에 방송을 하고 싶다. 이를 위해서는 방송국을 찾아가야 하는데, 이 방송국들은 각각 커버하는 주가 다르다. 방송국에 찾아가는 데는 비용이 드므로 방송국을 가장 적게 찾아가면서도 50개 주를 다 포함하게끔 하고 싶다. 이를 해결하기 위해 탐욕 알고리즘을 사용한다. (거의 정답에 가까운 답을 유추) 아직 방송하지 않은 지역 중 가장 많은 지역에 방송할 수 있는 방송국을 고른다. 이미 방송되고 있는 지역이 일부 포함되어 있어도 관계 없다. 모든 주에 방송이 될 때까지 반복한다. states_needed = set(["mt", "wa", "or", "id", "nv", "ut", "ca", "az"]) # 방송하고자 하는 주의..

Spinal Tap Case 문제 문자열을 spinal case로 변환하라. Spinal case란 소문자로 이루어지고 dash(-)로 연결된 문자열을 말한다. 예시 spinalCase("This Is Spinal Tap") should return "this-is-spinal-tap". Passed spinalCase("thisIsSpinalTap") should return "this-is-spinal-tap". Passed spinalCase("The_Andy_Griffith_Show") should return "the-andy-griffith-show". Passed spinalCase("Teletubbies say Eh-oh") should return "teletubbies-say-eh-oh..

다익스트라 알고리즘(Dijkstra's algorithm) 최단 시간 경로 너비 우선 탐색이 최단 경로(가장 짧은 단계)였던 반면, 다익스트라 알고리즘은 가장 빠른 경로 즉, 최단 시간 경로를 탐색한다. 다음과 같은 단계를 거친다. 가장 가격이 "싼" 정점을 찾는다. 가장 가격이 싼 정점이란 도달하는 데에 걸리는 시간이 가장 짧은 정점을 말한다. 이 정점의 이웃 정점들의 가격을 조사한다. 그래프 상의 모든 정점에 대해 이 일을 반복한다. 최종 경로를 계산한다. 예시 위 그래프에서 A까지 가는 시간은 6, B까지 가는 시간은 2이므로 B가 가장 싼 정점이다. 이 때 도착점까지 얼마 걸리는 지는 알 수 없으므로 무한대라고 한다. 정점 B의 이웃 정점의 가격을 조사한다. B에서 A를 가는 시간은 3이므로 출발..

너비 우선 탐색(Breadth-First Search) 그래프 연결의 집합을 모형화한 것 그래프는 정점(node)와 간선(edge)로 이루어진다. 이어진 정점을 이웃(neighbor)이라고 한다. 그래프에는 방향 그래프와 무방향 그래프가 있다. 무방향은 화살표가 없고 서로 상호 관계가 있다는 뜻이다. 너비 우선 탐색 그래프를 대상으로 하는 탐색 알고리즘이다. 다음과 같은 질문을 던지면 도움이 된다. 정점 A에서 B로 가는 경로가 존재하는가?(ex. 내 네트워크 중 바나나칩 판매상이 있는가?) 정점 A에서 B로 가는 최단 경로는 무엇인가?(ex. 누가 가장 가까운 바나나칩 판매상인가?) 네트워크를 통해 바나나칩 판매상을 찾으려고 한다고 가정했을 때, 내 친구부터 탐색하고, 친구 중에 없으면 친구의 친구를 ..

해시 함수 해시 함수에 관한 일반적인 사실 문자열을 받아서 숫자를 반환하는 함수. 문자열에 숫자를 할당(mapping)한다. 해시함수에는 일관성이 있어야 한다. "apple"을 넣을 때마다 항상 반환되는 숫자는 같아야 한다. 다른 단어가 들어가면 다른 숫자가 나와야 한다. 예컨대 어떤 값이 들어가든 "1"이 나오는 함수는 좋지 않다. 해시함수는 같은 이름에 대해 항상 같은 인덱스를 할당한다. 값이 저장된 위치(인덱스)를 정확하게 알려주므로 탐색을 할 필요가 없다.(ex. 이진탐색, 단순탐색) 그렇기 때문에 빅오표기법으로 O(1)의 시간이 걸린다. O(1)은 상수 시간(constant time)이라고 불린다. 이는 테이블의 크기에 관계없이 항상 똑같은 시간이 걸린다는 의미이다. (항목이 10억개라고 해서,..

선택정렬(Selection Sort) 가장 많이 들은 노래 순으로 정렬하기 노래 리스트 전체 중에서 가장 감상 수가 높은 노래를 하나 뽑아서 새로운 리스트 첫 줄에 작성한다. 이 때 원래의 리스트에서는 그 곡을 삭제한다. 나머지 리스트 전체 중에서 가장 감상 수가 높은 노래를 뽑아서 새로운 리스트 두번 째줄에 작성한다. 이 역시 원래 리스트에서는 삭제한다. 이를 계속 반복하면 원래의 리스트가 비워졌을 때에 새로운 리스트에는 감상 수가 높은 순으로 노래가 정렬된다. 이렇게 n개의 노래를 정렬하려면 빅오 표기법으로 O(n^2)만큼의 시간이 걸린다. 첫 번째 실행에서는 n개의 항목을 단순 탐색하므로 O(n)의 시간이 걸린다. 첫 번째 시행 후 원래의 리스트에서 항목이 한 개 지워지므로 다음 탐색은 O(n-1)..

분할정복(Divide-and-Conquer) 분할정복전략은 다음과 같이 동작한다. 가장 간단한 경우로 기본 단계를 찾는다. 주어진 문제를 작게 줄여서 기본 단계가 되도록 만드는 법을 찾아낸다. 배열의 모든 원소를 합하는 sum함수를 재귀를 사용하여 만들기 기본 단계 찾기: 원소가 하나이거나 원소가 없을 때에 sum을 구하는 것은 매우 간단하다. sum([7]); // prints 7 sum([]); // prints 0 그러므로 원소가 하나이거나 없을 때의 합계를 구하는 것이 기본 단계가 된다. 주어진 문제를 작게 줄여서 기본 단계가 되도록 하기 sum([2,4,6])은 2 + sum([4,6]) 과 같다. sum([4,6])은 4 + sum([6])과 같다. sum([6])은 6이다. // 기본 단계 ..

문제 첫 번째 글자가 자음일 경우 문자의 맨 뒤로 보낸다. 앞글자가 모음이 될 때까지 반복한 뒤에 "ay"를 붙인다. 첫 번째 글자가 모음일 경우 문자 맨 뒤에 "way"를 붙인다. 예시 translatePigLatin("glove") should return "oveglay". 내가 푼 답 function translatePigLatin(str) { if((/[aeiou]/).test(str[0])) { return str + "way"; } if(!(/[aeiou]/).test(str)) { return str + "ay"; } while(!(/[aeiou]/).test(str[0])) { var result = str.substring(1) + str[0]; str = result; } return..