꾸준합니다

[boj] 6588. 골드바흐의 추측

[boj] 6588. 골드바흐의 추측 문제 링크 : https://www.acmicpc.net/problem/6588 사용 언어 : Node.js 6588번: 골드바흐의 추측 각 테스트 케이스에 대해서, n = a + b 형태로 출력한다. 이때, a와 b는 홀수 소수이다. 숫자와 연산자는 공백 하나로 구분되어져 있다. 만약, n을 만들 수 있는 방법이 여러 가지라면, b-a가 가장 큰 www.acmicpc.net 1742년, 독일의 아마추어 수학가 크리스티안 골드바흐는 레온하르트 오일러에게 다음과 같은 추측을 제안하는 편지를 보냈다. 4보다 큰 모든 짝수는 두 홀수 소수의 합으로 나타낼 수 있다. 예를 들어 8은 $ 3 + 5 $로 나타낼 수 있고, 3과 5는 모두 홀수인 소수이다. 또, $ 20 = 3..

소수

이번 포스트에서는 소수(Prime number)에 대해 알아보도록 하겠습니다. 1. 소수란? 소수는 약수가 1과 자신 이외에는 없는 자연수를 나타냅니다. 때문에 자연수 $ N $이 소수가 되려면 2보다 크거나 같고 $ N-1 $ 보다 작거나 같은 자연수 중 나누어 나머지가 0이 되는 수가 존재해서는 안됩니다. 2. 소수 구하기 (1) Loop 가장 먼저 떠올릴 수 있는 방법은 2부터 $ N-1 $까지 순차적으로 확인 해 보는 방법이 있습니다. function isPrime(number) { if (number < 2) return false; for (let i = 2; i < number; i++) { if (number % i === 0) return false; } return true; } 이 함..

최대공약수와 최소공배수

이번 포스트에서는 최대공약수와 최대공배수에 대해서 알아보겠습니다. 1. 최대공약수란? 최대 공약수 (Greatest Common Divisor)란 두 수, 혹은 그 이상의 여러 수의 공통인 약수 (공약수) 중 가장 큰수를 의미 하며 수학 기호로 $ GCM(a,b) $와 같이 표현 합니다. 만일 $ GCD(a,b) = 1 $인 경우 두 수 a, b는 서로소 (Relatively prime, Coprime)라고 합니다. 2. 최대공약수 구하기 2부터 $ min(a, b) $ 까지 모든 정수로 나누어 보기 function getGCD(a, b) { const large = a > b ? a : b; const small = a > b ? a : b; let gcd = 1; for (let i = 2; i

재귀 (2) : 미래의 나야, 부탁해~

이번 포스트에서는 미래의 내가 풀어주는 재귀의 마법 같은 힘에 대해 알아보겠습니다. 1. 재귀의 카테고리 재귀에 관련된 문제를 풀이하다보면 해당 문제들이 비슷한 패턴을 띄고 있는 것을 발견할 수 있습니다. 그 패턴에 대해 알아보며 비슷한 문제를 발견 했을때 해결할 수 있는 힘을 길러 보겠습니다. (1) 패턴 1 - 반복 실행 반복적으로 하나의 작업을 실행하는 카테고리 입니다. 기저 조건을 가지고 단순히 하나의 작업을 기저 조건을 만족 할 때까지 반복 합니다. 이전 포스트에서 다뤘던 CountDown 함수가 그러 합니다. function countdown(number) { if (number < 0) return; console.log(number); countdown(number - 1); } 만일 배열..

나머지 연산

이번 포스트에서는 나머지 연산 ( Modular arithmetic )에 대해서 알아보겠습니다. 1. 나머지 연산 ( Modular arithmetic )이란? 양의 정수 제수 $ b $(Divider)와 임의의 정수 피제수 $ a $(Dividend)에 대해, $ a = bq + r $을 만족시키는 유일한 정수 $ q $와 $ 0

[boj] 1158. 요세푸스 문제

[boj] 1158. 요세푸스 문제 문제 링크 : https://www.acmicpc.net/problem/1158 사용 언어 : Node.js 1158번: 요세푸스 문제 첫째 줄에 N과 K가 빈 칸을 사이에 두고 순서대로 주어진다. (1 ≤ K ≤ N ≤ 5,000) www.acmicpc.net 요세푸스 문제는 다음과 같다. 1번부터 N번까지 N명의 사람이 원을 이루면서 앉아있고, 양의 정수 K(≤ N)가 주어진다. 이제 순서대로 K번째 사람을 제거한다. 한 사람이 제거되면 남은 사람들로 이루어진 원을 따라 이 과정을 계속해 나간다. 이 과정은 N명의 사람이 모두 제거될 때까지 계속된다. 원에서 사람들이 제거되는 순서를 (N, K)-요세푸스 순열이라고 한다. 예를 들어 (7, 3)-요세푸스 순열은 이다..

재귀 (1) : Call me

오늘은 컴퓨터 과학에서의 재귀의 개념에 대해서 알아보도록 하겠습니다. 1. 재귀 ( Recursion )란? 재귀란 무엇일까요? 여기 너무나도 명확하게 답해줄 수 있는 예시가 있습니다. function foo() { foo(); } 이와같이 재귀란 함수가 자기 자신을 재호출하는 로직을 뜻하는 용어입니다. 다른 예를 하나 더 볼까요? function CountDown(number) { for(let i=number; 0 5는 기저 조건이 아니기에 $ Factorial(4) $를 호출합니다. $ Factorial(4) $가 호출 되었을 때 => 4는 기저 조건이 아니기에 $ Factorial(3) $를 호출합니다. ... $ Factorial(1) $가 호출 되었을 때 => 1은 기저 조건이기에 반환합니다...

스택과 큐 - 제약을 통한 문제 해결 전략

이번 포스팅에서 효율성 보다 코드의 간결함에 중점을 둔 자료구조에 대해 알아보겠습니다. 스택과 큐는 임시데이터를 처리할 수 있는 도구입니다. 임시데이터란 사용 후에는 의미 없는 데이터로서 제거해도 무관합니다. 스택과 큐는 임시데이터를 처리하며 주로 처리 "순서"에 중점을 둡니다. 1. 스택 ( Stack )이란? 스택이 데이터를 저장하는 방법은 배열과 같습니다. 다만 몇 가지의 제약 사항을 가지고 있습니다. 데이터는 스택의 끝에만 삽입 가능 => push 데이터를 스택의 끝에서만 삭제 가능 => pop 마지막 원소( Top )만 읽기가 가능 => peek 스택의 연산은 보통 두 문장으로 LIFO ( Last-In, First-Out / 후입선출 )으로 표현합니다. 항상 삽입된 마지막 항목이 첫 번째로 출..