[자료구조와 알고리즘] 자료구조와 알고리즘이란?

2024 03 25

글 내용 출처 : 한양사이버대학교 알고리즘 수업

---

1. 자료구조

---

• 자료(data)를 담는 구조
• 접근 및 수정을 가능하게 하는 자료의 조직, 관리, 저장
• 대량의 데이터를 효율적으로 관리할 수 있는 데이터의 구조
• 코드 상에서 효율적으로 데이터를 처리하기 위해 데이터 특성에 따라 체계적으로 데이터를 구조화해야 함

---

2. 알고리즘

---

• 어떤 문제를 해결하기 위한 방법의 절차
• 문제를 풀어내기 위해 정해진 일련의 절차나 방법을 공식화한 형태로 표현한 것

---

알고리즘 순서도 예시

---

3. 알고리즘 기본형

---

순차구조	처음부터 순서대로 처리함
선택구조	조건식으로 판단하여 실행할 처리를 전환함
반복구조	조건을 만족하는 동안 같은 처리를 반복함

---

3-1.  알고리즘 기본형 - 순차구조

---

• 처음부터 순서대로 처리함
• 원하는 처리를 차례로 작성

순차 구조 예시

---

3-2. 알고리즘 기본형 - 선택구조

---

• 조건식으로 판단하여 실행할 처리를 전환하는 것
• 예상하지 못한 상황을 가정하여 이를 회피할 수 있도록 함
• 선택 구조에 있어서 조건 판단을 실행하는 식을 '조건식'이라 함

선택 구조 예시

 

---

3-3. 알고리즘 기본형 - 반복구조

---

 

반복구조 예시

---

4. 알고리즘 기술 방법

---

순서도	도형 기호를 사용하여 알고리즘을 기술함
프로그래밍 언어	여러 종류의 언어로 알고리즘을 구현
의사 코드(pseudo code)	프로그래밍 언어에 의존하지 않고 알고리즘을 기술 할 수 있음

---

4-1. 순서도

---

	터미널	알고리즘의 시작과 종료를 나타내는 기호 시작터미널 기호에는 안에 '시작', 종료터미널 기호는 안에 '종료'등을 기재
	처리기호	처리를 나타내는 기호 가장 많이 사용함 기호 안에 구체적인 처리 내용을 기재함
	판단기호	조건식에 의한 선택을 나타내는 기호 기호 안에 조건을 판단하는 내용을 기재
	루프기호(시작)	반복구조의 시작을 나타내는 기호
	루프기호(종료)	반복구조의 종료를 나타내는 기호
	흐름선	기호들을 서로 연결하여 처리의 흐름을 나타냄 기본은 위에서부터 아래로의 수직 방향 처리가 수평방향이나 아래에서 위로 향할 때는 흐름의 방향을 확실히 하기 위해 화살표를 사용

---

의사코드는 다음에 따로,

---

---

5. 자료구조와 알고리즘에 대한 이해

---

자료구조	데이터를 어떠한 형태로 저장하고 관리할 것인지에 대한 방법 어떻게 효율적으로 자료를 저장할 것 인가에 대한 고민
알고리즘	저장된 데이터를 찾거나 변형 및 수정할 때 필요한 방법 문제를 해결하기 위한 절차에 대한 고민

---

6. 알고리즘의 복잡도 분석

---

• 직접 구현하지 않고서도 처리 시간을 분석할 수 있음
• 알고리즘이 수행하는 연산의 횟수를 측정하여 비교함
• 연산의 횟수는 n의 함수

 

시간 복잡도 분석(Time Complexity)	처리 시간 분석
공간 복잡도 분석(Space Complexity)	처리 시 필요로 하는 메모리 공간 분석

 

• 시간 복잡도는 알고리즘에서 연산들이 몇 번 수행되는지를 숫자로 표시
• 알고리즘이 수행하는 연산의 개수를 계산하여 두 개의 알고리즘을 비교
• 연산의 수행 횟수는 입력의 개수 n에 대한 함수 T(n)으로 표기함 ( T는 Time )

 

---

7. 빅오(Big-oh) 표기법

• 연산 횟수로 측정하는 표기법

---

• 입력 크기 n에 대해 계산 횟수가 어느 정도인지를 표현함
• 점근 표기법으로 알고리즘의 수행 시간을 대략적으로 나타냄

---

예시

O(1)	input n에 대해 계산 횟수가 일정함
O(n)	input n에 대해 n과 계산 횟수가 비례함
O(n2)	input n에 대해 계산 횟수가 제곱으로 증가함

---

O(1)	상수형	O(log n)	로그형
O(n)	선형	O(n log n)	로그선형
O(n2)	2차형	O(n3)	3차형
O(2n)	지수형	O(n!)	팩토리얼형
O(nk)	k차형

 

---

7-1. 빅오 표기법 - 대표적인 알고리즘 시간 복잡도

---

시간 복잡도	알고리즘	n=32
O(1)	해시 테이블(입력 크기와 상관없이 일정한 시간)	1
O(log2n)	이전 탐색(로그 시간 수행 시간 증가)	5
O(n)	순차 탐색(입력 크기와 비례적인 수행 시간 증가)	32
O(n log2 n)	퀵 정렬(O(n)보다는 수행시간이 훨씬 길지만 O(n2)보다는 훨씬 작음)	160
O(n2)	선택 정렬(두 for가 중첩되어 구현)	1,024
O(n3)	N의 3제곱으로 수행 시간 증가	32,768

---