Data structure

자료구조와 알고리즘 완벽 정리 (출제빈도: 상)

자료구조와 알고리즘 기본 개념

자료구조란?

• 논리적으로 설계된 데이터 구조
• 구조적으로 모여있는 데이터의 집합
• 데이터 유형과 업무 상황에 따라 선택해서 활용

자료구조의 특징

• 데이터 구조의 구성 방식이 성능에 직접적인 영향을 미침
• 데이터 용량과 실행시간을 최소화하는 것이 목표
• 추가, 삭제, 탐색을 효율적으로 연산하도록 설계 필요

자료구조의 유형

1. 단순구조

• 기본 데이터를 확장하여 자료구조 구성

2. 선형구조

• 데이터 간 1:1 대응 관계로 구성
• 구분:
  • 순차구조: 탐색속도 우선
  • 연결구조: 이동(삽입, 삭제) 속도 우선
• 종류: 스택, 큐, 데크, 선형 리스트, 연결 리스트

3. 비선형구조

• 1:N, N:M 구조
• 종류: 트리, 그래프

4. 파일구조

• 실제 데이터 기록 시 활용
• 종류: 순차 파일, 직접 파일, 색인 순차 파일

알고리즘

정의

• 문제를 해결하는 효율적인 해법
• 알고리즘 + 데이터구조 = 프로그램

알고리즘 원칙

1. 출력은 반드시 1개 이상 존재
2. 모든 기능은 명확한 의미와 완벽한 구성을 가짐
3. 모든 기능은 정해진 횟수만큼 반복되며 실제 연산 가능해야 함

알고리즘 성능 판단 기준

• 정확성
• 명확성
• 수행량(연산의 수행 횟수)
• 메모리 사용량

알고리즘 표현 방법

1. 순서도(Flow Chart)
   • 도형과 기호로 표현
2. 의사코드(Pseudo Code)
   • 일반적인 언어로 코드와 유사하게 표현

알고리즘 설계 기법

1. 동적 계획법
   • 작은 문제의 해결법을 활용하여 큰 문제 해결
2. 탐욕적 알고리즘
   • 각 분기에서 최적의 해 선택
   • 전체적인 최적해를 보장하지는 않음
3. 재귀적 알고리즘
   • 동일한 풀이를 반복적으로 호출
4. 근사 알고리즘
   • 빠른 계산을 위해 근사 해법 수행
5. 분할 정복법
   • 문제를 작은 단위로 분할하여 해결
6. 퇴각 검색법
   • 탐색 실패 시 이전 성공 분기로 되돌아가는 방식
   • 예시: 깊이 우선 탐색 알고리즘(DFS)

선형구조 상세 설명

스택(Stack)

• 데이터 입출력이 한쪽에서만 발생
• 특징: 후입선출(LIFO: Last In First Out)
• 주요 개념:
  • 스택 포인터(TOP): 위치 정보 저장
  • PUSH(삽입): Overflow 발생 가능
  • POP(추출): Underflow 발생 가능
• 활용: 0 주소 명령어 방식

수식 표기법

• 전위식: +AB
• 중위식: A+B
• 후위식: AB+

예시: (A-B)*C+D

전위식 변환: -AB → *-ABC → +*-ABCD
후위식 변환: AB- → AB-C* → AB-C*D+

큐(Queue)

• 데이터 입출력이 반대쪽에서 발생
• 특징: 선입선출(FIFO: First In First Out)
• 포인터:
  • Rear(삽입): 마지막 삽입 데이터 위치
  • Front(삭제): 처음 삽입된 데이터 위치
• 초기값: -1
• 활용: 대기행렬 처리

데크(Deque)

• 입출력이 양쪽에서 가능한 양방향 큐
• 포인터: Left, Right
• 입력방식: 스크롤 방식
• 출력방식: 쉘프 방식

선형리스트

• 특징:
  • 연속된 공간에 저장
  • 빠른 접근 속도
  • 느린 삽입/삭제 속도
• 대표유형: 배열
• 배열 특징:
  • 연속적 데이터 나열
  • Index로 위치 구분
  • 고정 크기 메모리 사용
  • 논리적/물리적 순서 동일
• 연산 효율:
  • 추가 평균이동: (N+1)/2
  • 삭제 평균이동: (N-1)/2

연결리스트

• 구성: 노드(데이터 + 포인터)
• 종류:
  1. 단일 연결리스트
     • 단일 포인터로 다음 위치 참조
     • 마지막 포인터는 Null
     • 첫 노드부터 탐색
  2. 단일 원형 연결리스트
     • 마지막 노드가 첫 노드 참조
     • 순환 탐색 가능
  3. 이중 연결리스트
     • 전/후 노드 위치 참조
     • 양방향 탐색 가능
     • 데이터 복구 가능
  4. 이중 원형 연결리스트
     • 양방향 탐색
     • 순환 구조
     • 데이터 복구 가능

비선형구조 상세 설명

트리(Tree)

• 1:N 계층 구조
• 특징:
  • 간선(Edge, Branch)으로 연결
  • N개 노드 트리의 간선 수: N-1
  • 방향성 있는 비순환 그래프

주요 용어

• 근(Root) 노드
• 단말(Leaf) 노드
• 내부(Internal) 노드
• 형제(Sibling) 노드

구조 관련 용어

• 노드의 크기
• 노드의 깊이
• 노드의 높이
• 트리의 높이
• 노드의 레벨
• 노드의 차수
• 트리의 차수

이진트리 종류

1. 전 이진트리
   • 형제노드가 0개 또는 2개
2. 완전 이진트리
   • 마지막 레벨 제외 모든 형제노드가 2개
   • 순서대로 채워진 구조
3. 포화 이진트리
   • 모든 형제노드가 2개

트리 순회 방식

1. 중위 순회
   • 좌측자식 → 부모 → 우측자식
   • G -> D -> H -> B -> E -> A -> F -> C
2. 전위 순회
   • 부모 → 좌측자식 → 우측자식
   • A -> B -> D -> G -> H -> E -> C -> F
3. 후위 순회
   • 좌측자식 → 우측자식 → 부모
   • G -> H -> D -> E -> B -> F -> C -> A

그래프(Graph)

• N:M 다대다 구조
• 특징:
  • 다중 경로 설정 가능
  • 독립된 부분 그래프 구성 가능
  • 순환 가능

그래프 종류

• 방향성: 방향/무방향 그래프
• 노드 연결: 부분/완전 그래프
• 특정노드 연결: 연결/비연결 그래프
• 순환성: 순환/비순환 그래프
• 가중치: 가중치/비가중치 그래프

주요 용어

• 정점(Vertex)
• 간선(Edge, Branch)
• 인접 정점(Adjacent Vertex)
• 사이클
• 단순 경로(Simple Path)

구조 분석 개념

• 정점의 차수(Degree)
• 진입 차수(In-Degree)
• 진출 차수(Out-Degree)
• 경로 길이(Path Length)

방향 그래프

• 방향성 존재
• <A,B>와 <B,A>는 다른 표현
• 최대 간선수: n(n-1)

무방향 그래프

• 방향성 없음
• (A,B)와 (B,A)는 동일 표현
• 최대 간선수: n(n-1)/2