자료구조 - 01. 자료구조

자료의 출처는 '엘리스 AI 트랙 2기 (https://aitrack.elice.io/)' '자료구조' 강의이며, 학습 후 정리한 내용입니다.

⚡️올바르지 않은 내용이 있을 경우 댓글로 남겨주시면 감사하겠습니다.⚡️

---

지료구조란?

01. 자료구조의 의미

자료구조란?

자료를 저장하는 구조로, 여러 가지 종류가 있으며 저장된 자료에 대해 접근하는 방법 등의 차이가 존재

형태에 따라 장단점이 존재하며 구현하고자 하는 프로그램의 성능을 고려하여 알맞은 자료구조를 선택

프로그램에 필요한 자료를 효율적으로 담기 위해 자료구조를 배우며,

프로그램에서 특정 알고리즘을 구현하기 위해 적절한 자료구조를 사용해야 좋은 성능을 낼 수 있다.

02. 추상적 자료형

추상적 자료형이란?

자료형:

자료형은 어떤 자료가 식별되는 방법을 정의하고 자료에 적용할 수 있는 연산을 결정한다.

자료를 특정 분류에 따라 올바르게 표현하기 위한 정의와, 그구현이 바로 자료형

자료형의 중요성 - 값의 해석 방법 명시

65

예를 들어, 65라는 자료가 있다.
컴퓨터는 이 자료가 수를 나타내는 65인지, 아니면 알파벳 'A' 를 나타내는 값인지 자료형을 모르는 경우에는 해석할 수 없다.

자료형의 중요성 - 연산 방법 제공

(컴퓨터는 내부적으로 unicode라고 불리는 숫자를 문자에 대입하는 방식으로 각 문자를 식별하고, 65는 'A'에 해당)

또, 수를 나타내는 자료형은 덧셈, 뺄셈 등을 비롯한 연산이 가능

추상적 자료형:

자료를 담는 방법과, 자료에 대한 연산에 대한 정의가 담긴 것, 구현 방법은 정의되어 있지 않다.

추상적 자료형은 구현 방법을 명시하고 있지 않다는 점이 특징

그릇을 추상적 자료형이라고 한다면, 그릇이 보관하는 자료와, 그 자료에 해당하는 연산의 정의를 포함해야 한다.

자료 연산

그릇은 음식을 보관하고, 그릇에 담긴 음식을 먹을 수 있다.

이때 음식을 어떻게 먹을 수 있는지, 즉 어떻게 자료에 접근할 수 있는지는 주어지지 않는다.

추상적 자료형과 자료구조

'그릇' 이라는 추상적 자료형이 있고,

그릇에 음식을 어떻게 담을 것인지, 그릇을 이용하여 어떻게 음식을 먹을 수 있는지 명확히 구현된 것을 자료구조라고 할 수 있다.

정리

추상적 자료형: 자료들과, 그 자료들에 대한 연산들을 개념적으로 정의만 한 것

자료구조: 자료를 저장하는 방법과 자료에 적용할 수 있는 연산을 구체적으로 제공한것

추상적 자료형을 구체적으로 구현한 결과 => 자료구조

03. 배열과 연결 리스트

리스트(List)

리스트라는 이름의 추상적 자료형이 있다.

리스트가 담는 자료

순서가 존재하며, 일렬로 나열된 값들이 들어있다.

리스트가 담는 자료에 적용되는 연산

조회 : 임의의 위치의 자료가 무엇인지 알아본다.

삽입 : 임의의 위치에 자료를 추가한다.
삭제 : 임의의 위치의 자료를 제거한다.

이외에도 다양한 연산이 있다.

# 리스트라는 추상적 자료형을 구현한 대표적인 두 가지 자료구조: 배열, 연결 리스트

배열(Array)

리스트라는 추상적 자료형을 구현한 대표적인 예시가 바로 '배열'이다.

(Python에서는 배열을 리스트라는 이름으로 제공한다.)

배열 - 조회

배열에 저장되는 값들은 순서를 나타내는 번호를 가진다.

이번호를 인덱스라고 부른다.

인덱스는 1이 아닌 0부터 시작하며, 100개의 인덱스가 존재할 때, 인덱스는 0~99까지 존재한다.

배열내의 특정 순서의 값을 조회하고자 할 때 단번에 찾아낼 수 있다.

5번 인덱스의 값은? 2

배열 - 삽입

자료를 추가할 땐 조금 번거롭다.
새로운 자료가 추가되면서, 자료들의 순서를 변경해주어야 하기 때문이다.

3번 인덱스에 10을 추가하자.

우선, 새로운 자료가 들어갈 공간을 마련해주어야 한다.

배열에 들어갈 자료가 하나 늘었으므로 공간도 하나 더 만들어준다.

추가될 자료가 들어갈 공간을 비워주기 위해 기존 자료들은 한 칸씩 밀려나게 된다.

마련된 빈 자리에 추가될 값을 넣어준다.

배열 - 삭제

자료를 제거할 때는 이와 반대로 진행하면 된다.

제거할 인덱스의 자료를 비운다.

자료가 줄어들었으므로, 빈자리를메꾸기위해자료들이한칸씩당겨진다.

