[WEEK01] 정글 5기 - 컴퓨팅 사고로의 전환

1. 자료구조

문자열	- 일련의 문자로 이루어진 데이터 - 불변성을 가지고 있어 수정이 불가능.    즉, 문자열을 변경할려면 새로운 문자열을 생성
배열	- 동일한 데이터 타입의 요소를 연속된 메모리 공간(index 확인 가능)에 저장하는 자료구조 - 인덱스를 사용하여 요소에 접근, 추가, 삭제, 수정 등 작업 가능 - 정적 배열 생성 시 크기 고정, 동적 배열 생성 시 조정 가능
Linked List	- 연결 리스트는 데이터를 감싼 노드를 포인터로 연결해서 공간적인 효율성을 극대화시킨 자료구조 - 싱글 연결 리스트는 next 포인터만 가진다. 이중 연결 리스튼 next, prev 포인터를 가진다.
스택(stack)	- 가장 마지막으로 들어간 데이터가 가장 첫 번째로 나오는 성질(LIFO, Last In First Out)을 가진 자료 구조 - 비어있는 Stack에서 데이터를 pop하면 Stack Underflow, Stack의 최대 사이즈가 넘어가면 Stack Overflow
큐(queue)	- 먼저 집어넣은 데이터가 먼저 나오는 성질(FIFO, First In First Out)을 지닌 자료구조

 

Stack Underflow와 Stack Overflow 란?

 

비선형 자료구조

비선형 자료구조	- 일렬로 나열하지 않고 자료 순서나 관계가 복잡한 구조 - 일반적으로 트리나 그래프를 말한다.
그래프	- 그래프는 정점과 간선으로 이루어진 자료구조
트리	- 그래프 중 하나로 그래프의 특징처럼 정점과 간선으로 구성되고, 트리 구조로 배열된 일종의 계층적 데이터의 집합 - 루프 노드, 내부 노드, 리프 노드 등으로 구성된다. 특징     ㆍ1. 부모, 자식 계층 구조를 가진다.     ㆍ2. 간선수 = 노드수 - 1     ㆍ3. 트리 내의 노드끼리의 경로는 반드시 존재
이진 탐색 트리 (Complete Binary Tree)	- 모든 왼쪽 자식들 <= n < 모든 오른쪽 자식들 을 만족하는 Tree - 평균 : O(logn) / 최악 : O(n)
AVL 트리
레드 블랙 트리
힙	- 완전 이진 트리 기반의 자료구조 - 힙은 일종의 반정렬 상태(느슨한 정렬 상태)를 유지한다.     ㆍ부모 노드의 키 값이 자식 노드의 키 값보다 항상 큰(작은) 이진 트리를 말한다. - 최대힙(최소힙) : 루트 노드에 있는 키는 모든 자식에 있는 키 중에서 가장 커야한다(작아야한다).
완전 이진 트리란?	- 삽입할 때 왼쪽부터 차례대로 추가하는 이진 트리
우선순위 큐	- 우선순위 대기열이라고도 하며, 대기열에서 우선순위가 높은 요소가 우선순위가 낮은 요소보다 먼저 제공되는 자료구조 - 힙을 기반으로 구현     ㆍ배열이나 연결리스트는 삭제[ O(1) ]가 빠르나 삽입의 경우에는 O(n)으로 효율이 낮다. 힙은 둘 다 O(log n) 이다.
맵	- 특정 순서에 따라 키와 매핑된 값의 조합으로 형선된 자료구조
셋	- 특정 순서에 따라 고유한 요소를 저장하는 컨테이너 - 중복이 없고, 유니크한 값만 저장하는 자료구조
해시테이블	- 해시값을 인덱스로 하여 원소를 새로 저장한 배열 - 무한에 가까운 테이블들을 유한한 개수의 해시 값으로 매핑한 테이블 - 탐색, 삽입, 삭제 시 평균적으로 O(1)의 시간 복잡도를 가지며 unordered_map으로 구현 - 최악의 경우 O(n)이 되는데 Hash Collision과 관련있다.     ㆍ특정 key값을 변환하는 과정에서 서로 다른 key값이 같은 hash value로 변경되는 문제 - 해시함수 : 키를 해시값으로 변환하는 과정 - 버킷 : 해시 테이블에서 만들어진 원소
해시 함수	Key가 int형인 경우 - capacity(해시 테이블 크기)로 나눈 나머지를 해시값으로 한다. Key가 int형이 아닌 경우 - 다음과 같은 라이브러리 사용     ㆍsha256 알고리즘     ㆍencode() 함수     ㆍhexdigest() 함수     ㆍint() 함수

 

해시 충돌	- 저장할 버킷이 중복되는 현상 - 해시 충돌은 두 개 이상의 아이템이 동일한 저장공간이 지정되는 현상이다. - 이는 해시 함수의 특성상 제한된 크기의 해시 테이블에 무한한 수의 가능한 키들을 매핑하기 때문에 발생 - 즉, 다양한 키들이 동일한 해시 값을 가질 수 있기 때문에 충돌 발생
해시 충돌을 해결하는 방법!	1. 체인법 2. 오픈 주소법
체인법(open hashing)	- 해시값이 같은 원소를 연결 리스트로 관리합니다. - 해시값이 같은 데이터를 체인 모양의 연결 리스트로 연결하는 방법을 말하며 오픈 해시법이라고도 합니다. - 체이닝은 각 버킷에 연결리스트를 사용하여 여러 키-값 쌍을 저장하는 방법이다. - 장점     ㆍ해시 테이블의 크기에 영향을 받지 않고, 일정한 성능을 유지할 수있다. - 단점     ㆍ연결 리스트를 위한 추가 메모리가 필요하다.     ㆍ연결리스트가 길어지면, 해시 테이블의 값을 찾는데 시간이 많이 소요될 수 있다.
오픈 주소법 (open addressing & closed hashing)	- 빈 버킷을 찾을 때까지 해시를 반복한다. - 충돌이 발생했을 때 재해시를 수행하여 빈 버킷을 찾는 방법을 말하며 닫힌 해시법(closed hashing)이라고 한다. - 빈 버킷이 나올 때까지 재해시를 반복하므로 선형 탐사법이라고도 한다.  - 삭제 완료 상태도 저장한다.

 

