[TIL] WEEK01

Keyword: 배열, 문자열/ 반복문과 재귀함수/ 복잡도(BigO, 시간, 공간)/ 정렬/ 완전탐색/ 이분탐색/ 분할정복/ 스택/ 큐/ 우선순위 큐/ Linked List/ 해시테이블

• 자료구조: 데이터를 저장/조작/관리하는 방법
  배열/문자열/연결리스트/스택/큐/우선순위큐/해시테이블
• 알고리즘: 문제를 해결하기 위한 계산적인 절차나 방법
  반복문/재귀함수/정렬/완전탐색/분할정복

1. 배열, 문자열

• 배열(Array): 하나의 변수에 ‘같은 성질’을 가지는 항목들의 집합으로, ‘연속’된 메모리 공간에 순차적으로 저장된 데이터의 모음

  • 선형 자료구조
  • 선언할 때 고정된 크기를 정함
  • 연속된 메모리에 저장되어 있어야 하기 때문에 중간에 특정 요소를 삽입/삭제하는 경우 그 이후의 모든 요소들을 이동시켜줘야 한다. (overhead 증가, 삽입/삭제 비용 증가)
  • 시간 복잡도: 삽입/삭제=O(N), 원소 접근:O(1)
  • Random Access: O(1)의 시간에 Index를 통해 모든 배열 요소에 액세스 가능

• 문자열(String): 문자를 저장할 수 있는 배열

  • 문자열의 끝에는 Null 문자(‘\0’)를 함께 저장한다. 때문에 문자열을 다룰 땐 이 ‘\0’ 문자까지 포함해 ‘문자길이+1’로 크기를 할당해야 한다.
    • ex. 문자: ‘A’, 문자열: “A”(‘A’+’\0’)

2. 반복문과 재귀함수

• 반복문(Iteration): 명령을 반복적으로 실행하는 것

• 재귀함수(Recursion Function): 함수에서 자신을 다시 호출하여 반복 작업을 수행하는 것

• 반복문 vs 재귀함수

  • 스택 메모리: 반복문은 스택 메모리를 사용하지 않지만, 재귀함수는 함수가 호출될 때마다 (매개변수/지역변수/return값/종료 후 돌아가는 위치)가 스택 메모리에 저장됨
  • 무한 반복: 무한 루프는 CPU 사이클을 반복적으로 사용, 재귀 함수는 Stack Overflow 발생
    • 함수를 반복적으로 호출하며 스택메모리에 콜 스택이 쌓임, 호출 횟수가 많아지면 스택메모리를 초과해 발생되는 것 (일반적인 반복문은 지역 변수들이 호출될 때 한 번만 할당되어 발생되지 않음)
  • 속도: 반복문은 빠른 실행, 재귀함수는 느린 실행
  • 종료: 반복문은 설정한 조건에 도달할 때까지 반복 실행, 재귀함수는 함수 호출 본문에 조건부를 포함해 재귀를 재호출지 않고 함수를 강제 반환

• 그럼에도 재귀함수를 사용하는 이유

  • 변수 사용을 줄임
  • 가독성 향상
  • 재귀적 표현이 자연스러운 경우 유용(ex. 피보나치 수열, 팩토리얼)

3. 복잡도(BigO, 시간, 공간)

: 알고리즘의 성능을 분석하고 평가하기 위한 척도

• 시간 복잡도(Time Complexity): 수행 시간을 분석한 결과(이지만 아래 이유 때문에 특정 입력을 기준으로 필요한 연산의 횟수)

  • 실제 실행 시간은 하드웨어 성능/프로그래밍 언어 등에 따라 값이 달라지기 때문에 고려하지 않고 명령어의 실행 횟수를 의미

• 공간 복잡도(Space Complexity): 메모리 사용량을 분석한 결과

• Big-O 표기법: 시간/공간 복잡도를 표현하는 대표적인 방법으로, 알고리즘 실행에 있어 최악의 경우를 나타낸다. 즉, 상한선을 기준으로 표기

  • 영향력이 없는 항과 상수 계수를 제거하고 실질적 영향력이 가장 큰 항(최고차항)으로만 복잡도를 표현한다. 함수를 단순화하여 최고차항의 차수만을 고려하는 점근식 표기법
  • 최악의 경우 n번까지 수행되면 프로그램을 끝낼 수 있다(상한 접근)
  • O(1)<O(logN)<O(n)<O(nlogN)<O(n^2)<O(2^n)

• Big-Ω 표기법: Big-O와 반대로 하한선을 기준으로 표기

  • 최소 n번은 수행되어야 프로그램을 끝낼 수 있다(하한 접근)

