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

[알고리즘 기초] 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)