241021 CS 스터디 정리

1. 자료구조의 큰 그림

1) 자료구조와 알고리즘

• 어떤 자료구조를 사용하느냐에 따라 사용 가능한 알고리즘이 달라지는 등 밀접한 관계를 가지고 있음

(1) 자료구조

• 어떠한 구조로 데이터를 효율적으로 저장하고 관리하기 위한 방법
• 핵심적인 자료구조 7가지가 있음

2) 알고리즘

• 어떠한 목적을 이루기 위해 필요한 일련의 연산 절차
• 트리 순회, 깊이 우선 탐색, 너비 우선 탐색, 최단 경로 알고리즘 등

2) 시간복잡도와 공간복잡도

• 시간복잡도, 공간복잡도로 성능 차이를 파악할 수 있음

(1) 시간복잡도

• 입력의 크기에 따른 프로그램 실행 시간의 관계
• 입력이 커질수록 프로그램 실행 시간이 길어지는 경향성을 보임
• 일관된 성능 판단 척도로서 기능하기 위해 빅 오 표기법을 사용함

• 빅 오 표기법
  • 함수의 점근적 상한을 표기하는 방법
  • $O(N)$과 같이 실행시간의 상한 형태로 표현
  • 입력값 N에 대한 연산 횟수에서 최고차항의 차수만 고려해 표현
  • 가장 대중적으로 사용되고 있는 표기법

• 빅 세타 표기법
  • 입력값 N에 대한 연산의 평균적인 실행 시간을 의미

• 빅 오메가 표기법
  • 함수의 점근적 하한을 표기하는 방법

(2) 공간복잡도

• 입력에 따라 필요한 메모리 자원의 양에 대한 점근적 상한을 표현
• 시간복잡도와 마찬가지로 빅 오 표기법으로 표현되나 주로 성능 판단의 척도인 시간복잡도를 가리키는 경우가 많음

2. 배열과 연결 리스트

1) 배열

• 일정한 메모리 공간을 차지하는 여러 요소들이 순차적으로 나열된 자료구조
• 0부터 시작하는 각 요소를 식별하는 고유한 순서 번호인 인덱스 존재
• 배열 속에 배열을 포함하며 2차원, 3차원 배열로 확장 가능

• 특정 값 접근/수정: $O(1)$
• 특정 요소 추가/삭제/검색 : $O(N)$

2) 연결 리스트

• 노드의 모음으로 구성된 자료구조
• 다음 노드의 위치정보를 가지고 있으므로 메모리 내 불연속적으로 저장할 수 있음

• 특정 값 접근/수정: $O(N)$
• 특정 요소 추가/삭제: $O(1)$

(1) 노드

• 저장하고자 하는 데이터, 다음 노드 위치 정보를 포함하는 구성 단위
• 헤드: 연결 리스트의 첫 번째 노드
• 꼬리: 연결 리스트의 마지막 노드

(2) 싱글 연결 리스트

• 노드 내에 다음 노드의 위치 정보가 저장
• 다음 노드의 위치만 알 수 있고 이전 노드의 위치를 알 수 없음
• 한쪽 방향으로 연결되어 있으므로 단방향 탐색만 가능

(3) 이중 연결 리스트

• 싱글 연결 리스트의 단점을 보완하기 위한 연결 리스트
• 이전 노드의 위치정보도 알고 있어 양방향 탐색 가능
• 메모리의 저장공간이 더 필요하다는 단점 존재

(4) 환형 연결 리스트

• 꼬리 노드가 헤드 노드를 가리켜 원형으로 구성된 연결 리스트
• 모든 노드 데이터를 여러 차례 순회해야 할 때 유용함
• 이중 연결 리스트로도 환형 연결 리스트 구현 가능

3. 스택과 큐

1) 스택

• 한쪽에서만 데이터 삽입 및 삭제가 가능한 자료구조
• 후입선출: 나중에 삽입된 데이터가 먼저 나오는 구조
• 함수의 호출 과정, 뒤로 가기 등 다양한 곳에서 활용

2) 큐

• 한쪽으로 데이터 삽입, 다른 쪽으로 데이터 삭제가 가능한 자료구조
• 선입선출: 먼저 삽입된 데이터가 먼저 나오는 구조
• 임시 저장된 데이터를 순차적으로 처리해야 하는 버퍼로도 활용

(1) 원형 큐

• 데이터를 삽입하는 쪽과 삭제하는 쪽을 연결해 원형으로 사용하는 자료구조

(2) 덱

• 양쪽으로 데이터 삽입 및 삭제가 가능한 양뱡향 큐

(3) 우선순위 큐

