Language/Algorithm

[알고리즘 기초] 00_intro ASP (Algorithm Problem Solving) / Python

migrationArc 2021. 6. 8. 15:04

[알고리즘 기초] 00_intro ASP (Algorithm Problem Solving) / Python

[알고리즘 기초] 00_intro ASP (Algorithm Problem Solving) / Python

0. 시작하기 전

- Programing Language

  • Python
  • Java
  • C
  • C++
  • C#
  • Java script

 

 

- 프로그래밍 절차

  1. 요구사항 분석 -> 문제 / 제약조건 파악
  2. 설계 -> 설계 : 연필로 적으며 가장 작은 test case를 해결해보기
    • 개발론에서는 1,2 가 중요하다고 함. software는 도구일 뿐이다.
  3. 구현 -> 코딩
  4. 테스트
  5. 유지보수

 

1. Algorithm

  • 어떤 문제를 해결하기 위한 절차나 방법. ex) 요리 레시피.
  • 식을 만들 수 있으면 유리.

 

 

- 알고리즘을 표현하는 방법은 크게 두가지

  1. pseudocode(중간코드) : 타인이 보았을 때, 어떠한 논리인지 설명 될 수 있을 정도만 작성. 
    ex)
def CalcSum (n) :
    sum = 0
    for i in range(1, n+1 ):
        sum = sum + i;
    return sum;
  2. 순서도

 

 

- 좋은 알고리즘 : ASP 과정의 목표

  • 적확성
  • 작업량(적은 연산)
  • 메모리 사용량(적은 사용량)
  • 단순성
  • 최적성(최적화 문제)

 

 

- 시간 복잡도 : 알고리즘의 작업량의 표현

  • 실제 걸리는 시간을 측정
  • 실행되는 명령문의 개수를 계산

 

 

- 빅-오 표기법 (Big-Oh Notation)

  • 시간 복잡도 함수 중에서 가장 큰 영향력을 주는 n에 대한 항만 표시
  • 계수(coefficient)는 생략
  • ex) 
    • O(3n + 2) = O( 3N ) = O(N) (최 고차항의 n만 선택, 계수 제거)
    • O(2n^2 + 10n 100) = O(n^2)

 

저작자표시