해쉬테이블의 구현
이번 포스트에서는 해쉬테이블의 대한 내용과 그 구현에 대해서 설명하도록 하겠습니다. 해쉬테이블 해쉬테이블이란, 해쉬함수에 기반하여 키, 값의 쌍을 저장하는 자료구조 입니다. 삽입, 삭제, 탐색의 연산을 평균적으로 O(1)의 시간복잡도로 처리할 수 있고, 최악의 경우 O(n)의 시간복잡도가 소요됩니다. 키, 값의 쌍을 저장하는 경우 사전의 표현이 가능하고, 키만 저장하는 경우 집합의 표현이 가능합니다. 여기서 말하는 사전이란, 키와 값의 쌍들의 모음을 다루는 추상자료형으로 삽입, 삭제, 탐색의 연산이 가능합니다. 해쉬함수 해쉬함수란, 키를 입력으로 받아 해쉬테이블 내 키와 값이 저장될 위치 인덱스를 출력해주는 함수입니다. 이때 출력 값을 보통 해쉬 값, 해쉬 코드 등으로 부릅니다. 하지만, 해쉬함수를 거쳐..
2023. 9. 12.
비선형 자료구조 (그래프)
이번 포스트에서는 비선형 자료구조 중 하나인 그래프에 대하여 설명하겠습니다. 그래프 그래프는 간선으로 연결된 정점들의 모음을 표현한 자료구조입니다. 이때 정점과 정점을 연결하는 간선들이 방향을 가지지 않는 경우, 이 그래프를 무방향 그래프라고 합니다. 반대로, 방향을 가지는 경우 방향 그래프라고 정의합니다. 부분그래프는 그래프 G의 정점 V와 간선 E가 있을 때, 부분그래프 G'는 다음 수식을 만족합니다. G' = (V', E'), V' 는 V에 속하고, E'는 E에 속해야합니다. 무방향 그래프 G 내 임의의 서로 다른 두 정점 u, v에 대해, u에서 v로 가는 경로가 존재한다면, G는 연결 되었다고 합니다. 이때, G 내에서 최대로 연결된 부분그래프를 연결요소 라고한다. 반대로 방향 그래프 G 에서 ..
2023. 9. 11.