자료구조와 알고리즘

프로그램은 자료구조와 알고리즘으로 아루어져있다. 프로그램 내에서 배열, 리스트 등을 선언 및 정의하는 부분을 자료구조라 하고, 그 외 프로그램이 돌기위한 논리적 구조를 알고리즘이라 한다.

자료구조

자료구조란, 문제해결을 위해 데이터를 조직하여 표현하는 방법이다.
보편적으로 사용되는 자료구조로는 Array, Stack, Queue, List, Tree, Graph 등이 있다.

예를 들어,
전화번호부는 이름과 전화번호을 나열해야하므로 Array, Linked List, Tree 등을 사용할 수 있다. 그러나 이름을 빨리 검색하고 싶다거나 새로운 데이터를 쉽게 저장하고 싶다는 등의 제한사항에 따라 여러가지 중 더 좋은 자료구조를 선택할 수 있다. 주어진 문제의 특성에 맞는 자료구조를 선택함으로써 프로그램 개발이 쉬워지고 성능을 향상시킬 수 있다.

Abstract Data Type

자료구조를 기술할 때 사용하는 방법
자료구조는 추상데이터타입을 실제 프로그램으로 구현한 것이다.
(그냥 추상 개념 그 자체인 듯..? 세부명세를 포함하지 않고, 함수를 호출하는 곳에는 함수의 구현부를 은닉하는… 리턴타입, 매개변수, 함수명만 보여짐. 그냥 추상 개념 자체잖아?)

알고리즘

알고리즘은 문제 해결을 위해 특정한 일을 수행하는 명령어들의 집합이다.

알고리즘은 아래 조건을 만족해야한다.

입력과 출력
명확성 : 알고리즘을 구성하는 명령어들의 의미가 명확해야함.
유한성 : 유한한 수의 명령어들을 실행한 후 종료해야함.
유효성 : 모든 명령어들은 실행 가능해야함.

최초의 알고리즘은 유클리드 최대공약수 알고리즘이다!
-> 큰 수에서 작은 수를 뺀 수와 작은 수의 최대공약수는 같다는 성질을 이용하여 알고리즘 구성.
뺄셈 대신 mod를 사용해도 된다!

알고리즘 표현방법

말로 서술
pseudo code(의사코드)
flow chart

알고리즘의 효율성

알고리즘의 수행시간이나 알고리즘이 수행하는 동안 사용되는 메모리의 크기로 그 효율성을 따질 수 있다.
이에 수행시간을 따지는 것을 시간 복잡도, 메모리의 크기를 따지는 것은 공간 복잡도라 한다.
그러나 컴퓨팅 파워가 상향평준화되어 현재, 빅데이터 이상의 데이터를 다루는 것이 아니라면 메모리의 크기가 알고리즘 수행에 큰 영향을 미치지 않는다.
따라서 일반적으로 알고리즘을 비교할 때 시간복잡도가 주로 사용된다.

시간복잡도

알고리즘이 수행되는 동안 사용된 기본적인 연산 횟수를 입력 크기의 함수로 나타낸 것.
기본 연산은 데이터 간 크기 비교, 데이터 읽기, 갱신, 숫자 계산 등의 단순한 연산을 말한다.
데이터 수가 무한에 가까운 아주 큰 수일 때 연산 횟수가 궁금하다!