1강 제 1강 알고리즘

제 1장 알고리즘 소개

 

학습목표

1. 알고리즘의 중요성과 개념을 이해할 수 있다.

2. 기본 자료구조의 개념과 특성을 이해하고, 알고리즘 설계에 활용할 수 있다.

3. 알고리즘의 분석 방법과 점근성능의 표기법을 이해하고 적용할 수 있다.

4. 순환 알고리즘의 개념과 주요 점화식의 의미를 이해할 수 있다.

 

주요용어

#알고리즘 #배열 #연결리스트 #스택 #큐 #트리 #그래프 #공간 복잡도 #시간 복잡도 #점근성능 #O-표기 #빅오

#Ω표기 #빅세타표기 #Θ표기 #빅델타표기 #점화식

 

 

 

 

1.1 알고리즘의 개념

알고리즘(algorithm)은 문제 해결을 위한 레시피(조리법)라고 할수 있다.

알고리즘은 주어진 문제를 해결하기 위한 일련의 처리 과정을 단계적으로 나열한 것이다.

 

 

 

예제 1. 주어진 숫자 (25, 15, 35, 60, 45, 80, 55, 75) 중에서 최댓값을 찾는 문제를 해결하는 알고리즘을 표현하시오.

 

알고리즘 개념 예 (최댓값 찾기)

 

 

1.1.1 알고리즘의 정의

 

 

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

 

• 입출력( input & output ) : 0개 이상의 외부 입력,  1개 이상의 출력
• 명확성 ( definiteness ) : 각 명령은 모호하지 않고 단순 명확해야 함
• 유한성 ( finiteness ) : 한정된 수의 단계를 거친 후에는 반드시 종료
• 유효성 ( effectiveness ) : 모든 명령은 컴퓨터에서 수행 가능 해야 함
• ( 실용적 관점 ) : 효율적이어야함 

알고리즘  : 주어진 문제에 대한 결과를 생성하기 위해 모호하지 않고 간단하며

               컴퓨터가 수행 가능한 유한개의 일련의 명령들을 순서적으로 구성한것

 

 

 

1.1.2 알고리즘의 생성 

 설  계 : 상향식 설계 , 하향식 설계

표현/기술 : 일상 언어, 순서도(flow chart), 의사코드, 프로그래밍 언어..........

정확성 : 수학적 검증

효울성 분석 : 공간 복잡도, 시간 복잡도

 

표현 예1

 

표현 예 2

 

 

 

1.2 기본 자료 구조

 

***자료구조 (data structure) : 컴퓨터 기억 공간 내에 자료를 표현하고 조직화하는 방법

 

좋은 프로그램을 만들려면 자료구조와 알고리즘이 적절히 조화를 이루어야 한다.

주어진 문제에 적합한 자료구조의 선택이 알고리즘의 설계 및 효율에 큰 영향을 미친다.

 

 

기본 자료구조 의 예

 

 

1.2.1 배열과 연결 리스트

 

(1) 배열 (array) : < 인덱스, 원소값 > 쌍의 집합 ,선형 

  동일한 자료형을 갖는 여러 원소를 하나의 변수 이름으로 모아 놓은 데이터 집합체

 

1. 원소의 논리적 순서와 저장된 물리적 순서가 같다.

2. 표현이 간단하고, 인덱스를 이용해서 빠른 접근이 가능 한것이 장점

 

→ 인덱스를 통한 직접적인 원소 접근, 삽입/ 삭제 시 자료의 이동에 따른 오버헤드 발생 , 저장공간 낭비

 

 

(2) 연결 리스트 (linked list) : ( 데이터 , 링크 )

  노드 ( 하나 이상의 (데이터, 링크) 필드로 구성) 라는 저장 구조를 이용한 자료 구조

 

1.몇 개의 링크 필드만 조정하는 작업을 통해 삽입과 삭제를 간단하게 수행할 수 있다.

2.기억 장치의 할당과 반환을 통해 동적으로 관리할 수 있다

 

