알고리즘 - 1강. 알고리즘 소개

알고리즘 - 1강. 알고리즘 소개

- 알고리즘 기본 개념

- 알고리즘의 설계 및 분석 

- 분할 정복 알고리즘/동적 프로그래밍/욕생쟁이/정렬/탐색/근사/해시

- 알고리즘의 기본 개념

- 컴퓨터 과학? : 컴퓨터를 활용해서 주어진 문제를 해결하기 위한 학문

- 알고리즘?

  - (페리스아 수학자 알콰리즈미에서 유래

  - 문제 해결을 위한 '레시피'

  - '맛잇고 좋은 음식' vs '효울적인 알고리즘'

  - 주어진 문제를 풀기 위한 명령어들의 단계적 나열

  - 입출력(1개 이상 출력), 명확성, 유한성(반드시 종료), 유효성(컴퓨터에서 수행 가능해야 함)

- ex) 최댓값 구하기, 퀘닉스버그 다리 문제 (한붓그리기, 오일러경로),

  단일 출발점 최단 경로(데이스트라 알고리즘),  

- 알고리즘 생성 단계

  - 설계 -> 표현/기술 -> 정확성 검증 -> 효율성 분석

- 알고리즘에서 자료구조는?

- 자료 구조? 컴퓨터 기억공간 내에 자료를 표현하고 조직화하는 방법

- 프로그램 = 자료구조 + 알고리즘

- 기본자료구조 (배열,연결리스트)/(스택,큐)/(트리,그래프)

                      선형 자료구조              / 비선형 자료구조

- 배열과 연결리스트 

- 배열 : 논리적 순서 = 물리적 순서, - 삽입, 삭제를 할 때 단점, 데이터 접근 장점

- 1차원 배열, 2차원 배열

- 연결 리스트 : 논리적 순서 != 물리적 순서, - 삽입, 삭제가 간단, 데이터 접근 단점

-단일 연결 리시트, 단일 원형 연결 리스트, 이중 연결 리시트 등

- 스택과 큐

- 스택 : 삽입과 삭제가 한쪽 끝에서 이루어짐 (LIFO, last in first out, 후입선출) 

- top

- 큐 : 한쪽에는 삽입, 한쪽에는 삭제 (FIFO, first ins first out 선입선출)

- front(삭제), rear(삽입)

- 트리와 그래프

- 1. 루트 노드가 존재, 2. 루트 노드를 제외한 서브 트리로 이루어 짐

- 차수, 리프 노드, 부모 노드, 선조, 레벨, 높이, 숲 ...

- 이진 트리 (각 노드의 차수가 2 이하인 순서 트리) - 공백도 이진 트리, 노드 하나도 이진 트리, 노드 왼쪽 오른쪽 순서에 따라 다른 트리

- 레벨 i에서 최대 노드 개수,...

- 포화 이진 트리, 전 이진 트리(차수가 1인 노드가 없다), 완전 이진 트리, 균형 이진 트리

- 이진 트리의 구현

- 일차원 배열을 이용

- 연결 리스트를 이용

- 그래프 G=(V,E), V :정점의 집함, E :간선의 집합 

- 무방향 그래프, 방향 그래프

- 그래프의 구현

-  (2차원 배열)인접 행렬

-  (2차원 연결 리스트)인접 리스트