Algorithm

LeetCode, Programmers 문제 풀이

알고리즘

🧱 구현(Implementation)

• 시뮬레이션(Simulation)
  : 문제에서 제시한 알고리즘을 한 단계씩 차례대로 수행
• 완전 탐색(Brute Force)
  : 모든 경우의 수를 전부 탐색
  • DFS/BFS
    : 그래프를 탐색하는 대표적인 알고리즘. DFS는 너비를 우선적으로 탐색하며 스택이나 재귀함수로 구현, BFS는 깊이를 우선적으로 탐색하며 큐로 규현
  • Permutation & Combination
    : 순열과 조합으로 가능한 모든 경우의 수 탐색
  • Recursion
    : 재귀 호출을 이용해 가능한 모든 경우의 수 탐색
  • Back Tracking
    : 가능한 모든 경우를 탐색하지만, 조건에 맞지 않는 경로는 미리 배제하여 탐색 횟수를 줄임
  • Bitmask
    :비트 연산을 사용해 부분 집합 문제나 특정 조건을 만족하는 경우의 수를 효율적으로 탐색

😈 그리디(Greedy)

매 선택에서 가장 비용이 적은 노드를 고르는 방법.

• Kruskal(minimum spanning tree)
  : 최소 신장 트리를 찾기 위한 알고리즘
• Dijkstra(shortest path)
  : 그래프에서 여러 노드가 존재할 때, 특정 노드에서 출발해 다른 노드로 가는 각각의 최단 경로를 구할 경우 사용

📥📤 동적 프로그래밍(Dynamic Programming)

전체 문제의 답을 부분 문제로 쪼개서 풀더라도 최종 결과 역시 최선의 선택이 되는 '최적 부분 구조' & 쪼개진 부분 문제들에서 동일한 패턴이 반복적으로 등장하는 '중복되는 부분 문제' 형태를 이루는 문제를 해결하는 알고리즘. 메모리를 더 사용하더라도 연산 속도를 증가시키는 것이 목적

• Memoization: 하향식 접근법
• Tabulation: 상향식 접근법
  • Floyd-Warshall(shortest path): 모든 지점에서 다른 모든 지점까지의 최단 경로를 모두 구해야 하는 경우 사용

🗂️ 정렬(Sorting)

데이터를 특정 기준에 따라 순서대로 나열하는 알고리즘

• 선택 정렬(Selection Sort)
  : 매번 가장 작은 데이터를 선택해 정렬된 데이터의 뒤로 정렬
• 삽입 정렬(Insertion Sort)
  : 삽입할 위치 이전 데이터는 이미 정렬되어있다는 가정 하에 특정 데이터를 적절한 위치에 삽입하여 정렬
• 병합 정렬(Merge Sort)
  : 분할 정복 기법을 사용하여 작동. 배열을 반으로 나누고 각 부분 배열을 재귀적으로 정렬한 다음, 정렬된 부분 배열을 병합하여 전체 배열을 정렬
• 퀵 정렬(Quick Sort)
  : 분할 정복 기법을 사용하여 작동. 피벗을 선택하고, 피벗을 기준으로 배열을 분할함. 피벗보다 작은 요소는 피벗의 왼쪽에, 큰 요소는 오른쪽에 위치하도록 재배치한 다음 각 부분 배열에 대해 재귀적으로 정렬을 수행
• 계수 정렬(Count Sort)
  : 모든 데이터가 양의 정수ㄴ일 때 값을 비교하지 않고 값의 발생 횟수를 이용해 정렬. 현존하는 정렬 알고리즘 중 기수 정렬과 더불어 가장 빠름

👓 이진 탐색(Binary Search)

정렬된 데이터로 현재 데이터 값의 크기가 원하는 테이더 값의 크기보다 큰지 작은지 판단하여 탐색 방향을 정함으로써 필요 없는 부분은 탐색하지 않음

💡 시간복잡도 최적화 기법

• Pre-fix Sum
  :구간 합이 반복적으로 필요한 경우 배열의 각 원소까지의 누적된 합을 미리 계산하여 저장하는 기법
• Grid Compression
  : 좌표 압축을 통해 시, 공간 복잡도를 최적화하는 기법. 큰 좌표 값을 작은 범위의 연속된 값으로 변환하여 메모리 사용을 줄이고 연산 속도를 높임
• LR Technique
  : 배열을 왼쪽에서 오른쪽으로, 오른쪽에서 왼쪽으로 순회하여 특정 조건을 만족하는 구간을 빠르게 찾음
• +1-1 Technique
  : 구간의 시작 지점에 +1, 끝 지점에 -1을 하여 구간 내의 모든 값을 빠르게 계산하는 기법. 주로 구간의 빈도 수 계신 시 사용
