작은 방

정렬 개념

• 정렬은 사용자가 정의한 순서로 데이터를 나열하는 것을 말한다. 사용자가 정의한 순서는 오름차순 / 내림차순일 수도 있고 임의의 조건이 될 수도 있다.

정렬이 필요한 이유

• 데이터를 정렬하면 원하는 데이터를 쉽게 찾을 수 있다. 이진 탐색 트리가 그 예이다.
• 데이터를 정렬하지 않은 값에서 중앙값을 찾으려면 모든 데이터를 확인하고 비교해야 한다. 반면 데이터를 정렬하면 데이터의 값을 보거나 비교할 필요 없이 말 그대로 데이터 전체 크기에서 중간의 값만 찾으면 그 값 자체가 중앙값이 된다.

삽입 정렬

• 데이터의 전체 영역에서 정렬된 영역과 정렬되지 않은 영역을 나누고 정렬되지 않은 영역의 값을 정렬된 영역의 적절한 위치로 놓으며 정렬한다.

  

• 정렬되지 않은 영역의 맨 앞에 있는 값을 키라고 부른다.
• 삽입 정렬의 과정
  • 최초에는 정렬된 영역을 왼쪽 1개, 정렬되지 않은 영역을 나머지로 친다.
  • 키와 정렬된 영역의 맨 끝 값부터 거슬러 올라가며 다음 처리를 한다.
    • 키보다 크면 해당 값을 오른쪽으로 한 칸 밀어낸다.
    • 키보다 작거나 더 이상 비교할 값이 없으면 밀어낸 자리에 키를 넣는다.
  • 모든 데이터가 정렬된 영역이 될 때까지 위의 단계를 반복한다.
• 삽입 정렬의 시간 복잡도
  • 최악의 경우 O(N^2)
  • 최선의 경우 O(N)

병합 정렬

• 정렬되지 않은 영역을 쪼개서 각각의 영역을 정렬하고 이를 합치며 정렬하는 방식
  • 이런 방식을 분할 정복 (Divide and Conquer) 이라고 한다.

• 정렬되지 않은 영역이 1칸이 될 때까지 반씩 쪼갠 후 다시 조합할 때 오름차순으로 정렬하며 합친다.
• 병합 정렬에서의 핵심은 ‘병합할 때 정렬하는 부분을 어떻게 구현해야 하는ㄱ?’ 이다.
• 병합 정렬의 과정
  • 각 데이터의 첫 번째 원소를 가리키는 포인터를 만든다.
    • 포인터가 가리키는 두 값 중 작은 값을 선택해 새 저장 공간에 저장한다.
    • 값이 선택된 포인터는 다음 위치의 값을 가리킨다.
  • 새 저장 공간에 하나의 데이터가 완전히 저장될 때까지 위 과정을 반복한다.
    • 저장할 값이 남은 데이터의 값을 순서대로 새로운 저장 공간에 저장한ㄷ.
    • 그러면 새로운 저장 공간에 두 개의 데이터가 정렬된 상태로 저장된다.
  • 새로운 저장소에 저장된 값의 개수와 초기에 주어진 데이터에 들어있는 값의 개수가 같을 때까지 과정 1, 2를 반복한다.

📄
포인터라는 개념?
말 그대로 특정 배열의 원소를 가리키기 위한 화살표 같은 것.

• 병합 정렬의 시간 복잡도
  • 병합 정렬의 동작은 분할과 정복(결합)으로 나눠진다.
  • 분할은 배열을 계속 반으로 나누는 과정이고, 더 이상 나눌 수 없을 때까지 반복하므로
    • log_2N번 진행한다.
  • 정복은 다시 병합하며 정렬하는 과정이기 때문에 데이터가 N개면
    • N번 진행하여 병합한다.
  • 분할과 정복을 종합하면 log_2N번의 나누기와 N번의 병합을 수행하므로 총 Nlog_2N번 연산한다.
  • 다만, 시간 복잡도에서는 밑이 2인 로그는 생략하므로 O(NlogN)이라고 할 수 있다.

