자료구조란?
자료구조는 컴퓨터가 데이터를 효율적으로 다룰 수 있게 도와주는 데이터 보관 방법과 데이터에 관한 여러가지 연산을 뜻한다
덧셈/ 뺄셈/ 나눗셈/ 곱셈/ 논리/ 시프트 등 다양하다
자료구조는 다음 그림과 같이
단순 자료구조(Primitive Data Structure)와
복합 자료구조(Non-Primitive Data Structure)로 나뉜다
복합 자료구조는 다시 선형 자료구조(Linear Data Structure)와 비선형 자료구조(Non-Linear Data Structure)로 나뉘고
선형 자료구조는 다음 그림처럼 데이터 요소를 순차적으로 연결하는 자료구조로 구현하기 쉽고 사용하기도 쉽다
배열(Array_과 링크드 리스트(Linked List), 스택(Stack), 큐(Queue) 등이 여기에 해당된다
비선형 자료구조는 데이터 요소를 비순차적으로 연결한다
그림과 같이 한 데이터 요소에서 여러 데이터 요소로 연결되기도 하고
여러 데이터 요소가 하나의 데이터 요소로 연결 되기도 한다 트리와 그래프가 해당된다
배열(Array)
배열은 데이터를 순서대로 저장하는 가장 기본적인 데이터 구조이다
인덱스를 사용하여 요소에 직접 액세스할 수 있어 빠른 검색이가능하지만
배열의 크기는 생성할때 결정되며 배열이 가득 차게 되면 데이터를 추가할 수 없다
일부 프로그래밍 언어에는 동적배열(Dynamic Array) 을 제공해 크기를 자동으로 조정이 가능
배열과 링크드리스트는 데이터를 저장하고 접근하는데 사용되는 자료구조
연결(Linked List)
데이터를 배선으로 나누어 저장하는 자료구조이다 각 회로는 다음 회로를 제공한다
링크드리스트는 요소를 추가하거나 제거하는데 용이하지만 특정 요소를 검색하는 것에는 배열보다 느릴 수 있다
스택(Stakc)
스택은 데이터가 후입선출 자료구조이다
가장 늦게 추가된 데이터가 가장 먼저 제거된다
함수호출, 수식계산, 브라우저 뒤로가기/앞으로가기
스택과 큐는 데이터를 저장하고 검색하는데 사용되는 자료구조
큐(Queue)
큐는 데이터를 먼저 처리하는 선입선출 데이터 구조이다
이러한 특성 때문에 대기열 작업 처리 등에 많이 사용된다
예: 스케줄링
해시 테이블(Hash table)
해시 테이블은 키(Key)와 값(Value) 를 저장하는 데이터 구조이다
데이터를 저장하고 검색하는데 사용되는 자료구조
트리(Tree)
트리는 자료를 계층적으로 구성하기 위란 자료구조
이진트리(Binary Tree) 는 모든 노드가 최대2개의 자식 노드를 가지고
이진트리탐색(Binary Search Tree) 는
모든 노드의 왼쪽 자식 노드는 해당 노드보다 작은 값을 오른쪽 자식 노드는 래당 노드보다 큰 값을 가지는 특수 형태이다
트리의 가장 상위는 루트 노드(Root Node) 라 하고 루트 노드를 제외한 모든 노드는 부모,자식 관계를 갖는다
자식노드가 없으면 리프 노드(Leaf Node)
그래프(Graph)
그래프는 객체 간의 관계 를 표현하는 자료구조
네트워크(Network), 지도(Map), 교통망(Traffic), 인터넷(Internet) 등 다양한 분야에서 활용된다
방향성에 따라 방향 그래프(Directed Graph) 와 무방향 그래프(Undirected Graph) 나뉘고
네트워크 분석과 최단 경로 알고리즘 등에 사용되는
가중치 그래프(Weighted Graph) 가 있다
힙(Heap)
힙은 특정한 규칙을 받는 트리구조이다
보통 최대값이나 최소값을 빠르게 찾아내기 위해 사용된다
자료구조, 알고리즘을 공부해야 하는 이유
자료구조
자료구조의 내부를 이해하면 라이브러리에서 엉뚱한 자료구조를 피해 선택할 수 있다
자료구조는 알고리즘이 데이터를 효울적으로 사용할 수 있게 도와주는 핵심 역할을 하기 때문이다 자료구조를 모르면 알고리즘 공부가 더 어렵게 느껴진다
알고리즘
어떠한 문제를 분석해 컴퓨터가 알아들을 수 있는 형태로 설계하고 구현하는 과정을 익힌다는 의미이다 단순한 요령이 아니라 알고리즘 동작에 소요되는 메모리(공간) 와 프로세싱(시간) 을 이해하고 자원을 효율적으로 활용해 더 좋은 코드를 작성하는 방법을 익히는 것이다
개발의 알고리즘이란?
어떠 문제를 풀기 위한 단계적 절차라고 생각하면 된다
문제 풀이의 절차를 설계한다는 의미이며 프로그래밍 언어를 사용해
풀이 절차를 코드로 작성해 실제로 동작하게 하는 것이다
정렬 알고리즘 (Sorting Algorithm)
데이터를 정해진 기준에 따라 일정한 순서로 나열 하는 알고리즘이다
데이터 처리에 있어서 매우 중요하고 데이터베이스에서 빠른 검색을 하기 위해 데이터 정렬 작업이 필요하다
대표적으로: 버블 정렬(Bubble Sort), 선택 정렬(Selection Sort), 삽입 정렬(Insertion Sort), 퀵 정렬(Quick Sort), 병합 정렬(Merge Sort), 힙 정렬(Heap Sort) 등이 있다
검색 알고리즘(Search Algorithm)
주어진 데이터를 원하는 값을 찾는 알고리즘이다
데이터베이스에서 특정 데이터를 검색하거나 인터넷 검색 엔진에서 검색어에 맞는 문서를 찾는 작업 등에 사용된다
대표적으로:선형 검색(Linear Search) 데이터를 처음부터 끝까지 차례로 검색
이진 검색(Binary Search) 데이터가 정렬되어 있을 경우 중간값 기준으로 검색 범위를 반으로 줄여가며 검색
그리디 알고리즘 (Greedy Algorithm)
최적에 가까운 값을 구하기 위해 사용되는 알고리즘
각 단계에서 가장 최적인 선택을 하는 방법으로 문제를 해결
문제 해결을 위한 시간 복잡도가 매우 빠르고 간단하고 직관적인 알고리즘
예: 거스름돈을 계산하는 문제에서 그리디 알고리즘은 가장 큰 금액의 동전부터 차례대로 거스름돈을 계산
동적 계획법 (Dynamic Programming)
큰 문제를 작은 문제로 나눠서 푸는 알고리즘 기법
문제의 최적해(답)를 구하기 위해 이전에 구한 해(답)를 저장하고 이를 다시 활용 하여 문제를 푸는 방법으로 중복 계산을 피하고 계산 속도를 빠르게할 수 있다
분할 정복(Divide and Conquer)
문제를 작은 부분 문제로 나누어 푸는 알고리즘 기법
작은 단위로 쪼개어 해결하고 이를 결합해 전체 문제를 해결한다
대표적으로: 이진 탐색, 합병 정렬, 퀵 정렬 등이 있다
작은 단위로 나누기 때문에 문제를 푸는 시간 복잡도를 절약할 수 있고
병렬처리가 가능하다
백트래킹 (Backtracking)
해(답)를 찾는 도중 가능성이 없는 루트를 배재하여 정답을 찾아가는 알고리즘 기법
퇴각 검색(DFS)으로 상태 공간 트리(State Space Tree)를 탐색하면서 답을 찾아간다
그래프 알고리즘(Graph Algorithm)
그래프 자료구조를 이용해 그래프 상에서 최단경로, 최소 스패닝 트리 등의 문제를 해결하는 알고리즘
네트워크관리, 교통체계, 무선 통신망 등 최적의 경로나 통신량 등을 계산하는데 유용하다