배열이 담고 있는 자료가 하나 줄었으므로 남는 공간도 제거한다.

연결 리스트(Linked List)

배열은 각 자료에 인덱스를 붙여 저장하는 반면,
연결 리스트는 여러 개의 '노드'를 저장하는 방식으로 구현한다.

노드는 자료와 포인터를 가진다.

자료는 저장하는 값 자체를 의미하고, 포인터는 자신의 다음 순서의 노드를 가리킨다.

연결 리스트 단점: 조회

연결 리스트 장점: 자료의 추가, 삭제

인덱스를 이용하여 절대적인 순서를 표현하는 배열과는 달리,

연결 리스트는 자신의 다음 노드를 가리키는 상대적인 순서를 표현한다.

연결리스트 - 조회

이러한 특성 때문에, 연결 리스트에서 특정 위치의 자료를 찾는 것이 번거롭다.

배열은 찾는 자료의 위치와 관계없이 항상 단번에 값을 찾을 수 있지만,
연결 리스트는 찾는 자료의 위치가 시작점으로부터 멀수록 연산 횟수가 많아진다.

3번째 값의 자료는? 2

연결 리스트 - 삽입

조회 연산과 마찬가지로 연결 리스트 상에서 n번째 위치를 찾아야 하는 과정은 동일

3번째 위치에 10을 추가하자

추가할 위치의 이전 노드의 포인터를 새로운 노드로, 새로운 노드의 포인터를 이전 노드가 가리키던 노드로 설정한다.

연결 리스트 - 삭제

4번째 위치의 자료를 제거하자

제거할 노드의 이전 노드의 포인터가 제거할 노드가 가리키던 노드를 가리키도록 설정

배열 vs. 연결리스트

	배열	연결리스트
장점	특정 위치의 자료 탐색	자료의 삽입과 삭제
단점	사료의 삽입과 삭제	특정 위치의 자료 탐색

배열과 연결리스트의 장단점이 서료 교차한다.

04. 자료구조의 구현 방법

자료구조의 구현 방법

자료구조는 추상적 자료형에 명시된 표현 및 연산 방법을 구현한다.

객체지향 프로그래밍에서 추상적 자료형은 인터페이스

자료구조는 클래스로생각할수있다.

자료구조를 만드는 데에는 클래스가 탁월하다.

클래스가 갖고 있는 '필드'(멤머변수)가 자료에 해당하고, '메서드'가 자료에 적용할 수 있는 연산이다.

인터페이스: 객체지향 구조에서 추상 메서드만으로 이루어진 설계용 클래스로,

구현 부분이 비어있는 메서드를 추상 메서드라고 하며 상속받는 클래스에서 이를 구현하여 사용한다.

즉, '리스트'라는 인터페이스에는 "삽입과 삭제를 지원해야 한다"라는 명세만 주어지고

실제 동작 부분은 리스트를 상속받은 배열 클래스, 연결 리스트 클래스에서 구현

(Java 등 다른 언어와는 달리 Python에서는 인터페이스 기능을 직접 지원하지는 않으므로 별도의 클래스를 만들어 사용)

자료구조의 구현 예시

import queue q = queue.Queue()

파이썬 기본 라이브러리 중, '큐'라는 자료구조를 구현한 Queue 클래스도 있다.

큐 자료구조의 자료 저장 및 연산 방법을 갖추고 있다.

문제 해결하기

좋은 해법인지 생각해보기

좋은 해법힌지 판단하는 기준은 여러 가지가 있다.

(코드가 간결한가? 얼마나 빠른가? 리소스를 얼마나 차지하는가? 구현 시간이 짧은가?...)

수행하는 명령의 수가 적을수록 시간이 덜 걸린다

시간 복잡도

알고리즘이 문제를 해결하는 데 걸리는 시간을 정량화하여 나타낼 수 있는 방법

일반적으로, 문제에서 주어지는 최악의 경우에 대한 소요 시간을 나타내는 데 사용

(최악의 경우: 문제 해결 시 가장 오래 걸리는 경우)

Big-O Notation(𝑂()): 최악 조건의 시간 복잡도를 의미

자료구조를 공부해야하는 이유

작성하고자 하는 프로그램의 목적을
가장 효율적으로 달성할 수 있는 자료구조를 사용하기 위해서

각 자료구조의 특성과 동작 방법을 제대로 이해하고 있어야 한다.

문재 해결

1. 문제를 파악한다.
   (=어떤자료를담을지,자료에어떤의미가있는지파악)
2. 자료구조에 필요한 기능을 파악한다.
   ( = 자료를 어떻게 사용하는지 파악)
3. 문제를 효율적으로 해결하는 자료구조를 설계 및 사용한다.
   (=목적에맞는자료구조로문제를해결)

조회 활용하기

연결리스트

연결 리스트의 특정 노드를 삭제하기 위해서 그 특정 노드에 접근하는 과정이 필요

연결 리스트의 특성에 의해 특정 원소에 접근하기 위해서는 시작 원소부터 하나씩 따라가야 한다.

연결 리스트는 어떤 노드를 삭제하기 위해서 그 노드의 이전 노드와 다음 노드가 무엇인지 알고 있어야 하기 때문

