자료구조
- 데이터를 효율적으로 관리 및 사용 할수 있는 방법을 말한다.
가장 자주 등장하는 자료구조
- Stack, Queue, Tree, Graph
대부분의 자료구조는 특정 상황에 놓인 문제를 해결하는데에 특화 되어있기 때문에
많은 자료구조를 알수록 특정상황에 가장 효율적인 방법을 적용할수가 있다.
Stack
- 데이터를 순서대로 쌓는 구조를 가진 자료구조이다.
가장 먼저 들어간 데이터가 가장 나중에 나올수 있다.
1,2,3,4,5 이 순서대로 데이터가 쌓인다고 하면 데이터를 하나씩 빼게 될떄
1,2,3,4
1,2,3
1,2
1
이런식으로 빠지게 되는 자료구조를 말한다.
- 입력과 출력이 하나의 방향으로 이루어져 있고
이런 구조를 LIFO 또는 FILO라고 부른다.
주로 브라우저의 뒤로가기, 앞으로가기에서 적용되고 있다.
Queue
- Stack와 가장 반대되는 개념을 가진 자료 구조이다.
가장 먼저 들어간 데이터가 가장 먼저 나올수 있다.
- 밑빠진 독을 생각하면 된다.
이런 구조를 FIFO 또는 LILO라고 부른다.
주로 임시 저장 장치로 사용된다.
예를들면
컴퓨터에서 인쇄를 할떄 프린터기는 CPU에 비해서 속도가 많이 느리다.
그러기 떄문에 인쇄 작업을 하면 CPU는 모든 정보를 다 전달하지만 그에 비해 전달된 정보를 모두 출력해 놓지 않은 상태이다(프런터는)
그러므로 CPU는 Queue라는 저장공간에 자료를 저장해 놓고 다른 일을 하러 가고
프린터기는 Queue에서 자료를 뺴오며 작업을 하게 된다.
그래프
수학의 그래프와는 다른 형태를 가지고 있는 그래프를 말한다.
그래프는 여러개의 점들이 서로 연결되어 있는 관계를 말하며 직접적으로 관계가 있는 경우 선이있다(간접적이라면 점이있다)
하나의 점을 정점이라고 하며 선은 간선이라고 한다.
- 간선은 양방향으로 작용할수도 있다.(일반통행이 아니다)
주로 네비게이션(길찾기), 검색엔진 등에서 사용된다.
간선이 단순히 서로의 연관관계만을 표현(관계가 있다)라는 정보만 담고 있으면 비가중치 그래프라고 한다.
반대로 간선을 통해서 다른 정보도 얻을수 있다면 가중치 그래프 라고한다.
예를들면
- 부산 -> 서울로 가는데 네비게이션에서 부산->서울로 갈수 있다만 알고 있다면 비가중치 그래프
- 부산 -> 서울로 가는데 얼마나 걸리는지도 알고 있다면
가중치 그래프
알아둬야할 그래프 용어
무(방)향 그래프 : 양방향 통행이 가능한 그래프를 말한다.
진입차수/진출차수 : 한 정점에 들어오고 나가는 간선의 갯수를 의미
인접 : 두 정점이 간선으로 이어져 있다면 이 두 정점은 인접한 정점이라고 부른다
자기루프 : A에서 진출한 간선이 바로 A로 돌아오는것을 의미
사이클 : A -> B -> C -> A 와 같이 이동하는 것을 의미한다.
DFS, BFS
- 둘의 차이는 데이터를 탐색하는 순서
=> 모든 자료를 하나씩 확인해 본다는 점은 같다.
DFS는 너비 우선 탐색을 이용한다.
- 가장 가까운것부터 모두 확인해본뒤에 그다음 먼거부터 확인하는 방식
BFS는 깊이 우선 탐색을 활용한다.
- 한가지의 끝을 먼저 확인한뒤에 그 다음꺼의 끝을 확인하는 방식
이해가 안간다면 검색을 해보기를 추천한다.
-> 사용하는 방식에 따라서 장단점이 다양하다.
인접행렬
정점간의 연관관계를 행렬로 표현한 것이다.
- 이해하기 쉬우니 부가 설명은 하지 않겠다.
만약 내비게이션에 적용하게 된다면 0,1 대신 거리값이 들어가기도 한다.
인접리스트
- 정점간의 연관관계를 리스트 형식으로 표현한 것이다.
보통 순서는 중요하지 않으면
인접행렬은 모든 값을 가져오지만 인접리스트는 특정값만 조회할수 있어서
메모리를 더 효율적으로 사용할수가 있다.
Tree
- 무방향 그래프의 한 구조 형식으로 되어있다.
- 하나의 데이터의 뒤에 여러개의 데이터가 연결되어있을수 잇는 비선형 구조이다.
== 계층적이고 비선형인 자료 구조이다. ==
계층적으로 뻗어 나가기 떄문에 사이클이 따로 존재하지 않는 구조이다.
노드 : 개별 데이터를 부른다(A,B,C 등등)
Root : 트리 구조의 시작점이 되는 노드(A)
부모 노드 : 두 노드가 상하관계로 연결되어 있을 떄 루트에 더 가까운 노드
자식 노드 : 두 노드가 상하관계로 연결되어 있을떄 루트에서 더 멀리있는 노드
리프 : 자식 노드가 없는 노드
서브트리 : 부모노드, 자식노드 로 구성되어 있는 트리를 말한다.
트리는 서브트리로 구성되어 있다고 말할수 있다.
이외에도 높이, 깊이 레벨 등도 있지만 단순히 위치를 말하는 것이기 떄문에 SKIP 하겠다.
Tree는 주로 토너먼트 대진표, 조직도 등에 사용된다.
이진트리
- 자식 노드가 최대 두 개인 노드들로 구성된 트리
포화, 정 이진, 완전 으로 3가지가 있다.
포화 이진트리 : 정 이진 + 완전 이진 이 모두 합쳐진 형태이다.
정 이진 트리 : 노드가 0개 혹은 2개의 자식 노드를 가지는 트리이다.
완전 이진 트리 : 마지막 레벨의 노드는 차있지 않아도 되지만 왼쪽은 채워져 있어야 하는 트리이다.
우선순위큐, heap
- 우선순위큐는 우선순위가 높은 데이터부터 뽑는 큐
- heap 은 완전 이진트리의 한 형태이다.
heap같은 경우에는 상향식, 하향식에 따라서 들어오는 데이터를
오름차순, 내림차순으로 자동 정렬이 되며
데이터를 꺼낼떄에는 root(루트)노드부터 빠져나가게 된다.
heap이 붕괴될떄 즉 형식에 맞지 않을떄는 노드의 위치를 변경해야 하고 이것을 수행하기 위해서 힙 생성 알고리즘(heapify)를 수행한다.
++ 추가적인 공부 ++
- 자료구조는 문제 해결의 기초라고 생각하기 떄문에 추가적으로 유튜브 강의를 통해서 공부한 내용을 정리하고자 한다.
- 여기에서 정리하는 부분은 어떤 자료구조가 있고 어떤게 효율적이다만 적겠다.
- 더 궁금한점은 참고링크를 따라가면 된다.
참고 링크 : https://www.youtube.com/watch?v=O-O-90zX-U4&list=PLRx0vPvlEmdDHxCvAQS1_6XV4deOwfVrz&index=5
정렬
- 삽입, 버블, 선택, 퀵정렬, 병합정렬이 있다.
삽입, 버블, 선택은 굉장히 비효율적이기 떄문에[N*N의 속도] 사용하지 않고 주로 퀵정렬, 병합정렬이 사용된다.
퀵정렬, 병합정렬은 [n*log(n)]의 속도를 가지며 주로 정렬을 할때에 사용된다.
병합정렬과 퀵정렬의 사용법은 링크를 참고하면 좋을 것 같고
병합정렬과 퀵정렬의 차이는 퀵정렬은 피벗값을 옮겨가면서 사용하지만
병합정렬은 피벗값을 고정해 놓고 사용을 한다.
추가로 퀵정렬은 최악의 경우[N*N] 속도를 가지게 되지만
- 정말 최악인 경우
병합정렬은 그럴 가능성이 없다
- 항상 [n*log(n)] 의 속도를 가진다
계수정렬
- 크기가 한정되어 있는 상황(특정 상황)에서만 최고의 효율을 발휘하는 정렬이다
속도는 N을 가지게 된다.
위에서 말하는 특정 상황이라면 배열에서 5이하의 값을 정렬하시오
같은 특정 범위에 해당하는 상황을 말한다.
작동 원리를 간단하게 적어보자면
새로운 배열에 1,2,3,4,5 라는 index를 놓고
기존 배열에서 1이 검색될떄마다 1의 value값을 상승시킨뒤
후에 해당 index값을 연속해서 출력해주면 된다.
설명이 잘 됬는지 모르겠어가지고;; 자세한 사항은 위에있는 링크를 참고!!
합집합 찾기[Union-Find]
- 여러개의 노드가 있을떄 두가지 노드를 선택후 이 두가지 노드가 서로 같은 그래프에 속하는지 판별하는 알고리즘
Find알고리즘은 두개의 노드가 같은 집합에 속해있는지 확인하는 알고리즘이다
개별적으로 존재하는 배열을 표현한 것이다.
이후 이런식으로 배열이 서로 연관관계를 가지게 된다면
이런 진행방향을 거쳐서
결국 이렇게 연관관계를 정리를 할수가 있다.
추가 설명없이 간단하게 그림으로 설명을 하였다.
=> 이 방법이 가장 이해가 빠를것 같아서
