전체 글

[CS] 해시(Hash)와 해시 충돌 해결 방법

해시(Hash) 데이터를 효율적으로 관리하기 위해 임의의 길이 데이터를 고정된 길이의 데이터로 매핑 해시 함수: 데이터를 효율적으로 관리하기 위해 임의의 길이의 데이터를 수학적 연산을 통해 고정된 길이의 데이터로 매핑하는 함수이다. 해시 함수에 의해 얻어지는 값을 해시 코드, 해시라고 한다. 해시 테이블: 키와 값을 매핑해둔 데이터 구조이다. 해시 함수로 얻은 해시를 키로 활용하여 index로 사용하고 해당 index에 데이터를 저장하여 효율적인 검색을 위해 사용된다. 해시 순서 해당 원소의 해시 함수를 이용하여 해시값을 얻는다. 해시값을 주소로 하는 위치에 원소를 저장한다. 저장 후 검색 시에도 원소의 해시값으로 계산하여 해당 위치로 이동한다. 추상 자료형 사전구조 인터페이스와 기능 구현을 분리한 자료..

[CS] 프로세스와 스레드

프로세스(Process) 메모리에 적재되고 CPU 자원을 할당받아 프로그램이 실행되고 있는 상태 프로세스는 Code, Data, Stack, Heap 영역의 네가지 구조로 되어있다. 코드 영역(code area) : 프로그래머가 작성한 프로그램이 코드 영역에 작성된다. 데이터 영역(data area) : 코드가 실행되면서 사용한 변수나 파일들의 각종 데이터들이 모여있다. 스택 영역(stack area) : 호출한 함수가 종료되면 되돌아올 메모리의 주소를 스택에 저장하거나 변수 사용 범위에 영향을 미치는 영역을 구현 할때 사용된다. 힙 영역(heap area) : 동적으로 할당되는 데이터들을 위해 존재하는 공간이다. 서로 다른 프로세스간의 메모리 공간 접근은 허용되지 않는다. 운영체제 관점에서는 프로세스가..

[백준 16953] A → B

https://www.acmicpc.net/problem/16953 16953번: A → B 첫째 줄에 A, B (1 ≤ A < B ≤ 109)가 주어진다. www.acmicpc.net B에서 A로 찾아나가는 식으로 해결하면 간단하다 let [A,B] = require('fs').readFileSync('/dev/stdin').toString().trim().split(' ').map(Number) let cnt = 1; // 연산횟수 카운트 (문제내용상 1부터 카운트) while(A

[백준 13305] 주유소 / Node.js / 그리디 알고리즘 기초

https://www.acmicpc.net/problem/13305 13305번: 주유소 표준 입력으로 다음 정보가 주어진다. 첫 번째 줄에는 도시의 개수를 나타내는 정수 N(2 ≤ N ≤ 100,000)이 주어진다. 다음 줄에는 인접한 두 도시를 연결하는 도로의 길이가 제일 왼쪽 도로부터 N-1 www.acmicpc.net 문제 지문이 길어도 요점을 이해하는 것이 중요 1. 기름값이 저렴한지 비교한다. 2. 더 저렴한 주유소까지만 갈 수 있는 기름만 주유하고 이동한다. 본 문제에선 단위의 값이 크므로 BigInt를 사용하여야 한다. const input = require('fs').readFileSync('/dev/stdin') .toString().trim() .split('\n') .map((v)=..

[백준 11047] 동전0 / Node.js / 그리디 알고리즘 기초

https://www.acmicpc.net/problem/11047 11047번: 동전 0 첫째 줄에 N과 K가 주어진다. (1 ≤ N ≤ 10, 1 ≤ K ≤ 100,000,000) 둘째 줄부터 N개의 줄에 동전의 가치 Ai가 오름차순으로 주어진다. (1 ≤ Ai ≤ 1,000,000, A1 = 1, i ≥ 2인 경우에 Ai는 Ai-1의 배수) www.acmicpc.net 문제를 풀 수 있는 방법은 다양하지만 가장 효율적이고 쉬운 방법을 찾자 let [I,...input] = require('fs').readFileSync('/dev/stdin').toString().trim().split('\n') let K = +I.split(' ')[1] let coins = input.map(Number).so..

[백준 1931] 회의실 배정 / Node.js