• Big-θ 표기법: Big-O와 Big-θ를 모두 만족하는 상한선과 하한선 사이를 기준으로 표기

  • 평균적으로 n번 수행되면 프로그램을 끝낼 수 있다(평균값)

• 시간 복잡도를 계산하는 Tip

  • O(1): 어떤 입력에도 항상 같은 시간을 갖는 경우(ex. 변수 대입, 출력 등)
  • O(logN): 문제를 해결하는데 필요한 단계들이 연산마다 특정 요인에 의해 줄어듬
  • O(N): 입력값 크기에 비례해 처리시간이 증가 (ex. for문)
  • O(n^2): 이중 for문같은 경우 (ex. for i in range(N) 안에 for j in range(N)인 경우 i가 N회, j는 i마다 N회)
  • O(2^n): 재귀함수를 한 번 호출할 때마다 2번씩 호출하게 되는 경우(ex. fibonacci(n) 함수 속 fibonacci(n-1)+fibonacci(n-2))

• 알고리즘의 성능 평가

  • Best Case: 최적의 입력을 한 상태에서 작업을 완료하는 데 가장 연산 횟수가 적은 경우
  • Worst Case: 최악의 입력을 한 상태에서 작업을 완료하는 데 가장 연산 횟수가 많은 경우
  • Average Case: 여러 경우의 수를 고려해 총 연산 횟수를 계산하고 시행 횟수로 나눈 경우

• 각 표기법 별 대표 알고리즘

  • O(1): Stack-push/pop
  • O(log[n]): Binary Tree
  • O(n): loop
  • O(nlog[n]): Quick Sort/Merge Sort/Heap Sort
  • O(n^2): 중첩 loop/Insert Sort/Bubble Sort/Selection Sort
  • O(2^n): 피보나치 수열

4. 정렬

: 주어진 데이터를 일정한 기준에 따라 순서대로 나열

• 정렬 시 고려사항

  • 시간 복잡도
  • 메모리 사용량
  • 안정성(stablity) -> 데이터의 순서가 바뀌는지?
  • 직렬 vs 병렬

• 내부 정렬과 외부 정렬

  • 내부 정렬: 정렬할 모든 데이터를 하나의 배열에 저장할 수 있는 경우
  • 외부 정렬: 정렬할 데이터가 많아 하나의 배열에 저장할 수 없는 경우

• 선택 정렬(Selection Sort): 아직 정렬하지 않은 부분에서 가장 값이 작은 원소부터 선택, 알맞은 위치로 옮기는 작업을 반복해 정렬하는 방법

  • 안정성 보장 X
  • 시간 복잡도: O(n^2)

• 삽입 정렬(Insertion Sort): 아직 정렬되지 않은 부분의 맨 앞 원소를 정렬된 부분의 알맞은 위치에 삽입해 정렬하는 방법(두 번째 원소부터 선택해 비교 시작)

  • 안정성 보장 O
  • 시간 복잡도: O(n^2)
    • 이미 정렬되어 있다면 Best case, O(n)

• 버블 정렬(Bubble Sort): 인접한 두 수를 비교 후 필요에 따라 교환을 반복해 정렬하는 방법

  • 안정성 보장 O
  • 시간 복잡도: O(n^2)

• 병합 정렬(Merge Sort): 둘 이상의 부분집합으로 가르고, 각 부분집합을 정렬한 다음 병합하는 방법

  • 안정성 보장 O
  • 분할 정복(Divide-and-Conquer) 사용
    • 해결하고자 하는 문제를 작은 크기의 동일한 문제들로 분할한 후, 각각의 작은 문제를 순환적으로 해결 후 합함
  • 데이터 집합이 메모리에 한 번에 올리기 너무 클 때 좋은 방법
  • 시간 복잡도: O(nlogN)
    • 다른 알고리즘과 비교했을 때 단점: O(n) 수준의 메모리가 추가로 필요

• 힙 정렬(Heap Sort): 최대 힙 트리나 최소 힙 트리를 구성해 정렬하는 방법

  • 안정성 보장 X
  • 내림차순 정렬=최대 힙, 오름차순 정렬=최소 힙
  • 힙의 특성을 이용하기 때문에’ 부모 값이 자식 값보다 항상 크거나, 작아야 한다’는 조건을 만족하는 완전 이진 트리여야 하
  • 시간 복잡도: O(nlogN)

