자료구조의 의미

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

자료구조를 배우는 이유:
자료구조에 따라 장단점이 존재하며 구현하고자 하는 프로그램의 성능을 고려하여 알맞은 자료구조를 선택해야 한다. 프로그램의 자료를 효율적으로 담고 활용하기 위해 사용한다.

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

추상적 자료형

어떤 자료와 그 자료에 대한 연산(동작)들의 수학적인 정의를 의미한다. 그러나, 그 정의를 구현하는 방법은 정확하게 명시되어 있지 않다.
추상적 자료형의 추상적이라는 단어의 의미에서 알 수 있듯 명확하지 않은 것이다.

자료형

자료형은 어떤 자료가 식별될 수 있는 방법과, 그 자료에 대한 여러 가지 연산을 제공한다.

65라는 자료는 그대로 수를 나타낼 수도 있고 유니코드로 해석한 'A'를 나타낼 수 있다.
따라서 이를 컴퓨터가 해석하기 위해서는 자료형을 명시해주어야 하는 것이다.
만일 수를 나타내는 자료형이라면 사칙연산이 가능하나, 문자의 경우 사칙연산을 적용할 수 없다.

자료형은 어떤 자료가 식별되는 방법을 정의하고, 자료에 적용할 수 있는 연산을 결정한다.
자료를 특정 분류에 따라 올바르게 표현하기 위한 정의와 이의 구현이 자료형이라고 할 수 있다.

추상적 자료형

추상적 자료형은 구현 방법을 명시하고 있지 않다는 점에서 구별된다.

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

그릇이 음식을 담고, 그 그릇에 담긴 음식을 먹을 수 있어야 하듯, 추상적 자료형 또한 자료를 담고 연산을 할 수 있어야 한다. 그러나, 어떻게 자료에 접근할 수 있는 지에 대한 방법은 주어지지 않는다.

여기서 추상적 자료형에 자료를 어떻게 저장하고, 연산을 할 수 있는 지에 대해 명확히 구현된 것을 자료구조라고 할 수 있다.

정리

• 추상적 자료형: 자료들과, 그 자료에 대한 연산들을 개념적으로 정의만 한 것
• 자료구조: 자료를 저장하는 방법과 자료에 적용할 수 있는 연산을 구체적으로 제공한 것

추상적 자료형을 구체적으로 구현한 결과가 자료형이라고 할 수 있다.

배열과 연결 리스트

주의 파이썬의 리스트와 자료구조에서의 리스트는 다른 개념이다.

리스트

리스트는 순서가 존재하고 일렬로 나열된 값을 가진 추상적 자료형이다.

리스트가 제공하는 대표적 연산:

• 조회: 임의의 위치의 자료가 무엇인지 탐색.
• 삽입: 임의의 위치에 자료를 추가.
• 삭제: 임의의 위치에 자료를 제거.

리스트라는 추상적 자료형을 구현한 대표적인 예시가 배열(array)이다

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

let array = [1,2,3,4,5,6]; //index: 0,1,2,3,4,5

배열 - 조회

배열은 배열 내의 특정 순서의 값을 조회하고자 할 때, 효율적이고 빠른 연산을 할 수 있다.

배열 - 삽입

반면, 자료를 추가할 때에는, 새로운 자료가 추가되면서, 자료들의 순서를 변경해주어야 하기 때문에 번거롭다.
삽입 연산에서는 추가된 자료가 들어갈 공간을 비워주기 위해, 기존 자료는 한 칸씩 밀려나게 된다.

배열 - 삭제

삽입과 반대로, 제거할 인덱스의 자료를 비우고 자료가 줄어들었으므로 빈자리를 메꾸기 위해 자료들이 한 칸씩 당겨진다. -> 배열이 담고 있는 자료가 하나 줄었으므로, 남는 공간도 제거한다.

연결 리스트 (Linked List)

리스트를 구현한 자료구조 중, 대표적인 다른 자료구조는 연결 리스트이다.
배열은 각 자료에 인덱스를 붙여 저장하나, 연결 리스트는 여러 개의 노드를 저장하는 방식으로 구현한다.

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

연결 리스트 - 탐색

연결 리스트는 이러한 특성으로 특정 위치의 자료를 찾는 것이 번거롭다. 찾고 싶은 자료를 찾으려면, 첫 번째 노드부터 차례로 포인터를 통해 이동하며 탐색해야 하기 때문이다.

따라서, 연결 리스트는 찾는 자료의 위치가 시작점으로부터 멀어질 수록 연산 횟수가 많아진다.

연결 리스트의 장점은, 자료의 추가와 삭제에서 드러나는데,

연결 리스트 - 삽입

