[알고리즘]알고리즘 강의의 시작

컴퓨터과학 = 컴퓨터 + 데이터 + 프로그램

프로그램 = 알고리즘 + 입력 언어

 

컴퓨터과학 == 알고리즘 과학

컴퓨터의 한계는 알고리즘의 존재 여부로 갈린다.

 

강의의 목적) 알고리즘의 설계 및 분석 방법을 습득하자! 

-> 컴퓨터 기반 문제 해결 방법에 대해 체계적으로 생각하는 훈련

-> 주어진 문제에 대한 지적 추상화 능력 및 통찰력 향상

 

문제(데이터) -알고리즘(일련의 단계적인 처리과정, 효율적인) -> 결과(정보)

 

알고리즘 예시)

퀘닉스버그 다리 문제 = 오일러 경로를 찾는 문제(그래프의 모든 간선을 오직 한 번씩만 지나는 경로) = 한붓 그리기

단일 출발점 최단경로

 

자료구조란?

컴퓨터에서 데이터 사이의 논리적 관계를 표현하고 조직화하는 방법

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

자료구조와 알고리즘 어느 것 하나 놓쳐선 안돼~~

기본 자료구조 = {선형 자료구조: 배열, 연결 리스트, 스택, 큐} + {비선형 자료구조: 트리, 그래프}

    (선형 자료구조: 자료를 논리적으로 나열할 수 있다, 비선형 자료구조: 자료를 논리적으로 한 줄로 나열할 수 없다)

배열 : 삽입과 삭제를 할 때 데이터가 움직여야하므로, 삽입과 삭제가 빈번한 경우 배열이 효율적이지 않다.

연결 리스트 : 각 데이터가 데이터와 링크필드로 구성되고 노드로 연결되어 있다. 논리적, 물리적 표현이 일치하지 않지만 순서는 유지시켜줘야하므로 링크필드를 이용하여 순서를 유지시켜준다. 그래서 삽입과 삭제는 간편하지만 데이터를 찾아갈 때 순차적으로 찾아가므로 어렵다. 

단일 연결 리스트(링크필드가 하나다 == 한쪽으로만 찾아갈 수 있다), 이중 연결 리스트(링크필드가 두개다, 두가지 방향으로 검색할 수 있다), 단일 원형 연결 리스트(끝에서 처음으로 다시 찾아볼 수 있다)

스택 : 데이터의 삽입과 삭제가 한쪽에서만 이루어진다. 

큐 : 데이터가 한쪽에서 삽입하고 다른쪽에서 삭제가 이루어진다.

트리 : 하나 이상의 노드로 구성된 유한 집합, 노드의 차수(각 노드의 차수), 트리의 차수(트리에 있는 노드 중 가장 큰 차수), 리프노드(노드의 차수가 0인것)

이진 트리 : 각 노드의 차수가 2 이하인 순서 트리, 왼쪽 오른쪽 차수가 순서가 정해진 것이다. 포화이진트리(맆 노드를 제외한게 모두 차수가 2), 완전이진트리, 전이진트리(각 노드의 차수가 0 혹은 2), 균형 이진트리(노드의 차가 1 이하인 것), 경사 이진 트리(노드의 차수가 모두 1)

 

모든 자료구조는 배열, 연결 리스트  둘 중 하나를 사용한다. 

 

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

무방향 그래프,  방향 그래프, 가중그래프

그래프의 구현 

    인접 행렬(배열 이용, 2차 배열, 간선에 숫자가 있으면 숫자를 쓰고 없으면 0과 1로 간선의 존재 유무만 표시), 인접 리스트(연결 리스트 사용)