• 선입선출이 아닌 정해진 우선순위를 기준으로 처리하는 큐
• 힙을 기반으로 구현 가능함

4. 해시 테이블

• 키와 값의 대응으로 이루어진 표와 같은 형태의 자료구조
• 페이지 캐시, 아이노드 캐시 등 대응 관계가 필요한 상황에 활용
• 여러 개 존재하는 버킷들이 배열을 형성
• 검색 속도가 매우 빠르나 상대적으로 많은 메모리 공간을 차지

• 특정 값 접근/검색/삽입/삭제: $O(1)$

• 키: 해시 테이블에 대한 입력
• 값: 키를 통해 얻고자 하는 데이터
• 버킷: 키를 얻고자 하는 데이터가 저장되어 있는 곳

1) 해시 함수

• 임의의 길이를 지닌 데이터를 고정된 길이의 데이터로 변환하는 단방향 함수
• 키를 인자로 활용해 버킷 배열의 인덱스를 반환
• 키를 해시 함수에 통과시켜 원하는 버킷에 접근함

2) 해시 알고리즘

• 해시 함수의 연산 방법
• 대표적으로 SHA-1, SHA-256, SHA-512, SHA3, HMAC 등이 존재
• 같은 값이더라도 다른 알고리즘을 사용할 경우 도출되는 해시 값 상이
• 무작위 값, 단방향 암호, 데이터의 무결성 검증 위해 사용

3) 해시 충돌

• 서로 다른 키에 대해 같은 해시 값이 대응되는 상황
• 이를 해결하기 위해 체이닝, 개방 주소법, 이중 해싱 등을 사용함

(1) 체이닝

• 충돌이 발생한 데이터를 연결 리스트로 추가하는 방법
• 연결 리스트 노드를 추가할수록 속도가 떨어지는 단점 존재

(2) 개방 주소법

• 충돌이 발생했을 때 발생한 버킷의 인덱스가 아닌 다른 인덱스에 데이터를 저장하는 방법
• 순차적으로 가용 가능한 인덱스를 찾는 선형 조사법의 경우 인덱스 인근에 충돌한 여러 데이터가 몰려 저장되는 군집화 발생 가능성이 있음

(3) 이중 해싱

• 2개의 해시 함수를 사용하는 방법
• 충돌이 발생했을 때 다른 해시 함수에 대한 해시 값만큼 떨어진 거리에 위치한 인덱스를 찾음
• 무작위로 인덱스를 생성하는 과정을 통해 군집화 문제를 피할 수 있음

5. 트리

• 계층 구조를 표현하기 위한 자료구조
• 데이터를 저장하는 곳인 노드와 노드를 연결하는 간선으로 이루어져 있음
• 간선으로 연결된 노드는 상하관계를 형성함
• 하나의 노드를 데이터를 저장할 공간과 자식 노드의 위치 정보를 저장할 공간들의 모음으로 간주해 구현할 수 있음

1) 트리 관련 용어

(1) 노드

• 데이터가 저장되어 있는 곳
• 노드는 하나의 부모 노드와 하나 이상의 자식 노드를 가질 수 있음

• 루트 노드: 최상단 노드로 유일하게 부모 노드가 없는 노드
• 리프 노드: 자식 노드가 없는 최하단 노드

• 부모 노드: 상하관계 중 상위에 위치한 노드
• 자식 노드: 상하관계 중 하위에 위치한 노드
• 형제 노드: 같은 부모 노드를 공유하는 노드
• 조상 노드: 부모 노드와 그 부모 노드
• 자손 노드: 자식 노드와 그 자식 노드

(2) 차수

• 각 노드가 가지는 자식 노드의 수

(3) 레벨

• 루트 노드에서 시작해 특정 노드에 이르기까지 거치는 간선의 수
• 트리의 깊이와 같은 개념
• 가장 높은 레벨이 트리의 높이가 됨

(4) 서브 트리

• 트리 안에 포함되어 있는 트리
• 서브 트리도 트리이므로 루트 노드를 가질 수 있음

2) 트리 순회

• 트리의 모든 노드를 한 번씩 방문하는 것

(1) 전위 순회

• 루트 노드부터 시작해 왼쪽 서브트리를 전위 순회하고 이후 오른쪽 서브트리를 전위 순회하는 방법

(2) 중위 순회

• 루트 노드를 기준으로 왼쪽 서브트리를 중위 순회하고 루트 노드 방문 후에 오른쪽 서브 트리를 중위 순회하는 방법

(3) 후위 순회

• 루트 노드를 기준으로 왼쪽 서브트리를 후위 순회하고 오른쪽 서브 트리를 후위 순휘한 뒤에 마지막으로 루트 노드를 순회하는 방법

