알고리즘의 이해

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

자료구조 : 접근 or 수정이 용이하도록 자료를 저장하거나 구성하는 방법을 말한다

• list
• stack
• Queue
• Tree
• Graph

알고리즘이 성립되기위한 조건

• 알고리즘이 유한시간 내에 종료되어야함
• 알고리즘이 올바른 출력을 낼 수 있어야 함

알고리즘의 효율성

• 상대적 효율성 : 메모리, 시간 등에서의 효율성 차이
• 절대적 효율성 : 주어진 입력크기에 대해 수행시간이 제곱인지, 지수표현으로 나타나는지 등
• ex) Greedy Method : 매 단계 가능한 해들 중 가장 좋은 해를 찾는 기법
• ex) Divide and Conquer : 주어진 문제의 입력을 분할해 문제를 해결하는 기법
  • 동전 더미에서 저울질을 통해 가짜동전하나를 식별해내는 방법
    -> 일반적인 경우 홀수/짝수개의 동전에서 각각 두개씩 묶어서 저울질을 하면 총 n/2만큼 수행
    -> 분할정복을 이용하면 더미를 반으로 나누어서 저울질한다. 따라서 log 2의 n만큼 수행한다.

알고리즘 과정

• 문제의 이해
  • 컴퓨팅 자원 확인
  • 적절한 자료구조 결정
  • 알고리즘 설계
  • 알고리즘 정당성 검증 : 유한시간내에 종료될 수 있는지
  • 알고리즘 효율성 분석
• 프로그램 작성

알고리즘의 표현 방법

• 자연어 표현
• 흐름도 표현
• 유사 코드 표현
• 프로그래밍 언어 표현

1 . 자연어 표현

• 장점 : 가장 읽기 쉽다
• 단점 : 의미 전달이 모호해질 우려가 있다

2 . 흐름도 표현

• 장점 : 이해하기 쉽다
• 단점 : 알고리즘이 복잡하면 흐름도가 매우 복잡해지며 작성에도 많은 시간 소요

3 . 유사코드로 표현

• 장점 : 고수준의 구조적 표현범
• 단점 : 프로그래밍 언어에 비해 덜 구체적임 (구현상 세부 문제를 감춤으로써 알고리즘 핵심내용에 보다 집중하고자 할 경우 장점으로 작용)
• 특징 : 가장 많이 사용됨

4 . 프로그래밍언어로 표현

• 장점 : 가장 정확
• 단점 : 구현 관련 세부 사항들로 인해 알고리즘 핵심내용을
  파악하는 데에는 오히려 방해가 될 수 있다

알고리즘 표현의 구체성 및 정확성

• 자연어 < 흐름도, 유사코드 < 프로그래밍 언어

알고리즘 표현속도

• 자연어 > 흐름도, 유사코드 > 프로그래밍 언어

알고리즘의 성능분석

알고리즘의 성능 = 시간 측면 성능 + 공간 측면 성능

• 수행 시간 분석
  • 두개의 알고리즘의 실제 수행 시간 측정
  • 실제로 구현이 필요
  • 동일한 하드웨어 사용
• 알고리즘의 복잡도 분석
  • 직접 구현 x , 알고리즘이 수행하는 연산 횟수 측정
  • 일반적으로 연산 횟수는 n의 함수
  • 공간 복잡도 분석 : 수행시 필요로 하는 메모리 공간 분석
  • 시간 복잡도 분석 : 수행 시간 분석

수행시간 분석

• 컴퓨터에서의 수행시간 측정 방법에는 clock함수 사용

공간 복잡도 분석

• 고정 공간 요구
  • 프로그램 입력의 횟수나 크기와 관계없는 공간 요구
  • 명령어 공간, 단순 변수, 고정 크기의 구조화 변수, 상수
• 가변 공간 요구
  • 프로그램 입력에 의존
  • 가변 공간, 스택 공간
    

시간 복잡도 분석

• ex) 덧셈, 뺄셈 횟수등을 계산해서 실행시간을 측정
  -> 매우 비효율적
• 입력 크기에 따른 프로그램 단계 수 변화를 통해 대략적 분석
  • 프로그램 단계 : 실행 시간이 인스턴스 특성에 구문적으로 또는 의미적으로 독립성을 갖는 프로그램의 단위
• 시간 복잡도 비교
  • n을 n번 더하는 문제
    
    -> 각 알고리즘이 수행하는 연산의 개수를 세어 본다.