알고리즘 과 자료구조

알고리즘 과 자료구조

여행 가방을 예시로 들어보자.

• 어떻게 효율적으로 물건을 더 넣을수 있을까? = 자료구조
• 옷등 물건들을 어떤 순서로 넣어야 할까? = 알고리즘

테트리스를 예시로 들어보자.

• 적절한 모양의 블럭 = 자료구조
• 요리조리 돌리고 옮겨서 게임 클리어 = 알고리즘
  이렇기 때문에 알고리즘과 자료구조는 뗄레야 뗄수 없는관계이다.

알고리즘

• 문제해결을 위한 절차, 방법
• 어떠한 문제를 해결하기 위한 여러 동작들의 모음

시간복잡도

• 알고리즘이 실행되는데 소요되는 시간분석
• 점근 표기법(대문자 O 표기법) 예시 O(n)

알고리즘의 종류

1. 정렬

• 정렬 알고리즘 중에서도 종류가 굉장히 많다. 어떤식으로 정렬할것인지 에따라 성능이 달라진다.
• 선택 정렬 O(n2)
• 버블 정렬 O(n2)
• 삽입 정렬 O(n2)
• 병합 정렬 O(nlogn)
• 퀵 정렬 O(nlogn)

2. 탐색

• 선형 탐색 O(n)
• 이진 탐색(트리 구조) O(logn)
  • 저장된 값에서 반을 잘라 왼쪽에 있냐 오른쪽에 있냐 탐색하여 없는쪽을 제거 하고 다시 반복하는 알고리즘

3. 재귀

자료구조

• 자료를 효율적으로 이용할 수 있는 방법론
• 데이터를 구조적으로 표현하는 방식

자료구조의 종류

1. 원시구조

• 정수, 실수 , 문자 ...

2. 선형구조

• 배열, 연결리스트, 스택, 큐, 덱

3. 비선형구조

• 트리, 그래프

자료구조를 물리적으로 분류하면

1. 물리적구조

• 정수, 실수, 문자
• 배열 , 연결 리스트

2. 추상적 구조

• 스택, 큐, 덱, 트리, 그래프

배열(Array)

• 갯수(크기)가 정해진 배열 (정해진 타입만 들어올수 있다.)
• 100 개 짜리 배열이라면 100개만 저장할수 있다.
• 가장 빠른 자료구조중 하나다.
• 배열은 크기가 정해져 있으므로 늘리거나 줄이거나 할수 없다.

열결리스트(Linked-List)

• 크기가 정해져 있지않다.
• 배열보다 느리다. 3번 째의 값에 찾아 가려면 처음이나 끝에서 3번째까지 차례차례 찾아가야하기 때문이다.
• 노드를 활용한다.
• 노드란 해당 위치의 값, 다음 노드의 위치 혹은 이전 노드의 위치 를 저장한 덩어리 ? 라고 생각해보자.

1. 단방향 연결리스트

• 노드가 값, 다음 노드의 위치 를 갖는 형태로 한쪽방향으로만 연결되어있는 리스트를 뜻한다.

2. 양방향 연결리스트

• 노드가 값, 다음 노드의 위치, 이전 노드의 위치 를 갖는 형태로 양쪽 방향으로 연결되어있는 리스트를 뜻한다.

3. 원형 연결리스트

• 노드가 값, 다음 노드의 위치를 갖는 형태인데 다음 노드의 위치가 없다면 맨처음 노드 의 위치를 가르키도록 하는 리스트 이다.
• 무한으로 연결된 연결리스트 라고 할수 있겠다.

스택(Stack)

• FILO(First-in-Last-Out)
• 맨처음 저장된것이 맨마지막에 제거되는 구조
• 반대로 맨마지막에 저장된것이 맨처음 제거되는 구조
• 웹상에서 뒤로가기 버튼을 예시로 생각하면 이해가 쉽다.

큐(Queue)

• 한글로 풀어 보면 대기열 이라고 할수 있겠다.
• FIFO(First-in-First-Out)
• 먼저 저장된것을 먼저 제거한다.
• 은행에서 대기열을 예시로 생각하면 이해가 쉽다.

덱(Dequeue)(Doubled-endedqueue)

쉽게 말하면 Queue 가 양쪽으로 들어있다 라고 생각하자.
맨처음과 맨마지막 둘다 추가(insert), 제거(pop) 이 가능하다.

트리(Tree)

부모 자식 관계로 표현을 하기도 한다.
하나의 뿌리로부터 브랜치가 뻗어 나오는 구조.

그래프(Graph)

서로 연결된 그물망을 뜻한다.
시작과 끝이 없다.