알고리즘 1주차 - 자료구조와 알고리즘 개요

Keywords : 알고리즘, 추상화, ADT, 효율성, 공간복잡도, 시간복잡도, Big-Oh 표기법

 

알고리즘

• 필요성 : 정확하고 효율적인 소프트웨어 개발, 사용 및 관리
• 개념 1 : 문제 해결 방법을 추상화하여, 각 절차를 논리적으로 기술해놓은 명세서
• 개념 2 : 특정한 일을 수행하는 명령어들의 유한 집합
• 조건 :
  • 입력 : 알고리즘 수행에 필요한 자료가 입력될 수 있어야
  • 출력 : 알고리즘 수행 후 결과 출력될 수 있어야
  • 명확성 : 수행할 작업의 내용 및 순서를 나타낸 알고리즘 명령어들은 명확히 명세 되어야
  • 유한성 : 수행 후 반드시 종료 되어야
  • 효과성 : 모든 명령어들은 기본적이며 실행 되어야
• 표현 방법 : 
  • 자연어
  • 순서도
    • 장점 : 알고리즘 흐름 파악 용이
    • 단점 : 복잡한 알고리즘 표현 어려움
  • 프로그래밍 언어
  • 가상코드 
    • 장점 : ADL (알고리즘 기술 언어) 사용해 일반 프로그래밍 언어와 유사, 추후 언어 변환 용이
    • 단점 : 직접 실행 불가능
  • +) 누구나 이해할 수 있도록 명확하게 기술되어야 함

 

 

추상화

• 자료 추상화 (Data Abstraction) : 처리할 자료, 연산, 자료형에 대한 추상화 표현
• 추상 자료형 (ADT, Abstract Data Type) : 자료와 연산자의 특성을 논리적으로 추상화
• 비교 : 
  • 추상화 : 무엇인가? - 자료 : 추상 자료형 - 연산 : 알고리즘 정의
  • 구체화 : 어떻게 할 거인가? - 자료 : 자료형 - 연산 : 프로그램 구현

 

자료구조

• 개념 : 자료를 효율적으로 표현, 저장, 처리할 수 있도록 정리

 

알고리즘의 효율성

• 컴퓨터 프로그램을 통한 문제 해결에 매우 중요한 관심 분야
• 분석 기준 :
  • 알고리즘을 사용하는 데 드는 비용이 얼마인가?
  • 비용이 가장 적게 드는 알고리즘은 무엇인가?
• 공간 복잡도 : 고정 공간 + 가변 공간
• 시간 복잡도 : 컴파일 시간 + 실행 시간(명령문의 실행 빈도수에 따라 계산되며, 더 큰 관여 함)

 

Big-Oh 표기법

• logn < n < nlogn < n^2 < n^3 < 2^n
• 시간 복잡도를 의미