[알고리즘] 데이터 구조 분석 & 조작

데이터 구조와 저장 방식

데이터 구조

기본 저장 방법: 배열(순차 저장 방식), 연결 리스트(체인 저장 방식)

기본 저장 방법은 말 그대로 기초가 되는 방법으로 해시 테이블, 스택, 힙, 트리, 그래프 등의 구조는 구체적인 방식인 상위 구조다. 상위 구조는 하위 구조인 배열과 연결 리스트로 이뤄져 있으며 API의 특성만 다른 정도다.

즉, 기본 저장 방법을 활용하면 스스로 데이터 구조를 만들 수도 있기 때문에 두 방법을 잘 익혀놓는다면 반은 갈 수 있다.

배열

• 장점: 끊어지지 않고 연속적인 저장 방식으로 임의 접근 가능, 인덱스를 통해 빠르게 요소를 찾을 수 있고 저장 공간도 절약 가능
• 단점: 연속되기 때문에 메모리 공간을 한 번에 할당. 배열을 확장할 때도 더 큰 배열을 새로 할당하고 복사를 진행하므로 시간복잡도는 O(n). 배열 중간에 요소를 삽입/삭제하는 경우에도 매번 뒤의 모든 데이터를 이동하므로 시간복잡도 O(n).

연결 리스트

• 장점: 연속되지 않고 다음 위치를 가리키는 포인터에 의존하므로 확장과 같은 문제는 발생하지 않음. 요소의 선행, 후행 요소만으로 포인터를 조작해 요소의 제거와 삽입이 가능하므로 시간복잡도가 O(1).
• 단점: 저장공간이 연속적이지 않아 인덱스를 사용한 요소 위치는 모르므로 임의 접근 불가능. 각 요소에 대한 선행, 후행 요소 위치에 대한 포인터를 저장해야하므로 더 많은 저장공간이 필요.

상위 데이터 구조 구현

큐, 스택

• 배열: 확장과 축소의 문제를 염두에 두고 구현
• 연결 리스트: 메모리 공간을 배열로 구현 시보다 많이 사용

그래프

• 인접 리스트(연결 리스트): 공간 절약 가능하나 효율성이 행렬보다 떨어짐
• 인접 행렬(이차원 배열): 연결성 빠르게 판단하나 많은 공간 소모

해시 테이블

• 배열: 해시 함수를 통해 키를 하나의 큰 배열에 매핑. 폐쇄 해싱으로 해시 충돌을 해결할 수 있으며 배열 특성을 사용해 연속 주소를 지정하므로 포인터 저장공간은 필요치 않으나 조작이 어려움.
• 연결 리스트: 개방 해싱에 연결 리스트 특성이 필요하고 조작이 간단하나 포인터 저장을 위한 추가 공간이 필요.

트리

• 배열: 힙을 구현할 수 있으며 힙은 완전 이진 트리이므로 배열 사용 시 포인터가 필요 없어 조작이 간단.
• 연결 리스트: 일반적인 트리가 되나 완전 이진 트리가 아니므로 배열 사용은 적합하지 않음. 이를 기반으로 이진 탐색 트리, AVL 트리 등 여러 설계가 가능.

데이터 구조 조작

기본적으로 데이터 구조에서 하는 기본 작업은 순회와 접근이며 이를 기반으로 추가, 삭제, 수정, 검색을 하게 된다. 결국 이 작업들을 했을 때 효율성이 높은 데이터 구조를 선택해서 활용해야하는 것이다.

순회

각 데이터 구조에 대한 순회와 액세스는 선형, 비선형 두 가지 방법이 있다. 선형 방법은 for/while 반복문, 비선형 방법은 재귀함수를 활용하는 것이 대표적이다.

예를 들어 배열을 순회하는 for문은 전형적인 선형 반복 구조다. 코드로 많이들 사용해 봤을테니 예시는 생략한다.

연결 리스트 또한 순회와 반복, 재귀 구조를 갖는다.

class ListNode {
	int val;
    ListNode next;
}

void traverse(ListNode head) {
	for(ListNode p = head; p !== null; p = p.next){...}
}

void traverse(ListNode Head) {
	// 전위 순회 head.val
    traverse(head.next);
}

이진 트리 순회는 일반적인 비선형 재귀 순회 구조다. 또한 미들웨어 호출은 사실 연결 리스트를 재귀적으로 순회하는 과정이다.