https://www.acmicpc.net/problem/1931 1931번: 회의실 배정 (1,4), (5,7), (8,11), (12,14) 를 이용할 수 있다. www.acmicpc.net 그리디 알고리즘(Greedy Algorithm, 탐욕 알고리즘) 매 상황에서 최선의 선택을 하는 알고리즘을 의미 알고리즘 문제를 풀기 위한 최적의 아이디어를 떠올릴 수 있는 능력을 요구한다 본 문제에선 시작 시간이 빨라도 끝나는 시간이 너무 늦어버리면 다음 회의를 하지 못하는 경우가 생길 수 있다. => 최대한 회의실을 사용하기 위해서는 끝나는 시간이 빨라야 한다. 주의사항으로 회의실을 이용하는 시간은 겹칠 수 없다는 점도 유의한다. 또한, 끝나는 시간이 같을 경우에는 일찍 시작을 해야 최대한 더 많이 이용을 할..

[Javascript] 자료구조 (Data Structure)

자료구조란 데이터 값들을 저장하거나 조직하는 방법. 각 원소들이 논리적으로 정의된 규칙에 의해 나열되며 자료에 대한 처리를 효율적으로 수행할 수 있도록 자료를 구분하여 표현한 것. 연산에 사용되는 컴퓨터의 메모리 자원은 매우 한정적인데 반해 처리해야 할 데이터는 무수히 많을 수 있다. 따라서 이 메모리 공간을 효율적으로 사용해야 하는데 필요한 것이 자료 구조이다. 효율적인 자료 구조의 선택 → 효율적인 알고리즘의 선택이 된다. 1) 단순 구조(Primitive Data Structure) 프로그래밍에서 사용되는 기본 데이터 타입 Javascript에는 6개의 원시 타입(Number, String, Boolean, null, undefined, Symbol)이 있다. (Symbol - ES6 버전의 Jav..

[Javascript] Lazy evaluation(지연 평가)

컴퓨터 프로그래밍에서 Lazy evaluation은 계산의 결과 값이 필요할 때까지 계산을 늦추는 기법. Javascript에서는 배열 데이터 구조를 많이 쓰는데, 연산의 성능을 끌어올리기 위해 필요한 기법 중 하나이다. 예시 1. 엄격한 평가 Array(100000).fill().map((v, i) => i) .map((v) => v + 1) .filter((v) => v % 3 === 0) .slice(0, 10); //[ 3, 6, 9, 12, 15, 18, 21, 24, 27, 30 ] 0부터 10만까지의 숫자가 담긴 배열 각각의 요소에 1씩을 더해서 3의 배수가 되는 숫자 10개만 추리는 코드. map에서 10만 filter에서 10만 slice에서 10해서 총 200010번의 연산을 해야한다...

[Javascript] Generator Function

단 한 번의 실행으로 함수의 끝까지 실행이 완료되는 일반 함수와는 달리, 제너레이터 함수는 사용자의 요구에 따라 (yield와 next를 통해) 일시적으로 정지될 수도 있고, 다시 시작될 수도 있다. 또한, 제너레이터 함수의 반환으로는 제너레이터가 반환된다. Generator / yield Generator는 이 제너레이터 함수의 반환으로 iterable 프로토콜과 iterator 프로토콜을 따르는 객체이다. 이 때, 제너레이터의 이터러블에서 반환하는 이터레이터는 자기 자신이다. function* generator(params) { yield 'hello'; yield 'world'; // statements return 'hi'; } const resultGenerator = generator(); c..

[Javascript] 커링(Currying)이란

수학과 컴퓨터 과학에서 커링(currying)이란 다중 인수 (혹은 여러 인수의 튜플)을 갖는 함수를 단일 인수를 갖는 함수들의 함수열로 바꾸는 것을 말한다. 커링의 사용 예시 커리 함수는 '함수를 매개 변수로' 받는다. 커리 함수는 실행 시점에 매개 변수로 받은 함수의 인자를 사용하는 함수를 다시 반환한다. 반환되는 함수는 Lexical scope 개념에 의해 커리 함수에 전달된 함수를 기억한다.(= 클로저) Step 1. 커링 대상 함수 선언 커링 대상 함수인 sum은 매개 변수로 num1, num2 두 개를 받는다. function sum(num1, num2) { return num1 + num2; } console.log(sum(10, 20)); // 30 Step 2. 커링 함수 선언 커리 함수..