하루 알고리즘(JS)

https://www.acmicpc.net/problem/24267 코드 const input = require('fs').readFileSync(process.platform === "linux" ? "/dev/stdin" : "./input.txt").toString().trim(); const result = ( BigInt(input) * BigInt(input - 1) * BigInt(input - 2) ) / BigInt(6); console.log(`${result}\n${3}`); 문제 설명 문제는 주어진 MenOfPassion 알고리즘에 대한 수행 시간을 분석하고, 그 결과를 특정 형식으로 출력하는 문제인데요. MenOfPassion 알고리즘은 세 개의 중첩된 for 반복문을 사용하여 특..

https://www.acmicpc.net/problem/24266 24266번: 알고리즘 수업 - 알고리즘의 수행 시간 5 오늘도 서준이는 알고리즘의 수행시간 수업 조교를 하고 있다. 아빠가 수업한 내용을 학생들이 잘 이해했는지 문제를 통해서 확인해보자. 입력의 크기 n이 주어지면 MenOfPassion 알고리즘 수행 시 www.acmicpc.net 코드 function menOfPassionAlgorithmPerformance(n) { // n을 BigInt로 변환 const bigN = BigInt(n); // BigInt를 사용하여 n^3 계산 const result = bigN ** BigInt(3); console.log(result.toString()); // 코드1의 수행 횟수를 문자열로 ..

https://www.acmicpc.net/problem/24265 24265번: 알고리즘 수업 - 알고리즘의 수행 시간 4 오늘도 서준이는 알고리즘의 수행시간 수업 조교를 하고 있다. 아빠가 수업한 내용을 학생들이 잘 이해했는지 문제를 통해서 확인해보자. 입력의 크기 n이 주어지면 MenOfPassion 알고리즘 수행 시 www.acmicpc.net 코드 function menOfPassionAlgorithmPerformance(n) { // 코드1의 수행 횟수, n(n-1)/2번 console.log((n * (n - 1)) / 2); // 코드1의 수행 횟수를 다항식으로 나타냈을 때, 최고차항의 차수는 2 console.log(2); } const readline = require('node:rea..

https://www.acmicpc.net/problem/24264 24264번: 알고리즘 수업 - 알고리즘의 수행 시간 3 오늘도 서준이는 알고리즘의 수행시간 수업 조교를 하고 있다. 아빠가 수업한 내용을 학생들이 잘 이해했는지 문제를 통해서 확인해보자. 입력의 크기 n이 주어지면 MenOfPassion 알고리즘 수행 시 www.acmicpc.net 코드 function menOfPassionAlgorithmPerformance(n) { console.log(n * n); // 코드1의 수행 횟수, n^2번 console.log(2); // 코드1의 수행 횟수를 다항식으로 나타냈을 때, 최고차항의 차수는 2 } const readline = require('node:readline'); const rl..

https://www.acmicpc.net/problem/24263 24263번: 알고리즘 수업 - 알고리즘의 수행 시간 2 오늘도 서준이는 알고리즘의 수행시간 수업 조교를 하고 있다. 아빠가 수업한 내용을 학생들이 잘 이해했는지 문제를 통해서 확인해보자. 입력의 크기 n이 주어지면 MenOfPassion 알고리즘 수행 시 www.acmicpc.net 코드 function menOfPassionAlgorithmPerformance(n) { console.log(n); // 코드1의 수행 횟수, n번 console.log(1); // 코드1의 수행 횟수를 다항식으로 나타냈을 때, 최고차항의 차수는 1 } const readline = require('node:readline') const rl = read..

https://www.acmicpc.net/problem/24262 24262번: 알고리즘 수업 - 알고리즘의 수행 시간 1 오늘도 서준이는 알고리즘의 수행시간 수업 조교를 하고 있다. 아빠가 수업한 내용을 학생들이 잘 이해했는지 문제를 통해서 확인해보자. 입력의 크기 n이 주어지면 MenOfPassion 알고리즘 수행 시 www.acmicpc.net 코드 function menOfPassionAlgorithmPerformance(n) { console.log(1); // 코드1의 수행 횟수는 항상 1 console.log(0); // 코드1의 수행 횟수를 다항식으로 나타냈을 때, 최고차항의 차수는 0 } // 예제 입력 menOfPassionAlgorithmPerformance(1); 풀이 설명 이 문..

Rabin-Karp? Rabin-Karp 알고리즘은 문자열 매칭 알고리즘 중 하나로, 주어진 문자열에서 패턴 문자열을 찾는데 사용되는데 문자열을 해시값으로 변환하여 패턴 문자열의 해시값과 일치하는 부분을 찾아내는 방법을 사용해요. 그럼 구현 해볼까요? 코드 구현 function RabinKarp(text, pattern) { const n = text.length; const m = pattern.length; const base = 26; // 사용할 기수 const prime = 101; // 사용할 소수 // 패턴 문자열과 전체 문자열의 해시값을 계산합니다. let patternHash = 0; let textHash = 0; let power = 1; for (let i = 0; i < m; i+..

Knuth-Morris-Pratt? Knuth-Morris-Pratt 알고리즘은 문자열 검색 알고리즘 중 하나로, 특정 문자열에서 패턴 문자열을 찾는 알고리즘이에요. 이 알고리즘은 패턴 문자열의 길이와 검색 문자열의 길이에 비례하는 시간복잡도를 가져서 대용량의 문자열에서 효율적으로 검색할 수 있죠. 동작 방식 패턴 문자열을 전처리하여 접두사(prefix)와 접미사(suffix)의 최대길이를 구해요. 검색 문자열을 순회하며 패턴 문자열을 비교해요. 만약 일치하지 않는 문자가 있다면, 해당 문자가 포함된 접미사와 접두사를 이용하여 패턴 문자열을 이동시켜요. 이동한 패턴 문자열과 검색 문자열을 다시 비교해줘요. 일치하지 않는 문자가 없을 때까지 위 과정을 반복해요. 그럼 이제 구현해볼까요? 코드 구현 func..

Open addressing? Open addressing은 충돌이 발생하면 해시 테이블 내의 다른 빈 슬롯에 데이터를 저장하는 기법인데요. Open Addressing 방식에서는 해시 충돌이 발생했을 때, 선형 탐사, 제곱 탐사, 이중 해싱 방법으로 충돌을 해결하는데요. 이것들에 대해 알아보자면 Linear Probing (선형 탐사) 해시 충돌이 발생하면, 다음 인덱스를 탐사하며 빈 공간을 찾아요. 탐사하는 인덱스는 hash(key) + i (i는 0, 1, 2, ...)와 같이 계산하죠. Quadratic Probing (제곱 탐사) 선형 탐사의 단점을 보완하기 위해, 제곱 값을 이용해 탐사하는 방법인데 탐사하는 인덱스는 hash(key) + i^2 (i는 0, 1, 2, ...)와 같이 계산해요...