힙 정렬

• 힙이라는 자료구조를 사용해 정렬한다.
• 따라서 힙 정렬은 힙 자료구조가 무엇인지 먼지 알아야 한다.
• 힙 정렬을 하기 위해서는 먼저 주어진 데이터로 힙을 구축해야 한다.
  • 힙은 특정 규칙이 있는 이진 트리이다. 규칙에 따라 최대 힙, 최소 힙으로 나뉠 수 있다.
  • 최대 힙은 부모 노드가 자식 노드보다 크고, 최소 힙은 부모 노드가 자식 노드보다 작다.힙이란?

    

• 왼쪽의 최대 힙을 보면 부모 노드는 항상 자식보다 크다. 반대로 오른쪽의 최소힙은 부모 노드가 항상 자식보다 작다.

힙 구축 방법 : 최대힙

• 최대힙과 최소힙은 힙을 구성하는 규칙만 다르고 나머지는 모두 동일하다.
• 최대힙을 구축하는 maxHeaplify()라는 함수가 있다고 가정하고 어떻게 연산을 하는 지 알아보자.
  • 현재 노드와 자식 노드의 값을 비교한다.
    • 현재 노드의 값이 가장 크지 않으면 자식 노드 중 가장 큰 값과 현재 노드의 값을 바꾼다.
    • 만약 자식 노드가 없거나 현재 노드의 값이 가장 크면 연산을 종료한다.
  • 맞바꾼 자식 노드의 위치를 현재 노드로 하여 위의 과정을 반복한다.

 📄
 힙을 구축할 때는 자식 노드가 없으면 아무런 동작도 하지 않으므로 N부터 힙 구축을 시작하지 않아도 된다. 현재 노드 인덱스가 N/2을 넘으면 자식 노드의 인덱스가 N을 넘는다. 힙의 크기는 N이므로 실제 노드의 인덱스가 N 이상 넘어가는 일은 없으므로 고려하지 않아도 괜찮다.

• 힙 구축은 N이 아니라 N/2부터 시작해도 괜찮다.
• 힙 정렬 과정 : 최대힙
  • 최대힙에서 힙 정렬은 루트 노드가 가장 큰 값이므로 루트 노드의 값을 빼서 저장하기만 하면 된다. 다만 루트 노드의 값을 뺀 이후 최대힙을 유지하는 것이 중요하다.
    • 정렬되지 않은 데이터로 최대힙을 구축한다.
    • 현재 최대힙의 루트 노드와 마지막 노드를 맞바꾼다. 맞바꾼 뒤 마지막 노드는 최대힙에서 제외한다.
    • 현재 최대힙은 마지막 노드가 루트 노드가 되었다. 따라서 최대힙을 다시 구축해야 하기 때문에, maxHeapify(1)을 진행하여 최대힙을 구축하고 위의 과정을 다시 수행한다. 이 과정을 최대힙의 크기가 1이 될 때까지 반복한다.
• 힙 정렬의 시간 복잡도
  • 정렬되지 않은 값 N개를 힙으로 나타내면 높이가 logN인 트리가 된다. 데이터는 N개이므로 각 데이터에 대해 힙 정렬을 수행하면 시간 복잡도는 O(NlogN)이다.

우선순위 큐

