[자료구조] 자료구조와 알고리즘

✍️ 자료구조와 알고리즘

프로그램 = 자료구조 + 알고리즘

자료구조란? 자료를 정리하여 보관하는 여러 가지 구조
알고리즘이란? 주어진 문제를 처리하는 절차(현재 상태와 도달하고자 하는 상태의 gap을 문제라고 한다.)

메모리에서 자료구조를 표현할 때 아래와 같은 구조를 가진다.

알고리즘의 조건

• 입력: 0개 이상의 입력이 존재하여야 한다.
• 출력: 1개 이상의 출력이 존재하여야 한다.
• 명백성: 각 명령어의 의미는 모호하지 않고 명확해야 한다.
• 유한성: 한정된 수의 단계 후에는 반드시 종료되어야 한다.
• 유효성: 각 명령어들은 실행 가능한 연산이어야 한다.

의사코드(pseudocode)가 알고리즘 기술에 가장 많이 사용된다.

✍️ 추상자료형

데이터 타입과 그 데이터 타입이 사용할 수 있는 연산을 같이 생각해야 한다.

추상자료형(ADT: Abstract Data Type)이란? 데이터 타입을 추상적(수학적)으로 정의한 것
데이터나 연산이 무엇(what)인지 정의하고, 그에 반해 어떻게(how) 컴퓨터 상에서 구현할 것인지는 신경쓰지 않는다.
추상화(abstraction)란? 사용자에게 중요한 정보는 강조되고 반면 중요하지 않은 구현 세부 사항은 제거하는 것

추상자료형의 장점으로는 외부로부터 내부 자료를 함부로 접근 못하게 한다는 것이다.
이를, 캡슐화(Encapsulation) 또는 정보은닉(Information Hiding)라고 한다.

✍️ 알고리즘의 성능분석

시간 복잡도(time complexity)란? 얼마나 오래 걸리느냐를 표시
공간 복잡도(space complexity)란? 메모리를 얼마나 잡아먹느냐를 표시

알고리즘의 복잡도 분석은 직접 구현하지 않고서도 수행 시간을 분석할 수 있다.

알고리즘의 성능분석을 표기할 때 빅오표기법을 사용하는데 연산희 횟수를 대략적(점근적)으로 표기한 것이고 최악의 경우 이정도의 성능을 낼 수 있음을 알려준다.
즉, 정확한 연산의 개수보다는 일반적인 증가추세가 중요하다는 의미이다.
만약, T(n) = n^2 + n + 1 이라면 n^2이 차수가 가장 높기 때문에 O(n^2)이라고 표기한다.

아래의 표는 대표적인 Big-O Complexity를 나타낸 것이다.

순차탐색에서의 예시를 들자면 아래와 같은 배열이 있다고 가정하자.

Best case - 찾고자 하는 값이 5라면, 이 숫자가 맨 앞에 있어서 한번만 탐색하면 되므로 O(1)이다.
Worst case - 찾고자 하는 값이 43이라면, 이 숫자가 맨 뒤에 있어서 n번 탐색하면 되므로 O(n)이다.
Average case - 우리가 찾고자 하는 값들을 균일하게 탐색한다고 가정하면 (1 + 2 + ... + n) / n = (n + 1) / 2이므로 O(n)이다.