YELOPER

1️⃣ 슬라이딩 윈도우란? 고정 사이즈의 윈도우가 이동하면서 윈도우 내에 있는 데이터를 이용해 문제를 풀이하는 알고리즘 배열이나 리스트의 요소의 일정 범위 값을 비교할 때 사용하면 매우 유용 배열과 그 부분 배열을 어떤 조건하에서 계산하는 경우에 주로 사용 예) 구간 합 구하기, 부분 문자열 구하기 등 2️⃣ 구간마다 일일이 합을 구할 경우 vs 슬라이딩 윈도우 알고리즘을 활용할 경우 1. 구간마다 일일이 합을 구할 경우 앞에서 구했던 값이 있음에도 불구하고 다음 번에 또 구하고.. 또 구하고.. 시간복잡도가 늘어날 수밖에 없다 -> 효율성이 떨어짐 2. 슬라이딩 윈도우 알고리즘을 활용할 경우 최초 윈도우에 대해서만 값을 구하고 한 칸씩 윈도우를 밀 때에는 이전 구간 합을 활용함 -> 효율성 좋음 윈도우..

1️⃣ 그리디 알고리즘이란? 선택의 순간마다 당장 눈 앞에 보이는 최적의 상황만을 쫓아 최종적인 해답에 도달하는 방법 그리디 알고리즘을 해결하기 위해서는 최적이라 생각되는 해답을 찾고 이를 통해 최종 문제의 해답에 도달하는 방식으로 접근해야 함 locally optimal solution -> globally optimal solution 그러나, 이런 방법은 항상 최적의 결과를 보장하지 않음 (특정한 상황에서만 보장) 2️⃣ 그리디 알고리즘을 사용할 수 있는 두 가지 조건 탐욕적 선택 속성(Greedy Choice Property) : 앞의 선택이 이후의 선택에 영향을 주지 않는다 최적 부분 구조(Optimal Substructure) : 문제에 대한 최종 해결 방법은 부분 문제에 대한 최적 해결 방법..

프로그래머스에서 피보나치 수열 코딩테스트 문제를 풀다가... 신나게 재귀함수로 풀어야지~~ 하고 풀었지만 시간초과, 런타임 에러... 프로그래머스에서 제공하는 코딩테스트 연습 힌트 모음집을 보니까 딱 나의 케이스에 대한 내용이 있었다🤣 일반적인 재귀를 단순히 사용 시 동일한 작은 문제들이 여러 번 반복 되어 비효율적인 계산이 되어 시간초과가 난 것이었다,, return f(n) = f(n-1) + f(n-2) 이렇게 하게 되면 f(n-1)에서 한 번 구한 값을 f(n-2)에서 또 같은 값을 구하는 과정을 반복하게 되기 때문에 100번째 피보나치 수를 구하기 위해 호출되는 함수의 횟수는 기하급수적으로 증가하는 것이다. 그러나 한 번 구한 작은 문제의 결과 값을 저장해두고 재사용하게 되면 앞에서 계산된 값을..

1. 추상자료형이란? 어떤 데이터의 구체적인 구현 방식은 생략한 채, 데이터의 추상적인 형태와 그 데이터를 다루는 방법만을 정해놓은 것 ADT(Abstract Data Type) 2. 스택(Stack) 데이터를 집어넣을 수 있는 선형(linear) 자료 나중에 집어넣은 데이터가 먼저 나옴. LIFO(Last In First Out) 데이터를 집어넣는 push / 데이터를 추출하는 pop / 맨 나중에 집어넣은 데이터를 확인하는 peek class Stack { constructor() { this._arr = []; } push(item) { this._arr.push(item); } pop() { return this._arr.pop(); } peek() { return this._arr[this._a..

1. 해시 테이블이란? 자료구조 종류 중 하나로 key와 value를 가짐 직업 : 개발자 나이 : 28 2. 해시란? 해시함수라고 하는 함수를 이용해서 입력값을 고정길이 문자열로 치환하는 것 배열은 key값에 숫자만 받을 수 있지만 해시는 문자열까지 받을 수 있음 문자열로 받은 key 값을 해싱이라는 과정을 통해서 일정 길이의 주소값으로 바꿔서 저장해두고 있기 때문 --> 해시 함수의 역할 3. 자바스크립트에서는 좀 더 쉽게 해시 테이블을 사용할 수 있게끔 해주는 자료구조가 있다. --> Map 4. Map이란? key가 있는 데이터를 저장하는 데 쓰이는 자료구조 Map의 key값은 문자열 가능 --> 해시에 이용 가능 5. Map 메서드 new Map() --> Map의 객체를 만들 때 사용 map...

1. 문제 설명 2. 답안 const NUM = 3; function solution(number) { let answer = 0 const tmp = [] const backtrack = (cur) => { // tmp 길이가 3이면 if (tmp.length === NUM){ // tmp의 합을 계산 후 0이면 answer에 1 더하기 answer += tmp.reduce((a,b)=> a + b) ? 0 : 1 return } // tmp 만들기 for (let i = cur; i < number.length; i++){ tmp.push(number[i]) // 재귀호출할 때마다 cur을 사용하여 다음 인덱스로 이동 backtrack(i + 1) // 다음 경우를 탐색하기 전 현재 요소를 제거 tm..

1. 문제 설명 2. 답안 function solution(score) { let arr = [] for(let item of score){ let [eng, math] = item arr.push((eng + math) / 2) } let answer = [...arr].sort((a,b) => b - a) return arr.map(x => answer.indexOf(x) + 1) } - 처음에 reduce로 객체 만들어서 시도하였으나,, 그렇게 하니까 중복된 값이 사라져서 다른 방법으로 시도,, - sort는 원본 배열을 수정하므로 얕은 복사를 통해 answer에 할당 - indexOf는 값에 해당하는 첫번째 인덱스를 반환해주니 중복된 값도 그 첫번째 인덱스로 들어가서 해결!

1. 문제 설명 2. 답안 function solution(keyinput, board) { let answer = [0,0] for (let item of keyinput){ switch (item){ case 'left' : if (-answer[0] < board[0] / 2 - 1) answer[0]--; break; case 'right' : if (answer[0] < board[0] / 2 - 1) answer[0]++; break; case 'up' : if (answer[1] < board[1] / 2 - 1) answer[1]++; break; case 'down' : if (-answer[1] < board[1] / 2 - 1) answer[1]--; break; } } return ..

1. 문제 설명 2. 답안 function solution(spell, dic) { let answer = [] for(let item of dic){ let arr = [] for(let i = 0; i !x.includes(false)).length > 0 ? 1 : 2 }

1. 문제 설명 2. 답안 function solution(sides) { return Math.min(...sides) * 2 - 1 } - 어떻게 접근해야하는지도 감이 안 잡혔던 문제.. 다른 사람 풀이 보니까 이렇게 한 줄로 적혀있어서 육성으로 헐... 이랬는데 역시나 수학 문제였던 것 ㅠㅠㅠ 수학이 사람 잡네😭 - 댓글에 적혀있던 풀이 sides = [a,b] 이고(a>b라고 가정, 이는 sort해주면됩니다.) 새로 주어지는 변의 길이를 c라고 했을 때, a가 가장 긴변인 경우 즉 a > c인 경우 b + c > a > c 이므로 a > c > a-b 이기 때문에 c의 정수 갯수는 b-1개입니다. / c가 가장 긴변인 경우도 이런식으로 하면 되고 a=c 인경우 한가지 이므로 2b-1이 나옵니다.