• 우선순위 큐는 우선순위가 높은 데이터부터 먼저 처리하는 큐이다. 쉽게 말해 큐는 큐인데 우선순위에 따라 팝을 하는 큐인 것.
• 우선순위 큐의 내부동작은 힙과 매우 유사하므로 우선순위 큐를 구현할 때는 힙을 활용하는 것이 효율적이다. 여기를 다 공부하면 우선순위 큐 자체가 정렬과 연관이 있음을 알게 된다.
• 우선순위 큐 동작 과정
  • 우선순위 큐의 우선순위 기준은 작은 값일수록 우선순위가 높다고 가정
    • 빈 우선순위 큐를 하나 선언
    • 3을 삽입한다. 빈 큐이므로 별다른 우선순위를 생각하지 않고 맨 앞에 푸시한다.
    • 이어서 1을 삽입한다. 1은 3보다 작으므로 우선순위가 높다. 따라서 1을 3으로 삽입한다. 이렇게 하면 3보다 1이 먼저 pop 될 것이다.
    • pop을 수행하면 1이 나온다.
  • 우선순위에 따라 데이터를 pop할 수 있으므로 정렬과 깊은 연관이 있다는 것도 알았을 것이다.
• 힙으로 우선순위 큐를 구현해야 하는 이유
  • 우선순위 큐의 핵심 동작은 우선순위가 높은 데이터를 먼저 팝하는 것
  • 이를 위해 앞서 언급했던 것처럼 데이터를 푸시할 때마다 아무 정렬 알고리즘을 사용해서 데이터를 우선순위에 맞게 정렬해도 된다.
    • 하지만 최소힙이나 최대힙은 특정 값을 루트 노드에 유지하게 하는 특징이 있고, 이는 우선순위 큐의 핵심 동작과 맞아 떨어지므로 힙을 활용하면 우선순위 큐를 효율적으로 구현할 수 있다는 것을 알 수 있다.
    • 자바스크립트에서는 힙을 공식적으로 제공하지 않는다.
• 우선순위 큐가 활용되는 분야
  • 우선순위 큐는 데이터의 중요성 혹은 우선순위에 따라 처리해야 하는 경우 많이 활용된다.
    • 작업 스케줄링
    • 응급실 대기열
    • 네트워크 트래픽 제어
    • 교통 네트워크 최적화

위상 정렬

• 일의 순서가 있는 작업을 순서에 맞춰 정렬하는 알고리즘
• 위상 정렬은 일의 순서가 중요하므로 반드시 간선의 방향이 있어야 한다.
• 만약 그래프에 순환이 있거나 간선의 방향이 없으면 일의 방향이 없는 것이므로 방향 비순환 그래프 (Directed Acyclic Graph)에서만 사용할 수 있다.
• 위상 정렬과 진입차수
  • 위상 정렬은 자신을 향한 화살표 개수를 진입차수로 정의하여 진행한다. 

    

     
    • 진입차수가 0이라고 하면 자신을 향한 화살표가 없다는 뜻이므로 ‘선행 작업이 필요 없는, 바로 할 수 있는 일’이라는 뜻과 같다.
• 위상 정렬 과정
  • 위상 정렬은 기본적으로 바로 진행할 수 있는 일, 다시 말해 진입차수가 0인 일을 해결하고 관련된 작업의 진입차수를 1씩 낮추면서 새롭게 진입차수가 0이 된 작업들을 해결하는 식으로 진행한다.
  • 이 해결이라는 행위는 큐를 활용하여 구현한다.
  • 진입차수가 0인 작업을 일단 전부 큐에 넣고 하나씩 팝하면서 해당 작업과 연결되어 있는 작업들의 진입차수를 줄이고 진입차수가 0이 된 작업을 큐에 넣는다.
    • 위상 정렬을 진행할 그래프가 있으면 앞서 말한대로 진입차수를 노드에 작성한다.
    • 진입차수가 0인 노드를 큐에 푸시한다. 그런 다음 팝을 하면서 인접한 노드의 진입차수를 -1한다.
    • 노드들이 모두 푸시 후 팝 작업이 완료되면 팝한 순서를 늘어놓는다.
• 위상 정렬의 시간 복잡도
  • 위상 정렬은 모든 정점과 간선을 딱 한 번씩만 지나므로 시간 복잡도는 O(|V| + |E|)가 된다.

계수 정렬

