programmers 구명보트
문제 링크
분류 / 레벨 / 언어탐욕법(Greedy) / LV.2 / Javscript
설명그리디 알고리즘에서 우선순위로 둘 만한것 = 처리하기 쉬운 요소, 놔두면 피곤해지는 요소이 문제에서는 비교적 무거운 사람을 우선순위로 둘 만하다.
오름차순으로 정렬하여,pop()한 사람을 먼저 태우고, 그 위에 가벼운 사람을 가능한 실어서 출발시킬 것이다.
전체 코드1234567891011121314151617181920function solution(people, limit) { let boat = 0; let sum = 0; people.sort((a, b) => a - b); while (people.length > 0) { if (sum === 0) { boat++; sum += people.pop(); } else { while (sum &l ...
programmers 큰 수 만들기
문제 링크
분류 / 레벨 / 언어탐욕법(Greedy) / LV.2 / Javscript
설명처음에는 자료구조를 따로 두지 않고,input으로 들어온 number만 가지고 풀었다.그러니 필요이상으로 루프를 돌게되어 시간복잡도가 매우 커졌다.
그래서 정답으로 return할 스택 answer을 하나 추가하고,k가 남아있을 동안, ‘pop() 이벤트 = k 차감’으로 풀었다
전체 코드12345678910111213141516function solution(number, k) { const answer = number.split("").reduce((acc, curr) => { if (k > 0) { let i = acc.length - 1; while (i > -1 && k > 0 && acc[i] < curr) { ...
programmers 숫자 야구
문제 링크
분류 / 레벨 / 언어완전탐색 / LV.2 / Javscript
설명숫자 야구라는 미니게임이 있다.이 문제는 게임을 만드는 것은 아니고, 그것을 풀어나가는 과정을 만드는 것이다.
먼저 공역은 1-9 사이의 서로 다른 수들로 이루어진 3자리 수이고,따로 주어지지 않아서 알아서 구현해주어야 한다.
공역을 default 답안으로 선택하고,input과 compare(numA, numB)함수의 결과값을 참고하여 답안을 줄여나간다.
전체 코드1234567891011121314151617181920212223242526272829303132333435363738function solution(baseball) { const full = []; for (let a = 1; a < 10; a++) { for (let b = 1; b < 10; b++) { if (a === b) continue; ...
programmers 조이스틱
문제 링크
분류 / 레벨 / 언어탐욕법(Greedy) / LV.2 / Javscript
설명그리디 풀이 시도그리디 카테고리에 있어서 처음엔 그리디 방법론으로 접근했다.조이스틱이 좌-우로 움직이는 순간을 1 turn으로 생각한다.다음 조건을 만족시키며 turn을 반복한다.
[1]ㅡ(왼쪽으로 연속된 A의 개수) <내위치> [2]ㅡ(오른쪽으로 연속된 A의 개수)
[1]과 [2]중 작은 쪽으로 이동한다.(Greedy : 현재 내 위치에서 not A가 더 가깝게 있는 쪽으로 움직인다.)BBAAA<내위치>ABBB => [1]AAAAB<내위치>AABB => [2]만약 [1]과 [2]가 같다면 순리대로 오른쪽으로 이동한다.BBAAB<내위치>BBBB => [2]
모든 글자가 A라면 turn loop를 끝낸다.
그리고 조이스틱의 여러 움직임을 answer++, answer ...
진수 계산
10진수는 number 형을 가지고,다른 모든 진수는 string 형을 갖는다.
편의상 10진수를 A,다른 b진수를 B라고 한다면다음 메서드로 진수 간 변환할 수 있다.
A -> toString(b) -> BB -> parseInt(number, b) -> A
10진수를 변환-> 16진수12let dec = 2378;let hex = dec.toString(16); // "94a"
-> 2진수12let dec = 2378;let bin = dec.toString(2); // "100101001010"
그 외2진수 -> 10진수12let bin = "100101001010";let dec = parseInt(bin, 2); // "2378"
2진수 -> 16진수 (2진수 -> 10진수 -> 16진수12let bin = "1111011";l ...
ES6에서 알면 좋은 문법(feat. 알고리즘 문제풀이)
알고리즘 문제를 풀며 많이 사용했던 JS 기술들을 정리해보았다.코테에서 파이썬만큼 강력하진 않지만, JS도 익숙해지면 충분히 좋은 언어다.
Arrayconst vs letES6에 변수 선언 방식이 다음과 같이 추가되었다.
const = 재할당 불가능let = 재할당 가능
배열도 마찬가지이다.단 헷갈릴 수 있는 부분이 있어 따로 정리해보았다.
123456789101112131415161718const constArr = [1, 1, 1];let letArr = [2, 2, 2];constArr[1] = ["new"]; //가능letArr[1] = ["new"]; //가능constArr.push("new"); //가능letArr.push("new"); //가능// 단, 아래처럼 통으로 갈아치우는 것은 차이가 생긴다constArr = ["new", "arr"]; / ...
programmers 타일 장식물
문제 링크
분류 / 레벨 / 언어동적계획법(Dynamic Programming) / LV.3 / Javscript
설명DP문제는 계산한 값들을 어딘가에 저장해두고 다시 읽어오는 방식으로 푼다.다른 알고리즘 문제들이 count++을 하거나, 누적 값들을 넘겨가며 처리했다면DP는 “언제” 계산했는지와 “어떤”값인지 까지 메모리에 올려 둔다.
문제를 독해하고아 몇 턴 지나면 이 값 또 써야하는데??싶으면 DP로 문제를 풀자!
전체 코드123456789101112function solution(N) { if (N === 1) return 4; const squares = [1, 1]; let count = 2; while (N > count) { squares.push(squares[count - 1] + squares[count - 2]); count++; } return squares[count - ...
programmers 여행경로
문제 링크
분류 / 레벨 / 언어DFS,BFS / LV.3 / Javscript
설명DFS 문제를 재귀로 풀 때는 보통 이런 틀을 갖추고 푼다.
123456let count = 0;const dfs = (상태, 누적 정보)=>{ if() dfs(다음 상태, 누적 정보) if() count++}dfs(초기 상태, 초기 정보)
전체 코드12345678910111213141516171819202122232425262728function solution(tickets) { const routes = []; const next = (now, remains, route) => { if (remains.length === 0) { routes.push(route.concat(now)); return; } remains.forEach((remain, i) ...
programmers 소수 찾기
문제 링크
분류 / 레벨 / 언어완전탐색 / LV.2 / Javscript
설명소수를 찾는 문제인데 크게 구현해줄 함수가 2개 있다.
number => 소수여부: boolean
string => [숫자들의 배열]: array
이 함수들을 따로 정의하고1번 함수 ( 2번 함수 (문제 input) ) 의 return 값 중true인 것의 개수를 반환하면 답이다.
전체 코드1234567891011121314151617181920212223242526272829303132const isSoSu = n => { if (n === 0 || n === 1) return false; if (n === 2 || n === 3) return true; for (let i = 2; i <= n / 2; i++) { if (n % i === 0) return false; } return ...
programmers 모의고사
문제 링크
분류 / 레벨 / 언어완전탐색 / LV.1 / Javscript
설명완전탐색은 사실상 대기업 코딩테스트에서 가장 많이 나오는 주제이다.별도의 방법론이 필요없고, 모든 경우의 수를 검증해주기만 하면 된다.그래서 알고리즘 트레이닝을 안 하고 서비스 개발만 주로 했던 사람(like me)도 부담없이 풀 수 있다.
전체 코드12345678910111213141516171819202122232425262728const picks = [ [1, 2, 3, 4, 5], [2, 1, 2, 3, 2, 4, 2, 5], [3, 3, 1, 1, 2, 2, 4, 4, 5, 5]];const pickCycles = [5, 8, 10];function solution(answers) { let max = 0; return answers .reduce( (acc, cur, idx) => { pickCycl ...
