본문 바로가기

Algorithm65

프로그래머스 마법의 엘레베이터 JavaScript 프로그래머스 마법의 엘레베이터 Javascript 프로그래머스 마법의 엘레베이터는 재귀를 활용한 풀이를 요구하는 문제입니다. 특정 층에서 0층으로 이동하기 위해서는 주어진 선택의 숫자를 조합해서 최소의 수로 이동해야 합니다. 문제에서 주어진 -1, +1, -10, +10 ... 으로 이동하기 위해서는 숫자 별로 조합해보면서 최소의 수를 만드는 공식을 우선 작성해봐야 합니다. 예를 들어 0층에서 16층으로 이동하기 위해서는 간단하게 2가지 방법을 생각해볼 수 있습니다. 각각의 방법을 공식화 하면 다음과 같은 공식을 만들어낼 수 있습니다. solution 함수를 재귀로 돌리면서 몫과 나머지를 구한 다음 각 숫자들을 조합해서 최소의 수가 나오는 결과값을 반환하면 됩니다. 프로그래머스 마법의 엘레베이터 Java.. 2023. 4. 10.
프로그래머스 가장 큰 수 Javascript 프로그래머스 가장 큰 수 Javascript 프로그래머스 가장 큰 수 문제는 Level 2에 해당하는 문제로 문자열 Sorting 능력을 테스트하는 문제입니다. 문제의 핵심은 numbers 배열로 주어지는 숫자들을 어떤 규칙에 따라서 배치할 것인가 인데요, 이 문제만 해결하면 간단하게 sorting 함수를 작성해서 풀어볼 수 있습니다. 예를 들어 [41,40,4]로 구성된 배열이 주어졌을 때 각 원소들을 여러번 반복해서 4자리를 끊어서 반복된 숫자를 비교해 볼 수 있습니다. 41 vs 40 : 4141과 4040을 비교했을 때 4141이 더 크기 때문에 41이 앞에 와야 됨을 알 수 있습니다. 40 vs 4 : 4040과 4444를 비교했을 때 4444가 더 크기 때문에 4가 앞에 와야 됨을 알 수 있습.. 2023. 4. 7.
프로그래머스 체육복 Greedy 탐욕법 문제 Javascript 프로그래머스 체육복 문제 프로그래머스 체육복 문제는 탐욕법으로 풀어보는 것이다. 탐욕법 알고리즘은 각 단계에서 최적이라고 고려되는 것을 선택하는 것을 반복하는 방법이다. 현재 선택이 마지막까지 적용되는 경우 탐욕법으로 문제를 풀어볼 수 있다. 체육복 문제에서는 앞에있는 학생이 체육복을 빌려줄수도 있고, 뒤에 있는 학생이 빌려줄수도 있다. 따라서 가장 우선해서 옷을 빌려줄 순서를 정해야 한다. 먼저 옷을 잃어버린 학생과 빌려줄수 있는 학생 배열을 생성하고, 학생순서대로 스캔해나가면서 옷을 빌려줄 관계를 설정해주면 된다. 프로그래머스 체육복 자바스크립트 배열이 생성된 후로 옷을 잃어버린 학생들의 배열을 순회하면서 옷을 빌려줄 수 있는 경우(Math.abs(r-l) === 1) count를 증가하면서 최종적으.. 2023. 4. 5.
프로그래머스 완주하지 못한 선수 해시 맵 사용 풀이 파이썬 프로그래머스 완주하지 못한 선수 해시 맵 사용 파이썬 완주하지 못한 선수 문제는 인자로 participant와 completion이 주어집니다. 참가자 중 단 한명의 선수만 완주하지 못하는데요, 완주하지 못한 선수를 찾아내야 합니다. 문제 제약 조건은 다음과 같습니다. 참여선수는 1 ~ 10,000명 participant - competion = 1 참가자 이름은 알파벳 20자 이하 참가자 중 동명이인 존재할 수 있음 문제의 핵심은 동명이인이 있다는 점입니다. 단순하게 문자열만 비교해서 문제를 풀 수 없습니다. 해시 맵 사용 파이썬 이 문제가 요구하는 핵심 개념은 해시 맵입니다. key ~ value로 이루어진 자료구조를 통해서 선수들의 이름과 완주 여부를 체크해주어야 합니다. 문제에서 요구하는 hash.. 2023. 3. 22.
Queue 알고리즘 프린터 문제 문제 풀이 ① 그림 그려보기 ② Code function queuePrinter(bufferSize, capacities, documents){ // 변수 선언 let count = 0; let queue = Array(bufferSize).fill(0); let totalBufferVolume = 0; const calculateToalSize = (array) => array.reduce((acc, cur)=>{return acc+cur},0) // 최초 1번만 실행됨 let currentDocument = documents.shift(); queue.unshift(currentDocument); queue.pop(); totalBufferVolume = calculateToalSize(queue);.. 2022. 10. 13.
Queue 박스 포장 문제 문제 풀이 문제를 생각해보면 박스 포장 후 나가는 사람들의 자료구조는 Queue를 사용하고 있음을 알 수 있습니다. 첫번째 사람의 박스 갯수와 뒤의 사람 박스 갯수를 비교해서 Max값을 구하면 코드를 작성하는 건 쉽습니다. Javascript 코드 function paveBox(boxes) { let ans = []; while(boxes.length > 0){ let findIdx = boxes.findIndex(item=>boxes[0] < item); if(findIdx === -1){ ans.push(boxes.length); boxes.splice(0); }else{ ans.push(findIdx) boxes.splice(0, findIdx) } } return Math.max(...ans); .. 2022. 10. 12.
코딩 테스트 알고리즘 공부 방법 순서 정리 보호되어 있는 글 입니다. 2022. 10. 11.
[Stack] 웹 브라우저 뒤로가기 앞으로가기 문제 Stack 웹 브라우저 뒤로가기 앞으로가기 문제 Stack 웹 브라우저 뒤로가기 앞으로가기 풀이 function browserStack(actions, start) { if(typeof start !== 'string') return false; let prevStack = []; let nextStack = []; let current=start; actions.forEach(item=>{ // 뒤로가기(prevStack pop) // 현재 페이지 nextStack push if(item === -1 && prevStack.length !== 0){ nextStack.push(current); current = prevStack.pop() } // 앞으로 가기(nextStack pop) // 현재 페이.. 2022. 10. 11.
[Algorithm] 벨만-포드 알고리즘 (Bellman-Ford) Node.js 벨만-포드 알고리즘이란? 그래프 자료구조에서 최단 거리를 구하는 알고리즘입니다. 그래프 상에서 정점간 최단 거리를 구하는 알고리즘에는 다익스트라 알고리즘이 많이 사용되고, 속도도 빠르지만 굳이 벨만 포드 알고리즘을 사용하는 이유는 음의 가중치가 나왔을 때 다익스트라가 사용불가능하기 때문입니다. 벨만 포드 알고리즘은 한 노드에서 다른 노드로 향하는 최단 거리를 구한다. 간선이 음의 가중치를 가져도 최단거리를 구할 수 있다. 시간 복잡도는 O(V\*E)다. 벨만 포드 VS 다익스트라 알고리즘 다익스트라 알고리즘은 현재 정점에서 연결된 가장 작은 가중치를 가진 정점을 선택하게 됩니다. 예를 들어 아래 그림에서 1번에서 3번으로 가는 최단거리를 구할 때 2가지 경로가 존재합니다. (1 >>> 3)으로 가면 거리.. 2022. 8. 5.
플로이드 워셜 알고리즘 (Floyd-Warshall Algorithm) Node.js 플로이드 알고리즘이란? 플로이드 워셜 알고리즘은 그래프 상에서 가능한 모든 경로의 최단거리를 뽑아내는 문제입니다. 플로이드 워셜 알고리즘의 시간복잡도는 O(V^3)입니다. 그래프 상에서 경로의 최단거리를 구해내는 다익스트라 알고리즘과는 다르게 음의 가중치도 사용할 수 있습니다. 플로이드는 이 알고리즘을 개발하고 튜링상을 수상합니다. 플로이드 알고리즘 설명 플로이드 워셜 알고리즘을 적용하기에 가장 좋은 분야는 방향성 그래프가 주어지는 상황입니다. 예를 들어 vertex 4개가 다음과 같은 방향성을 가진 그래프가 있다고 가정합니다. 이 그래프에서 1에서 3으로 가기 위해서는 stopover가 있어야 합니다. 3에서 1로는 갈 수 있지만 1에서 3으로 가기 위해서는 1-2-3을 거쳐 가야 하고, 혹은 1-4-.. 2022. 8. 4.
[Algorithm] 조합 최적화 알고리즘 subsetSum Node.js 조합 최적화 알고리즘은 주어진 배열 내에서 특정 조건을 만족하는 최적의 조합을 찾아내는 문제입니다. 조합(Combination)이란? 조합은 서로 다른 n개의 원소중에서 순서에 상관없이 r개의 원소를 선택하는 것입니다. 순열(Permutation)은 순서를 가진 조합입니다. let output = subsetSum([1, 8, 3, 15], 10); console.log(output); // --> 9 (= 1 + 8) output = subsetSum([20, 80, 99, 27, 35], 100); console.log(output); // --> 100 (= 20 + 80) output = subsetSum([10, 20, 15, 25, 30], 5); console.log(output); // -.. 2022. 8. 2.
[Algorithm] TSP 알고리즘(해밀턴 경로 방문 판매원 문제) Node.js 그래프 이론상에서 해밀턴 경로란 모든 꼭짓점을 한번씩 지나는 경로를 의미합니다. 해밀턴 순환은 해밀턴 경로인 순환을 의미합니다. 해밀턴 경로를 가지는 그래프는 해밀턴 그래프 혹은 자취 존재 그래프(Traceable Graph)입니다. NP hard란 무엇인가? NP-hard는 Nondetermisitic Polynomial - Hard를 의미합니다. 비결정적 다항식으로 답을 도출해내기 난해한 문제를 의미합니다. 예를 들어 다음과 같은 문제가 주어지면 x 값은 12라는 것을 도출해낼 수 있습니다. 변수를 정의할 상수가 충분히 존재하기 때문입니다. x - 10 = 2 NP-hard의 대표적인 문제가 TSP(Traveling Saleman Problem)입니다. 어떤 출발점에서 해밀턴 경로를 충족하면서 최단거.. 2022. 7. 31.
[Algorithm] 병합 정렬(Merge Sort) 구현하기 Node.js 병합 정렬(Merge Sort)이란? 병합정렬(Merge Sort)는 합병 정렬이라고도 부르며 안정 정렬에 속하는 알고리즘입니다. 분할 정복(Divide and Conquer) 알고리즘의 하나로 1945년 존 폰 노이만이 개발하였습니다. 즉, 하나의 문제를 2개의 작은 문제로 분할한 다음 해당 결과를 모아 전체 문제의 답을 구해나가는 방식을 차용합니다. 병합 정렬은 안정 정렬로 데이터 분포에 영향을 거의 받지 않고, 입력 데이터에 상관없이 동일한 시간복잡도(O(N log N)을 가집니다. 분할 단계에서는 비교연산과 이동 연산을 수행하지 않지만, 분할된 데이터들을 특정 조건에 맞춰 병합하는 과정에서 호출의 깊이 Log N 번과 입력 데이터의 길이 N을 곱한 O(N log N) 시간복잡도가 소요됩니다. 병합.. 2022. 7. 19.
[Algorithm] 백준 2580 스도쿠 Node.js 스도쿠는 18세기 스위스의 수학자 레온하르트 오일러가 창안한 라틴방진(Latin Square)를 기초로 합니다. 미국의 건축가 하워드 간즈(Howard Garns)가 넘버플레이스라는 이름으로 1979년 소개했습니다. 대중화 된 계기는 1984년 일본 니코리사 에서 스도쿠라는 이름을 붙여 판매하면서 알려지기 시작했습니다. 스도쿠를 푸는 방법은 간단합니다. 3가지 규칙에 부합하는 숫자를 찾아 빈칸에 입력하면 됩니다. 가로줄 중 1~9가 중복없이 들어가야 합니다. 세로줄 중 1~9가 중복없이 들어가야 합니다. 3x3 칸 중 1~9가 중복없이 들어가야 합니다. 백준 2580 스도쿠 문제 문제 스도쿠 문제를 푼 최종 모습을 출력하세요 입/출력 입력 아홉줄에 걸쳐 한줄에 9개씩 숫자가 입력됩니다. 숫자가 채워져야 .. 2022. 7. 18.
[Algorithm] Ugly Number 구하기 (Node.js) 문제 uglyNumber는 2,3,5로만 나누어 떨어지는 숫자입니다. 주어진 n번째 uglyNumber을 반환합니다. uglyNumber uglyNumber는 2,3,5로만 나누어 떨어지는 숫자입니다. 1번째 uglyNumber은 1입니다. uglyNumber = 1,2,3,4,5,6,8,9,10,12,15,16 ... 입/출력 입력 number >= 1 출력 number 타입을 반환합니다. 주의사항 uglyNumber을 배열에 저장할 때 n번째 uglyNumber은 n-1 인덱스를 가집니다. 풀이 uglyNumber은 소수(Prime Number)와 맥을 같이 합니다. 우선 소수를 구하는 로직은 다음과 같습니다. const checkPrime = (num) =>{ for(let i=2; i 2022. 7. 15.

티스토리툴바