배열, 연결리스트

강정우·2022년 7월 9일

자료구조

algorithm

목록 보기

9/28

1. 자료구조의 의미

자료구조란 : 자료를 저장하는 구조. 여러가지 종류가 있으며 저장된 자료에 대해 접근하는 방법등의 차이가 존재한다.
프로그램에 필요한 자료들을 효율적으로 담기 위해 공부.
프로그램에서 특정 알고리즘을 구현하기 위해 적절한 자료구조를 사용해야 좋은 성능을 낼 수 있다.

2. 추상적 자료형

추상적 자료형이란 : 어떤 자료와 그 자료에 대한 연산(동작)들의 수학적인 정의를 의미한다. 그리고 그 정의를 구현하는 방법은 명시되어있지 않다.
일단 자료형이란? : 자료형은 어떤 자료가 식별될 수 있는 방법과, 그 자료에 대한 여러가지 연산(동작)을 제공하는 것이다.
자료형은 어떤 자료가 식별되는 방법을 정의하고 자료에 적용할 수 있는 연산을 결정한다. 또한 자료를 특정 분류에 따라 올바르게 표현하기 위한 정의와, 그 그현이 바로 자료형이라고 할 수 있다.
추상적 자료형은 구현 방법을 말 그대로 정확히 명시하고 있지 않다는 것이다.
추상적 자료형을 구체적으로 구현한 결과가 자료구조

3. 배열과 연결 리스트

여기서 나오는 리스트는 python의 리스트가 아니다.
따라서 리스트가 더 큰 개념이며 리스트의 대표 자료형이 배열(python의 list)이다.
배열의 삽입 및 삭제 : 우선 배열 길이를 +1 해준다 -> 추가할 index를 제외한 뒷번호의 index를 모두 한칸씩 뒤로 미룬다 -> 추가할 index에 번호를 추가한다.
단점: 자료의 삽입과 삭제
장점 : 찾는 자료의 위치와 관계 없이 항상 단번에 값을 찾을 수 잇다.
링크드 리스트 : 모든 값은 노드이고 다음 노드를 가르키는 포인터를 갖고있다.
단점 : 특정 위치의 자료를 찾는 것이 번거롭다. 찾는 자료의 위치가 시작점보다 멀수록 연산 횟수가 많아진다.
장점 : 자료의 추가와 삭제가 매우 빠르다. 왜냐 포인터의 위치만 바꾸면 되기 때문.

4. 자료구조의 구현 방법

추상적 자료형은 인터페이스 느낌 자료구조는 그것을 구현한 클래스 느낌
java는 interface가 있지만 python은 없기에 meta class를 따로 넣어주어야 함.
자료구조는 추상적 자료형에 명시된 표현 및 연산방법을 구현한다.
클래스의 필드 == 자료, 메서드 == 연산 느낌이다.
python의 기본 라이브러리 중 Queue 클래스도 있다. 이는 큐 자료구조의 자료 저장 및 연산 방법을 갖추고 있다.
여러 정수를 담을 수 있는 컴테이너를 가져야함.(container는 list, tuple, dictionary처럼 하나 이상의 요소를 담을 수 있는 것이다. 내부적으로 container class를 상속받은 sub class에 해당한다.)

*최댓값 기계에 대한 구현은 따로 post 하겠음.

5. 구슬 넣기 문제 해결하기 및 문제해결 능력

추상적 자료형은 구현 방법을 지정하지 않는다.
좋은 해법인지 판단하는 기준은 여러개가 있다.
1.코드가 간결한가?
2.얼마나 빠른가? (가장 중요!!)
3.리소스를 얼마나 차지하는가?
4.구현시간이 짧은가?... etc...
시간 복잡도(최악조건의 시간 복잡도 == Big-0 Notation)
알고리즘이 문제를 해결하는데 걸리는 시간을 정량화하여 나타낼 수 있는 방법, 일반적으로 문제에서 주어지는 최악의 경우에 대한 소요시간을 나타내는 데 사용한다.
1.문제를 파악한다.
2.자료구조에 필요한 기능을 파악한다.
3.문제를 효육적으로 해결하는 자료구조를 설계 및 사용한다.

