데이터의 묶음을 저장하고 사용하는 방법을 정의함
데이터는 분석하고 정리하여 활용해야 의미를 갖는다.
필요에 따라 데이터의 특징을 잘 파악해 정리하고 활용할 수 있어야함
데이터를 체계적으로 정리해 저장해두는 것이 중요하다.
자료구조 시각적으로 보여주는 사이트 모음
스택 Stack
입출력이 하나의 방향으로 이루어진다.
Last In First Out 후입선출
입력 : push / 출력 : pop
데이터를 한번에 하나만 넣거나 꺼낼 수 있다.
스택은 크기가 제한되어있다.
활용: 뒤로가기, 앞으로가기
큐 Queue
입출력 방향이 다르며 입출력 방향이 고정되어있다.
First In First Out 선입선출
enqueue : 입력 / dequeue : 출력
데이터를 한번에 하나만 넣거나 꺼낼 수 있다.
활용: 프린트
컴퓨터 장치들 사이에서 데이터를 주고받을때 각 장치 사이에 존재하는 속도의 차이나 시간차이를 극복하기 위해 임시기억장치로 큐를 사용하는데, 이를 버퍼라고 한다.
트리
이진트리
자식노드가 최대 두개인 노드로 구성된 트리
정이진트리: 각 노드가 0개 혹은 2개의 자식노드를 갖는다.
포화이진트리: 정이진트리면서 완전이진트리인 경우
완전이진트리: 마지막레벨을 제외한 모든 노드가 가득 차 있어야 하고, 마지막 레벨에서는 왼쪽이 채워져있어야함
이진탐색트리
이진탐색 + 연결리스트
각 노드에 중복되지 않는 키가 있음
루트노드의 왼쪽 서브트리는 해당 노드의 키보다 작은 키를 갖는다.
루트노드의 오른족 서브트리는 해당 노드의 키보다 큰 키를 갖는다.
좌우 서브트리도 모두 이진 탐색 트리여야한다.
탐색과정
- 루트 노드의 키와 찾고자 하는 값 비교.
찾고자 하는 값이 맞다면 종료- 찾고자 하는 값이 루트 노드의 키보다 작으면 왼쪽 서브트리로 탐색 진행
- 찾고자 하는 값이 루트 노드의 키보다 크면 오른쪽 서브트리로 탐색 진행
트리 순회
간단한 예시를 생각하면 아주 쉽다.
원쁠원 계산식을 나타낼때 보통 1+1 으로 하는데 이는 inorder이다.
+11이것은 preorder, 11+이것이 postorder이다. 이것을 그림으로 아주 간단히 나타내면
preorder
루트를 먼저 방문한다. 즉 부모 노드가 먼저 방문된다.
주로 부모 노드가 먼저 생성되어야 하는 트리를 복사할 때 사용한다.
inorder
제일 왼쪽 끝에 있는 노드부터 순회하기 시작해 오른쪽 노드로 이동한다.
부모 노드가 서브트리 방문 중간에 방문된다.
이진탐색트리의 오름차순으로 값을 가져올 때 쓰인다.
postorder
루트를 가장 마지막에 방문한다. 왼쪽 끝에 있는 노드부터 순회사기 시작해 루트를 거치지 않고 오른쪽으로 이동해 순회한 뒤에 마지막에 루트를 방문한다.
트리를 삭제할 때 사용하는데, 자식노드가 먼저 삭제되어야 상위 노드를 삭제할 수 있기 때문이다.
그래프
직접적인 관계가 있는 경우 두 점 사이를 이어주는 선이 있다.
간접적인 관계라면 몇 개의 점과 설에 걸쳐 이어진다.
점 : 정점(vertex), 선 : 간선(edge)
그래프 표현
인접행렬
두 정점을 이어주는 간선이 있을때 인접하다고 한다.
인접행렬은 이 관계를 2차원 배열의 형태로 나타낸다.
이어져 있을 경우 1, 아닐경우 0으로 표시한다. 가중치 그래프일 경우 1,0 이외의 의미있는 값을 나타낼 수도 있다.
가장 빠른 경로를 찾을때 주로 사용한다.
- a 진출차수 1개, b 진출차수 2, c 진출차수 1
[0][2] === 1
[1][0] === 1
[1][2] === 1
[2][0] === 1
인접리스트
각 정점이 어떤 정점과 인접하는지 리스트로 표현.
각 정점마다 리스트를 갖고있다.
그래프에서는 우선순위를 보통은 중요하게 다루지 않는다.
우선순위가 필요하다면 큐나 힙과 같이 다른 자료구조를 활용한다.
메모리를 효율적으로 사용하고 싶을 때 인접리스트를 사용한다.
인접행렬은 연결 가능한 모든 경우의 수를 저장해 메모리차지를 더 많이 한다.
그래프 용어
정점 (vertex): 노드(node)
간선 (edge): 정점 간의 관계
인접 정점 (adjacent vertex): 하나의 정점에서 간선에 의해 직접 연결되어 있는 정점
가중치 그래프 (weighted Graph): 연결의 강도가 얼마나 되는지 적혀져 있는 그래프
비가중치 그래프 (unweighted Graph): 연결의 강도가 적혀져 있지 않는 그래프
무(방)향 그래프 (undirected graph)
진입차수 (in-degree) / 진출차수 (out-degree): 한 정점에 진입(들어오는 간선)하고 진출(나가는 간선)하는 간선이 몇 개인지를 나타낸다.
인접 (adjacency): 두 정점 간에 간선이 직접 이어져 있다면 이 두 정점은 인접한 정점이다.
자기 루프 (self loop): 정점에서 진출하는 간선이 곧바로 자기 자신에게 진입하는 경우 자기 루프를 가졌다 라고 표현한다. 다른 정점을 거치지 않는다!
사이클 (cycle): 한 정점에서 출발하여 다시 해당 정점으로 돌아갈 수 있다면 사이클이 있다고 한다.
BFS: 너비우선탐색
주로 두 정점 사이의 최단경로를 찾을 때 사용한다.
DFS: 깊이우선탐색
모든 노드를 완전히 탐색한다.
DFS와 BFS의 장단점은 또 무엇이 있을까요?
그래프가 굉장히 크다면 어떤 탐색 기법을 고려해야 할까요?
반대로, 그래프의 규모가 작고, depth가 얕다면 어떤 탐색 기법을 고려해야 할까요?