딕셔너리 활용

이 단점을 개선하기 위해 연결 리스트 내에 딕셔너리를 두고, 모든 노드들의 정보를 저장하고 있도록 한다.

딕셔너리는 내부적으로 해시 테이블이라는 자료구조로 동작하며,

어떠한 key에 대한 value를 𝑂(1)의 시간 복잡도로 접근할 수 있다.

이중 연결 리스트 활용

삭제할 노드를 알아냈다고 해서 끝이 아니다.

삭제할 노드의 다음 노드와 이전 노드를 알아야 하는데,

현재로서는 이전 노드에 접근할 방법이 없다.

노드에 포인터가 두개가 있고
각각 이전 노드와 다음 노드를 가리키는

형태의 연결 리스트를 이중 연결 리스트라고 한다.

이중 연결 리스트를 이용하여 노드를 간편하게 삭제할 수 있다.

조회

배열이든 연결 리스트든,

번호가 주어졌을 때 해당 번호가 몇 번째인지 알기 위해서는

맨 첫 번째 주문부터 하나씩 확인해봐야 한다.

배열이 조회가 빠른 이휴

배열의 요소들은 컴퓨터에서 물리적으로 가깝기 때문이다.

연결 리스트는 각각 별도의 객체들을 임의로 연결하는 방식으로 구현되지만

배열의 경우, 각 요소들이 컴퓨터 내부에서 매우 가깝게 위치하고 있다.

자료를 메모리에 저장하는 방법 - 배열

메모리 상 인접하고 있으니까, 0 번쨰 인덱스에서 1번째 인덱스로 바로 옆칸으로만 이동하면 된다 -> 인덱스 간 이동이 매우 빠르다!

자료를 메모리에 저장하는 방법 - 연결 리스트

포인터에 의해 마음대로 엮어준 것 뿐이다. 별도의 객체를 찾으러 나가기 때문에 배열보다 오래걸릴 수 있다.

따라서 전체 요소를 순회하는 연산 또한 배열이 더 유리하다.

주문 관리 시스템이 처리하는 주문의 양이 같더라도, 주문조회가 많을 때, 적을 때 유리한 자료구조가 각각 있다.

알고리즘이 같더라도 데이터의 처리에 따라 성능이 다르다.

따라서 데이터의 입출력과 문제 상황을 잘 파악하여 적절한 자료구조를 선택해야 한다.

---

해쉬 테이블

해쉬 테이블

각 데이터(value)를 고유한 key에 대응하도록 저장하는 개념

배열의 index를 key로 이용하기

장점
(운 좋으면) 자료의 쓰기 연산이 빠르다.

자료의 읽기 연산이 빠르다.

단점

“자료가 없다”를 표현하는 것이 쉽지 않다. 공간이 지나치게 낭비될 수 있다.

key와 value를 각각 배열에 저장하기

장점

공간의 낭비가 없다.

자료가 없는 경우를 표현할 수 있다.

단점

자료의 읽기(조회) 연산이 느리다.

자료의 쓰기(입력 등) 연산도 느리다.

해쉬(hash)

해시란 임의의 데이터에 해시 함수를 이용하여
고정된 길이의 데이터(문자열 등)으로 변환하는 것을 의미

변환하는 과정 자체를 해싱(hashing), 변환된 값을 해시 값(hash value) 라고도 부른다.

해시를 이용하여 Key-Value Store를 구현할 수 있다.

해시를 이용하여 구현된 Key-Value Store를 해시 테이블(Hash Table),

또는 딕셔너리(Dictionary)라고 한다.

해시 함수의 충돌: 비둘기집의 원리

좋은해시함수는중복되는해시값이최대한없도록하여 되도록 충돌이 발생하지 않는 함수이다.

그러나 해시 함수의 반환값의 경우의 수는 유한하고,

입력값의 경우의 수는 무한하기 때문에 비둘기집의 원리에 의해 충돌은 어쩔 수 없이 발생한다.

해시 - 충돌 해결 방법: 개별 체이닝

Key-Value Store의 각 인덱스를 '연결 리스트'로 만들어서 동일한 인덱스의 값들을 연결하는 방법이다.

해시 - 충돌 해결 방법: 오픈 어드레싱

충돌이 발생했을 때 자료를 저장하기 위해 빈 공간을 탐색하는 방식

따라서 모든 원소가 자신의 해시 값과 일치하는 인덱스에 저장된다는 보장은 없다.

위 예시에서는 Dodo 자료를 저장하기 위해 가장 가까운 빈 공간을 탐색하였고, 그 결과 인덱스 2에 저장하였다.

오픈 어드레싱에서 빈 공간을 찾는 방법은 여러 가지가 있지만

가장 간단하고 대표적인 방법은 '선형 탐사 방식'이다.

앞서 살펴 본 것 처럼,원래 인덱스의 다음 인덱스부터 탐색하여 가장 가까운 빈 공간을 찾는 방법

Python에서는 딕셔너리의 해시 값 충돌이 발생하였을 때 오픈 어드레싱 방식으로 해결하도록 구현되어 있다.