• 퀵 정렬(Quick Sort): 데이터 집합 내 임의로 기준(pivot)값을 정하고 해당 pivot을 기준으로 한 쪽엔 pivot보다 작은 값들/다른 한 쪽엔 큰 값들, 두 개의 부분 집합으로 나눈다. 더 이상 쪼갤 부분 집합이 없을 때까지 반복하는 방법

  • 안정성 보장 X
  • 분할 정복법 사용
  • 시간 복잡도: O(nlogN)
    • Worst case, O(n^2)

5. 완전 탐색(Brute Force)

: 가능한 모든 경우의 수를 시도해 탐색하는 알고리즘 (ex. 3자리 암호의 자물쇠를 풀려고 000~999까지 시도해보는 것)

• 장점: 모든 데이터를 다 뒤지기 때문에 완전탐색으로 못 푸는 문제가 없음
• 단점: 최악의 경우 모든 데이터를 다 뒤져봐야하기 때문에 효율성이 최악
• 구현 방법
  1. Brute-Force기법: 반복/조건문을 활용해 모든 경우의 수를 테스트
  2. 재귀(Recursive): 재귀 함수 사용
  3. 순열(Permutation): n개의 원소 중 r개의 원소를 중복 허용 없이 나열
  4. 비트마스크(Bitmask): 2진수 표현 기법을 활용
     • 모든 경우의 수가 각 원소에 포함되는 경우/포함되지 않는 경우 두 가지 선택으로 구성되는 경우에 유용
  5. BFS/DFS: 그래프에서 완전탐색할 때 사용, 모든 정점을 탐색하기 위한 방법

6. 이분 탐색(Binary Search)

: 정렬된 리스트에서 탐색 범위를 반으로 점차 줄여나가며 특정 값의 위치를 탐색하는 알고리즘

• 장점: 완전탐색보다 효율적이고 속도가 빠름
• 단점: 미리 정렬이 되어있는 리스트에서만 사용 가능
• 구현 방법
  • 초기 left, right 인덱스 값 선언
  • left<=right라면 반복
    • (left+right)/2로 mid값 계산
    • 찾아야 하는 값=mid값, 해당 값 return
    • 찾아야 하는 값<mid, right=mid-1
    • 찾아야 하는 값>mid, left=mid+1

7. 분할 정복(Divide-and-Conquer)

: 너무 복잡하거나 방대한 문제를 나눌 수 없을 때까지 나눠 각각의 하위 문제를 해결한 후, 다시 합쳐 답을 얻는 알고리즘
분할(Divide): 문제를 더 이상 분할할 수 없을 때까지 동일한 유형의 여러 하위 문제로 나눔
정복(Conquer): 가장 작은 단위의 하위 문제를 해결하여 정복
* 조합(Combine): 하위 문제에 대한 결과를 원래 문제에 대한 결과로 조합

• 장점: 병렬적으로 문제를 해결, 한 번에 해결하기 어려운 문제를 나눔으로써 문제를 해결할 수 있음
• 단점: 함수를 재귀적으로 호출(Overhead 발생), 스택에 다양한 데이터를 보관하고 있어야 하기 때문에 Stack overflow가 발생하거나 과도한 메모리 사용

8. 스택(Stack)

: 데이터를 쌓아올린 형태의 선형 자료구조

• top으로 정한 한 쪽 끝에서만 자료를 넣고 뺄 수 있는 LIFO(Last-in-First-out)형식

• 연산
  • pop(): 가장 위에 있는 항목(최근에 추가된)을 제거
  • push(): 가장 윗 부분에 추가
  • peek(): 가장 위에 있는 항목 반환
  • isEmpty(): 비어 있을 때 true 반환
  • isFull(): 꽉 찼을 때 ture 반환
• 구현
  • 배열 or 연결리스트

9. 큐(Queue)

: 줄을 서서 기다리는 형태의 선형 자료구조

• 삽입하는 곳(rear)과 삭제하는 곳(front)가 나뉘어져 있는 FIFO(First-in-First-out)형식

• 연산
  • Enqueue(): 큐 맨 뒤에 요소 추가
  • Dequeue(): 큐 맨 앞에 요소 삭제
  • Peek(): front에 위치한 데이터 읽음
• 구현
  • 배열 or 연결리스트
    • 배열로 구현시 앞에서 삭제시 그 뒤 모든 요소들을 앞으로 이동시켜주어야 하기 때문에 비효율적
• 문제점: 삽입할 수록 rear가 증가하게 되면 결국 full 상태가 된다. 그러나 front에서 삭제가 일어났다면 full 상태가 아닐 수 있다. 그러니 이 때 첫 번째 원소의 위치를 index[0]에 위치하게 만들고, 이를 기준으로 rear 위치도 재정의 해줘야 함. 이 문제로 큐는 원소 이동에 따른 많은 비용이 발생(->해결책: 원형 큐)

