📘 알고리즘(Algorithm)
📖 알고리즘
📃 알고리즘의 정의
- 주어진 문제를 해결하는 일련의 방법 또는 절차.
📃 알고리즘을 배우는 이유
-
컴퓨터처럼 사고하는 능력을 기르기 위해.
-
문제를 작고 관리하기 쉬운 부분으로 나누고 각 부분을 체계적으로 해결하여 문제를 해결하는 능력을 기르기 위해
-
코딩 테스트 연습을 위해
📕 도전 문제 1 ~ 5
📃 문제 1
두 자연수 a와 b가 주어질 때, 이 둘의 최대공약수를 구하는 함수를 작성하세요.
🔒 제한사항
- a, b는 1 이상 1000 이하의 자연수입니다.
💻 답
function gcd (a, b) {
let i;
//유클리드 호제법
while (b !== 0) {
i = a % b;
a = b;
b = i;
}
return a;
}
console.log(gcd(1071, 1029)); // 21-
gcd = greatest common divisor (최대 공약수)
-
유클리드 호제법 - 두 양의 정수 혹은 두 다항식의 최대 공약수를 구하는 방법.
-
gcd는 a와 b를 나누어떨어지게 하는 수 중 가장 큰 정수
-
a > b일 때, a를 b로 나눈 나머지를 n으로 하고
a를 b, b를 n으로 대입하는 과정을 a 또는 b가 0이 될 때 까지 반복한다. -
ex) a=189, b=153일 때 189/153=1 나머지 36이다.
= (189 = 153 * 1 + 36)이므로 gcd(189, 153) == gcd(153,36)이 성립한다.
과정을 반복해 a 또는 b가 0이 됐을 때 다른 쪽의 값이 최대공약수가 된다.
-
📃 문제 2
주어진 배열에서 짝수와 홀수의 개수를 각각 세는 함수를 작성하세요. 함수는 [짝수 개수, 홀수 개수]의 배열을 반환해야 합니다.
🔒 제한사항
- 배열의 길이는 1 이상 1000 이하입니다.
- 배열의 원소는 1 이상 1000 이하의 자연수입니다.
💻 답
function oddEven (arr) {
let odd = 0;
let even = 0;
const calArr = [];
arr.forEach(element => {
element % 2 === 0 ? even++ : odd++;
});
calArr.push(even);
calArr.push(odd);
return calArr;
}
const arr = [1, 2, 3, 4, 5, 6];
console.log(oddEven(arr)); // [3, 3]- 요소에 2로 나눈 나머지 값이 0이면 짝수 0이 아니면 홀수
📃 문제 3
문자열이 주어지면 해당 문자열을 역순으로 배치한 후, 알파벳을 하나씩 오른쪽으로 이동시킨 결과를 출력하세요. 예를 들어, a는 b, z는 a로 변환됩니다.
🔒 제한사항
- 문자열은 소문자 알파벳으로만 구성됩니다.
- 문자열의 길이는 1 이상 1000 이하입니다.
💻 답
function move (str) {
let movedStr = str.toLowerCase()
.split('')
.reverse()
.map(element => {
// 아스키코드 +1 = 다음 알파벳으로 변환
element = element.charCodeAt() + 1;
// z일 경우 a로
if (element > 122) element = 97;
// 아스키코드로 변환된 요소를 다시 문자열로 변환
return String.fromCharCode(element);
});
return movedStr.join('');
}
const str = "hello";
console.log(move(str)); // pmmfi-
소문자로만 구성 toLowerCase()
-
split('') ''를 기준으로 각 요소로 배열을 만드는 함수
-
reverse() 배열을 역순으로 만드는 함수
-
map() 각 요소에 인자로 전달된 함수를 실행한 결과를 모아 새 배열로 만듦
-
String.charCodeAt() - 넘겨진 인덱스의 문자를 UTF-16 유닛 코드로 반환
없을 경우 index 0 사용 -
String.fromCharCode() - 인자로 넘겨진 UTF-16 유닛 코드를 문자로 반환
📃 문제 4
회전 초밥을 먹을 때, 접시들의 번호가 주어집니다. 이 중에서 임의의 연속된 접시를 선택하여 먹을 때, 가능한 모든 선택에서 가장 다양한 초밥 종류의 개수를 구하세요.
🔒 제한사항
- 접시의 개수는 2 이상 1000 이하입니다.
- 각 접시는 1 이상 30 이하의 정수로 표현됩니다.
💻 답
function sushiMix (sushi) {
const mixCnt = [];
// 빈도 수
let cnt = 0;
// 각 요소의 연속되는 경우의 빈도 수를 저장
for (let i = 0; i < sushi.length; i++) {
cnt = 0;
for (let j = i+1; j < sushi.length; j++) {
// 연속되지 않는 경우 = 같은 숫자가 나오는 경우
if (sushi[i] == sushi[j]) break;
cnt++;
}
mixCnt.push(cnt);
}
// 빈도수를 담은 배열의 최댓값을 반환
return Math.max(...mixCnt);
}
const sushi = [1, 2, 1, 3, 2, 1, 4, 1];
console.log(sushiMix(sushi)); // 4📃 문제 5
양의 정수가 주어질 때, 숫자에서 k개의 자릿수를 제거하여 얻을 수 있는 가장 큰 수를 구하세요.
🔒 제한사항
number는 최대 1,000,000자리까지 입력될 수 있습니다.k는 1 이상len(number)- 1 이하입니다.
💻 답
function plus (number, k) {
// 정수를 문자열로 변환 -> 배열로 변환 -> 내림차순으로 정렬
let num = number.toString().split('').sort((a,b) => b - a);
// 배열의 마지막 요소를 삭제하는 pop() 함수
// 자릿수 k 만큼 반복
for (let i = 0; i < k; i++) {
num.pop();
}
return num.join('');
}
const number = 1924;
const k = 2;
console.log(plus(number, k)); // 94- sort()
- 콜백 함수의 실행 결과가 양수면 요소를 낮은 인덱스로,
음수면 높은 인덱스로 정렬 0이면 같으므로 그대로
- 콜백 함수의 실행 결과가 양수면 요소를 낮은 인덱스로,
