Programming/코딩테스트

[python 기반] 자료구조와 알고리즘 전체 요약

aram 2022. 8. 14. 17:46

파이썬의 데이터 구조 : https://dailystudy.tistory.com/49 

# 자료구조 : 요리의 재료, 재료를 다듬는 법(코딩) #

- 단순 자료구조

1. 정수 integer

2. 실수 float

3. 복소수 = 실수 + 허수

4. 문자 char

5. 문자열 string

 

- 선형 자료구조(한 줄로 순차적)

1. 리스트

  • 선형리스트(=순차리스트 Ordered List)
    • 입력 순서대로 저장
    • 배열, 주소값이 빈틈없이 붙어 있는 구조
      > 빈칸이 어디에 있으면 안 됨
      > 중간 삭제 후 뒤의 데이터를 앞으로 가져온다면 마지막 빈칸도 삭제해야 함
      > 데이터 양이 많아지면 많은 작업 필요 > 되긴 되는데 시간이 오래 걸림(오버헤드)
    • 삽입/삭제가 드문 신문기사, 연대별 소설 등에서 주로 사용됨
    • 장점 > 메모리 공간 절약, 메모리에 접근이 빠름
    • 단점 > 오버헤드
  • 단순 연결 리스트(*)
    • 떨어진 곳에 위치한 데이터를 화살표로 연결한 것
    • 논리적으로는 붙어 있지만, 노드들이 물리적으로는 떨어진 곳에 위치
    • 일반적인 생성 및 삭제 등이 빈번한 자료형
    • 노드 Node 구조  = 데이터 Data + 링크 Link
      > 노드를 따라 가면 선형 리스트 순서와 동일
    • 헤드 head  = 첫 번째 노드를 잡고 있는 변수
    • 현재 current = 지금 처리 중인 노드
    • 이전 pre = 현재 처리 중인 노드의 바로 앞 노드
    • 마지막 노드의 링크 = None = 노드의 길이 > node의 link가 비어 있으면 끝
    • 장점 > 오버헤드x (앞뒤 링크만 수정하면 되니까)
    • 단점 > 공간이 더 필요로 함. 접근이 느림
  • 원형 연결 리스트
    • 꼬리가 다시 머리로 연결되는 구조 
    • 리스트 형태 = 원 Circle 형태
    • 마지막 노드의 링크 = Head
  • 위 두 리스트의 시간 차이는 거의 없음
    > 단순 연결 리스트의 마지막에 도달하면 컴퓨터는 점프해서 처음으로 돌아감
    > 원형 연결 리스트는 실무에서 거의 사용 안 됨

 

