Day20

자료구조 및 알고리즘

1. 알고리즘 기초

1-1. 알고리즘 개념

• 알고리즘(Algorithm): 문제를 해결하기 위한 단계적 절차나 규칙

• 알고리즘의 표현 방법:

  • 의사코드: 프로그래밍 언어와 유사하지만 더 자유로운 형태의 표현 방식
    • 특징:
      1. 특정 프로그래밍 언어의 문법을 엄격히 지키지 않아도 됨.
      2. 단계별 논리 흐름(조건, 반복 등)을 구조적으로 표현하기에 좋음.
      3. 실제 코드로 옮기기 수월.
  • 자연어 표기법: 일상적인 언어를 사용하여 알고리즘을 설명하는 방식
    • 특징:
      1. 비전문가도 쉽게 이해할 수 있음.
      2. 전체적인 흐름이나 핵심 아이디어를 빠르게 전달하기 좋음.
      3. 문장이 모호해질 수 있으므로 정확한 표현에 신경 써야 함.

• 좋은 알고리즘의 조건

  1. 정확성
     • 입력한 값에 대해 올바른 결과가 나와야함.
     • 정해진 단계를 따라 실행되고, 반드시 멈추는 시점이 있어야함.
     • 값은 입력값이면 항상 같은 결과가 나와야함.
  2. 효율성
     • 시간 복잡도: 실행 시간이 너무 오래 걸리지 않아야 함.
     • 공간 복잡도: 컴퓨터의 메모리를 적절하게 사용해야함.
  3. 명확성
     • 각 단계가 명확하고 이해하기 쉬워야 함.
     • 다른 사람도 읽고 이해할 수 있어야 함.
     • 필요한 경우 주석으로 설명을 추가하면 좋음.
  4. 확장성
     • 다양한 상황에서 사용할 수 있어야함.
     • 나중에 수정하거나 개선하기 쉬워야 함.
     • 문제가 생겼을 때 어디가 잘못됐는지 찾기 쉬워야 함.

• 알고리즘 성능 분석

  • 알고리즘이 얼마나 효율적으로 동작하는지를 측정하는 방법
  • 주로 시간(실행 속도)과 공간(메모리 사용량)을 기준으로 평가
  • 주로 빅오(Big-O) 표기법을 사용하여 얼마나 시간이 필요한지 나타냄.

빅오 표기법은 알고리즘의 시간 복잡도를 수학적으로 표현한 방법

시간 복잡도	데이터 크기 상한	대표알고리즘	특징	비고
O(1)		배열 인덱스 접근, 스택/큐 삽입/삭제	입력 크기와 관계없이 항상 같은 시간
O(log N)	10^18 (64비트 정수 최대값)	이진 탐색, 균형 이진 탐색 트리	입력이 커져도 시간이 로그 값으로 증가	N이 매우 커도 빠르게 동작
O(N)	10^8 (1억)	배열 순차 탐색, 최대/최소값 찾기	입력과 시간이 비례하여 증가	1초에 수행 가능
O(N log N)	10^6 (백만)	병합정렬, 퀵소트, 힙정렬	가장 효율적인 비교 기반 정렬 알고리즘	N=10^7에서 2.3초 소요
O(N²)	10^4 (만)	버블정렬, 삽입정렬, 선택정렬	입력이 커지면 입력 크기의 제곱으로 시간 증가	1초 정도 소요
O(2^N)	20	부분 집합 생성	입력이 커지면 지수적으로 증가	N=30만 되어도 10초 소요
O(N!)	10	순열 생성	입력이 증가할 때마다 시간이 팩토리얼로 폭발적 증가	N이 조금만 커져도 시간이 기하급수적 증가

• 시간 복잡도 계산하는 법
  1. 명령문 개수 계산
     • 반복문, 조건문, 대입문 등 각각의 명령문이 실행되는 횟수를 계산
     • 각 줄의 실행 횟수를 더하여 전체 실행 횟수를 구함
  2. 가장 큰 항만 남기기(빅오 표기법)
     • 입력 크기(n)가 매우 커질 때는 작은 항들의 영향력이 미미해지기 때문에 가장 큰 항만 고려함
     • 상수항은 실제 실행 환경에 따라 달라질 수 있어서 제외
     • 증가 추세를 파악하는 것이 목적이므로 정확한 횟수보다는 전체적인 증가 패턴이 중요