6. 주문관리 시스템 문제 해결하기

이것을 통해 배울 수 있는 것은 주문이 많은가 적은가에 따라 적절한 자료구조를 사용해야 한다는 것이다.

위 사진은 시간 복잡도를 나타낸 것이다. 것으로 보기엔 비슷해 보이는데 차이는 실제 구동해보면 시간 차이가 매우 심하다. 이는 연결 리스트의 성질때문인데 앞서 설명한 것 처럼 삭제 할 때 처음부터 계속 조회를 하기 때문이다.
딕셔너리 활용
이를 개선하기 위해 연결 리스트내에 딕셔너리를 활용한다. 딕셔너리는 내부적으로 해시 테이블이라는 자료구조로 동작하며 어떠한 key에 대한 value를 O(1)의 시간 복잡도로 접근할 수 있다.
이는 삭제할 때 key를 이용하여 바로 접근할 수 있는데 문제는 삭제 후 이전, 이후 노드들을 이어주어야 한다. 이를 보완하기 위해 또 이중 연결 리스트라는 개념이 있는데 이것은 포인터를 앞뒤로 쓰는 개념이다.
주문 조회는 배열이 유리하고 주문의 삭제, 삽입은 연결리스트가 유리하다 따라서 어떤 작업이 많냐에 따라 유리한 자료구조를 사용해야 한다.

7. 해시 테이블

해시(hash)란 임의의 테이터에 해시함수를 이용하여 고정된 길이의 데이터(문자열 등)로 변환하는 것을 의미한다.
변환하는 과정 자체를 해싱, 변환된 값을 해쉬 값 라고도 부른다.
python 내장함수의 해싱 예시
파이썬 내장함수 hash()를 이용하여 임의의 값의 해시 값(정수)을 알 수 있다. 파이썬의 hash() 함수는 보안을 이유로 프로그램을 실행할 때마다 반환값이 달라진다.
해시를 이용하여 구현된 key-value store를 해시 테이블 또는 딕셔너리라고 한다.
좋은 해시함수는 중복되는 해시값이 최대한 없도록 하여 되도록 충돌이 발생하지 않는 함수이다.
그러나 해시 함수의 반환값의 경우 수는 유한하고, 입력값의 경우의 수는 무한하기 때문에 비둘기집의 원리에 의해 충돌은 어쩔 수 없이 발생한다.
비둘기집의 원리란? : n개의 비둘기 집에 (n+1)마리 비둘기를 한 집에 한 마리씩 넣는 것은 불가능하다는 원리를 말한다. 당연하가 n마리여야 가능한 전재이다.
그래서 해시충돌 해결방법으로 등장한 개념이 개별 체이닝!
key-value store의 각 인덱스를 '연결 리스트'로 만들어서 동일한 인덱스의 값들을 연결하는 방법이다. 아래 예에서는 동일한 인덱스(1)를 갖는 Elice와 Dodo 자로를 서로 연결하였다.
Linear Probing
해쉬 테이블 저장공간 안에서 충돌 문제를 해결하는 기법
오픈 어드레싱(open addressing)
충돌이 발생했을 때 자료를 저장하기 위해 빈 공간을 탐색하는 방식.
따라서 모든 원소가 자신의 해시 값과 일치하는 인덱스에 저장된다는 보장은 없다.
오픈 어드레싱에서 빈 공간을 찾는 방법은 여러가지가 있다. 하지만 간당하고 대표적인 방법은 선형 탐사 방식이다.
원래 인덱스의 다음 인덱스부터 탐색하여 가장 가까운 빈 공간을 찾는 방법이다.