2. 스택 FILO

  • Frist In Last Out
  • 한쪽이 막힌 파이프 > 입구 == 출구
  • push() = 데이터 삽입
  • pop() = 데이터 추출 >> 지정 빼기x, 그냥 빼는 것
  • top = 제일 최상단의 데이터(변수)
  • 오버플로(top >= SIZE-1) : 스택이 꽉 찼음 (컴퓨터 
  • is_stack_full() : top == SIZE-1
  • is_stack_empty() : top == 1
  • 함수호출 : A() > B() > C() > D(), 괄호 검사 > 컴파일러

 

3. 큐 

  • 일반 큐 FIFO
    • Frist In Frist Out
    • 양쪽이 뚫인 파이프, 식당의 대기줄과 같이 먼저 들어간 데이터가 먼저 나오는 구조
    • 입구 != 출구
    • enQueue(인큐) = 큐에 데이터 삽입
    • deQueue(데큐) = 데이터 추출
    • front(머리) = 저장된 데이터 중 첫 번째 데이터
    • rear(꼬리) = 저장된 데이터 중 마지막 데이터
    • top == rear == 1
    • 앞쪽이 빈 경우 > 전체 한 칸씩 당기기 > 데이터가 많은 > 오버헤드o > 매우 비효율적 > 원형 큐로 해결
  • 원형 큐(*) = 환형 큐
    • 꼬리가 다시 머리로 이어지는 구조
    • %SIZE. top = rear = 0 원형 큐 초기화
    • (rear + 1) == front : 큐 꽉 참
    • 빈칸과 꽉찬 것 구분 ==1칸 사용 못함 > 오버헤드x

 

- 비선형 자료구조(하나의 데이터에 여러 개가 이어지는)

1. 트리 : 컴퓨터 상위 폴더 안에 하위 폴더들이 계속 이어져 있는 구조

  • 트리(Tree) 자료구조 - 나무를 거꾸로 뒤집어 놓은 형태
  • 트리 자료구조 용어
    • 루트 노드 root node : 부모가 없는 노드 > 최상위 노드
    • 부모 노드 parent node : 상위 노드
    • 자식 노드 child node : 부모 노드에 연결되어 있는 노드
    • 부모-자식관계 : 링크되어 있는 노드
    • 리프 노드 leaf node : 자식이 없는 노드 > 트리구조의 가장 아래 위치
    • 에지 edge : 노드와 노드 사이의 연결 링크 link, 이어주는 선 > 노드와의 관계 표시
    • 차수 : 부모 노드에 연결되어 있는 자식의 수
  • 이진 트리
    • 전형적인 이진 트리 : 모든 노드의 자식이 최대 2개인 트리
    • 루트 노드 기준 ☞ 루트의 왼쪽 서브 트리  // 오른쪽 서브 트리
    • 종류
      • 포화 이진 트리(full binary tree) : 모든 노드의 자식이 2개로 꽉찬 형태
      • 완전 이진 트리(complete binary tree) : 빈 번호 없이 순차적으로 번호 부여가 가능한 트리
      • 일반 이진 트리 : 일반적으로 흔히 볼 수 있는 형태 > 중간 번호가 빈 형태
      • 편향 이진 트리(skewed binary tree) : 한쪽으로만 치우쳐진 형태
    • 노드 구조 : 왼쪽 link  |  데이터  |  오른쪽 link
    • 이진 탐색 트리(*)의 특징
      • 이진 트리 중 가장 활용도 높음
      • 데이터 크기를 기준으로 일정 형태로 구성
      • 왼쪽 서브 트리 = 모두 작은 값
      • 오른쪽 서브 트리 = 모두 큰 값

 

2. 그래프

  • 그래프 구조 : 여러 노선이 함께 포함된 형태 또는 링크드인(Linked in)과 같은 사회 관계망 서비스의 연결 등의 형태
  • 용어
    • 정점 : 그래프의 꼭지점
    • 엣지 : 정점을 연결하는 링크
  • 트리는 이름이 없지만 그래프는 이름 있음
  • 종류
    • 무방향 그래프 : 방향성x
    • 방향 그래프 : 방향 표기
    • 가중치 그래프 : 엣지마다 가중치가 다르게 부여 (ex, 톨게이트 비)
  • 그래프 순회 Grapy Traversal : 그래프의 모든 정점을 한 번씩 방문하는 것
    • 깊이 우선 탐색
    • 너비 우선 탐색
  • 그래프의 인접 행렬 = 2차원 배열
    • 그래프를 코드로 구현할 때 = 인접 행렬 사용
    • 인접 행렬 = 정방형 행렬, 정점이 4개인 4x4로 표현
    • 무방향 그래프 : 대각선 기준 서로 대칭, 대각선은 사용 안 함(= 0으로 표기)

 

- 파일 자료구조(파일 내용이 저장되는 방식)

1. 순차 파일 Sequential File : 연속 저장

2. 색인 파일 = 순차 파일 + 직접 파일

3. 직접 파일 Direct File : 임의의 물리적 위치에 기록

 

# 알고리즘 : 요리법 #

- 어떤 문제를 해결해 가는 논리적인 과정

- 알고리즘 표현법 : 일반 언어, 의사코드, 순서도, 그림 등 종합적으로 활용

- 알고리즘 성능

  • 시간 복잡도 Time Complexity 로 분석 : 실제론 연산수(시간은 사용 컴퓨터의 성능에 따라 상대적)
  • 빅-오 표기법 Big-Oh Notation : O(f(n)) - 성능이 무엇인지 알려주는 표기법
  • 실무에서는 데이터 건수가 정말 많지만은 않음.
    적당하다면 느리지만 코드 짜는게 짧게 걸리는 O(n²)이 O(n log n)보다 나음

 

- 정렬

  • 순서대로 데이터가 나열되어 있는 것
  • 정렬 알고리즘 종류(결과 형태만 다름. 같은 방식으로 처리)
    • 선택 정렬(Selection Sort)
    • 삽입 정렬(Insertion Sort)
    • 버블 정렬(Bubble Sort)
    • 퀵 정렬(Quick Sort)
  • 선택 정렬
    • 맨 앞의 값을 가장 작은 값으로 지정 > 나머지 값과 비교해서 제일 작은 값 찾음
    • 방 2개짜리 : 임시 공간을 사용해서 두 변수 값 교환
    • 방 1개짜리 : 가장 작은 값을 제외하고 나머지값만 비교

 

- 검색(=탐색)

  • 원하는 것을 찾는 것
  • 검색 실패 시 return -1 이 일반적
  • 순차 검색 - 정렬x : 방법이 없어서 어쩔 수 없이 처음부터 차례로 끝까지 찾음 > 비효율적
  • 이진 검색(*) - 정렬o
     : 월등히 효율적
    : 전체를 반씩 잘라서 한쪽을 버리는 방식 == 분할 정복(검색할 범위를 1/2씩 반복해서 분할)
    : 찾는 값 = 중앙 => 찾음
    : 시작 > 끝  => 실패

 

- 재귀함수

  • 동일한 작동을 무한적으로 반복하는 알고리즘
  • 재귀 호출 Recursion : 자신을 다시 호출
  • 무한 반복을 마치고 되돌아가는 조건을 함께 사용

 

* 내용참고&출처 : 태그의 수업을 복습 목적으로 정리한 내용입니다.

728x90