정보처리기사 필기 준비하며 정리한 내용입니다.
자료구조
- 개념
- 자료들을 한정적인 공간에 효율적으로 저장 및 처리하는 모든 작업.
- 빠르게 찾을 수 있게 된다! 시간 단축
- 특징
- 효율성
- 추상화
- 재사용성
자료구조의 분류 ⭐
- 선형 구조 : 데이터들이 연속적으로 있는 구조
- 리스트
- 선형 리스트
- 연결 리스트
- 스택
- 큐
- 데크
- 리스트
- 비선형 구조 : 연속적X
- 트리 : 사이클 발생X
- 그래프 : 사이클 발생 O
- 트리와 그래프가 비선형 구조라는 것을 알아두자!
선형 구조
배열 Array = list
- 논리적으로도, 메모리상에 올라간 상태로도(물리적으로도) 이어져있다.
- 자료형과 기억 공간의 크기가 같다.
- 연속적, 순서적 (논리, 물리적으로도!)
리스트
- 선형 리스트
- 배열과 똑같은 형태
- 연속적인 기억장소에 저장된다
- 장점
- 저장 효율 뛰어남
- 접근 속도 빠름
- 간편한 자료구조
- 단점
- 자료의 삽입, 삭제가 어려움
- 연결 리스트 Linked List
- 삽입 삭제를 쉽게 하기 위함!
- 데이터영역에 데이터 저장시킴(임의의 공간에), 위치값을 포인터영역에 넣는다. (각 노드의 포인터 부분을 이용해 연결한다)
- 각 노드는 데이터 저장공간 * 다음 노드 가리키는 링크pointer 정보를 가진다
- 마지막 노드는 다음 공간이 없으니 Null 값을 가진다
- 각 노드는 데이터 저장공간 * 다음 노드 가리키는 링크pointer 정보를 가진다
- 데이터영역에 데이터 저장시킴(임의의 공간에), 위치값을 포인터영역에 넣는다. (각 노드의 포인터 부분을 이용해 연결한다)
- 장점
- 선형리스트와 반대로 삽입 삭제가 용이하다
- 포인터 주소값만 변경하면 되니까!
- 희소행렬 표현할 때 기억장소 이용효율이 좋다
- 희소행렬 = 0이 많은 것
- 선형리스트와 반대로 삽입 삭제가 용이하다
- 단점
- 데이터 저장공간의 낭비는 있다!
- 포인터를 위한 추가 공간이 필요해서
- 중간에 연결 끊어지면 다음 노드 찾기 어려움
- 인터 찾는 시간이 필요해서 시간이 좀 걸린다
- 데이터 저장공간의 낭비는 있다!
- 종류
- 단순 연결 리스트 (단방향)
- 한 방향으로만 연결되어 있는 리스트 (단순)
- 단순 연결 환형 리스트
- 위와 비슷하지만 가장 끝 노드가 제일 앞의 노드를 가리킨다
- 환형 = 뱅글뱅글 동그라미
- 이중 연결 리스트 (양방향)
- 양쪽으로 연결되는 것
- ←→ 두개의 포인터
- 첫, 마지막 노드 Null값
- 이중 연결 환형 리스트
- 위와 같은데 첫 마지막 노드가 서로를 가리킨다
- 단순 연결 리스트 (단방향)
스택
- 드럼통 같은 구조. 쌓인다! 맨 아래에 있는 걸 빼기가 어렵지
- 한 방향으로만 자료의 삽입과 삭제가 일어나는 자료 구조
- 후입선출 Last in First Out 구조 (맨 나중에 들어온게 맨 먼저 빠진다)
- 삽입은 push 연산
- 삭제는 pop연산
- Top이라는 포인터가 있다 (스택 공간의 위치를 가리킨다!)
- 후입선출 Last in First Out 구조 (맨 나중에 들어온게 맨 먼저 빠진다)
- 한 방향으로만 자료의 삽입과 삭제가 일어나는 자료 구조
- 용어들
- Overflow 스택이 가득 차 있을 때 Push 수행 시 발생
- Underflow 스택이 비어있을 때 Pop 연산 수행 시 발생
- 스택의 용도 ⭐
- 인터럽트 처리
- 수식의 계산
- 서브루틴의 복귀번지 저장
- 웹 브라우저 방문기록
- 재귀호출
- 깊이 우선 탐색
- 스택의 삽입 삭제 알고리즘 ⭐
- 삽입
- 처음 Top = Top + 1
- 삭제
- 마지막에 Top = Top - 1
- 삽입
큐 Queue
- ← 줄서기 구조 ←
- 한쪽끝에서 삽입, 반대쪽 끝에서 삭제가 이루어진다.
- First in First Out 선입선출 구조
- 통상적으로 삽입에 enQueue연산, 삭제에 deQueue 연산을 이용
- 포인터 2개
- enQueue연산 시 rear 포인터
- deQueue연산 시 front 포인터 이용
- 포인터 2개
- 용도
- 너비 우선 탐색
- 인쇄작업 대기목록
- 프로세스 관리
데크
- 입력 삭제가 양쪽 끝에서 모두 발생할 수 있는 자료구조
- Stack과 Queue의 장점을 뽑아 구성됨
- Scroll 입력제한 데크
- 입력은 한쪽 출력은 양쪽
- 스마트폰 스크롤하는동안 다른 입력을 못한다는 걸 기억해두자!
- 입력은 한쪽 출력은 양쪽
- Shelf 출력제한 데크
- 입력은 양쪽 출력은 한쪽
비선형 구조
트리 : 사이클 발생X
- 트리의 개념
- 노드가 하나 이상의 자식을 가지는 것
- 트리의 용어들
- 노드 : 기본 구성 요소
- 근 노드 Root Node 뿌리 노드 : 가장 상위에 위치한 시작 노드
- 레벨 : 근노드 기준으로 특정 노드까지의 경로 길이
- 깊이
- 조상 노드 : 특정 노드에서 루트에 이르는 경로상의 노드
- 자식 노드 : 특정 노드에 연결된 다음 레벨의 노드
- 부모 노드 : 이전 레벨 노드
- 형제 노드 : 같은 부모
- 깊이 : 최대 레벨
- 차수 ⭐
- (특정 노드의) 차수
- 자식을 낳은 숫자
- 트리의 차수
- 이 트리에서 가장 자식을 많이 낳은 개수 (최대 차수)
- (특정 노드의) 차수
- 단말 노드 = Terminal Node, Leaf Node : 가장 마지막에 있는 노드 (자식을 낳지 않은)
- 트리의 순회 방법 ⭐
- 전위 순회
- 부모를 먼저 방문
- 중위 순회
- 부모를 중간에 방문
- 후위 순회
- 부모를 마지막에 방문
- 전위 순회
- 트리의 종류
- Binary Tree 이진 트리
- 차수가 2 이하 (최대 자식수가 2개까지)
- 깊이가 H인 이진 트리의 최대 노드 수는 2^H-1
- 1을 빼는 이유는 근 노드는 하나니까
- 특정 레벨 L의 최대 노드수는 2(L-1)
- Complete Binary Tree 완전 이진 트리
- 마지막 레벨을 제외하고 모든 노드가 채워진 트리
- 중간에 노드가 비어있으면 안된다
- 모든 노드들이 레벨별로 왼쪽부터 채워져있으면 완전 이진 트리!
- Binary Search Tree 이진 탐색 트리
- 정렬된 이진 트리
- 효율적 탐색 능력 유지 + 빈번한 입력 삭제 가능하게 고안된 트리
- 노드 안의 데이터가
- 왼쪽 노드와 그 이하 차일드들은 현재 노드보다 작아야하고
- 오른쪽 노드와 그 이하 차일드들은 현재 노드보다 커야 한다.
- 따라서 노드보다 작은값←왼쪽, 큰값→오른쪽
- 어떤 값을 찾을 때 그 값보다 작은지 큰지 판단하고 방향 정하면 된다!
- 이것이 이진탐색
- 어떤 값을 찾을 때 그 값보다 작은지 큰지 판단하고 방향 정하면 된다!
- 정렬된 이진 트리
- Balanced Binary Tree 균형 이진 트리
- 너무 지나치게 치우쳐 있지만 않으면 된다
- 종류
- red-black tree
- AVL tree
- 자기가 알아서 스스로 균형을 잡는 이진 탐색트리
- 탐색시간이 가장 빠르다
- Unbalanced Binary Tree 편향 이진 트리
- 한쪽 방향으로만 쏠려있는 것
- Full Binary Tree 포화 이진 트리
- 모든 레벨에서 모든 노드가 채워진 트리
- 모든 레벨 L의 노드 수 2(L-1)
- ⭐ 영어쪽 개념과 다르다고 하니 정처기 용으로만 이렇게 기억해두자.
- B 트리
- 데이터베이스에서 널리 사용된다.
- Binary Tree 이진 트리
그래프 : 사이클 발생 O
- 그래프의 개념
- G = (V, E) 버텍스와 엣지의 집합이다
- Vertex 정점 : 노드들의 집합
- Edge 간선 : 정점들 사이의 상호 연결의 집합
- G = (V, E) 버텍스와 엣지의 집합이다
- 그래프의 최대 간선Edge수
- 무방향 그래프
- n개의 Vertex정점으로 구성된 무방향 그래프의 최대 간선수
- n(n-1)/2
- ‘나’를 제외한 나머지와 연결이 되어있으므로!
- 나누기 2를 하는 이유
- 방향 그래프가 아니기 때문!
- n개의 Vertex정점으로 구성된 무방향 그래프의 최대 간선수
- 방향 그래프
- 최대 간선수
- n(n-1)
- 나를 제외하고 나머지와 ‘두개씩↔’ 연결되어있으므로!
- 최대 간선수
- 무방향 그래프
- 그래프의 표현방법
- Adjacency Matrix 인접 행렬
- 연결됐으면1, 안됐으면0
- 무방향 그래프, 방향 그래프
- 연결됐으면1, 안됐으면0
- Adjacency List 인접 리스트
- 연결되어 있는 것들 각각 표시
- Adjacency Matrix 인접 행렬
- 그래프의 순회 방법
- 모든 곳들을 방문
- 깊이 우선 탐색
- 스택 이용
- 최대한 깊이 내려간 뒤 더 갈 곳이 없으면 백트래킹하여 옆으로 이동
- 뒤로 돌아와서 그 다음 갈 데를 찾아가는 것
- 사이클이 형성되면 안돼!
- 너비 우선 탐색
- 큐 이용
- 과정
- 연결된 데에 먼저 간다
- 연결된 게 더이상 없으면 다음 탐색
