⇒ PriorityQueue는 스레드 안전을 제공하므로 멀티스레딩 환경에서 유용하지만, 단일 스레드 환경에서는 heapq가 더 간편하다.
문제 풀이
JS로도 풀어보고 싶었지만 JS에는 heap 모듈이 따로 없고 코테 외에서는 라이브러리를 사용할 수 있다.
더 맵게
파이썬 풀이
# 스코빌 섞을 수 없는 경우: 길이가 2보다 짧을 시 -1import heapq
def solution(scoville, K):
heapq.heapify(scoville)
mix_count = 0while scoville[0] < K:
if len(scoville) < 2:
return -1
first = heapq.heappop(scoville)
second = heapq.heappop(scoville)
new_food = (first + second * 2)
heapq.heappush(scoville, new_food)
mix_count += 1return mix_count
자바스크립트 풀이⇒ 이 코드는 모든 테스트 케이스를 통과하지만 효율성에서 걸린 코드이다.
functionsolution(scoville, K) {
scoville.sort((a, b) => b - a);
let mix_count = 0;
while (scoville.at(-1) < K) {
if (scoville.length < 2) return -1;
let first = scoville.pop();
let second = scoville.pop();
let new_food = first + second * 2;
scoville.push(new_food);
scoville.sort((a, b) => b - a);
mix_count++;
}
return mix_count;
}
해시는 해시 함수를 사용해서 변환한 값을 인덱스로 삼아 키와 값을 저장해서 빠른 데이터 탐색을 제공하는 자료구조이다.
보통은 인덱스를 활용해서 탐색을 빠르게 만들지만 해시는 키를 사용해 데이터 탐색을 빠르게 한다.
해시는 키와 데이터를 일대일 대응하여 저장하므로 키를 통해 데이터에 바로 접근할 수 있다. 사람에게는 숫자로 데이터를 관리하는 배열보다 조금 더 접근성이 좋은 자료구조이다.
키워드
값
최종적으로 얻고자 하는 정보
키
값을 검색하기 위해 활용하는 정보
해시 함수
키를 이용해 해시값 또는 인덱스로 변환하는 함수
해시의 특징
해시는 단방향으로 동작한다.
키를 통해 값을 찾을 수 있지만 값을 통해 키를 찾을 수는 없다.
단방향으로만 동작하는 해시의 특성은 외부에 정보를 안전하게 제공한다는 특징이 있어 네트워크 보안에서 많이 활용된다.
찾고자 하는 값을 O(1)에서 바로 찾을 수 있다.
키 자체가 해시 함수에 의해 값이 있는 인덱스가 되므로 값을 찾기 위한 탐색 과정이 필요 없다.
값을 인덱스로 활용하려면 적절한 변환 과정을 거쳐야 한다.
해시 분야
해시는 단방향으로만 검색할 수 있는 대신 빠르게 원하는 값을 검색할 수 있다.
그래서 해시는 데이터를 저장하고 검색하거나 보안이 필요할 때 활용된다.
비밀번호 관리
해시 함수를 활용해 해싱한 비밀번호를 저장한다. 비밀번호가 맞는지 확인할 때도 마찬가지이다.
데이터베이스 인덱싱
데이터베이스에 저장된 데이터를 효율적으로 검색할 때 해시를 활용한다.
블록체인
블록체인에서 해시 함수는 핵심 역할을 한다. 각 블록은 이전 블록의 해시값을 포함하고 있으며, 이를 통해 데이터 무결성을 확인할 수 있다.
해시 구현
해시 함수가 변환한 값은 인덱스로 활용해야 하므로 해시 테이블의 크기를 넘으면 안 된다.
해시 함수가 변환한 값의 충돌은 최대한 적게 발생해야 한다.
충돌 : 서로 다른 두 키에 대해 해싱 함수를 적용한 결과과 동일한 것을 의미
자주 사용하는 해시 함수
나눗셈법
가장 떠올리기 쉬운 단순한 해시 함수
나눗셈법 : 키를 소수로 나눈 나머지를 활용
h(x) = x mod k
위와 같이 계산하는 경우 자연스레 나눗셈법의 해시 테이블 크기는 K가 된다. 왜냐하면 K에 대해 모듈러 연산을 했을 때 나올수 있는 값은 0 ~ 9(K - 1)이기 때문이다.
곱셈법
나눗셈법과 비슷하게 모듈러 연산을 활용하지만 소수는 활용하지 않는다.
황금비를 사용한다.
h(x) = (((x * A) mod 1) * m
m은 최대 버킷의 개수, A는 황금비이다.
문자열 해싱
키의 자료형이 문자열일 때도 사용할 수 있는 해시 함수인 문자열 해싱
문자열 해싱은 문자열의 문자를 숫자로 변환하고 이 숫자들을 다항식의 값으로 변환해서 해싱한다.
hash(s) = (s[0] + s[1] * p + s[2] * p^2 + … + s[n-1] * p^n-1) mod m
p는 31이고, m은 해시 테이블의 최대 크기이다.
p를 31로 정한 이유는 홀수이면서 메르센 소수이기 때문이다.
메르센 소수는 해시에서 충돌을 줄이는데 효과적이라는 연구 결과가 있다.
해시 함수 적용시 중요한 점
해시 함수를 적용한 값이 해시테이블 크기에 비해 너무 클 수 있다는 점.
그래서 해시 함수가 내는 결과의 크기를 해시 테이블 크기에 맞도록 하는 작업이 필요하다.
hash(s) = (s[0] % m + s[1] * p % m + s[2] * p^2 % m + … + s[n-1] * p^n-1 % m) mod m
위처럼 중간 중간 모듈러 연산을 해 더한 값을 모듈러 연산하면 오버플로우를 최대한 방지할 수 있다.
충돌처리
서로 다른 키에 대해서 해시 함수의 결괏값이 같으면 충돌이라고 한다. 하나의 버킷에 2개의 값을 넣을 수는 없으므로 해시 테이블을 관리할 때는 반드시 충돌 처리를 해야 한다.
체이닝으로 처리하기
해싱한 값이 같은 경우 충돌을 해결하는 간단한 방법
체이닝은 충돌 발생 시 해당 버킷에 연결 리스트로 같은 해시값을 가지는 데이터를 연결한다.
충돌이 많아지면 그만큼 연결 리스트의 길이가 길어지고 다른 해시 테이블의 공간은 덜 사용하므로 공간 활용성이 떨어진다.
충돌이 많으면 연결 리스트 자체의 한계 때문에 검색 성능이 떨어진다. 연결리스트는 맨 앞의 데이터부터 검색해야 하기 때문
개방 주소법으로 처리하기
체이닝에서 연결 리스트로 충돌값을 연결한 것과 다르게 빈 버킷을 찾아 충돌값을 삽입한다.해시 테이블을 최대한 활용하므로 체이닝보다 메모리를 더 효율적으로 사용할 수 있다.
선형 탐사 방식
선형 탐사 방식은 충돌이 발생하면 다른 빈 버킷을 찾을 때까지 일정한 간격으로 이동한다.
h(k, i) = (h(k) + i) mod m
m은 수용할 수 있는 최대 버킷. 선형 탐사 시 테이블의 범위를 넘으면 안 되므로 모듈러 연산을 적용한 것.
이중 해싱 방식
말 그대로 해시 함수를 2개 사용하는 방식
해시 함수를 N개로 늘리기도 한다.
두번째 해시 함수의 역할은 첫번째 해시 함수로 충돌이 발생하면 해당 위치를 기준으로 어떻게 위치를 정할 지 결정하는 역할을 한다.
JS에서의 해시
자바스크립트에서는 주로 Map을 사용하여 객체를 생성해 해시 테이블을 만든다.
// 맵 객체 생성 let hash = new Map(); // 객체에 키:값을 삽입 hash.set("key1", 1234); hash.set("key2", "hi"); // 객체에 삽입된 값을 가져오는 법 console.log(hash.get("key1")); //1234 console.log(hash.keys()); //{"key1", "key2"} console.log(hash.values()); //{1234, "hi"} // 객체의 값을 모두 삭제 hash.clear(); // 객체의 특정 값 삭제 hash.delete("key1");
해시 문제 풀이
1. 폰켓몬
해시 카테고리에 있는 문제임은 알았으나 아직 자바스크립트로 해시를 구현한다는 것이 잘 감이 잡히지 않아 지금까지 풀어왔던 것처럼 단순하게 풀어봤다. 문제를 읽어보니 결론적으로 필요한 것은 N/2의 값인 것 같아 num으로 값을 미리 구한 후, 중복 된 값을 모두 없애버린 answer에서 if문으로 상황에 따른 처리를 해주었다. 풀이 후에 Set()과 해시 테이블 코드가 결국 비슷하게 돌아간다고 생각해서 찾아보니 둘은 기본적으로 다른 개념이지만 실제 구현에서는 해시 테이블을 기반으로 한 Set을 많이 사용하게 되므로 이를 Hast Set이라고 부르기도 한다는 것을 알았다.
function solution(nums) {
var answer = [...newSet(nums)];
let num = nums.length / 2;
if (num > answer.length) {
return answer.length;
} else {
return num;
}
return answer;
}
2. 해시 알고리즘을 이해하고 싶어서 다른 분의 풀이를 참고했다. 그리고 이 코드를 이해하면서 대충 이해했다. nums에 들어온 각 값들이 해시테이블에 존재하지 않는다면 우선 넣고, 존재할 때마다 해당 포켓몬의 수를 하나씩 늘리는 것.
functionsolution(nums) {
let answer = 0;
let bag = newMap();
nums.forEach((monster) => {
if(bag.get(monster)) bag.set(monster, bag.get(monster) + 1);
else bag.set(monster, 1);
});
if (bag.size < nums.length / 2) answer = bag.size;
else answer = nums.length / 2;
return answer;
}
3. 파이썬도 어느 정도 함께 이해하고 싶어서 파이썬 코드로도 풀이해보았다. 파이썬도 set 으로 중복을 없앨 수 있고, 다시 배열 형태로 사용하고 싶다면 list()안에 넣어서 사용해야 한다.
defsolution(nums):
num = len(nums) // 2
answer = list(set(nums))
returnlen(answer) if num > len(answer) else num
2. 완주하지 못한 선수
해시 코드
function solution(participant, completion) {
var answer = new Map();
for (let i = 0; i < participant.length; i++) {
if (answer.get(participant[i])) {
answer.set(participant[i], answer.get(participant[i]) + 1);
} else {
answer.set(participant[i], 1);
}
}
for (let i = 0; i < completion.length; i++) {
if (answer.get(completion[i])) {
answer.set(completion[i], answer.get(completion[i]) - 1);
}
}
for (let [key, value] of answer) {
if (value > 0) {
return key;
}
}
}
해시 쓴다고 쓴건데 다른 사람들 코드 보면서 빨리 이 길을 접어야 하나 진지하게 고민할 정도의 코드가 나온 것 같다 ^_^
2. 둘러보던 중 가장 마음에 들었던 코드
내가 작성한 첫번째 for문을 forEach로 바꿔서 각 배열에 쉽게 접근하고 if 문 대신 or의 경우 왼쪽의 값이 false이면 오른쪽 값이 된다는 것을 이용해 이름이 있는 경우 기존 값 + 1, 없는 경우 0 + 1이 되어 1로 세팅된다.
두번째 for문 대신 find() 메소드를 사용해 completion 배열 안에 이름이 있다면 값을 줄이고 없는 경우 해당 인덱스의 사람 이름을 return 한다.
defsolution(participant, completion):par = sorted(participant)com = sorted(completion)fori in range(len(com)):ifpar[i] != com[i]:returnpar[i]returnpar[-1]
js 답변들 둘러보다보니 정렬 후 다르거나 마지막 사람이 미완주자가 되는 것을 이용해서 풀이한 코드가 많아서 그대로 파이썬에 적용했다.
3. 전화번호 목록
해시를 사용하지 않고 정렬과 startsWith 메소드를 사용해서 풀이한 방법.
예시로 나온 phone_book의 element들이 ["119", "97674223", "1195524421"] 라고 가정하는 경우 접두사가 되는 요소는 접두사가 포함되는 요소보다 짧을 것이고, sort로 정렬하면 비슷한 요소들이 가깝게 정렬이 될 테니 정렬 후에 근처에 있는 요소를 확인하면 된다.
function solution(phone_book) { phone_book.sort(); for (let i = 0; i < phone_book.length - 1; i++) { if (phone_book[i + 1].startsWith(phone_book[i])) { return false; } } return true; }
해시를 사용해 풀이하는 방법
해시 사용 방법을 통한 풀이를 제대로 이해 못해서 추후 수정 예정
파이썬 코드
파이썬에도 startswith 메소드가 있다는 점!
defsolution(phone_book):
sorted_arr = sorted(phone_book)
for i inrange(len(sorted_arr) - 1):
if sorted_arr[i + 1].startswith(sorted_arr[i]):
returnFalsereturnTrue
1번 풀이를 파이썬으로 똑같은 방식을 사용해 풀이한 과정이다.
이건 파이썬 해시를 사용한 다른 분의 코드이다.
defsolution(phone_book):answer = Truehash_map = {}forphone_number in phone_book:hash_map[phone_number] = 1forphone_number in phone_book:temp = ""fornumber in phone_number:temp+= numberiftemp in hash_map and temp != phone_number:answer = Falsereturnanswer
우선 hash 사용을 위해 hash 객체 하나를 생성한다. phone_book에 주어진 번호를 도는 동안 hash_map에 키로 저장하고 값을 1로 할당한다. 그리고 안에 있는 값을 바로 하나씩 꺼내어서 사용할 것이다. 우선 temp 변수를 초기화한다. 각 번호 묶음의 번호 한 자리씩을 꺼내어 temp에 저장한다. 만약 temp가 hash_map에 존재하면서 temp가 phone_number은 아니라면 전체 전화번호와는 동일하지 않다는 뜻이므로 다른 번호의 접두사가 된다는 의미이다.
애플리케이션이 커짐에 따라 상태가 어떻게 구성되고 구성 요소 간에 데이터가 어떻게 흐르는 지에 대해 더 의도적으로 생각하는 것은 도움이 된다.
중복되거나 중복된 상태는 버그의 일반적인 원인이다.
Redux
리덕스는 자바스크립트 애플리케이션에서 상태 관리를 간편하게 하기 위해 사용하는 대표적인 라이브러리 중 하나이다. 특히, 리액트와 함께 자주 사용되지만 리덕스는 리액트에 한정되지 않고 모든 자바스크립트 애플리케이션에서 사용할 수 있다.
리덕스의 핵심 개념
스토어
애플리케이션의 상태를 담고 있는 객체이다. 스토어는 단 하나만 존재하며, 이 곳에 애플리케이션의 모든 상태가 저장된다.
액션
상태를 변화시키기 위한 의도를 나타내는 객체이다. 액션은 ‘type’ 이라는 속성을 필수적으로 가져야 하며, 이 외에도 상태 변화를 위한 추가 데이터를 포함할 수 있다.
리듀서
액션을 받아 상태를 업데이트하는 함수이다. 이전 상태와 액션을 인자로 받아 새로운 상태를 반환하는 순수 함수이다.
디스패치
액션을 스토어에 전달하는 함수이다. 디스패치된 액션은 리듀서를 통해 상태를 업데이트되게 한다.
구독
상태가 변경될 때마다 특정 동작을 실행하도록하는 함수이다. 리덕스는 상태가 변경되면 자동으로 리액트 컴포넌트를 다시 렌더링하게 할 수 있다.
리덕스의 작동 원리
graph TD;
A[사용자의 이벤트 발생] --> B[특정 액션 생성];
B --> C[디스패치];
C --> D[리듀서로 전달];
D --> E[전달받은 액션 + 현재 상태];
E --> F[새로운 상태가 스토어에 저장];
F --> G[스토어 상태 업데이트, 해당 상태 구독 시 컴포넌트 재렌더링]
리덕스의 장점
예측 가능하다
상태 변화가 예측 가능하게 이루어지므로 애플리케이션의 동작을 쉽게 파악할 수 있다.
중앙 집중식 관리
모든 상태가 하나의 스토어에서 관리되기 때문에 상태를 추적하기 쉽다.
디버깅 용이성
리덕스 개발 도구를 통해 상태 변화 과정을 시각적으로 확인할 수 있어 디버깅이 용이하다.
유연성
미들웨어를 활용해 비동기 작업이나 로직, 에러 처리 등을 쉽게 추가할 수 있다.
Redux-saga
리덕스 애플리케이션에서 비동기 작업을 관리하기 위한 미들웨어
리덕스 자체는 동기적인 상태 관리에 초점을 맞추기 때문에 비동기 로직을 처리하는 데 추가적인 도구가 필요하기 때문에 만들어졌다.
리덕스 사가의 작동 원리
graph TD;
A[특정 액션 디스패치] --> B[Watcher Saga가 감지];
B --> C[액션에 따른 Worker Saga 실행];
C --> D[비동기 작업 수행];
D --> E[수행 결과에 따라 액션 재디스패치];
E --> F[리듀서의 상태 업데이트];
Redux-saga를 사용하는 이유
리덕스 애플리케이션에서 비동기 작업이 복잡해질수록 단순한 상태관리에는 한계가 있다.
복잡한 API 호출 순서, 타이밍, 에러 처리 등의 작업이 필요한 경우 매우 유용하다.
옵저버블
옵저버블은 비동기 데이터 스트림을 관리하는 개념이다.
주로 리액티브 익스텐션 라이브러리를 통해 사용된다.
함수형 프로그래밍과 반응형 프로그래밍의 개념을 결합하여 데이터 흐름을 효율적으로 처리하는 도구이다.
옵저버블의 장점
조합성
여러 데이터 스트림을 조합하거나 변환할 수 있어 복잡한 비동기 로직을 간결하게 표현할 수 있다.
유연성
옵저버블은 데이터를 처리하는 시점을 제어할 수 있어 실시간 데이터 흐름을 다루는 데 유리하다.
함수형 프로그래밍
순수 함수와 연산자를 사용하여 데이터를 처리하는 함수형 프로그래밍 스타일 지원한다.
옵저버블과 프로미스 비교
프로미스
단일 비동기 작업의 결과를 나타낸다. 작업이 완료되면 하나의 값을 반환한다.
옵저버블
여러 비동기 이벤트의 스트림을 나타낸다. 여러 개의 값을 발행할 수 있으며, 데이터 흐름을 제어할 수 있다.
Context-API
전역적으로 데이터를 관리하고 여러 컴포넌트 간에 쉽게 데이터를 공유할 수 있도록 도와주는 기능
일반적으로 리액트에서는 데이터가 부모에서 자식 컴포넌트로 props를 통해 전달하지만 깊게 중첩된 컴포넌트 구조에서는 이 방식이 비효율적이기 때문에 사용한다.
Context API의 주요 개념
Context
전역적으로 관리하고 있는 데이터를 저장하는 컨테이너 역할.
React.createContext() 함수를 사용하여 생성된다.
생성된 Context는 Provider과 Consumer을 통해 데이터를 주고 받습니다.
Provider
Context에서 제공하는 컴포넌트로 데이터를 전달하는 역할을 한다. Provider은 컴포넌트 트리에서 Context를 구독하는 하위 컴포넌트에게 값을 전달한다. 이 때 Value 속성을 통해 전달할 데이터를 정의한다.
Consumer
Context에서 제공하는 또 다른 컴포넌트로 데이터를 소비하는 역할을 한다. Consumer은 Context로부터 전달된 데이터를 받아 사용하는 컴포넌트이다. 함수형 컴포넌트는 useContext 훅을 사용하여 더 간단하게 Context 데이터를 소비할 수 있다.
useContext
함수형 컴포넌트에서 Context를 쉽게 사용할 수 있게 도와주는 리액트 훅이다. Consumer를 사용하는 것보다 코드가 간결해지고 직관적으로 Context에 접근할 수 있다.
Context API의 장점
Prop Drilling 방지
부모에서 자식으로 일일이 ‘Props’를 전달 해야하는 번거로움을 해결할 수 있다. 이를 통해 코드가 더 간결하고 관리하기 쉬워진다.
전역 상태 관리
Context API를 사용하면 애플리케이션 전역에서 상태를 관리하고 필요한 곳에서 쉽게 접근할 수 있다. 간단한 상태 관리에서 리덕스 같은 라이브러리 없이도 Context API만으로 충분히 해결할 수 있다.
재사용성
Context를 통해 전역적으로 데이터를 관리하면 특정 상태나 설정을 여러 컴포넌트에서 재사용할 수 있다
클래스형과 함수형의 차이
클래스형 컴포넌트
ES6을 사용하여 정의된다.
상태와 라이프사이클 메서드를 사용하여 컴포넌트의 동작을 제어한다.
this 키워드를 사용해 상태 및 메서드에 접근한다.
장점
상태와 라이프사이클 관리
클래스형 컴포넌트는 상태를 관리하고, 라이프사이클 메서드를 사용하여 컴포넌트의 생명주기를 제어할 수 있다.
오래된 프로젝트에서 많이 사용
리액트 초기에는 상태 관리와 라이프사이클 메서드를 사용해야 할 때 클래스형 컴포넌트가 필수적이다.
함수형 컴포넌트
단순한 자바스크립트 함수로 정의
React Hooks를 사용하여 상태 및 라이프사이클을 관리할 수 있다.
useState, useEffect 등 다양한 훅을 사용하여 클래스형 컴포넌트에서 사용했던 기능들을 함수형 컴포넌트에서 쉽게 구현할 수 있다.
장점
간결한 코드
this 피워드가 필요하지 않아 코드 작성이 더 쉽다.
React Hooks의 도입
훅을 사용해 상태 관리, 사이드 이펙트 처리 등을 할 수 있으며, 함수형 컴포넌트에서도 클래스형 컴포넌트의 기능을 모두 사용할 수 있다.
classPerson{
// 생성자 메서드constructor(name, age) {
this.name = name;
this.age = age;
}
// 클래스 메서드greet() {
console.log(`Hello, my name is ${this.name}`);
}
}
// 클래스 인스턴스 생성const person1 = new Person('Alice', 25);
person1.greet(); // "Hello, my name is Alice"
function f2() { "use strict"; // 엄격 모드 참고 return this; } f2() === undefined; // true
메서드 안에서 쓴 this
일반 함수가 아니고 메서드인 경우
메서드 호출 시 내부 코드에서 사용된 this는 해당 메서드를 호출한 객체로 바인딩된다.
var num = 0; function showNum() { console.log(this.num); } showNum(); //0 var obj = { num: 200, func: showNum, }; obj.func(); //200
이벤트 핸들러 안에서 쓴 this
이벤트 핸들러에서 this는 이벤트를 받는 HTML 요소를 말한다.
var btn = document.querySelector('#btn') btn.addEventListener('click', function () { console.log(this); //#btn });
생성자 안에서 쓴 this
생성자 함수가 생성하는 객체로 this가 바인딩 된다.
function Person(name) { this.name = name; } var kim = new Person('kim'); var lee = new Person('lee'); console.log(kim.name); //kim console.log(lee.name); //lee // new 키워드를 빼면 일반 함수 호출과 같아져서 window가 바인딩된다.
명시적 바인딩을 한 this
명시적 바인딩은 짝을 짓는다.
apply()
apply()에서 매개변수로 받은 첫번째 값은 함수 내부에서 사용되는 this에 바인딩된다.
두번째 값인 배열은 자신을 호출한 함수의 인자로 사용한다.
func.apply(thisArg, [argsArray]);
//인수들의 단일 배열을 받는다.
functionCharacter(name, level) {
this.name = name;
this.level = level;
}
functionPlayer(name, level, job) {
Character.apply(this, [name, level]);
this.job = job;
}
var me = new Player('Nana', 10, 'Magician');
화살표 함수는 전역 컨텍스트에서 실행되더라도 this를 새로 정의하지 않고, 바로 바깥 함수나 클래스의 this를 쓴다.
var Person = function (name, age) { this.name = name; this.age = age; this.say = function () { console.log(this); // Person {name: "Nana", age: 28} setTimeout(() => { console.log(this); // Person {name: "Nana", age: 28} console.log(this.name + ' is ' + this.age + ' years old'); }, 100); }; }; var me = new Person('Nana', 28); //Nana is 28 years old
