[TIL] 230523 - 백준 알고리즘 문제 풀이

오늘 한 것

- 백준 알고리즘 문제 풀이
4989번 : 베르트랑 공준
2869번 : 달팽이는 올라가고 싶다
10250번 : ACM 호텔
1929번 : 소수 구하기
1110번 : 더하기 사이클

---

백준 문제 풀이 

백준 4989번 : 베르트랑 공준 (난이도 하)

https://www.acmicpc.net/problem/4948

4948번: 베르트랑 공준

const fs = require('fs');
const filePath = process.platform === 'linux' ? '/dev/stdin' : __dirname + '/input.txt';
var input = fs.readFileSync(filePath).toString().split('\n');
let num = [];
for (let i = 0; i < input.length; i++) {
    if(parseInt(input[i]) == 0)
        break;
    num.push(parseInt(input[i]));
}

let num_lit = new Array(Math.max.apply(null, num) * 2); // 최댓값의 2배만큼 수열 만들기
num_lit.fill(true); // 소수면 true 소수가 아니면 false
num_lit[0] = false; // 0 // 0 과 1은 소수가 아니니까 0과 1은 제외
num_lit[1] = false; // 1

for(let i = 2; i <= parseInt(Math.sqrt(num_lit.length)); i++) { // 2부터 소수인지 판별 하되
    if (!num_lit[i]) // 소수가 아닌 수로 판별 된 것은 ( 이미 제외시킨 수니까 ) 제외
        continue;
    for (let j = i + i; j < num_lit.length; j += i) { // 자기 자신을 제외한 다음 배수부터 ( i + i ) 배수만큼 ( += i ) 수열에서 소수 제외시키기
        num_lit[j] = false;
    }
}

num.forEach((n)=>{
    let count = 0;
    for (let i = n + 1; i <= 2 * n; i++) {
        if(num_lit[i])
            count++;
    }
    console.log(count);
})

드라이버로 처음 참여했던 문제... 다들 Java하셔서 js로 설명해주시느라 고생하셨어요
문제를 잘 푸는것도 중요하지만 시간도 문제라는 걸 알게 된 문항
알고리즘 시간 복잡도를 이론으로 배울 때는 솔직히 와닿지 않았었는데 이렇게 시간으로 결과가 나오니 왜 중요한지 알게되었다..
 

 백준 2869번 : 달팽이는 올라가고 싶다 (난이도 중하)

https://www.acmicpc.net/problem/2869

2869번: 달팽이는 올라가고 싶다

코드 추가 예정
 

 백준 10250번 : ACM 호텔 (난이도 중하)

https://www.acmicpc.net/problem/10250

10250번: ACM 호텔

코드 추가 예정
 

백준 1929번 : 소수 구하기 (난이도 중하)

https://www.acmicpc.net/problem/1929

1929번: 소수 구하기

const fs = require('fs');
const filePath = process.platform === 'linux' ? '/dev/stdin' : __dirname + '/input.txt';
var input = fs.readFileSync(filePath).toString().split(' '); // 콘솔 입력
let num = [];
for (let i = 0; i < input.length; i++) {
    if(parseInt(input[i]) == 0)
        break;
    num.push(parseInt(input[i]));
     }

// 방법 1
let num_lit = new Array(num[1] + 1).fill().map((arr,i) =>{
     if(i % 2 == 0)
         return false;
     return true;
 });
 num_lit[1] = false; // 1
 num_lit[2] = true;
 for(let i = 3; i <= parseInt(Math.sqrt(num[1])); i++) { // 2부터 소수인지 판별 하되
     if (!num_lit[i]) // 소수가 아닌 수로 판별 된 것은 ( 이미 제외시킨 수니까 ) 제외
         continue;
     for (let j = i + i; j < num_lit.length; j += i) { // 자기 자신을 제외한 다음 배수부터 ( i + i ) 배수만큼 ( += i ) 수열에서 소수 제외시키기
         num_lit[j] = false;
     }
 }

// 방법 2 - 에라토스테네스의 체 이용
let num_lit = new Array(/*max 수열 + 1*/ num[1] + 1); // 최댓값의 2배만큼 수열 만들기
num_lit.fill(true); // 소수면 true 소수가 아니면 false
num_lit[0] = false; // 0 // 0 과 1은 소수가 아니니까 0과 1은 제외
num_lit[1] = false; // 1

for(let i = 2; i <= parseInt(Math.sqrt(num_lit.length)); i++) { // 2부터 소수인지 판별 하되
    if (!num_lit[i]) // 소수가 아닌 수로 판별 된 것은 ( 이미 제외시킨 수니까 ) 제외
        continue;
    for (let j = i + i; j < num_lit.length; j += i) { // 자기 자신을 제외한 다음 배수부터 ( i + i ) 배수만큼 ( += i ) 수열에서 소수 제외시키기
        num_lit[j] = false;
    }
}

for (let i = num[0]; i < num[1]; i++) {
    if(num_lit[i])
        console.log(i);
}

 

백준 1110번 : 더하기 사이클 (난이도 중하)

https://www.acmicpc.net/problem/1110

1110번: 더하기 사이클

const fs = require('fs');
const filePath = process.platform === 'linux' ? '/dev/stdin' : __dirname + '/input.txt';
var input = fs.readFileSync(filePath).toString().split(' '); // 콘솔 입력
let num = input[0];

let temp = 0;
temp = num;

let count = 0;

do{
    if(temp < 10){
        temp = temp * 10 + temp;
    } else {
        temp = (temp%10 * 10) + (parseInt(temp / 10) + temp % 10) % 10;
    }
    count++;
} while(temp != num)
    console.log(count);
}

팀원 Jun님이 네비게이터, 팀원들이 모두 드라이버가 되어 작성된 마법의 코드

---

일기

짝 프로그래밍으로 알고리즘을 풀도록 지도해주시는데, 처음에는 짝 프로그래밍을 어떻게 진행하는지 어려웠지만 Jun님이 잘 이끌어주신 덕분에 장점을 확실하게 알 수 있었다.