ABOUT ME

-

Today
-
Yesterday
-
Total
-
  • 알고리즘 학습을 위한 준비
    프로그래밍/알고리즘 실무 2018. 4. 24. 14:33
    반응형





    * 컴퓨터 프로그램

    - 사람들의 문제를 해결하고 돕기 위한 도구로서의 프로그램

    - 컴퓨터는 S/W와 H/W의 두  요소로 구성됨

    - S/W는 응용프로그램과 운영체제로 분류됨

    - 프로그램은 명령어와 데이터의 집합(0,1)임


    * 알고리즘

    - 프로그램의 핵심은 문제 해결임

    - 알고리즘은 문제를 해결하는 방법의 절차


    - Data(자료) - 자료구조

    - Instruction(명령어) - 알고리즘

    - 서로 종속적


    * 알고리즘과 자료구조

    - 자료구조는 자료의 구성, 조직임

    - 알고리즘은 문제를 해결하는 방법의 절차

    - 알고리즘이 프로그래밍 코드로 표현되면 문제를 해결하기 위한 명령어들의 절차로 표현


    * 프로그램의 핵심요소

    - 자료구조

    - 알고리즘

    - 프로그램 구조(설계)



    * 좋은 프로그램이란?

    - 생산성이 높음

    - 유지보수성

    - 수정

    - 확장성


    * 알고리즘의 만족 조건

    - 0개 이상의 입력

    - 1개 이상의 출력

    - 명확성 : 실행 명령어의 의미가 모호하지 않게 명확해야함

    - 유효성 : 정확하게 실행 가능한 명령과 연산

    - 유한성 : 반드시 종료되어야 함


    * 알고리즘의 기술 방법

    - 사람의 언어로 표현

    - 플로우 차트로 표현 (Flow Chart)

    - 의사 코드로 표현 (Pseudo Code)

    - 프로그래밍 언어 (실무)


    * 알고리즘 계산 복잡도 (실행 시간을 나타내는 빅오 표기법)

    - 시간 복잡도 (Time Complexity) : 얼마나 오래 걸리는지 분석

    - 공간 복잡도 (Space Complexity) : 얼마나 기억공간이 필요한지 분석


    * 빅오(Big-oh) 표기법

    - 연산 횟수로 측정하는 빅오 표기법

    - 빅오 : 입력 크기 n에 대해 계산 횟수가 어느 정도 인지를 표현

    - 점근 표기법으로 알고리즘의 수행 시간을 대략적으로 나타냄

    - O(1) : 입력 크기 n에 대해 n과 무관하게 계산횟수가 일정

    - O(n): : 입력 크기 n에 대해 n과 계산횟수 비례

    - O(n^2) : 입력 크기 n에 대해 계산 횟수가 거듭제곱(지수)로 증가

    - 데이터 입력 크기 n에 대해 점근 표기법인 빅오에서는 최대 차항을 제외한 나머지는 입력크기 n이 커질수록 수행시간에 영향을 주지 않음

    - 최대차 항을 제외한 모든 항과 모든 계수를 제거


    * 빅오(Big-oh) 시간 복잡도

    - O(1) : 해시 테이블 (입력 크기와 상관없이 일정한 시간)

    - O(log2n) : 이진 탐색 (로그시간 수행시간 증가)

    - O(n) : 순차 탐색 (입력크기와 비례적인 수행시간 증가)

    - O(n log2n) : 퀵 정렬(O(n) 보다는 훨씬 수행시간이 길지만 O(n^2)보다는 훨씬 작음)

    - O(n^2) : 선택정렬 (두 for가 중첩되어 구현

    - O(n^3) : n의 3제곱으로 수행시간 증가


    반응형

    '프로그래밍 > 알고리즘 실무' 카테고리의 다른 글

    알고리즘 학습을 위한 준비  (0) 2018.04.24

    댓글 0

Designed by Tistory.