• 데이터에 의존하는 정렬 방식이다.
• 지금까지 배운 정렬들은 사용자가 정한 기준에 따라 정렬했다. 반면 계수 정렬은 데이터의 빈도수로 정렬한다.
  • 왼쪽의 배열에서 데이터의 빈도수를 세어 빈도수 배열에 저장한 것
  • 빈도수를 다 채운 다음 우선 순위가 높은 데이터부터 빈도수만큼 출력하는 것이 계수 정렬

    

• 계수 정렬의 한계
  • 계수 정렬의 핵심 동작은 앞서 본 것처럼 빈도수를 세어 빈도수 배열에 저장하는 것. 그래서 빈도수 배열에 저장할 값의 범위가 듬성듬성 있거나 음수가 있으면 계수 정렬을 하기 곤란하다.
• 계수 정렬의 시간 복잡도
  • 값이 N개인 데이터에서 데이터를 세는 과정은 전체 데이터를 한 번씩 체크하면 되므로 N번 탐색한다고 생각할 수 있다.
  • 값의 최솟값 ~ 최댓값 범위 크기가 K라면 빈도수 배열에서 K + 1만큼 탐색해야 하므로 계수 정렬의 시간 복잡도는 O(N + K) 라고 생각할 수 있다.
• 정렬 알고리즘의 시간 복잡도정렬 방법 최악의 경우 최선의 경우 특이점 

  삽입 정렬	O(N^2)	O(N)	데이터가 거의 정렬되어 있을 때는 최고의 성능 발휘
  병합 정렬	O(NlogN)	O(NlogN)	안정적인 성능으로 정렬 가능
  병합 과정에서의 추가적인 메모리 필요
  힙 정렬	O(NlogN)	O(NlogN)	안전적인 성능으로 정렬 가능
  데이터를 삽입과 동시에 빠르게 정렬할 수 있다
  계수 정렬	O(N + K)	O(N + K)	데이터에 의존적이므로 항상 사용 가능한 것은 아님
  위상 정렬	O(V + E)	O(V+E)	작업의 순서가 존재할 때 사용되는 알고리즘

  • N은 원소의 길이, K는 원소값의 범위, V는 정점, E는 간선의 개수
  • 정렬이 안정적이다?
    • 성능이 안정적이라는 뜻이 아니라 동일한 우선순위를 가진 원소들의 상대적 순서가 정렬 후에도 보존되는 것을 말한다.

문제 풀이

• • K번째 수

  

  • 가장 큰 수

  

  • H - index

  

출처

• 코딩테스트 합격자 되기 - 자바스크립트 편

• 힙은 우선순위 큐를 위해 만들어진 자료구조

우선순위 큐

• 우선순위 큐란?
  • 큐 : FIFO 형식의 자료구조
  • 우선순위 큐는 큐에 우선순위라는 개념을 접목시킨 자료구조이다.
  • 따라서 우선순위 큐는 먼저 들어오는 데이터가 아니라 우선순위가 높은 데이터가 먼저 나가는 형태의 자료구조.

힙

• 힙이란?
  • 우선순위 큐를 위해 고안된 완전 이진 트리 형태의 자료구조
  • 여러 값 중 최대값과 최소값을 빠르게 찾아내도록 만들어진 자료구조
  • 반정렬 상태를 유지
  • 이진 탐색 트리와 달리 중복된 값이 허용된다.

힙의 종류

• 최대 힙
  • 부모 노드의 키 값이 자식 노드의 키 값보다 크거나 같은 완전 이진 트리
• 최소 힙
  • 부모 노드의 키 값이 자식 노드의 키 값보다 작거나 같은 완전 이진 트리

힙의 데이터 저장 / 삭제 개념

• 최소 힙에 저장할 때
  • 들어올 새 노드를 우선 순위가 가장 낮다는 가정을 하고 맨 끝 위치에 저장
  • 부모 노드와 우선 순위를 비교해서 위치가 바뀌어야 하면 바꾼다
  • 올바르게 위치할 때까지 B 반복