2. 시간복잡도

시간복잡도	- 특정한 크기의 입력에 대하여 알고리즘이 얼마나 오래 걸리는지 - 알고리즘을 위해 필요한 연산의 횟수 - 시간제한이 1초인 문제에 대한 예시     ㆍN의 범위가 500인 경우 : 시간 복잡도가 O(N^3)인 알고리즘을 설계하면 문제를 풀 수 있다     ㆍN의 범위가 2000인 경우 : 시간 복잡도가 O(N^2)인 알고리즘을 설계하면 문제를 풀 수 있다     ㆍN의 범위가 100,000인 경우 : 시간 복잡도가 O(NlogN)인 알고리즘을 설계     ㆍN의 범위가 10,000,000인 경우 : 시간 복잡도가 O(N)인 알고리즘 설계
BigO	- 빅오 표기법을 간단히 정의하자면 가장 빠르게 증가하는 항만을 고려하는 표기법
공간복잡도	- 특정한 크기의 입력에 대하여 알고리즘이 얼마나 많은 메모리를 차지하는지를 의미 - 알고리즘을 위해 필요한 메모리양 - 코딩 테스트에서 보통 메모리 사용량을 128~512MB 정도로 제한한다     ㆍ다시 말해 일반적인 경우 데이터의 갯수가 1000만 단위가 넘어가지 않도록 설계할 것

 

자료 구조	접근		탐색		삽입		삭제
	평균	최악	평균	최악	평균	최악	평균	최악
배열(array)	O(1)	O(1)	O(n)	O(n)	O(n)	O(n)	O(n)	O(n)
연결리스트 (Linked List)	O(n)	O(n)	O(n)	O(n)	O(1)	O(1)	O(1)	O(1)
이중 연결 리스트 (doubly Linked List)	''	''	''	''	''	''	''	''
스택(stack)	O(n)	O(n)	O(n)	O(n)	O(1)	O(1)	O(1)	O(1)
큐(queue)	O(n)	O(n)	O(n)	O(n)	O(1)	O(1)	O(1)	O(1)
우선순위 큐 (Priority Queue)
해시테이블(hash table)	O(1)	O(n)	O(1)	O(n)	O(1)	O(n)	O(1)	O(n)

 

 

3. 정렬알고리즘

선택 정렬 (Selection Sort)	- 매번 가장 작은 것을 선택한다. - 선택 정렬은 가장 작은 데이터를 앞으로 보내는 과정을 N - 1번 반복하면 정렬 완료 - O(n^2)
삽입 정렬 (Insertion Sort)	- 특정 데이터를 적절한 위치에 삽입한다. - 정렬이 거의 되어 있는 상황에서는 퀵 정렬 알고리즘보다 좋다. - 최고 : O(n) / 평균 : O(n^2)
합병 정렬 (Merge Sort)	분할 정복(재귀) - 요소를 쪼갠 후, 다시 합병시키면서 정렬해나가는 방식 - O(n)
힙 정렬 (Heap Sort)	분할 탐색(재귀) - 완전 이진 트리를 기본으로 하는 Heap 자료구조를 기반으로 한 정렬 방식 - O(nlogn)
퀵 정렬 (Quick Sort)	분할 탐색(재귀) - 제일 많이 사용되는 알고리즘 - 기준 데이터를 설정하고 그 기준보다 큰 데이터와 작은 데이터의 위치를 변경 - 퀵 정렬에 피벗(Pivot)이 사용된다 -퀵 정렬에서는 이처럼 특정한 리스트에서 피벗을 설정하여 정렬을 수행한 이후에 피벗을 기준으로 왼쪽 리스트와 오른쪽 리스트에서 각각 다시 정렬을 수행한다. - 재귀함수와 동작원리가 같다. - 이미 정렬이 되어 있는 경우에는 매우 느리게 동작한다. - 평균 : O(nlog n) / 최악 : O(n^2)
계수 정렬 (Counting Sort)	- 특정한 조건이 부합할 때만 사용할 수 있지만 매우 빠른 정렬 알고리즘 - 특정한 값을 가지는 데이터의 개수를 '카운트'하는 방법 - 시간복잡도 : O(n + k[데이터 중 최대값])

코드 정리 자료 : https://github.com/minit97/jungle-crafton-algorithm-study/tree/main/week01/sort-algorithm

분할 정복	- 큰 문제를 작은 문제 단위로 쪼개면서 해결해나가는 방식
완전 탐색	- 가능한 모든 경우의 수를 탐색하는 방법
이분 탐색	- 정렬된 리스트에서 탐색 범위를 반으로 점차 줄여나가며 특정 값의 위치를 탐색하는 방법
정수론

 

4. 반복문과 재귀함수

재귀함수의 장단점

장점 - 코드가 더 깔끔하고 이해하기 쉬울 수 있다. 단점 - 함수 호출 시 메모리가 추가적으로 사용돼 메모리 소비가 많으며, 잘못 사용하면 스택 오버플로우를 일으킬 수 있다. - 또한, 반복문에 비해 빈번한 스택 메모리 할당/해제로 실행 속도가 느릴 수 있다.