• Tow Pointers
  : 배열이 하나 주어졌을 때, 시작과 끝 포인터를 조정해 값이 아닌 원하는 값의 위치를 찾는 기법. 이진 탐색과 비슷한 원리로 두 포인터를 양쪽 끝에서 시작하거나, 두 포인터 모두 0에서 시작하지만 하나는 진행 속도를 느리게, 하나는 빠르게 해 특정 구간을 만들어 해당 구간 내에 내가 원하는 데이터가 있는지 확인할 수 있음
• Sliding Window
  : 고정된 크기의 윈도우를 배열 또는 문자열 위에서 이동시키면서 특정 조건을 만족하는 구간을 찾는 기법

자료구조

선형 자료구조

• Array
  : 데이터를 연속된 메모리 공간에 저장하는 자료구조. 인덱스를 사용해 빠른 접근 가능
• Linked List
  : 노드들이 포인터로 서로 연결된 자료구조. 각 노드는 값과 다음 노드를 가리키는 포인터를 가지고 있음.
• Stack
  : 선입후출 구조로 데이터를 삽입하거나 추출할 때 맨 위에서 이루어짐. 주로 DFS 구현에 사용
• Queue
  : 선입선출 구조로 데이터를 삽입하거나 추출할 때 맨 앞에서 이루어짐. 주로 BFS에 사용
• Deque(Double-Ended Queue)
  : 양쪽 끝에서 삽입, 삭제가 모두 가능. 주로 이중 연결리스트로 구현
• Hash Table
  : 키를 값에 매핑할 수 있는 연관 배열

비선형 자료구조

• Graph
  : 노드와 노드 사이의 관계를 표현하는 자료구조. 노드들 간에 간선(edge)으로 연결됨. 방향성 및 순환성 여부에 따라 여러 종류가 있음.
  • Undirected Graph
    : 간선에 방향이 없는 그래프
  • Directed Graph
    : 간선에 방향이 있는 그래프
    • Cycle Graph
      : 순환 구조가 있는 방향 그래프
    • Acycle Graph
      : 순환 구조가 없는 방향 그래프
      • Tree
• Tree
  : 계층적 구조를 표현하기 위한 비순환 방향 그래프. 재귀로 정의된 자기참조형 자료구조. 루트 노드에서 시작해 각 노들이 부모-자식 관계를 가짐
  • Degenerate Tree
    : 모든 노드가 하나의 자식만을 가진 트리
  • Binary Tree
    : 각 노드가 두 개의 자식을 가질 수 있는 트리
    • Full Binary Tree
      : 모든 노드가 0개 또는 2개의 자식 노드로 구성
    • Perfect Binary Tree
      : 모든 노드가 2개의 자식 노드를 가지고 있으면서 모든 리프 노드가 동일한 깊이로 구성
    • Compelete Binary Tree = Heap
      : 리프 노드들을 제외하고 모든 노드가 완전히 채워져 있으며 리프 노드들은 가장 왼쪽부터 채워지도록 구성. Priority Queue 구현에 사용
    • Binary Search Tree
      : 모든 노드에 대해서 왼쪽 자식 노드는 부모 노드보다 작고 오른쪽 자식 노드는 부모 노드보다 큰 이진 트리
      • Self-balancing Binary Search Tree
        : 삽입 또는 삭제 연산을 수행할 때 회전을 통해 트리의 균형을 유지하는 이진 탐색 트리
        • AVL Tree
          : 각 노드에서 왼쪽 서브트리와 오른쪽 서브트리의 높이 차이가 1보다 크지 않도록 균형을 유지
        • Red-Black Tree
          : AVL 트리보다 더 유연한 구조를 가지며, 균형을 조절하기 위해 회전 뿐만 아니라 색깔 변경도 수행. 루트 노드와 모든 리프 노드는 블랙, 레드 노드의 자식은 모두 블랙이라는 특징을 가지고 있음
    • Binary Balanced Tree
      : 각 노드가 균형을 가진 이진 트리
  • B-Tree(Balanced Tree)
    : 다양한 자료를 효율적으로 탐색하기 위해 고안된 균형 이진 트리
  • B+Tree
    : B-Tree의 변형으로 모든 값이 리프 노드에만 있고, 모든 리프노드가 동일한 깊이에 있는 트리
  • B*Tree
    : B-Tree의 확장으로 더 컨 자료를 처리하고 트리의 높이를 줄이는 데 사용
  • Trie
    : 키-값 쌍을 저장하는 트리로, 각 노드에는 키에 대한 한 문자가 저장되며, 주로 문자열 검색에 사용