• 최소 힙에서 삭제할 때
  • 우선순위 큐의 pop == 가장 우선순위가 높은 데이터를 빼낸다.
    1. 루트 노드를 반환하고 마지막 노드를 루트 노드 자리에 옮긴다.
    2. n의 왼쪽, 오른쪽 자식노드 중 더 우선순위가 높은 것과 비료를 진행한다.
    3. 최소 힙의 구조를 유지할 때까지 B 반복
    ⇒ 이렇게 힙의 구조를 유지하는 과정을 heapify라고 한다.

파이썬의 우선순위 큐

• heapq 모듈

import heapq
# 파이썬의 heapq 모듈은 최소 힙을 기본으로 구현되어 있다.

pq = []

heapq.heappush(pq, (1, '작업1')) # (우선순위, 값)
heapq.heappush(pq, (4, '작업4'))
heapq.heappush(pq, (3, '작업3'))
heapq.heappush(pq, (2, '작업2'))

print(heapq.heappop(pq)) 
print(heapq.heappop(pq))

• PriorityQueue 클래스

from queue import PriorityQueue

pq = PriorityQueue()

pq.put((1, '작업1'))
pq.put((3, '작업3'))
pq.put((2, '작업2'))

print(pq.get())
print(pq.get())

⇒ PriorityQueue는 스레드 안전을 제공하므로 멀티스레딩 환경에서 유용하지만, 단일 스레드 환경에서는 heapq가 더 간편하다.

문제 풀이

JS로도 풀어보고 싶었지만 JS에는 heap 모듈이 따로 없고 코테 외에서는 라이브러리를 사용할 수 있다.

더 맵게

• 파이썬 풀이

• # 스코빌 섞을 수 없는 경우: 길이가 2보다 짧을 시 -1
  
  import heapq
  
  def solution(scoville, K):  
      heapq.heapify(scoville)
      
      mix_count = 0
      
      while 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 += 1
              
      return mix_count
  ​

• 자바스크립트 풀이⇒ 이 코드는 모든 테스트 케이스를 통과하지만 효율성에서 걸린 코드이다.

• function solution(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;
  }
  

디스크 컨트롤러

• 파이썬 풀이

이중우선순위큐

• 파이썬 풀이

스택

스택의 개념

• 스택
  • 쌓아 올린다는 것을 의미
  • 스택 자료구조는 책을 쌓는 것처럼 쌓아 올린 형태의 자료구조

스택의 특징

• 스택은 같은 구조의 크기와 자료를 정해진 방향으로만 쌓을 수 있고, top으로 정한 곳을 통해서만 접근할 수 있다.
• top에 있는 가장 위에 있는 자료는 가장 최근에 들어온 자료를 가리키고 있으며, 삽입되는 새 자료는 top이 가리키는 자료의 위에 쌓이게 된다.
• 스택에서 자료를 삭제할 때도 top을 통해서만 가능하다.
• 삽입하는 연산은 push, 삭제하는 연산은 pop
• 스택은 시간 순서에 따라 자료가 쌓여서 가장 마지막에 삽입된 자료가 가장 먼저 삭제된다는 구조적 특징이 있다.
  • 비어있는 스택에서 원소를 추출하려고 하는 것 → stack underflow
  • 스택이 넘치는 경우 → stack overflow
• ⇒ 후입선출 구조

스택의 활용 예시

• 스택의 특징인 후입선출을 활용하여 여러 분야에서 활용 가능하다.
• 웹 브라우저 방문 기록
  • 가장 나중에 열린 페이지부터 다시 보여준다.
• 역순 문자열 만들기
  • 가장 나중에 입력된 문자부터 출력한다.
• 실행 취소
  • 가장 나중에 실행된 것부터 실행을 취소한다.
• 후위 표기법 계싼
• 수식의 괄호 검사

큐

큐의 개념

• 말 그대로 줄
• 선입선출 방식의 자료구조

큐의 특징

