[CS] 자료형/자료구조

CS (Computer Science, 컴퓨터 과학)

 

자료형 (data type)

: 프로그래밍에서 값이 가질 수 있는 데이터의 종류. 데이터가 저장되는 형식.

자료형을 통해 컴퓨터는 해당 값이 어떻게 해석되고 처리되어야 하는지 알 수 있다.

 

 

주요 자료형 (8가지)

1. 정수형 (integer)

: 정수값을 저장함

5, -3, 100
# <class 'int'>

 

2. 실수형 (float)

: 실수값, 즉 소수점을 포함한 값

-0.5, -2.0, 3.141592
# <class 'float'>

 

3. 문자열 (string)

: 문자들의 집합. 큰따옴표나 작은따옴표로 싸인 텍스트

"hi", 'dino'
# <class 'str'>

 

4. 불리언 (boolean)

 : 논리연산에서 사용됨

True, False
# <class 'bool'>

 

5. 리스트 (list) 

: 여러 값을 순서대로 저장함. 대괄호 []로 감싸고 값은 쉼표로 구분

[1, 2, 3], ['A', 'B', 'C']
# <class 'list'>

 

6. 튜플 (tuple)

: 리스트랑 비슷하지만, 값을 변경할 수 없음. 소괄호 ()로 감싸고 값은 쉼표로 구분

(1, 2, 3), ('A', 'B', 'C')
# <class 'tuple'>

 

7. 딕셔너리 (dictionary)

: 키-밸류 쌍으로 이루어짐. 중괄호 {}로 감싸고 키와 밸류는 콜론 : 으로 구분한다. 값의 중복은 상관없지만 키는 중복되면 안됨.

{'name': 'dino', "age": "25"}
# <class 'dict'>

 

8. 집합 (set)

: 중복되지 않는 값들의 모임. 중괄호 {}로 감싸고 순서가 없음.

{1, 2, 3}, {'A', 'B', 'C'}
# <class 'set'>

 

 

---

 

자료구조 (data structure)

: 데이터를 효율적으로 저장하고 관리하기 위해 어떤 논리나 규칙으로 자료를 모아 놓은 구조.

 

 

1. 선형구조 (Linear structure)

• 자료들 간에 관계가 1:1로 순차적으로 나열되어 있는 것을 의미
• 데이터가 일직선, 연속적으로 배치되어 있는 형태
• 각 요소는 하나의 앞 요소와 뒤 요소만을 가짐

 

1-1. 배열 (Array)

가장 일반적이다. 메모리 상에 '같은 타입의 자료'가 연속적으로 저장된다.

ex) [1, 2, 3, 4, 5] 는 메모리에 연속적으로 배치된 '정수'들의 모임

 

: 너 메모리상에 오른쪽에 있는거 가져와. 하면 가져옴. 메모리상에 물리적인 위치가 순차적임.

 

 

1-2. 리스트

메모리상에 임의의 위치에 데이터를 저장하지만 각 데이터들이 앞뒤 관계를 갖게 하는 방법

 

-> 파이썬에서는 사실 배열과 리스트를 구분해서 쓰고있지 않음. 사실상 리스트로 거의 쓰고잇다.

: 메모리상에 오른쪽 가져와. 하면 이상한거 가져옴. 논리적인 구조가 연결되어있다.

 

 

1- 3. 스택

히스토리에서 사용됨.

선입후출 방식의 자료구조, 선입후출(후입선출)이란 먼저 들어온 데이터가 나중에 처리되는 것을 의미.

스택은 히스토리 기능을 구현할때 유용하고 DFS(깊이우선탐색), 후위연산, 백트래킹, 유효성검사 등 다양한곳에 사용됨.

 

 

1- 4. 큐

선입선출 방식의 자료구조, 선입선출이란 먼저들어온 데이터를 먼저 처리하는 것을 의미

큐는 작업스케줄링 기능을 구현하거나 캐시, BFS(넓이우선탐색), 티켓 시스템 등 다양한곳에서 사용.

 

 

 

2. 비선형구조

• 비선형 구조란 자료들 간에 관계가 1:N로 나열되어 있는 것을 의미.
• 예를 들어 집안 가계도나 회사 구조같은 것들이 비선형 구조에 해당함.

 

2-1. 그래프

노드(요소)와 간선으로 이루어진 자료 구조를 의미

네트워크. 망형...? 노드랑 간선 존재함. SNS

위 그림처럼 그래프는 무방향 그래프, 방향 그래프, 가중치 그래프 이렇게 3가지가 있으며 방향과 가중치를 모두 갖는 그래프도 있음.

 

 

2-2. 트리

트리는 그래프의 한 종류이며 나무의 가지나 뿌리가 뻗어나는 모양과 비슷하다고 하여 붙여진 이름

트리의 특징으로는 일반 그래프와는 다르게 사이클이 존재하지 않으며 부모노드와 자식노드를 통해 구조를 표현

 

트리 (tree)

• 이진트리: 각 부모노드의 자식노드가 최대 2개인 트리
• 포화이진트리: 이진트리에서 모든 부모가 2개의 자식노드를 갖는 이진트리
• 완전이진트리: 이진트리에서 거의 모든 노드가 채워져 있으며 가능한한 제일 왼쪽부터 채워져 있는 이진트리
• 편향이진트리: 한쪽으로만 자식을 갖는 트리

노드 (node)

• 루트노드: 제일 상단에 있는 노드
• 부모노드: 자식노드를 갖는 노드
• 자식노드: 부모노드를 갖는 노드
• 자손노드: 부모노드 하위에 있는 모든 노드

싸이클이 하나라도 생기면 그래프임. 

제일 상단 노드가 Root

부모-자식노드는 상대적인 개념이다. B는 A에게는 자식노드고, E와 D에게는 부모노드임.

바로 하위 노드가 자식노드임. A의 자식노드 : B, C

자신의 밑에 있는 모든 노드는 자손노드임. F, G는 B의 자손노드는 아님.

자식을 최대 두개까지만 갖고 있는 트리.(한개가져도 되고 안가져도 됨.)

ex) [A, [B, [D, E]], [C, [F]]]

- 편향트리 : [A, [B, [C]]]. 리스트랑은 다름. 리스트는 [A, B, C]

- 포화 이진트리 : 자식이 둘이던가 아예 없던가

- 완전 이진트리 : 왼쪽에서부터 자식이 꽉차있는 트리

만약 저 그림에서 F 없어도 완전이진트리. E가 없으면 그냥이진트리.

D 아래에 노드가 생겨도 왼쪽부터 꽉차있는건 맞으니 완전이진트리.

쓰는 이유: 중위순회할때.  없는 곳은 방문 안해서 단축하려고 쓰는거

 

 

---