하루 알고리즘(JS)

[바미] 알고리즘 수업 - 알고리즘의 수행 시간 3

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..

알고리즘 수업 - 알고리즘의 수행 시간 2

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..

[바미] 알고리즘 수업 - 알고리즘의 수행 시간 1

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); 풀이 설명 이 문..

[바미] Pattern matching algorithms - Rabin-Karp 알고리즘 구현하기

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+..

[바미] Pattern matching algorithms - Knuth-Morris-Pratt 알고리즘 구현하기.

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

[바미] Hash tables - Open addressing알고리즘 구현하기

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, ...)와 같이 계산해요...

[바미] Hash tables - chaining 알고리즘 구현하기.

chaining? 해시 테이블에서 충돌이 일어나면 chaining 알고리즘을 사용하여 충돌을 해결할 수 있는데, 이 알고리즘은 연결 리스트 를 사용하여 충돌된 데이터를 저장합니다. Chaining을 구현하기 위해서는 먼저 해시 테이블과 연결 리스트가 필요합니다. 해시 테이블은 키-값 쌍을 저장하는 자료구조로, 키를 해시 함수에 입력하여 버킷 인덱스를 계산하고, 해당 버킷에 값을 저장합니다. 연결 리스트는 각 버킷에 저장되는 데이터를 연결하여 저장하는 자료구조입니다. 코드 구현 해시 함수 구현 해시 함수는 키 값을 버킷 인덱스로 변환하는 함수입니다. 이번 예제에서는 간단한 해시 함수를 구현하여 사용해보겠습니다. function hashFunction(key, size) { let hash = 0; for ..

[바미] Tree algorithms - Trie trees 구현하기.

Trie tree? Trie tree는 문자열 검색을 효율적으로 수행하기 위한 트리 자료구조입니다. 이진 트리와는 달리 한 노드당 여러 개의 자식 노드를 가지며, 각 자식 노드는 해당 위치에 올 수 있는 문자를 나타내는 것이 특징이죠. 코드 구현 class TrieNode { constructor() { this.children = {}; this.isEndOfWord = false; } } class Trie { constructor() { this.root = new TrieNode(); } insert(word) { let current = this.root; for (let i = 0; i < word.length; i++) { let ch = word.charAt(i); let node = cu..

[바미] Dynamic programming - LIS 알고리즘 구현하기

LIS알고리즘? Longest Increasing Subsequence (LIS) 알고리즘은 어떤 수열에서 가장 긴 증가하는 부분 수열을 찾는 알고리즘을 말하는데요. 예를 들어, 수열 [3, 1, 5, 2, 4, 9]에서 LIS는 [1, 2, 4, 9]이 되죠. LIS 알고리즘은 동적 프로그래밍 기법을 사용하여 해결할 수 있는데 문제를 해결하기 위해 각 요소에 대한 최장 증가 수열의 길이를 계산하고, 최종적으로 이들 중 최대 값을 찾아주죠. 먼저 Bottom-up 방식으로 LIS 알고리즘을 구현해 보겠습니다. 이 방식에서는 DP table을 채우기 위해 이전 값들을 사용하는 방식으로 구현됩니다. Bottom-up 방식 코드 구현 function longestIncreasingSubsequence(nums..