10. 우선순위 큐(Priority Queue)

: 들어간 순서에 상관없이 우선순위(priority)가 높은 데이터가 먼저 나오는 것

• 모든 항목에 우선순위가 부여됨

• 우선순위 순으로 나오며 두 요소의 순위가 같으면 FIFO 순서에 따름

• 힙으로 구현하는 것이 가장 효율적

  • 배열: 우선순위에 기반해 전체 비교를 거쳐 알맞은 자리를 찾은 후, 해당 자리에 넣기 위해 전체 자료를 밀어내야 함
  • 연결리스트: 노드 간 연결을 거쳐 모든 노드에 접근해 비교연산을 해야 함

• 힙의 종류

  • 최대 힙: 루트 노드가 가장 큰 값을 가짐 (가장 큰 데이터 우선적 제거)
  • 최소 힙: 루트 노드가 가장 작은 값을 가짐 (가장 작은 데이터 우선적 제거)

• 힙의 삽입

  • 가장 마지막 노드에 추가, 부모 노드와 비교해 위치를 교체하며 올라가는 상향식

• 힙의 삭제

  • 루트 노드를 삭제 후 가장 마지막 노드가 루트 노드가 되어 자식노드와 비교하며 재정렬하는 방식
  • 만약 자식 노드 둘 다 부모 노드보다 낮은 경우 더 낮은 자식 노드로 이동

11. 연결 리스트(Linked List)

: 데이터(노드)가 사슬처럼 순차적으로 연결된 선형 자료구조

• 구조
  • 노드: 데이터를 저장하는 부분+다음 노드에 대한 포인터
  • Head: 첫 번째 노드
  • Tail: 마지막 노드
• 장점
  • 단순한 구조로 이루어져 있어 구현이 편하고 데이터의 추가/삽입/삭제가 쉬움
  • 현재 노드가 가지고 있는 포인터 정보만으로 추가적인 연산 없이 다음 노드를 가져올 수 있음
• 단점
  • 각 노드에 다음 노드를 가리키는 포인터가 필요하기 때문에 메모리가 추가로 필요
  • 헤드 노드의 정보만 가지고 있어 특정 위치에 있는 노드를 탐색하려면 순차적으로 찾아가야 함. 즉 많은 연산이 필요(*O(n), random access 불가능, sequential access)
• 이중 연결 리스트: 앞 뒤 노드 모두 연결 가능
• 원형 리스트: Head와 Tail이 링크된 리스트

12. 해시 테이블(Hash Table)
    : (Key, Value)로 데이터를 저장하는 비선형 자료구조 중 하나

• 각각의 Key값에 해시함수를 적용해 해시값을 얻어 고유한 index를 생성하고, 이 Index를 활용해 값을 저장/검색 (이 때 실제 값이 저장되는 장소 = Buket)

• Hash Function
  • key를 ‘고정된 길이’의 Hash 값으로 변경해줌
  • 서로 다른 key를 Input으로 넣어도 해시값이 동일한 경우가 발생=저장할 버킷이 중복되는 현상, 해시 충돌
  • 그렇기 때문에 가능한 한 해시값이 고르게 분산된 값을 출력하도록 만드는 좋은 function을 사용해야 함
    • 대처 방법 1. 체인법(Chaining): 해시값이 같은 원소를 Linked List로 관리 -> 해당 버킷에서 선형 검색을 함
    • 대처 방법 2. 오픈 주소법(Open Addressing): 빈 버킷을 찾을 때까지 해시를 반복
• Hash값: Value의 key가 됨
• Value: Buket에 저장되는 실질적인 값으로 hash값을 통해 접근 가능
• 장점
  • Key-Value가 1:1 매핑되어 있기 때문에 검색/삽입/삭제 과정 모두 평균 O(1)의 빠른 시간 복잡도를 가짐
  • 빠른 데이터 검색
    • 내부적으로 Buket을 사용해 데이터를 저장하기 때문
    • 배열은 특정 데이터를 찾을 때 Index[0]부터 선형 검색을 해야 하지만, 해시 테이블은 해시값을 Index로 해 새로 저장한 배열에서 값을 찾기 때문
• 단점
  • index를 hash값으로 하기 때문에 순차적인 Index를 보장하지 않는다
  • 최악의 경우, 해시 충돌이 전부 일어난 경우 O(n)의 시간 복잡도를 가짐
  • 데이터가 저장되기 전 미리 공간을 만들어놔야 해 공간 효율성이 떨어짐(공간 복잡도 O(n), n=key의 개수)