• 알고리즘 풀이 방법
  1. 어떻게 풀어야하나
     • 알고리즘 문제를 해결할 때 가장 큰 실수는 문제를 제대로 이해하지 않고 바로 코딩을 시작하는 것
     • 이러면 문제의 전체 흐름을 파악하지 않고 부분적으로만 구현하게 됨
     • 과도하게 하나의 반복문에 모든 로직을 처리하기보다, 코드의 가독성과 유지보수성을 고려하여 각 기능을 논리적으로 분리하는 것이 바람직
     • 문제 분석의 중요성
       1. 문제의 제약 조건을 놓치면 정확성과 효율성 모두를 놓치게 됨.
       2. 문제의 전체 구조를 보지 못하고 부분적인 해결에만 집중하게 됨
       3. 잘못된 방향의 구현은 디버깅과 수정에 많은 시간이 소요됨
     • 문제 해결 아이디어 설계의 중요성
       1. 문제의 전체 흐름을 파악해야 모든 예외 상황을 고려할 수 있음
       2. 복잡한 문제일수록 전체적인 로직을 먼저 설계하고, 이를 단계별로 구현하는 것이 중요
       3. 실무에서도 체계적인 설계 없이 구현하면 유지보수가 어려워지고, 버그 발생 가능성이 높아짐
  2. 알고리즘 문제해결 5단계

     1단계: 문제 이해 및 요구사항 분석하기
         - 문제를 천천히 정독하기
         - 예제 입출력을 통해 문제의 의도 파악하기
          - 주어진 입력과 출력 형식을 정확히 파악하기
          - 제약 조건과 요구사항, 규칙 정리하기
     
     2단계: 접근 방법 구상하기
          - 비슷한 유형의 문제 생각하기
          - 어떠한 유형의 알고리즘을 사용할지 정하기
          - 문제를 해결하기 위한 기본 아이디어 고안 혹은 문제 해결 절차에 대해 단계별로 나누기 및 도식화
     
     3단계: 세부 구현 설계 및 검토하기
          - 문제 해결 절차의 각 단계를 의사코드로 표현하기
          - 발생할 수 있는 예외 상황 찾아보기
          - 극단적인 케이스 고려하기
          - 시간 복잡도 분석하기 
     
     4단계: 코드 작성 및 구현하기
          - 세부 구현으로 표현된 아이디어를 실제 코드로 작성하기
          - 구현 과정에서 변수명, 함수명을 명확하게 작성하기
     
     5단계: 테스트와 디버깅
          - 다양한 테스트 케이스를 통해 코드의 정확성을 검증하기
            * 예시 입출력으로 테스트하기
            * 극단적인 케이스로 테스트하기
          - 오류가 발생하면 디버깅하기
          - 시간 초과의 경우 아이디어 수정 및 코드 최적화하기
            * 효율적인 입력 처리 고려
            * 적절한 자료구조 선택
            * 중복 계산 방지 (메모이제이션) 
            * 유망하지 않은 탐색 가지치기 (백트래킹)```

---

알고리즘 유형

1. 구현(Implementation) & 시뮬레이션(Simulation)

• 구현 문제: 문제의 요구사항을 실제 동작하는 코드로 구현 하는 능력이 중요합니다.
• 시뮬레이션 문제: 문제에서 요구하는 시나리오, 규칙, 절차를 차례대로 실행하는 능력이 요구됩니다.
• 특징
  1. 코딩 테스트에서 가장 기본이 되는 문제 유형입니다.
  2. 알고리즘적 난이도보다는 구현의 정확성이 중요합니다
  3. 요구사항을 빠짐없이 코드로 옮기는 것이 핵심입니다
  4. 문제의 조건과 제약을 정확히 이해하고 처리해야 합니다
• ⚠️주의⚠️
  • 구현 과정에서 자잘한 실수(인덱스 범위, 예외 상황 처리 등)를 하기 쉽기 때문에 꼼꼼함이 중요합니다.
  • 디버깅을 통한 중간 결과 검증이 매우 중요합니다.
  • 구현/시뮬레이션 문제를 해결할 때 가장 많이 하는 실수는 문제의 전체 흐름을 파악하지 않고 부분적으로 구현하는 것입니다.
• 구현 및 시뮬레이션의 주요 유형
  1. 단순 구현 : 주어진 알고리즘이나 규칙을 그대로 코드로 옮기는 문제입니다.
  2. 완전 시뮬레이션 : 문제에서 제시된 과정을 처음부터 끝까지 실행하여 결과를 도출하는 문제입니다.
  3. 상태 변화 시뮬레이션 : 특정 조건에 따라 시스템의 상태가 변화하는 과정을 구현하는 문제입니다.
  4. 규칙 찾기 및 구현 : 문제의 숨겨진 규칙을 찾아 이를 코드로 구현하는 문제입니다.

2. 완전 탐색 (Brute Force)

• 모든 경우의 수를 빠짐없이 조사하여 정답을 찾는 방법입니다.
• 특징
  1. 모든 경우를 시도하므로, 정답을 놓칠 가능성이 없습니다(시간과 메모리가 충분하다면).
  2. 입력 규모가 작을 때 유리하며, 구현이 비교적 간단합니다.
• 구현 방법
  1. 반복문을 이용한 구현
  2. 재귀 함수를 이용한 구현
• 대표적인 문제 유형
  1. 순열/조합 계산
  2. 부분집합 계산
  3. 그래프 전체 탐색

3. 그리디(Greedy) 알고리즘

• 매 순간 가장 최선의 선택를 함으로써 전체 최적해를 구하는 방식입니다.
• 특징
  • 다른 알고리즘(예: 완전탐색, 동적 계획법 등)보다 일반적으로 구현이 간단하고, 빠른 시간 안에 결과를 얻을 수 있습니다.
• 그리디 알고리즘의 적용 조건
  1. 탐욕 선택 속성(Greedy Choice Property)
     • 매 순간의 최선의 선택이 전체 문제의 최적해가 되어야 합니다.
  2. 최적 부분 구조(Optimal Substructure)
     • 부분 문제의 최적해들을 결합해 전체 문제의 최적해를 구할 수 있어야 합니다
• 대표적인 문제 유형
  1. 거스름돈 계산
  2. 회의실 배정 문제
  • 최소 신장 트리(MST)
    • 크루스칼(Kruskal), 프림(Prim) 알고리즘

4. 백트래킹 (Backtracking)

• 완전 탐색을 기반으로 하되, 유망하지 않은 경우(조건 불만족)는 미리 배제(가지치기) 하여 탐색 효율을 높이는 기법입니다.
• 특징
  1. 조건을 만족할 수 없는 상황을 빠르게 배제할 수 있어, 탐색 범위를 크게 축소할 수 있습니다.
  2. 대부분 재귀 함수로 구현합니다.
• 백트래킹의 적용 조건
  1. 상태 공간 트리 구성 가능성
     • 문제의 해결 과정을 트리 형태로 구조화할 수 있어야 합니다.
     • 각 단계별 선택지를 명확하게 정의할 수 있어야 합니다.
     • 예: 1부터 N까지의 수를 중복 없이 나열하는 순열 문제에서 각 자리수 선택
  2. 유망성 판단 기준(Promising)
     • 현재 상태에서 더 진행할 가치가 있는지 판단할 수 있는 명확한 기준이 있어야 합니다.
     • 예: 길 찾기 문제에서 벽이나 이미 방문한 곳인지 확인
  3. 가지치기 효율성
     • 유망하지 않은 경우를 제외했을 때 탐색 범위가 충분히 줄어들어야 합니다.
     • 가지치기 조건 검사가 너무 복잡하지 않아야 합니다.
     • 예: 특정 합을 만드는 문제에서 현재까지의 합이 목표값을 넘어선 경우
• 대표적인 문제 유형
  1. N-Queen 문제
     • 퀸이 서로 공격하지 않도록 배치하는 경우의 수를 찾는 문제
  2. 스도쿠 풀이
     • 불가능한 경우를 빠르게 가지치기해가며 정답을 찾는 방식
  3. 부분집합의 합
     • 특정 조건(목표 값 등)을 만족하는 부분집합을 찾기

5. 분할 정복 (Divide and Conquer)

• 문제를 작거나 유사한 하위 문제로 분할하고, 각 문제를 해결한 뒤 결과를 합쳐 최종 해를 구하는 방식입니다.
• 특징
  1. 분할 → 정복(해결) → 병합 단계를 거칩니다.
  2. 분할된 각 부분 문제는 서로 독립적이어야 합니다.
• 분할 정복의 적용 조건
  1. 분할 가능성(Divisibility)
  • 문제가 동일한 유형의 더 작은 하위 문제들로 나눠질 수 있어야 합니다
  • 분할된 문제는 원래 문제와 같은 성질을 가져야 합니다
  • 예: 병합정렬에서 배열을 더 작은 배열로 분할할 수 있음
  2. 하위 문제의 독립성(Independence)
  • 분할된 하위 문제들은 서로 독립적이어야 합니다
  • 어떤 하위 문제의 해결이 다른 하위 문제의 해결에 영향을 주지 않아야 합니다
  • 예: 퀵정렬에서 피벗을 기준으로 나눈 두 부분이 서로 독립적
  3. 병합 가능성(Mergeability)
  • 하위 문제들의 해답을 병합하여 원래 문제의 해답을 만들 수 있어야 합니다
  • 예: 병합정렬에서 정렬된 두 부분 배열을 하나의 정렬된 배열로 병합 가능
• 대표적인 문제 유형
  1. 병합 정렬(Merge Sort)
     • 배열을 반으로 나눈 뒤 각각 정렬 후 병합
  2. 퀵 정렬(Quick Sort)
     • 피벗(Pivot)을 기준으로 왼쪽은 피벗보다 작은 요소들, 오른쪽은 큰 요소들로 재귀적 정렬
  3. 이진 탐색(Binary Search)
     • 검색 구간을 절반씩 줄여가며 원하는 값을 찾는 방법

6. 동적 계획법 (Dynamic Programming, DP)

• 큰 문제를 작은 부분 문제들로 나누고, 각 부분 문제의 해를 저장(메모이제이션) 하여 재활용함으로써 전체 문제의 최적 해를 구하는 알고리즘 설계 기법입니다.
• 특징
  • 중복 계산을 획기적으로 줄일 수 있어, 지수 시간이 걸리는 문제도 다항 시간 안에 풀 수 있는 경우가 많습니다.
  • Top-Down 방식(메모이제이션) 또는 Bottom-up 방식(타뷸레이션)으로 구현합니다.
  • 점화식(Recurrence Relation)을 올바르게 세우는 것이 핵심입니다.
• 동적 계획법의 적용 조건
  • 최적 부분 구조(Optimal Substructure)
    • 작은 부분 문제들의 최적해들을 조합하여 큰 문제의 최적해를 구할 수 있어야 합니다.
    • 예: 최단 경로 문제에서 서울 → 대전 → 대구 → 울산 → 부산이 최단경로라면 다른 모든 부분 경로들(서울→ 대전→ 대구 등)도 각각 최단 경로여야 한다.
  • 중복되는 부분 문제(Overlapping Subproblems)
    • 동일한 작은 문제들이 반복적으로 나타나야 합니다.
    • 이러한 중복 문제들의 해를 저장해두고 재활용할 수 있어야 합니다.
    • 예: 피보나치 수열에서 f(n)을 구할 때 f(n-2)가 여러 번 계산됨
• 대표적인 문제 유형
  1. 수열 문제
     • 피보나치 수열: f(n) = f(n-1) + f(n-2)
  2. 최적화 문제
     • 배낭 문제(Knapsack Problem): 무게 제한이 있는 배낭에 물건들을 넣을 때, 가치의 합이 최대가 되도록 물건을 고르는 문제
     • 최장 증가 부분 수열(LIS: Longest Increasing Subsequence): 주어진 수열에서 증가하는 부분 수열 중 가장 긴 길이 찾기
  3. 경로 문제
     • 미로 찾기(최단 경로)

---

1-2. 완전 탐색과 그리디 알고리즘

---

1-3. 알고리즘 유형병 문제 및 가이드