• 정해진 한 곳을 통해서 삽입, 삭제가 이루어지는 스택과 달리 큐는 한쪽 끝에서 삽입 작업, 다른 끝에서 삭제 작업이 이루어진다.
• 삭제 연산만 수행되는 곳을 프론트, 삽입연산만 이루어지는 곳을 리어로 정한다.
• 큐의 리어에서 이루어지는 삽입 연산을 인큐
• 큐의 프론트에서 이루어지는 삭제 연산을 디큐라고 한다.
• 즉, 큐에서 프론트 원소는 가장 먼저 큐에 들어왔던 첫번째 원소
• 리어 원소는 가장 늦게 큐에 들어온 마지막 원소

활용 예시

• 큐는 주로 데이터가 입력된 시간 순서대로 처리해야 할 필요가 있는 상황에 이용
• 우선순위가 같은 작업 예약
• 은행 업무
• 콜센터 고객 대기시간
• 프로세스 관리
• 너비 우선 탐색 구현
• 캐시 구현

문제 풀이

같은 숫자는 싫어

자바스크립트

function solution(arr) {
    let answer = [];
    for (let i = 0; i < arr.length; i++) {
        if (arr[i] !== arr[i - 1]) {
            answer.push(arr[i]);
        }
    }
    return answer;
}

파이썬

def solution(arr):
    answer = []
    for e in arr:
        if answer and answer[-1] == e:
            continue
        answer.append(e)
    return answer

=> 로직은 같다. 현재 가리키고 있는 요소와 요소 -1의 인덱스를 가진 요소를 비교해서 다른 경우에만 answer에 push한다.

기능 개발

자바스크립트

function solution(progresses, speeds) {
    const answer = [];
    let days = progresses.map((progress, i) => Math.ceil((100 - progress) / speeds[i]));
    
    let maxDay = days[0];
    let count = 1;
    
    for (let i = 1; i < days.length; i++) {
        if (days[i] > maxDay) {
            answer.push(count);
            maxDay = days[i];
            count = 1;
        } else {
            count++;
        }
    }
    
    answer.push(count);
    return answer;
}

올바른 괄호

자바스크립트

function solution(s){
    let paren = 0;
    for (let i = 0; i < s.length; i++) {
        s[i] === "(" ? paren++ : paren--;
        if (paren < 0) {
            return false;
        }
    }
    return s.at(-1) == ")" && paren == 0;
}

프로세스

추후 수정

다리를 지나는 트럭

추후 수정

주식가격

추후 수정

해시의 개념

• 해시는 해시 함수를 사용해서 변환한 값을 인덱스로 삼아 키와 값을 저장해서 빠른 데이터 탐색을 제공하는 자료구조이다.
• 보통은 인덱스를 활용해서 탐색을 빠르게 만들지만 해시는 키를 사용해 데이터 탐색을 빠르게 한다.
• 해시는 키와 데이터를 일대일 대응하여 저장하므로 키를 통해 데이터에 바로 접근할 수 있다. 사람에게는 숫자로 데이터를 관리하는 배열보다 조금 더 접근성이 좋은 자료구조이다.

키워드

• 값
  • 최종적으로 얻고자 하는 정보
• 키
  • 값을 검색하기 위해 활용하는 정보
• 해시 함수
  • 키를 이용해 해시값 또는 인덱스로 변환하는 함수

해시의 특징

• 해시는 단방향으로 동작한다.
  • 키를 통해 값을 찾을 수 있지만 값을 통해 키를 찾을 수는 없다.
  • 단방향으로만 동작하는 해시의 특성은 외부에 정보를 안전하게 제공한다는 특징이 있어 네트워크 보안에서 많이 활용된다.
• 찾고자 하는 값을 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. 폰켓몬

