개발 노트/알고리즘 노트

문제 어떠한 수 N이 1이 될 때까지 다음의 두 과정 중 하나를 반복적으로 선택하여 수행하려고 한다. 단, 두 번째 연산은 N이 K로 나누어떨어질 때만 선택할 수 있다. N에서 1을 뺀다 N을 K로 나눈다 N과 K가 주어질 때, N이 1이 될 때까지 몇 번의 과정을 수행해야하는지를 구하시오. 며칠 전까지의 나였다면 사실 문제 자체는 아주 간단하다. while로 n이 1이 될 때까지 반복문을 돌리면서 외부 변수 count를 하나 만들고, 반복문이 한 번 시행될 때마다 count++를 해주면 끝이다. function solution(N, K) { let count = 0; while (N > 1) { if (N % K === 0) N /= K; else N -= 1; count++; } return coun..

문제 : 프로그래머스 레벨 1 - 최대공약수와 최소공배수 문제 : 프로그래머스 레벨 1 - 기사단원의 무기 최대공약수 내가 두 수의 최대공약수를 구하기 위해 짰던 코드는 대략 다음과 같다. 각각의 숫자에 대해 for 반복문을 돌면서 i로 나눈 나머지가 0인 숫자들의 배열을 만들고, 두 개의 배열 중 더 짧은 배열을 기준으로 마지막 인덱스에서부터 시작해서 indexOf를 통해 최대공약수를 찾았다. 최대공약수 하나 찾기 위해서 단일 반복문이 두 개와 이중 반복문 하나를 사용한 셈이다. 당연히 성능이 좋을 리 없다. const findGCD = (a, b) => { const min = Math.min(a, b); let gcd = 1; for (let i = 1; i { const lcm = (a * b) ..

문제 : 프로그래머스 레벨 1 - 3진법 뒤집기 나의 풀이 // 윽, 코드 스멜(?) const solution = n => parseInt(n.toString(3).split("").reverse().join(""), 3); 사실 이런 식으로 코드를 짜는 건 내가 선호하는 방식은 아니다. "나는 한 줄의 코드만으로 문제를 풀 수 있다"는 걸 과시(?)하고 싶었다고 할까. 실제 코드를 저런 식으로 짜면 ─ 너무나 축약된 나머지 ─ 이게 뭐하는 코드인지 눈에 잘 들어오지 않아서 유지보수는 둘째치고 다른 사람과 협업할 때 상당히 곤란할 것이다. const solution = (number) => { const convertedNumber = number.toString(3).split("").reverse(..

문제 : 프로그래머스 레벨 1 - 가장 많이 받은 선물 나의 풀이 우선 본론부터 말하자면 이번 문제에 대한 나의 풀이에 문제는 없다. 문제가 없을 뿐만 아니라 솔직히 다른 사람의 풀이와 비교해서 꿀리지 않는다고 생각한다. 다만 나 혼자 안고 있는 의문이 한 가지 있는데, 과연 내가 해시테이블을 사용해서 문제를 풀었다고 볼 수 있을까? 어느정도는 해시테이블을 '이용'했다고 볼 수 있을 거 같다. 그런데 해시테이블로 풀었다고 말하기는 어딘가 애매하다. 우선 전체 코드는 아래와 같다. function solution(friends, gifts) { var answer = 0; let table = {}; // 전체 테이블 초기화 for (i = 0; i < friends.length; i++) { table[..

버블 정렬 버블 정렬은 1) 인접한 두 개의 요소를 비교하며 2) j 인덱스의 요소가 j+1 인덱스의 요소보다 클 경우 3) 두 요소의 위치를 바꿔주는 방식으로 진행된다. 바깥의 for 반복문이 한 번 동작하면 인덱스의 마지막에 배열의 가장 큰 요소가 도착했다는 의미이므로, 안쪽의 for 반복문은 매번 n-1-i 번만큼만 동작하게 된다. function solution(arr) { const n = arr.length; for (i=0; i

문제 : 프로그래머스 레벨 1 - 숫자 문자열과 영단어 나의 풀이 사실 이 문제는 오늘이 두 번째 풀어보는 거다. 자바스크립트 처음 입문했을 쯤에 아주 간단해보여서 시도했다가 크게 엿을 먹고 도망쳤던 기억이 있다. 이후로 반년 정도가 지났고, 알고리즘 공부한지 한 2주 정도 된 지금 시점에서는 아주 간단하게 풀 수 있었다. 문자를 하나씩 받으면서 stack에 넣어주다가 해당 stack의 문자열이 switch의 특정 문자열과 일치하면 answer에 담아주고, 마지막에 이 answer의 문자를 숫자형으로 바꿔주기만 하면 끝이다. function solution(s) { var answer = ""; let stack = "" for (const i of s) { if (!isNaN(i)) { answer+=..

문제 : 프로그래머스 레벨 1 - 햄버거 만들기 나의 풀이 아주아주 간단하게 해결할 수 있는 종류의 문제이다. 딱 보자마자 스택으로 풀어야지 싶었다. 그래서 배열의 item을 하나씩 스택에 넣으면서 특정한 조건을 만족하는지 확인했다. 만약 이 조건을 만족하면 answer에 1을 더하고, 스택에 있는 놈 뒤에서 네 개 삭제하면 뚝딱이다. function solution(ingredient) { var answer = 0; let stack = [] for (const i of ingredient) { stack.push(i) if ( stack[stack.length-1] === 1 && stack[stack.length-2] === 3 && stack[stack.length-3] === 2 && stac..

문제 : 프로그래머스 레벨 1 - 과일장수 초기 아이디어 문제 자체는 굉장히 심플하다. 과일 장수가 얻을 수 있는 최대 이익을 실현하기 위해서는 배열을 내림차순으로 정렬하고, m개씩 잘라서 해당 상자의 가장 낮은 점수를 구하고, 이 점수들을 모아서 return 해주면 그만이다. function solution(k, m, score) { var answer = 0; let n = m - 1 score.sort((a, b) => b - a) while (score.length >= m) { let box = score.splice(0, m) if (box[n] > k) { answer += k * m } else { answer += box[n] * m } } return answer; } 그리고 처음 짠 ..

문제 : 프로그래머스 레벨 1 - 모의고사 나의 풀이 function solution(answers) { var answer = []; const cand1 = [1, 2, 3, 4, 5] const cand2 = [2, 1, 2, 3, 2, 4, 2, 5] const cand3 = [3, 3, 1, 1, 2, 2, 4, 4, 5, 5] let candi1 = [] let candi2 = [] let candi3 = [] let count = [0, 0, 0] while (candi1.length < 10000) { candi1 = [...candi1, ...cand1] candi2 = [...candi2, ...cand2] candi3 = [...candi3, ...cand3] } for (const ..

연산자// 나머지 연산자a % b// 주어진 숫자의 1의 자리 확인a % 10 Math 객체// 절댓값 찾을 때Math.abs(x)// 제일 큰 수 찾을 때Math.max(a, b, c, d, ...)// 제일 작은 수 찾을 때Math.min(a, b, c, d, ...)// 반올림Math.round(x)// 내림Math.floor(x)// 올림Math.ceil(x) 반복문// 조건식이 true면 동작하고, false면 멈춘다while (조건식) {}for (변수; 조건식; 추가_동작) {}// i에 index가 차례로 들어온다for (const i in arr) {}// i에 obj.key가 차례로 들어온다for (const i in obj) {}// i에 item이 차례로 들어온다for (const ..