연결 리스트에서 노드를 삽입할 때에는, 이전 노드의 앞 뒤 노드의 포인터 관계를 끊은 후, 추가할 위치의 이전 노드의 포인터를 새로운 노드로, 새로운 노드의 포인터를 이전 노드가 가리키전 노드로 설정하면 추가할 수 있다.

연결 리스트 - 삭제

연결 리스트의 삭제는, 제거할 노드의 이전 노드의 포인터가 제거할 노드가 가리키던 노드를 가리키도록 설정하면 삭제할 수 있다.
연결 리스트는 자신의 다음 노드를 가리키는 상대적인 순서를 표현하기 때문에, 이와 같은 연산이 가능하다.

배열

• 장점: 특정 위치의 자료 탐색이 유리
• 단점: 자료의 삽입과 삭제에서 효율이 낮음

연결 리스트

• 자료의 삽입과 삭제가 유리
• 특정 위치의 자료 탐색이 번거로움

자료구조의 구현 방법

자료구조는 추상적 자료형에 명시된 표현 및 연산 방법을 명시한다.
객체지향 프로그래밍을 예로 들면, 추상적 자료형은 인터페이스, 자료구조는 클래스로 생각할 수 있다.

인터페이스란?

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

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

즉, '리스트'라는 인터페이스에는 삽입과 삭제를 지원해야 한다라는 명세만 주어지고,
실제 동작 부분은 리스트를 상속받은 배열 클래스, 연결리스트 클래스에서 구현해야 한다.

Python의 인터페이스 예

class MyInterface(metaclass=Xmeta): # 추상 클래스로 만들기 위한 메타클래스 정의
	@abstractmethod # 추상 메서드임을 나타내는 데코레이션
    def func() :
    	pass

Java 등 다른 객체지향형 언어와는 달리 Python에서는 인터페이스의 기능을 직접 지원하지 않는다.
따라서 위와 같은 방식으로 표현해야 한다.

자료구조를 만드는 데에는 인터페이스가 상속받는 클래스가 탁월하다.
클래스가 갖고 있는 필드가 자료에 해당하고, 메서드가 자료에 적용할 수 있는 연산이다.

자료구조의 구현 예시

import queue
q = queue.Queue()

파이썬의 기본 라이브러리 중, queue라는 자료구조를 구현한 Queue클래스가 있다.
큐 자료구조의 자료 저장 및 연산 방법을 갖추고 있는 클래스이다.

컨테이너란? : 리스트,튜플, 딕셔너리 등의 하나 이상의 요소를 담을 수 있는 자료형이다.
내부적으로 Container 클래스를 상속받은 sub class에 해당한다.

예를 들어, 최댓값을 반환하는 작업을 위한 컨테이너는 다음의 연산을 수행하는 메서드를 갖는다.

1. 정수를 컨테이너에 추가
2. 정수를 컨테이너에서 제거
3. 컨테이너 내의 정수 중 최댓값 반환

자료구조 구현해보기

자료구조를 활용하여 좋은 해법인지 판단하는 몇가지 기준은

• 코드가 간결한지 (유지보수/해석 용이)
• 얼마나 빠른지 (시간 효율)
• 리소스를 얼마나 차지하는 지 (공간/메모리 효율)
• 구현 시간이 짧은가 (시간의 경제성)

  얼마나 빠른가

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

   sum = 0
   for i in range(30):
   	sum = sum + 1

  sum = 0
  for i in range(300000):
  	sum = sum + 1

  위의 코드가 아래 코드 보다 적은 수로 반복하여, 시간이 덜 걸린다.

시간 복잡도

알고리즘이 문제를 해결하는 데 걸리는 시간을 정량화하여 나타낼 수 있는 방법
일반적으로 문제에서 주어지는 최악의 경우(Big O notation)에 대한 소요시간을 나타내는 데 사용된다.

배열을 사용할 경우, 요소 n개를 모두 왼쪽으로만 삽입하는 경우가 최악의 경우이다. 요소의 수가 n개라면,
* (n(n+1))/2 의 시간복잡도이며, 최악의 경우이다.

연결 리스트를 사용할 경우, 요소 n개를 모두 왼쪽으로 상입하면 이전 노드 앞에 n번 만큼 첫 번째 노드를 만들어 연결만 해주면 되므로, O(n)의 시간 복잡도를 가진다.

마지막으로, 이 때문에 자료 구조를 공부해야 하는 이유는 자료구조에 따라 특성과 동작방법이 다르기 때문에 작성하고자 하는 프로그램의 목적을 가장 효율적으로 달성할 수 있는 자료구조를 사용하기 위해서 이다.

문제 해결을 위한 자료구조 활용

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

자료를 잘 저장하는 다는 것은?

구현하고자 하는 프로그램의 의도에 맞는 자료구조를 사용해서, 효율적인 성능으로 구현하는 것을 의미한다.