header

Day 4 - 2022/10/20

💡 새롭게 알게된 점

자료구조와 알고리즘

큐

First In First Out(FIFO)

Linear Queue

  1. Array로 표현: 배열이 꽉 찬다면 더 이상 추가할 수 없음. JS에서는 배열이 자유롭게 증감되어 이런 문제는 없지만 front나 rear 값이 무한정 늘어날 수 있음. 따라서 앞당기는 작업이 필요한데 선형 시간이 필요함
  2. Linked List로 표현하기: 배열로 구현했을 때와 다르게 인덱스에 대한 고민은 하지 않아도 됨

JS에서 shift() 함수는 선형 시간이 걸리기 때문에 shift()로 Queue를 구현하면 안됨!

Circular Queue

Front와 Rear가 이어져있는 Queue

  1. Array로 표현
  2. Linked List로 구현 → 환형 큐는 한정된 공간을 효율적으로 이용하게 위해 사용하는 자료구조이기 때문에 상관은 없지만 크게 이점이 없음


해시 테이블

키와 값을 받아 키를 해싱하여 나온 index에 값을 저장하는 선형 자료구조

삽입은 O(1)이며, 사전에 키를 알고 있는 경우는 삭제와 탐색도 O(1)로 수행

해시 함수

입력받은 값을 특정 범위 내 숫자로 변경하는 함수, 특정한 구현 방법이 정해져 있지는 않기 때문에 마음대로 구현해도 됨.

해시 함수의 문제점

해시 함수의 결과가 동일하여 겹친다면? 해시 충돌

해시 충돌을 어떻게 해결하지??

  1. 선형 탐사법
    • 충돌이 발생하면 옆으로 한 칸 이동한다. 단순하지만 특정 데이터 영역에 몰릴 수 있는 문제점이 존재하고, 이동한 버켓에서 또 충돌이 발생한다면 충돌이 발생하지 않을 때 까지 이동하기 때문에 최악의 경우 탐색에 선형 시간이 걸릴 수 있음.
  2. 제곱 탐사법
    • 충돌이 발생하면 충돌이 발생한 횟수의 제곱만큼 옆으로 이동한다. 충돌이 발생할수록 범위가 커지기에 데이터가 몰리는 경우가 선형 탐사법보다 덜 함.
  3. 이중 해싱
    • 충돌이 발생하면 다른 해시 함수를 이용한다. 충돌이 발생하면 충돌이 발생하지 않을 때 까지 두번째 해시로 계속해서 인덱스를 만들어낸다.
  4. 분리 연결법
    • 앞선 세 가지 방법과 다르게 충돌이 발생할 경우 다른 인덱스로 이동하지 않는다. 대신 해시 테이블의 요소를 연결 리스트로 만들어 충돌이 발생한 버켓에 그대로 요소를 추가한다. 최악의 경우 하나의 버켓이 무한정 늘어날 수 있다는 단점이 존재함.

해시 테이블을 어디에 사용해?

빠르게 값을 찾아야 하는 경우! 키를 알고 있는 경우 탐색과 삽입, 삭제가 모두 상수 시간에 끝난다! 최악의 경우 탐색에 선형 시간이 소요될 수도 있지만 연결 리스트나 배열보다는 안정적이다.

자바스크립트에서 해시 테이블을 사용해보자!

  1. Array → 실제로는 객체 타입이라 해시 테이블처럼 사용 가능하지만 올바른 사용 방법이 아니기에 추천하진 않음
  2. Object → 제일 간단하고 정석적인 방법
  3. Map → 기존 객체와 달리 키 값으로 Object나 배열같은 복잡한 타입도 키로 사용할 수 있기 때문에 다양한 타입을 넣을 수 있고, 여러 편한 메서드를 제공하여 순회를 편하게 할 수 있음
  4. Set → key와 value가 동일하게 들어가 중복된 내용을 제거할 때 자주 사용됨


그래프

정점과 정점 사이를 연결하는 간선으로 이루어진 비선형 자료구조. 정점(node) 집합과 간선(edge) 집합으로 표현할 수 있다.

어떤 특징이 있나요?

  • 정점은 여러 개의 간선을 가질 수 있다.
  • 간선의 방향이 존재하는 방향 그래프와 존재하지 않는 무방향 그래프로 나뉜다.
  • 간선은 가중치를 가질 수 있다. (예: 거리)
  • 탐색 시 계속 루프가 가능한 구역인 사이클이 존재할 수 있어 무한 루프에 빠지지 않도록 사이클을 찾아야 할 필요가 있다.

간선의 방향성에 따른 분류

무방향 그래프

간선에 방향이 존재하지 않는 즉, 양방향으로 이동이 가능한 그래프이다.

방향 그래프

간선에 방향이 존재하는 그래프.

전체 그래프의 연결 상태에 따른 분류

연결 그래프

모든 정점이 서로 이동 가능한 상태인 그래프. 특정 정점에서 또 다른 특정 정점까지 모든 경우의 수가 이동 가능해야 한다.

비연결 그래프

특정 정점쌍 사이에 간선이 존재하지 않는 그래프

완전 그래프

모든 정점끼리 연결된 상태인 그래프. 한 정점의 간선 수 = (모든 정점 수 - 1), 모든 간선의 수 = (모든 정점 수 - 1) * 모든 정점 수

사이클

그래프의 정점과 간선의 부분 집합에서 순환이 되는 부분

그래프의 구현 방법

  1. 인접 행렬 - 2차원 배열을 이용할 수 있음
  2. 인접 리스트 - 연결 리스트로 표현 가능

자바스크립트에서 그래프를 구현해보자!

  • 인접 행렬
    1. 정점의 크기만큼 2차원 배열을 만들고 연결이 안된 상태로 초기화.
    2. 행렬의 열 부분을 시작 정점, 행 부분을 도착 정점으로 두고 true값으로 두면 간선이 연결됨.
    3. 만약 가중치 값을 주고 싶다면 Boolean값이 아닌 null과 임의의 가중치 값을 넣으면 됨.
  • 인접 리스트
    1. 자바스크립트에서 배열은 마치 연결 리스트처럼 무한정 늘어날 수 있기 때문에 정점의 수 만큼 배열을 만듦
    2. 연결할 정점을 배열에 추가


❗️ 느낀점

오늘은 특강과 실습으로 코딩 테스트 문제 풀이가 2개 있어서 강의 내용이 많지 않았다.

아직 코딩 테스트 레벨 2정도까지밖에 안풀어서 큐를 구현해서 문제를 해결한 적은 많이 없지만 점점 효율성을 빡빡하게 보는 것 같아서 직접 구현할 수 있을 정도로 연습해야 겠다는 생각을 했다.

어제 링크드 리스트 3가지 클래스를 구현해봤는데, 완벽하게 동작하도록 짠 것 같지 않아서 내일 팀원들과 피드백 시간을 가질 예정이다. 얼마나 잘못 짰을지 .. 무섭다..

매일매일 강의를 들으면서 정리하고, TIL을 작성하는게 아직 습관이 들지 않아 힘든 감이 없지 않지만 그래도 화이팅!

오늘도 고생했다👊