(4) 레벨 순회

• 같은 트리에서 가장 낮은 레벨에 있는 노드부터 순서대로 순회하는 방법

3) 트리의 종류

(1) 이진 트리

• 이진 트리
  • 자식 노드의 개수가 2개 이하인 트리

• 편향된 이진 트리
  • 모든 자식 노드가 한쪽으로 치우친 이진 트리

• 정 이진 트리
  • 자식 노드의 개수가 0개 또는 2개인 이진 트리

• 포화 이진 트리
  • 리프 노드를 제외한 모든 노드들의 자식 노드 개수가 2개고 모든 리프 노드의 레벨이 동일한 이진 트리

• 완전 이진 트리
  • 마지막 레벨을 제외한 모든 레벨의 자식 노드 개수가 2개고 마지막 레벨의 모든 노드들이 왼쪽부터 존재하는 이진 트리

• 이진 탐색 트리
  • 특정 노드의 왼쪽 서브트리: 해당 노드보다 작은 값을 지닌 노드 존재
  • 특정 노드의 오른쪽 서브트리: 해당 노드보다 큰 값을 지닌 노드 존재
  • 탐색 속도: $O(logN)$

• 힙
  • 완전 이진 트리의 종류 중 하나
  • 최댓값과 최솟값을 빠르게 찾기 위해 사용
  • 탐색 속도: $O(logN)$

• 최대 힙: 부모 노드가 자식 노드의 값보다 큰 값인 이진 트리
• 최소 힙: 부모 노드가 자식 노드의 값보다 작은 값인 이진 트리

(2) 자가 균형 탐색 트리

• 이진 탐색 트리의 탐색 속도를 균일하게 유지하고자 루트 노드 기준 왼쪽 서브트리와 오른쪽 서브트리의 높이 차를 최소로 만들어주는 이진 탐색 트리
• AVL 트리, RB 트리가 있음
• 다진 탐색 트리로 B 트리가 있음

6. 그래프

• 정점이라 하는 데이터를 간선 또는 링크로 연결한 형태의 자료구조
• 트리는 상하관계를 가지는 그래프의 일종

1) 그래프의 종류와 구현

(1) 연결/비연결 그래프

• 그래프 상에 있는 임의의 두 정점의 경로가 존재/존재하지 않는 그래프

(2) 방향/무방향 그래프

• 그래프 상에 있는 간선에 방향이 있는/없는 그래프

(3) 가중치 그래프

• 간선에 가중치인 비용이 부여된 그래프
• 간선에 부여할 수 있는 값이라면 양수, 음수 상관없이 가능

(4) 서브 그래프

• 특정 그래프의 정점과 간선의 일부분으로 이루어진 그래프
• 트리에서의 서브 트리와 비슷한 개념

2) 그래프 표현 방식

(1) 인접 행렬 기반 그래프 표현

• NxN 크기의 행렬로 그래프를 표현하는 방법
• N: 정점의 개수
• 행/열: 출발/도착 정점
  graph = [[0]*N for _ in range(N)]

(2) 인접 리스트 기반 그래프 표현

• 그래프의 특정 정점과 연결된 정점들을 연결 리스트로 표현하는 방법
  graph = [[] for _ in range(N)]

2) 깊이 우선 탐색과 너비 우선 탐색

(1) 깊이 우선 탐색

• 그래프에서 더이상 방문 가능한 정점이 없을 때까지 최대한 깊이 탐색하기를 반복하는 탐색 방법
• 배열과 스택을 활용해 탐색

(2) 너비 우선 탐색

• 그래프에서 인접한 모든 정점들을 방문하고, 방문한 정점들과 연결된 모든 정점을 방문하는 것을 반복하는 탐색 방법
• 배열과 큐를 활용해 탐색

3) 최단 경로 알고리즘

• 한 정점에서 목적지 정점까지 이르는 가중치의 합이 최소가 되는 경로를 결정하는 알고리즘
• 지도 서비스의 최단 거리 알림, 네트워크 통신을 할 때 사용

(1) 다익스트라 알고리즘

1. 최단 거리 테이블에서 시작 정점을 제외한 정점들을 모두 가장 큰 수로 초기화함
2. 시작 정점을 방문
3. 방문한 정점과 인접한 정점들을 탐색
4. 경로 상의 가중치 합과 최단 거리 테이블 상의 값을 비교
5. 최단 거리 테이블을 갱신할 수 있다면 갱신
6. 방문하지 않은 정점 중 최단 거리가 가장 작은 정점 방문
7. 3~6번의 과정을 방문할 수 있는 모든 정점을 방문할 때까지 반복