알고리즘

알고리즘의 개요

알고리즘: 문제를 해결하기 위한 일련의 절차.

 

알고리즘의 표현 방법

• 자연어
  사람이 사용하는 언어.
  익숙한 언어로 이루어져 있지만 명확하지 않은 표현 때문에 오해가 발생할 수 있음.
  다루는 값의 타입의 모호함.
  변수나 객체가 구조체인 경우 어떠한 맴버에 값을 사용할지 모호함.
• 순서도
  기호와 선을 사용한 문제를 해결하는 과정을 표현.
  구조 흐름을 파악하는데 좋지만 복잡한 알고리즘에는 비효율적임.
• 의사코드
  프로그래밍 언어와 비슷한 형태.
  특정한 언어의 문법을 따르지는 않음.
• 프로그래밍 언어
  프로그래밍을 할 때 사용하는 언어.
  특정 언어의 문법을 모르면 알고리즘 구현에 어려움을 겪음.

알고리즘 설계: 가장 효율적인 문제 해결법을 찾는 과정.

 

알고리즘 제어 구조의 종류

• 순차 구조: 명령을 순서대로 수행.
• 선택 구조: 조건의 결과에 따라 명령을 선택해서 수행.
• 반복 구조: 같은 동작을 여러 번 반복하여 수행

알고리즘 조건

• 입력: 입력 자료는 0개 이상 존재.
• 출력: 결과는 1개 이상 존제.
• 유한성: 알고리즘은 보통은 종료되어야 함.
• 명확성: 알고리즘 명령은 모호하지 않음.
• 실행 가능성: 명령이 실행가능해야 함. 변수 선언을 하지 않거나 0으로 나누는 것과 같은 연산은 불가능함. 

알고리즘의 분석

알고리즘 복잡도: 알고리즘이 얼마나 빠르고 느리게 실행되는지, 메모리를 얼마나 사용하는지 나타낸 것임.

• 시간 복잡도: 실행하는 데 걸리는 시간.
• 공간 복잡도: 실행하는데 필요한 메모리의 공간.

시간 복잡도: 알고리즘이 시작되고 종료되기까지 어느 정도의 시간이 걸리는지를 표현.

 

빅오 표기법: 알고리즘의 시간 복잡도를 입력된 값의 크기에 따라 처리 횟수가 얼마나 증가하는 지를 나타내는 방식.

1. 함수식의 상수는 제거
2. 가장 높은 항만을 표기함.

정렬

정렬 알고리즘: 주어진 데이터를 순서대로 나열하는 알고리즘

• 선택 정렬: 아무렇게나 놓인 데이터 중 가장 작은 데이터를 가장 앞에 있는 데이터와 위치를 변경하는 알고리즘.
• 버블 정렬:나란히 놓인 데이터 두 개 중 숫자가 큰 데이터를 뒤로 보내며 정렬하는 방식.
• 삽입 정렬:아직 정렬되지 않은 데이터를 정렬된 부분 중 한 곳에 삽입하는 방식.
• 합병 정렬: 정렬된 여러 개의 데이터를 합병하여 하나의 정렬된 집합으로 만드는 정렬 방법.

검색

검색: 특정 데이터 집합에서 어떤 조건을 만족하는 데이터를 찾는 것.

• 순차 검색:  일렬로 나열된 데이터를 처음부터 순차적으로 검색하는 방식.
• 이진 검색: 데이터 가운데에 위치한 데이터가 검색 값보다 크면 오른쪽을, 작다면 왼쪽부터 탐색하는 방식.
• 해싱: 산술적인 연산으로 키가 있는 위치를 계산.