자료구조와 알고리즘

자료구조

자료 = Data

구조 = 데이터를 담는 구조 

 

목적: 자료를 더 효율적으로 저장하고, 관리하기 위해 사용하며, 잘 선택된 자료구조는 실행시간을 단축시켜주거나 메모리 용량의 절약을 이끌어 낼 수 있습니다!

 

자료구조의 선택 기준은?

- 자료의 크기

- 자료의 처리 시간

- 자료의 활용 빈도

- 자료의 갱신 정도

- 프로그램의 용이성

 

자료구조의 특징

1. 효율성

자료구조를 사용하는 목적은 효율적인 데이터의 관리 및 사용

 

2. 추상화

추상화란 복잡한 자료, 모듈, 시스템 등으로 부터 핵심적인 개념만 간추려 내는 것

 

3. 재사용성

다양한 프로그램에서 동작할 수 있도록 범용성 있게 설계하기 때문에 해당 프로젝트가 아닌 다른 프로젝트에서도 사용할 수 있음

 

자료구조의 분류

자료구조는 크게 선형 자료구조와 비선형 자료구조로 나뉩니다. 선형 자료구조의 경우 데이터가 일렬로 나열되어 있는 것을 뜻하고, 비 선형 자료구조는 특정한 형태를 띄고 있는 것을 뜻한다.

 

선형구조

- 배열(Array)

- 연결 리스트(Linked List)

- 스택(Stack)

- 큐(Queue)

 

비선형 구조

- 트리(Tree)

- 그래프(Graph)

 

알고리즘

문제를 푸는 논리적인 절차 혹은 어떠한 문제를 해결하기 위한 여러 동작들의 모임 

알고리즘은 유한성을 가지며, 언젠가는 끝나야 하는 속성을 가지고 있습니다.

 

알고리즘의 조건

-입력: 외부에서 제공되는 자료가 0개 이상 존재해야 함

-출력: 적어도 2개 이상의 서로 다른 결과를 내어야 함

-명확성: 수행과정은 무엇을 하기위한 것인지 명확하게 정의되어야 함

-유한성: 알고리즘의 명령어대로 수행했을때 처리된 후 종료되어야 함

-효율성: 모든 과정은 명백하게 실행가능한 것이어야 하며, 시간적 공간적 효율성을 가져야함

 

TIP: 알고리즘을 작성할 때는 항상 효율성을 고려해야 하며, 알고리즘의 성능을 분석할 때는 공간복잡도와

시간복잡도를 계산해야한다.

 

유클리드 알고리즘 (GCD: 최대공약수)

유클리드 알고리즘은 2개의 자연수의 최대공약수를 구하는 알고리즘으로 비교대상이 두 개의 자연수 a와 b중에서

(a>b 혹은 b>a) a를 b로 나눈 나머지를 x라고 했을때 GCD(a, b) = GCD(b, x)와 같고 "x가 0이면 그때 b가 최대공약수라는 원리를 활용한 알고리즘이다

ex) GCD(24,16) -> GCD(16,8) -> GCD(8,0) : 최대공약수 = 8

 

GCD 구하는 첫 번째 방법

GCD 구하는 두 번째 방법

GCD 구하는 세 번째 방법