TIL 11 알고리즘 공부하자
콜라츠 추측 [27번 문제]
[문제설명]
1937년 Collatz란 사람에 의해 제기된 이 추측은, 주어진 수가 1이 될때까지 다음 작업을 반복하면, 모든 수를 1로 만들 수 있다는 추측입니다. 작업은 다음과 같습니다.
1-1. 입력된 수가 짝수라면 2로 나눕니다.
1-2. 입력된 수가 홀수라면 3을 곱하고 1을 더합니다.
2. 결과로 나온 수에 같은 작업을 1이 될 때까지 반복합니다.
예를 들어, 입력된 수가 6이라면 6→3→10→5→16→8→4→2→1 이 되어 총 8번 만에 1이 됩니다. 위 작업을 몇 번이나 반복해야하는지 반환하는 함수, solution을 완성해 주세요. 단, 작업을 500번을 반복해도 1이 되지 않는다면 –1을 반환해 주세요.
[제한조건]
입력된 수, num은 1 이상 8000000 미만인 정수입니다.
function solution(num) {
let repeatCount = 0; // 반복횟수 선언
while (num !== 1){ // 입력값이 1하고 같지 않으면(같을 때 까지) 반복문
if (repeatCount > 500) { // 반복횟수가 500번 이상이면
return -1 // -1 출력
}
num % 2 === 0 ? num = num / 2 : num = num * 3 + 1
repeatCount++
// 입력값이 2로 나누어 떨어지(짝수)면 ? 입력값을 2로 나눔 : 그렇지 않다면 3을 곱하고 1을 더함
// 위 연산을 할 때 마다 반복횟수 1씩 증가
}
return repeatCount // 출력값 = 반복횟수
}
[접근방식]
repeatCount : 반복횟수
num : 입력값
while 반복문
작업한 내용에 대한 횟수 증가
[풀이]
혼자서 해결하기 어려워 블로그 참조
같은 숫자는 싫어 [31번 문제]
[문제설명]
배열 arr가 주어집니다.
배열 arr의 각 원소는 숫자 0부터 9까지로 이루어져 있습니다.
이때, 배열 arr에서 연속적으로 나타나는 숫자는 하나만 남기고 전부 제거하려고 합니다.
단, 제거된 후 남은 수들을 반환할 때는 배열 arr의 원소들의 순서를 유지해야 합니다.
예를 들면,
arr = [1, 1, 3, 3, 0, 1, 1] 이면 [1, 3, 0, 1] 을 return 합니다.
arr = [4, 4, 4, 3, 3] 이면 [4, 3] 을 return 합니다.
배열 arr에서 연속적으로 나타나는 숫자는 제거하고 남은 수들을 return 하는 solution 함수를 완성해 주세요.
[제한조건]
배열 arr의 크기 : 1,000,000 이하의 자연수
배열 arr의 원소의 크기 : 0보다 크거나 같고 9보다 작거나 같은 정수
=> 배열내 중복 숫자 제거
function solution (arr)
{
var answer = [];
answer.push(arr[0])
for(let i = 1 ; i < arr.length ; i++){
if(arr[i-1] !== arr[i]){
answer.push(arr[i])
}
}
}
solution([1,1,3,3,0,4,4,4,0,0,1,1,1,2])| arr | [ 1, 1, 3, 3, 0, 4, 4, 4, 0, 0, 1, 1, 1, 2] | |||||||||||||||
| arr[i-1] | 1 | 1 | 3 | 3 | 0 | 4 | 4 | 4 | 0 | 0 | 1 | 1 | 1 | 2 | ||
| arr[i] | 1 | 1 | 3 | 3 | 0 | 4 | 4 | 4 | 0 | 0 | 1 | 1 | 1 | 2 | ||
| answer.push() | 1 | 3 | 0 | 4 | 0 | 1 | 2 | |||||||||
| [1,3,0,4,0,1,2] | arr[0] | arr[i] | ||||||||||||||
| 4번 라인에서 push() |
7번 라인에서 push() |
|||||||||||||||
[접근방식]
중복값 제거 함수?
시도1. set으로 했으나 [1,3,0,1] 으로 출력이 되어야 하는데, [1,3,0] 만 출력
[풀이]
[문제링크]
[다른사람풀이]
정수 제곱근 판별 [25번 문제]
[문제설명]
임의의 양의 정수 n에 대해, n이 어떤 양의 정수 x의 제곱인지 아닌지 판단하려 합니다.
n이 양의 정수 x의 제곱이라면 x+1의 제곱을 리턴하고, n이 양의 정수 x의 제곱이 아니라면 -1을 리턴하는 함수를 완성하세요.
[제한조건]
n은 1이상, 50000000000000 이하인 양의 정수입니다.
function solution(n) {
let sqrt = Math.sqrt(n);
let integer = Number.isInteger(sqrt);
if(integer) return Math.pow(sqrt + 1, 2);
else return -1;
}
[접근방식]
- 제곱근 구하는 함수
- 숫자인지 확인 한번
- pow()
간단한 예) 7의 제곱, Math.pow(7, 2) // 49
[풀이]
1. 제곱근을 구하는 식을 변수 sqrt에 담는다.
2. 전달된 값이 정수인지 아닌지 확인하는 식을 변수 integer에 담는다.
3. 만약 숫자이면, 제곱근에 + 1한 값을 제곱 한다.
4. 정수가 아니면 -1을 리턴한다.
3진법 뒤집기 [29번 문제]
[문제설명]
자연수 n이 매개변수로 주어집니다. n을 3진법 상에서 앞뒤로 뒤집은 후,
이를 다시 10진법으로 표현한 수를 return 하도록 solution 함수를 완성해주세요.
[제한조건]
n은 1 이상 100,000,000 이하인 자연수입니다.
v
[접근방식]
[풀이]
[문제링크]
[다른사람풀이]
[문제설명]
명함 지갑을 만드는 회사에서 지갑의 크기를 정하려고 합니다. 다양한 모양과 크기의 명함들을 모두 수납할 수 있으면서, 작아서 들고 다니기 편한 지갑을 만들어야 합니다. 이러한 요건을 만족하는 지갑을 만들기 위해 디자인팀은 모든 명함의 가로 길이와 세로 길이를 조사했습니다.
아래 표는 4가지 명함의 가로 길이와 세로 길이를 나타냅니다.
명함 번호 가로 길이 세로 길이
1 60 50
2 30 70
3 60 30
4 80 40
가장 긴 가로 길이와 세로 길이가 각각 80, 70이기 때문에 80(가로) x 70(세로) 크기의 지갑을 만들면 모든 명함들을 수납할 수 있습니다. 하지만 2번 명함을 가로로 눕혀 수납한다면 80(가로) x 50(세로) 크기의 지갑으로 모든 명함들을 수납할 수 있습니다. 이때의 지갑 크기는 4000(=80 x 50)입니다.
모든 명함의 가로 길이와 세로 길이를 나타내는 2차원 배열 sizes가 매개변수로 주어집니다. 모든 명함을 수납할 수 있는 가장 작은 지갑을 만들 때, 지갑의 크기를 return 하도록 solution 함수를 완성해주세요.
[제한조건]
sizes의 길이는 1 이상 10,000 이하입니다.
sizes의 원소는 [w, h] 형식입니다.
w는 명함의 가로 길이를 나타냅니다.
h는 명함의 세로 길이를 나타냅니다.
w와 h는 1 이상 1,000 이하인 자연수입니다.
[접근방식]
[풀이]
[문제링크]
[다른사람풀이]