1. 해시 카테고리에 있는 문제임은 알았으나 아직 자바스크립트로 해시를 구현한다는 것이 잘 감이 잡히지 않아 지금까지 풀어왔던 것처럼 단순하게 풀어봤다. 문제를 읽어보니 결론적으로 필요한 것은 N/2의 값인 것 같아 num으로 값을 미리 구한 후, 중복 된 값을 모두 없애버린 answer에서 if문으로 상황에 따른 처리를 해주었다. 풀이 후에 Set()과 해시 테이블 코드가 결국 비슷하게 돌아간다고 생각해서 찾아보니 둘은 기본적으로 다른 개념이지만 실제 구현에서는 해시 테이블을 기반으로 한 Set을 많이 사용하게 되므로 이를 Hast Set이라고 부르기도 한다는 것을 알았다.

function solution(nums) {
    var answer = [...new Set(nums)];
    let num = nums.length / 2;
    if (num > answer.length) {
        return answer.length;
    } else {
        return num;
    }
  return answer;
}

2.  해시 알고리즘을 이해하고 싶어서 다른 분의 풀이를 참고했다. 그리고 이 코드를 이해하면서 대충 이해했다. nums에 들어온 각 값들이 해시테이블에 존재하지 않는다면 우선 넣고, 존재할 때마다 해당 포켓몬의 수를 하나씩 늘리는 것.

function solution(nums) {
    let answer = 0;
    let bag = new Map();
    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()안에 넣어서 사용해야 한다.

def solution(nums):
    num = len(nums) // 2
    answer = list(set(nums))
    return len(answer) if num > len(answer) else num

2. 완주하지 못한 선수

1. 해시 코드

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

var solution = (participant, completion) => {
    let completionCount = {};
    completion.forEach(name => {
        completionCount[name] = (completionCount[name] || 0) + 1;
    });

    return participant.find(name => {
        if (!completionCount[name]) {
            return true;
        }
        completionCount[name]--;
    });
};

3. 파이썬으로 작성한 코드

def solution(participant, completion):
    par = sorted(participant)
    com = sorted(completion)
    for i in range(len(com)):
        if par[i] != com[i]:
            return par[i]
        
    return par[-1]

js 답변들 둘러보다보니 정렬 후 다르거나 마지막 사람이 미완주자가 되는 것을 이용해서 풀이한 코드가 많아서 그대로 파이썬에 적용했다.

3. 전화번호 목록

1. 해시를 사용하지 않고 정렬과 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; }
2. 해시를 사용해 풀이하는 방법
   • 해시 사용 방법을 통한 풀이를 제대로 이해 못해서 추후 수정 예정
3. 파이썬 코드
   • 파이썬에도 startswith 메소드가 있다는 점!

     def solution(phone_book):
         sorted_arr = sorted(phone_book)
         for i in range(len(sorted_arr) - 1):
             if sorted_arr[i + 1].startswith(sorted_arr[i]):
                 return False
         return True
     

   • 1번 풀이를 파이썬으로 똑같은 방식을 사용해 풀이한 과정이다.
   • 이건 파이썬 해시를 사용한 다른 분의 코드이다.

     def solution(phone_book):
         answer = True
         hash_map = {}
         for phone_number in phone_book:
             hash_map[phone_number] = 1
         for phone_number in phone_book:
             temp = ""
             for number in phone_number:
                 temp += number
                 if temp in hash_map and temp != phone_number:
                     answer = False
         return answer
     

   • 우선 hash 사용을 위해 hash 객체 하나를 생성한다. phone_book에 주어진 번호를 도는 동안 hash_map에 키로 저장하고 값을 1로 할당한다. 그리고 안에 있는 값을 바로 하나씩 꺼내어서 사용할 것이다. 우선 temp 변수를 초기화한다. 각 번호 묶음의 번호 한 자리씩을 꺼내어 temp에 저장한다. 만약 temp가 hash_map에 존재하면서 temp가 phone_number은 아니라면 전체 전화번호와는 동일하지 않다는 뜻이므로 다른 번호의 접두사가 된다는 의미이다.

4. 의상

추후 수정 예정

5. 베스트 앨범

추후 수정 예정