본문 바로가기

CS/알고리즘

 (38)
[230327] 구명보트: Greedy 알고리즘 탐욕 알고리즘(Greedy Algorithm) greedy: 탐욕스러운, 욕심이 많은 즉, 매 순간 가장 좋아 보이는 것만 선택하며, 현재 선택이 나중에 미칠 영향에 대해서는 고려하지 않음 기준에 따라 좋은 것을 선택하는 알고리즘이므로, 문제에서 ‘가장 큰 순서대로’, ‘가장 작은 순서대로’와 같은 기준이 제시된 경우에 응용한다. 예제: 거스름돈 🧸 문제 당신은 음식점의 계산을 도와주는 점원이다. 카운터에는 거스름돈으로 사용할 500원, 100원, 50원, 10원짜리의 동전이 무한히 존재한다고 가정한다. 손님에게 거슬러줘야 할 돈이 N원일 때 거슬러 줘야 할 동전의 최소 개수를 구하라. 단, 거슬러 줘야 할 돈 N은 항상 10의 배수이다. 문제 해설 동전의 최소 개수를 구해야 하는 문제이므로, 가장 큰 ..
[230326] 짝지어 제거하기: stack 문제 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 내 풀이 i가 첫 번째 원소라서 stack에 원소가 하나밖에 없을 때, stack[stack.length - 2]는 undefined 다. function solution(s) { const stack = []; for(let i of s) { stack.push(i); if(stack[stack.length - 1] === stack[stack.length - 2]){ stack.pop(); stack.pop(); } } return stack.length === 0 ? 1 : 0; } (+) 효율성 ..
[230326] 영어 끝말잇기 문제 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 내 풀이 i = 1 부터 시작해야 oldWord가 존재함 oldWord = 현재 보는 단어의 이전 단어 wod = 현재 단어 하나라도 조건을 만족하지 않으면 [번호, 차례]를 반환한다. 조건1: 한 글자인 경우 (word.length === 1) 조건2: 현재 단어의 첫 글자와 이전 단어의 마지막 글자와 다른 경우 (word[0] !== oldWord[oldWord.length - 1]) 조건3: 현재 말한 단어가 이전 단어에 포함된 경우 (words.slice(0, i).includes(word)) 반..
[230326] 다음 큰 숫자 문제 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 내 풀이 2진수로 변환 후 1의 개수를 구하는 식이 반복되어서 함수를 생성하였다. n+1 숫자부터 보고 2진수 변환 후 1의 개수가 동일하다는 조건을 만족하는 숫자가 나오는 즉시 그 숫자를 해답으로 반환한다. function solution(n) { const binaryN = getOneNum(n); let temp = n; while(true) { const binaryTemp = getOneNum(++temp); if(binaryTemp === binaryN) return temp; } } cons..
[230326] 숫자의 표현 문제 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 내 풀이 i는 끝까지(n) 가면 비효율적이므로, Math.floor(n / 2) 까지만 가도록 작성하였음 answer = 1 ⇒ n은 무조건 포함되는데, i는 n까지 가지 않으므로 처음부터 n을 포함하고 시작함 function solution(n) { let answer = 1; const endNum = Math.floor(n / 2) for(let i = 1; i 0){ i++; if(n % i === 0) answer++; n -= i; } return answer; }
[230325] 3진법 뒤집기: parseInt, toString 문제 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 내 풀이 진짜 문제 그대로 풀었음. 3진수로 변환 (=toString(3)) 앞뒤로 뒤집음 (=[…1번].reverse().join(’’)) 다시 10진법으로 표현 (=parseInt(2번, 3)) function solution(n) { return parseInt([...n.toString(3)].reverse().join(''), 3) } parseInt: N진수 → 10진수 parseInt(num, N) toString: 10진수 → N진수 num.toString(N)
[230325] 이진 변환 반복하기 문제 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 내 풀이 “1”이 될 때까지 반복하므로, s가 “1”이라면 answer를 반환한다. “1”이 아니라면 변환하는 횟수를 더함. 따라서 answer[0] += 1. 그리고 s에서 0의 개수만큼 answer[1]에 더할 것이다. s를 0 단위로 쪼개고 그 길이에서 -1한 값이 s에서 0의 개수이므로, s.split(’0’).length - 1을 더한다. s에서 “0”을 모두 “”로 대체하여 0을 없애고, 그 길이만큼(.length) 이진수로 변환(=toString(2))한다. solution(s)를 반환하여 ..
[230325] 최솟값 만들기 문제 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 내 풀이 A를 오름차순, B를 내림차순으로 정렬 각 인덱스 값을 곱하여 총 합한다. function solution(A,B){ A.sort((a, b) => a - b); B.sort((a, b) => b - a); let answer = 0; for(let i = 0; i < A.length; i++){ answer += A[i] * B[i]; } return answer; }
반응형

티스토리툴바