[CS] 컴퓨터 기초 - 자료구조

자료구조란 데이터를 구조화하는 수단을 의미한다.
자료구조의 유형은 배열, 리스트, 스택, 큐, 트리가 있다.
컴퓨터의 메모리는 셀들로 구성되어 있다. 메모리 셀은 메모리 주소와 내용을 가지며, 메모리 주소는 연속적으로 구성된다.
각각의 자세한 설명은 아래 링크를 참고하자.

 

'Programming/DataStructure' 카테고리의 글 목록

 

배열

가장 간단한 메모리 자료구조이다.
일련의 연속적인 메모리 셀들로 구성된다.
메모리 셀들은 동질적인 데이터를 저장한다.
많은 수의 비슷한 항목에 대해서 하나의 변수 이름을 사용한다.

 

배열의 동작방식

선언은 각 언어 별로 다르다. JAVA의 경우 데이터 유형과 크기를 제공한다.
JAVA의 예시 int[] test = new int[5];

• int[]는 컴퓨터에게 배열이 정수를 보관함을 알려준다.
• test는 배열의 이름이다.
• new 키워드는 새로운 배열이 생성되는걸 명세한다.
• int[5]는 5개의 메모리 장소를 확보한다.

 

다차원 배열

다차원 배열은 둘 또는 그 이상의 1차원 배열로 구성된다.
각행의 위에 여러 행들이 쌓여 있다.
정의는 int[][] test2 = new int[3][3]; 식으로한다. (JAVA)
지정은 test2[1][1] = 1; 식으로 한다. (1을 2번째 행의 2번째 열에 놓는다.)

 

배열의 장점으로는 메모리 셀의 순차 접근을 허용하며, 구현이 쉽다는 점이 있다.
단점으로는 클래스와는 다르게 이질적인 항목들을 저장할 수 없다. 또한 동적인 메모리 할당이 불가능하고, 정렬되어 있지 않은 배열의 탐색은 효율적이지 않다.

 

리스트

리스트는 동적인 자료구조이다. 데이터의 양이 알려져 있지 않거나 변화할 수 있는 경우에 적절하다.
기본적인 세가지의 리스트 형태는 링크드 리스트, 스택, 큐가 있다.

 

링크드 리스트

링크드 리스트는 가변 데이터 집합을 위해 사용되는 구조를 말한다. 배열과는 다르게 데이터를 불연속적으로 저장하며, 데이터와 다음에 연결된 셀의 주소를 관리한다.
링크드 리스트는 고급자료구조의 기본이다. 각각의 구조들은 포인터에 기반한다. (포인터란 메모리 위치를 가리키는 메모리 변수를 의미한다.)
마지막 포인터 값은 null이다.
새로운 원소를 삽입시 배열과 다르게 크기 조정이 필요가없다. 데이터와 포인터를 가진 새로운 노드를 만든후 포인터를 조정해주면된다.
항목을 삭제할때도 유사한 과정을 거친다. 원소를 이동시키지 않고 리스트로부터 노드를 제거한다.

 

스택

스택은 특별한 형태의 리스트이다. 새 항목의 저장을 위해 리스트에 push하고 현재 항목의 검색을 위해 리스트로부터 pop한다.
LIFO(Last In First Out)의 자료 구조이다. 스택에 처음 push된 항목이 가장 나중에 pop된다.
Stack Pointer는 스택의 top을 나타낸다.

 

큐

큐는 다른 유형의 연결리스트이다.
FIFO(First In First Out)의 자료 구조이다. 삽입은 큐의 끝에서 이루어지며 삭제는 처음에서 이루어진다.
헤드 포인터는 큐의 시작을 유지하며, 테일 포인터는 큐의 끝을 유지한다.
큐에 넣는걸 enqueue라고 하며 큐에서 빼는걸 dequeue라고 한다.

 

트리

트리는 조직도나 가계도와 유사한 계층 자료 구조이다.
트리내의 각 장소는 노드라고 하며, 트리의 시작 노드는 루트라고한다.
노드들 사이에는 부모-자식 관계가 있다. 자식이 없다면 리프 노드라고한다.
깊이는 루트 노드로부터의 거리를 나타낸다.

 

이진 트리

이진 트리는 트리의 한 유형이다.
부모 노드는 0,1,2 개의 자식 노드를 가질 수 있다.
자식은 왼쪽, 오른쪽으로 구분된다.
이진 탐색 트리는 이진 트리의 한 종류이다.
왼쪽 자식 노드의 데이터 값은 부모 노드의 값보다 작고 오른쪽 자식 노드의 데이터 값은 부모 노드의 값보다 크다.

 

선택 정렬

선택 정렬이란 수작업 정렬 과정을 흉내 낸 정렬이다.

과정은 아래와 같다.

• 리스트에서 최소값을 찾는다.
• 첫 번째 위치에 있는 항목과 교환한다.
• 두 번째 위치로 이동한다.
• 줄어든 리스트를 대상으로 과정을 반복한다.
• 마지막 항목의 바로 이전 항목까지 과정을 진행한다.

 

버블 정렬

가장 오래된 정렬 방법 중 하나이다.

과정은 아래와 같다.

• 리스트 내의 마지막 원소부터 시작한다.
• 이 원소의 값을 바로 위 항목의 값과 비교한다.
• 만일 더 작다면 위치를 변경하고 리스트의 위를 계속한다.
• 더 작은 항목이 발견될 때까지 비교를 계속한다.
• 더 작지 않으면 다음 항목을 그 위의 항목과 비교한다.
• 가장 작은 값이 꼭대기로 올라갈 때까지 검사를 반복한다.
• 처음 항목이 제외된 리스트에 대해서 과정을 반복한다.