[자료구조와 알고리즘] 알고리즘의 개요

알고리즘의 개요

 

알고리즘(Algorithm)

주어진 문제를 해결하기 위한 잘 정의된 동작들의 유한집합

 

 

자료구조(Data Structure)

- 알고리즘의 객체
- 구조화되고 조직화된 자료의 저장/추출/관리 방법
- 추상데이터유형 (Abstracted Data Type)
- 배열,스택,큐,트리...

 

---

 

※ 알고리즘 선택 시 고려사항

① 하나의 문제에 대해 여러 알고리즘이 존재할 수 있다
② 절대적인 최상의 알고리즘은 없다
③ 주어진 문제와 환경을 먼저 숙지한다
④ 속도와 자원(resource)의 상관관계에 유의한다
⑤ 단순한 알고리즘을 지향한다
⑥ 지나친 속도결벽증은 금물이다
⑦ 알고리즘의 사용빈도에 따라 알고리즘을 선택한다

 

---

알고리즘의 예: 두 정수의 곱셈

 

① 전통적인 방식의 곱셈 기본연산

: 임의의 정수 X 한자리 정수 → 두 정수의 더하기

 

→ 기본연산이라고 하기에는 컴퓨터에게 너무 복잡하다

② a la russe 알고리즘: 45 X 37 연산 예시

알고리즘 적용 규칙		첫번째	두번째	세번째
1	두 정수를 첫번째, 두번째에 쓴다	45	37	37
2	첫번째 수가 홀수면, 두번째 수를 세번째 칸에 기록한다	22	74	-
3	첫번째 수를 2로 나누고(나머지 버림), 두번째 수에 2를 곱한다	11	148	148
4	첫번째 수가 0보다 크면 2로 돌아간다	5	296	296
5	세번째 칸의 수를 모두 더한다	2	592	-
		1	1184	1184
		연산결과 :		1665

 

※ 2를 곱하는 것의 의미

 

※ 2를 나누는 것의 의미

 

 

 

 

 

※ 해당 게시글은 개인 학습의 목적으로, 아래 강의를 수강한 후 정리한 학습노트입니다.

https://inf.run/LNCU