→ 특정 데이터에 접근하려면 순차적으로 방문 후 도달 ( 접근성 안 좋다)

 

 

 

1.2.2 스택과 큐

 

(1) 스택 ( stack ) : 후입선출 리스트 ( LIFO : Last - In - Firest -Out ) 

 

  한 쪽 끝에서만 데이터의 삽입과 삭제를 수행

 

 

(2) 큐 ( queue ) : 선입선출 리스트 ( FIFO : First - In - First - Out )

 

  한쪽에서는 삽입만 되고, 다른 한쪽 끝에서는 삭제만 수행되는 선행 리스트

 

 

 

1.2.3 트리 

 

트리 ( tree ) :

  하나 이상의 노드로 구성된 유한 집합 T 

 

( 조건 1 ) T 의 원소 가운데 단 하나의 루트 노드가 존재

( 조건 2 ) 루트 노드를 제외한 나머지 노드는 n 개 ( n >= 0 ) 의 서로 분리된 부분 집합 T1, T2,  .....m Tn 으로 나누어지며, 각 Ti는 트리가 된다. 이때 각 Ti 를 트리 T 의 서브트리 (subtree) 라고 한다.

 

A 를 루트 노드로, 총 14개의 노드로 구성

 

그림을 보면서 트리 관련 용어 정리 :

• 차수 ( degree ) : 노드의 서브트리의 개수 (차수 혹은 분기수 )  ex ) A의 차수 3 ,  C의 차수 0 , F 의 차수 2
• 리프 ( Leaf ) 노드 : 차수가 0인 노드 ( 리프 노드 또는 단말 노드(terminal node) ) ex ) { C, I, J, K, L, M, N }
• 부모 노드, 자식 노드, 형제 노드,  조상 , 후손 ...... ( 생략 )
• 트리의 차수 : 트리 내의 노드의 차수 중에서 최대 차수를 의미 ex ) 위 그림의 차수는 3 
• 레벨( level ) : 루트 노드로부터의 거리를 의미
• 높이 ( height  ) / ( depth ) :  높이 또는 깊이 ex )  그림의 트리느 높이가 4

 

 

 

이진 트리 ( binary tree ) : 

각 노드의 차수가 2이하인 순서 트리

 

특징 

• 레벨 i 에서 최대 노드의 개수 ( i >= 0 ) → 2^i 
• 높이가  h인 이진 트리가 가질수 있는 최대 노드의 수는 2^h - 1이다. (단, h>=1)
• 모든 이진 트리에 대해 단말 노드의 수를 n0, 차수가 2인 노드수를 n2라고 하면 n0 =n2 +1 이다.

 

포화 ( perfect ) 이진 트리 : 모든 리프 노드의 레벨이 같은 전 이진 트리

전 ( full ) 이진 트리 : 모든 노드의 차수가 0이거나 2 인 이진트리

**완전 ( complete ) 이진 트리 : 트리의 최대 레벨이 L 일 때 레벨 L - 1 까지는 포화 이진 트리를 형성하고,

                                         마지막 레벨 L 에서는 왼쪽에서부터 중간에 빈자리 없이 리프 노드들로 채워진 트리

균형 ( balabced ) 이진 트리 : 왼쪽서브트리의 높이와 오른쪽 서브트리 높이의 차이가 많아야 1 인 이진트리

 

 

 

 

 

 

 

1.2.4. 그래프 ( graph ) 

 

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

 

차수 : 해당 정점에 부수된 간선의 수를 의미

단순경로 (simple path ) : 한 경로상에서 처음과 마지막 정점을 제외한 모든 정점이 서로 다른 경로

사이클 ( cycle ) : 처음 과 마지막 정점이 같은 단순 경로를 말한다

루프 ( loop ) : 사이클이면서 결로의 길이가 1인 경로

 

그래프의 구형 ( 행렬, 리스트 )

 

2강 제 1강 알고리즘 1.3 알고리즘 설계

2강 제 1강 알고리즘 1.3 알고리즘 설계