자료구조와 알고리즘
안녕하세요. 그린입니다!
이번 포스팅에서는 자료구조와 알고리즘에 대한 개념에 대해 포스팅해보겠습니다.
컴퓨터 기본지식이자 좀 어려우면서 가장 중요하다고도 할 수 있는 자료구조와 알고리즘!
말하자면 한도 끝도 없을것이고 많은 부분이 있지만 이번 포스팅에서는 조금 간단하게 개념만 짚고 넘어가겠습니다^^
[용어 정리]
-. 알고리즘: 문제해결을 위한 절차/방법의 모음 (순차적인 방법)
-. 자료구조: 자료를 효율적으로 이용할 수 있는 방법론 (데이터를 최적화하여 재조립하는 느낌, 데이터 구조적표현, data structer)
[자료구조의 종류]
-. 원시구조 / 선형구조 / 비선형구조 / 물리구조 / 추상적 구조
:원시구조란, 자료(정수,실수 등..)를 쪼개거나 조합하여 만들어놓음
[자료구조의 활용]
1. 배열 (Array)
: 배열을 사용하면 간단하고 빠르게 자료구조를 만들 수 있다.
어느 정보의 접근하기 위한 소요시간이 길지 않다. 그러나 메모리에 우선 배열의 크기를 정해주어야한다.
2. 연결리스트 (Linked List)
1) 단순 연결리스트
: 하나의 리스트 요소가 다음의 리스트 요소의 주소를 가르키는 단방향
2) 이중 연결리스트
: 하나의 리스트 요소가 다음과 이전 요소의 주소를 가르키는 양방향(이중)
3) 원형 연결리스트
: 단방향 연결리스트에서 끝 요소가 다시 처음 요소를 가르키며 순환구조 리스트
연결리스트는 배열보다 비교적 느리다. 원하는 요소를 접근하기 위해서 주소를 찾아야하며 다 접근을 해야한다.
연결리스트 생성 시 메모리 공간에서 채운다. 메모리 차지 용량이 크다. 이유는 주변 주소를 저장하고 있어서이다.
3. 스택 (Stack)
: PUSH / POP의 키워드를 사용하며 후입선출(LIFO)이며 페이지 이동과 같은 곳에서 활용한다.
4. 큐 (Queue)
: PUT / GET의 키워드를 사용하며 선입선출(FIFO)이며 줄서기 및 대기열과 같은 곳에서 활용한다.
5. 덱(DEQUEUE)
: 스택 + 큐 (더블엔디드큐)로 스택과 큐의 선입선출 + 후입선출이 합쳐진 방법이다
6. 트리 (Tree)
: 부모/자식 클래스와 같이 상속이 이뤄지는 모양처럼 가계도의 트리 모양이다. 주로 앞서말한 상속과 같은 상황에서 활용된다.
7. 그래프 (Graph)
: 시작과 끝이 없는 형태로 그물망의 모양을 갖는다. 소셜 네트워크와 같은 형태에서 활용된다.
[알고리즘]
알고리즘에서는 정렬/재귀/탐색 알고리즘이 대표적이다.
1. 정렬 알고리즘
: 종류가 너무너무 다양하다. 같은 정렬이라도 종류에 따라 상황에 따라 성능이 천차만별임으로 절대적으로 빠르거나 우위를 가진것이 없다.
대표적으로 선택/버블/삽입/병합/퀵 정렬이 있다.
1) 선택정렬: 최솟값 찾고 계속 비교해가며 위치를 바꾼다. 시간복잡도는 O(n^)이다. (여기서 ^는 제곱을 뜻함.)
2) 버블정렬: 인접 요소 검사후 교환하는 방식으로 정렬한다. 시간복잡도는 O(n^)이다.
3) 삽입정렬: 모든 요소를 차례로 정렬된 배열과 비교하여 위치를 찾아 삽입한다. 시간복잡도는 O(n^)이다.
4) 병합정렬: 2개로 나누어 각 해결하며 다시 합치는 방식으로 대개 순환호출로 구현된다. 시간복잡도는 O(nlogn)이다.
5) 퀵정렬: 대체적으로 빠르고 어느상황에서든 평균 이상의 속도는 보여준다. 기존값(피벗)을 첫 요소로 잡고 좌/우측을 비교한뒤 다음 요소로 넘어가며 또 비교하는 분할정복 알고리즘으로 시간복잡도는 O(nlogn)이다. 그런데 최악의 경우에는 시간복잡도는 O(n^)이다.
시간복잡도와 공간복잡도가 있다.
-. 시간복잡도는 해당 작업을 완료하는 소요되는 시간을 구하는것으로, 점근표기법 혹은 빅오표기법으로 하여 나타낸다.
-. 공간복잡도는 프로그램 실행하여 완료되는데 필요한 자원 공간의 양이다. 요구되는 공간은 2개로 나눌 수 있다.
1) 고정 공간: 입출력을 여러번하던 크기가 어떻던 상관없이 필요한 공간으로 고정된 변/상수나 코드를 저장하는 공간으로 볼 수 있다.
2) 가변 공간: 어떤 인스턴스에 의존하는 크기를 가진 변수를 위해 필요한 공간으로 순환 호출 시 요구되는 추가 동적 공간이다.
2. 탐색 알고리즘
1) 선형탐색의 시간복잡도: O(n^)
2) 이진탐색의 시간복잡도: O(logn)
이진탐색은 트리구조를 사용한다. 트리 구조를 통해 중간값에서 부터 업다운하여 찾아간다. 약간 업다운 게임과 비슷한 방식으로 볼 수 있다.
이렇게 이번 포스팅에서는 자료구조와 알고리즘에 대해 학습해보았습니다..!
정말 세분해서 파고들자면 한도 끝도 없어 우선적으로 개괄적인 개념들을 소개해보았습니다~~
자료구조를 잘 파악해서 개발 시 로직을 잘 짜도록 연습해야겠습니다..!
이후 더 추가적으로 집중해서 학습하는 부분들은 꼭 다시 자세한 포스팅으로 돌아오겠습니다.
감사합니다 :D