Algorithm Basic

2019. 03. 18 (Mon)

I. 알고리즘

알고리즘

유한한 단계를 통해 문제를 해결하기 위한 절차나 방법

알고리즘 표현 방법

Psuedo Code

Flow Chart

좋은 알고리즘

정확성, 작업량, 메모리 사용량, 단순성, 최적성

작업량 : 시간 복잡도. 연산량으로 계산

알고리즘 설계 기법

완전 검색

그리드

분할정복

백트래킹

DP

NP

• 근사 알고리즘

II. SW 문제 해결

(1) 문제 해결 과정

일단 시간 보다 답을 구하는 것에 초점을 맞추자

분석과 설계를 먼저 다 끝내고 프로그래밍

• 논리 / 구현의 경계를 구분짓자

1. 문제를 읽고 이해한다.
2. 문제를 익숙한 용어로 재정의한다.
   1. 그림으로도 표현 가능
3. 어떻게 해결할지 계획을 세운다.
   1. 충분한 디자인 필요
4. 계획을 검증한다.
5. 프로그램으로 구현한다.
6. 어떻게 풀었는지 돌아보고, 개선 방법을 찾아본다.

일단 naive하게 짜보고 나중에 개선, 수정

(2) 알고리즘의 측정

Big-O notations

연산 횟수에 depend

시간 복잡도에서 영향력이 있는 n 항만 표시

최고차항 만 표시, 계수는 생략

(3) 비트 연산

1. 절대값 부호표기법

맨 왼쪽을 부호치로 설정. 0이면 +, 1이면 -

단점

• 오버플로우 발생 가능
• 0이 2개 발생하여 비효율적

2. 2의 보수

음수를 양의 2의 보수로 만들어 계산

3. 1의 보수

음수를 양의 1의 보수로 만들어 계산

---

• ← Previous Post
• Next Post →