🗓️ 2025년 7월 11일 (금) 오늘 하루 일정

✅ 오전

• 09:00 ~ 11:30
  • 알고리즘 기초 개념 학습
    • 시간 복잡도 vs 공간 복잡도
    • 정렬 알고리즘 개요 및 종류
    • 선택 정렬, 삽입 정렬, 버블 정렬, 퀵 정렬, 병합 정렬 정리
    • 탐색 알고리즘 개요 및 DFS, BFS, 이진 탐색 정리
    • 최단 경로 알고리즘: 다익스트라, 벨만-포드
• 11:30 ~ 13:00
  • C# 체크리스트 강의 Day.4 수강 (반복문 주제)

🍽️ 점심시간

• 13:00 ~ 14:00
  • 점심시간

✅ 오후

• 14:00 ~ 18:00
  • 오전에 학습한 알고리즘 전체 복습
  • 문제 풀이: Histogram에서 최대 직사각형 (LeetCode 84)
    • ToList(), Stack 사용 방식, while 조건 이해
  • 문제 풀이: Flood Fill (LeetCode 733)
    • DFS를 이용한 그림 색칠 방식 이해
  • 문제 풀이: Longest Increasing Subsequence (LeetCode 300)

🍽️ 저녁시간

• 18:00 ~ 19:00
  • 저녁시간

✅ 저녁

• 19:00 ~ 20:30
  • 정렬 알고리즘 & 탐색 알고리즘 복습
    • 삽입 정렬 while문의 역할
    • List와 배열, 제네릭 타입 관련 개념 정리

✅ 오늘 학습 키워드

• 시간 복잡도 / 공간 복잡도
• 기초 정렬 알고리즘
  • 선택 정렬
  • 삽입 정렬
  • 버블 정렬
• 고급 정렬 알고리즘
  • 퀵 정렬
  • 병합 정렬
• 탐색 알고리즘
  • 선형 탐색
  • 이진 탐색
  • DFS / BFS
• 최단 경로 알고리즘
  • 다익스트라
  • 벨만-포드
• C# 리스트 구조 이해
  • List<int> vs List<int>[]
  • List<(int, int)> 구조
• 문제 풀이 실습
  • 84번: Histogram에서 가장 큰 직사각형
  • 733번: Flood Fill
  • 300번: 최장 증가 부분 수열 (LIS)

✅ 오늘 학습 한 내용을 나만의 언어로 정리하기

오늘은 알고리즘 공부에 집중했다.

우선 시간 복잡도와 공간 복잡도의 개념부터 다시 정리했는데,

코드가 얼마나 오래 걸릴지, 얼마나 많은 메모리를 차지하는지를

Big-O 표기로 표현한다는 점을 다시 되짚었다.

그다음은 정렬 알고리즘들을 살펴봤다.

• 선택 정렬은 제일 작은 값을 찾아서 앞으로 보내는 방식이었고,
• 삽입 정렬은 앞에서부터 정렬된 상태를 유지하면서 새 값을 알맞은 위치에 "삽입"하는 구조였다.한 칸씩 왼쪽으로 이동하며 비교하기 위해서였다.
• 삽입 정렬의 while문 안에서 j-- 하는 이유도 알 수 있었다.

버블 정렬은 인접한 요소끼리 계속 비교해서 가장 큰 값을 뒤로 보내는 단순한 구조였고,

퀵 정렬과 병합 정렬은 분할 정복 기법을 활용해 효율적으로 정렬하는 고급 정렬 방식이었다.

정렬만큼 중요한 게 탐색이었다.

선형 탐색은 단순히 앞에서부터 찾는 방식,

이진 탐색은 정렬된 배열을 반으로 나누며 탐색하는 방식이었다.

또, DFS와 BFS는 그래프 탐색에서 자주 쓰이는 기본 알고리즘으로,

DFS는 깊이 우선, BFS는 너비 우선이라는 차이를 가졌다.

최단 경로 알고리즘도 정리했는데,

다익스트라는 우선순위 큐와 거리 배열을 활용해서 가장 짧은 경로를 찾고,

벨만-포드는 음수 간선이 있을 때도 사용할 수 있지만 시간이 오래 걸리는 알고리즘이었다.

문제 풀이도 여러 개 해봤다.

• 84번 히스토그램 문제에서는 스택을 이용해 최대 직사각형 넓이를 구했고,
• 733번 Flood Fill 문제는 DFS를 활용해서 같은 색 영역을 바꾸는 문제였다.
• 300번 LIS 문제에서는 DP를 활용해 가장 긴 증가 수열의 길이를 찾았다.

마지막으로 C#의 제네릭 컬렉션도 다시 정리했다.

List<int>는 단순 리스트고, List<int>[]는 리스트 배열,

List<(int, int)>은 튜플로 좌표나 쌍을 저장할 때 유용하다는 걸 배웠다.

사실 모든걸 이해하지는 못했지만 반복학습이 답일듯 싶다. 배울때 많이 배우고 복습 열심히하자!

🧩 학습하며 겪었던 문제점 & 에러

1. 문제정의: 삽입 정렬에서 j--의 동작이 직관적으로 이해되지 않았음

💻 관련 코드 예시:

for (int i = 1; i < arr.Length; i++)
{
    int key = arr[i];
    int j = i - 1;

    while (j >= 0 && arr[j] > key)
    {
        arr[j + 1] = arr[j];
        j--;  // ❗ 이 부분이 왜 필요한지 헷갈림
    }
    arr[j + 1] = key;
}

• 시도:
• j--가 어떤 역할을 하는지 흐름을 직접 손코딩하며 추적함
• 해결방법:
• 정렬된 구간 안에서 값을 비교하면서 왼쪽으로 한 칸씩 이동한다는 구조를 시각화함
• 새롭게 알게 된 점:
• j--는 값을 한 칸 왼쪽으로 이동하면서 앞쪽 값과 계속 비교하기 위한 인덱스 조절임
• 다시 만나게 된다면:
• 반복문에서 인덱스 흐름이 복잡할 땐 직접 배열 상태를 표로 그려보며 흐름을 따라가자. 사실 내가 순간적으로 이해하지 못했었다.. 다시 천천히 보니 이해 확실!

2. 문제정의: 2차원 배열의 특정 값을 변수로 복사할 때 참조와 복사의 차이를 헷갈렸음

💻 관련 코드 예시:

int[,] image = {
    {1, 1, 0},
    {1, 1, 0},
    {0, 0, 1}
};

int sr = 0, sc = 0;
int originalColor = image[sr, sc];  // ❗ 이 값이 원본과 어떻게 연결되는지 헷갈림

• 시도:
• originalColor를 수정해도 원본 배열이 바뀌는지 실험해봄
• 해결방법:
• int는 값 형식이라 복사되는 값이며, 배열의 참조가 아님을 확인
• 새롭게 알게 된 점:
• originalColor는 image 내부의 값을 복사한 독립된 값이므로 이후 원본과는 무관함
• 다시 만나게 된다면:
• 값 형식인지 참조 형식인지부터 먼저 따지고, 복사인지 연결인지를 구분하자

3. 문제정의: Longest Increasing Subsequence 문제 풀이에서 while문 흐름이 어려웠음

💻 관련 코드 예시:

List<int> dp = new List<int>();
foreach (int num in nums)
{
    int left = 0, right = dp.Count;
    while (left < right)
    {
        int mid = (left + right) / 2;
        if (dp[mid] < num)
            left = mid + 1;
        else
            right = mid;
    }

    if (left == dp.Count)
        dp.Add(num);
    else
        dp[left] = num;
}

• 시도:
• while문 조건과 이진 탐색 흐름이 감이 안 와서 각 변수 변화 과정을 출력해봄
• 해결방법:
• 람다식, 컬렉션 등을 하나씩 분해해서 단계별로 해석하고, dp 리스트의 변화 과정을 직접 따라감
• 새롭게 알게 된 점:dp는 증가 수열을 시뮬레이션하는 용도임
• 이 방식은 실제 LIS를 구하는 게 아니라 길이와 패턴만 유지하는 방식이며,
• 다시 만나게 된다면:
• 복잡한 알고리즘일수록 흐름을 그대로 받아들이기보다, 데이터 변화 흐름을 눈으로 확인하는 게 중요함

📝 메모

오늘은 정말 많은 알고리즘들을 배우고 복습한 하루였다. 처음엔 삽입 정렬이나 LIS 문제처럼 익숙하지 않은 로직 앞에서 살짝 멍해졌지만, 그럴수록 흐름을 따라가고 손으로 써보면서 하나씩 내 걸로 만들었다. 특히 “왜 이 코드가 이렇게 작동하지?”라는 질문을 놓지 않았던 게 결국 이해로 이어졌다는 걸 느꼈다.

“모르는 걸 부끄러워하지 말고, 이해하려는 과정을 포기하지 말자.” 오늘도 이 말이 딱 내 하루였다.

혼란스러웠던 코드들을 곱씹고 정리하는 이 시간이 내 실력을 한 단계 올려주는 귀한 과정이라는 걸 잊지 말자. 오늘보다 조금 더 성장한 나로 다시 공부 시작하면 된다!!!오예!! 😊

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

개념

• 복잡한 문제를 작은 하위 문제로 나누어 풀고, 결과를 저장해 재사용
• 조건: 최적 부분 구조, 중복 부분 문제

구현 방식

• Top-down: 재귀 + 메모이제이션
• Bottom-up: 반복문으로 작은 문제부터 해결

예시 (피보나치 Bottom-up)

int Fibonacci(int n) {
    int[] dp = new int[n + 1];
    dp[0] = 0; dp[1] = 1;
    for (int i = 2; i <= n; i++)
        dp[i] = dp[i - 1] + dp[i - 2];
    return dp[n];
}

대표 문제

피보나치 수열, 계단 오르기, 최소 동전, LCS, 배낭 문제

중복되는 하위 문제를 저장해 재활용하며 푸는 방법
→ 비효율적인 재귀 호출을 피하고 성능을 극대화함.

📌 대표 예시: 피보나치 수열, 계단 오르기, 최소 비용 문제

"같은 계산을 두 번 하지 않는다!"

2. 🪙 그리디 알고리즘 (Greedy)

개념

• 매 순간 최적의 선택을 하는 알고리즘
• 전체 최적을 보장하려면 특정 조건을 만족해야 함

예시 (동전 거스름돈)

int CoinChange(int[] coins, int target) {
    Array.Sort(coins); Array.Reverse(coins);
    int count = 0;
    foreach (int coin in coins) {
        count += target / coin;
        target %= coin;
    }
    return count;
}

대표 문제

동전 교환, 회의실 배정, 활동 선택, 최소 스패닝 트리

매 순간 가장 최적인 선택을 하는 방식
→ 전체 최적해가 보장되지는 않지만, 특정 조건에서는 매우 빠르고 정확함.

📌 대표 예시: 동전 거스름돈, 회의실 배정, 최소 회의 수

"지금 가장 좋은 걸 고르자!"

3. ⚔️ 분할 정복 (Divide and Conquer)

개념

• 문제를 작게 나누고, 각각 해결, 결과를 합쳐서 해결

예시 (이진 탐색)

int BinarySearch(int[] arr, int target) {
    int left = 0, right = arr.Length - 1;
    while (left <= right) {
        int mid = (left + right) / 2;
        if (arr[mid] == target) return mid;
        if (arr[mid] < target) left = mid + 1;
        else right = mid - 1;
    }
    return -1;
}

대표 문제

병합 정렬, 퀵 정렬, 이진 탐색, 거듭제곱, Karatsuba 곱셈

문제를 작게 나누고 → 각각 해결하고 → 다시 합쳐서 해결
→ 정렬, 탐색 등 대규모 데이터를 다룰 때 성능이 뛰어남.

📌 대표 예시: 퀵 정렬, 병합 정렬, 이진 탐색

"쪼개서 풀고, 다시 합쳐서 해결한다!"

4. 🔙 백트래킹 (Backtracking)

개념

• 모든 경우의 수 탐색 + 유망하지 않으면 가지치기
• DFS 기반 + 조건 검증

대표 문제

N-Queen, 스도쿠, 미로 찾기, 조합/순열 생성

모든 경우의 수를 탐색하지만, 유망하지 않으면 미리 포기(가지치기)
→ 순열/조합, 퍼즐, N-Queen 등에서 강력한 기법.

📌 대표 예시: N-Queen, 스도쿠, 조합 만들기

"정답이 아닐 것 같으면 일찍 그만두자!"

5. 🔗 유니온-파인드 (Disjoint Set / Union-Find)

개념

• 여러 노드가 같은 집합인지 판별하거나 병합
• 주로 그래프 사이클 탐지나 네트워크 연결에 사용

예시

int Find(int[] parent, int x) {
    if (parent[x] != x) parent[x] = Find(parent, parent[x]);
    return parent[x];
}

void Union(int[] parent, int a, int b) {
    int rootA = Find(parent, a);
    int rootB = Find(parent, b);
    if (rootA != rootB) parent[rootB] = rootA;
}

여러 노드가 같은 그룹인지 빠르게 확인하고 병합하는 구조
→ 네트워크 연결, 사이클 여부 확인 등에 사용됨.

📌 대표 예시: 친구 네트워크, 그래프 사이클 판별

"넌 누구랑 같은 팀이니?"

6. 🌲 트리 탐색 (DFS / BFS)

DFS

void DFS(int node, bool[] visited, List<int>[] graph) {
    visited[node] = true;
    foreach (var next in graph[node])
        if (!visited[next]) DFS(next, visited, graph);
}

BFS

void BFS(int start, List<int>[] graph) {
    var visited = new bool[graph.Length];
    var q = new Queue<int>();
    visited[start] = true; q.Enqueue(start);
    while (q.Count > 0) {
        int node = q.Dequeue();
        foreach (var next in graph[node])
            if (!visited[next]) { visited[next] = true; q.Enqueue(next); }
    }
}

DFS: 깊이 우선 탐색 – 한 갈래로 끝까지 파고드는 방식
BFS: 너비 우선 탐색 – 가까운 노드부터 차례로 탐색

📌 대표 예시: 미로 탐색, 경로 유무 확인, 거리 계산

DFS: "끝까지 가보고 안 되면 돌아온다"
BFS: "가까운 것부터 차례로 살핀다"

7. 🚉 최단 경로 알고리즘

📍 다익스트라 (Dijkstra)

• 양수 가중치 그래프의 최단 경로
• 우선순위 큐 사용 시: O(E log V)

📍 벨만-포드 (Bellman-Ford)

• 음수 가중치 허용, 음수 사이클 탐지 가능
• 시간 복잡도: O(V × E)

📍 플로이드-워셜 (Floyd-Warshall)

• 모든 정점 쌍 간 최단 거리
• DP 기반, 시간 복잡도: O(V³)

✅ 마무리 표 (한눈에 보기)

🌉 플로이드-워셜 알고리즘 (Floyd-Warshall)

1. 개념

플로이드-워셜 알고리즘은 모든 노드 쌍 간의 최단 거리를 구하는 알고리즘이다.
음수 간선이 있어도 동작하지만, 음수 사이클이 있으면 사용 불가하다.

• 동적 계획법(DP)의 한 형태
• 인접 행렬 기반
• 3중 반복문으로 구현됨

2. 작동 원리 요약

1. dist[i][j] = i에서 j로 가는 최단 거리
2. 중간에 거쳐가는 노드 k를 하나씩 고려하면서
   dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])
3. 모든 노드 쌍에 대해 최단 거리 계산

3. C# 예제 코드

void FloydWarshall(int[,] dist, int n)
{
    for (int k = 0; k < n; k++)         // 경유지
    {
        for (int i = 0; i < n; i++)     // 출발지
        {
            for (int j = 0; j < n; j++) // 도착지
            {
                if (dist[i, k] == int.MaxValue || dist[k, j] == int.MaxValue)
                    continue;

                if (dist[i, j] > dist[i, k] + dist[k, j])
                    dist[i, j] = dist[i, k] + dist[k, j];
            }
        }
    }
}

🔹 int.MaxValue는 무한(INF)을 의미
🔹 dist[i, j]는 i에서 j로 가는 최소 거리

4. 시간/공간 복잡도

5. 특징

• 모든 쌍의 최단 거리를 구할 수 있음
• 음수 간선 허용, 단 음수 사이클은 불가
• 간단한 구현, 하지만 시간 복잡도는 높음
• 다익스트라로 V번 반복해도 되지만, 구현은 이쪽이 더 간단

6. 활용 예시

• 모든 도시 사이의 최소 이동 비용 계산
• 최단 거리 기반의 경로 분석, 그래프 분석
• 유사한 관계 그래프에서 최소 전이 분석

7. 예시

정점: 0, 1, 2  
간선:
0 → 1 (4)
0 → 2 (11)
1 → 2 (2)

→ 결과:
0 → 2 최단 경로 = 0→1→2 = 4 + 2 = 6

8. 마무리 요약

• 플로이드-워셜은 모든 정점 쌍 최단 거리가 필요할 때 사용
• DP 기반의 알고리즘이며, 구현이 간단한 편
• 음수 간선이 있어도 안전하지만 음수 사이클만은 조심

🛤️ 벨만-포드 알고리즘 (Bellman-Ford Algorithm)

1. 개념

벨만-포드 알고리즘은 **음의 가중치(음수 간선)**가 있는 그래프에서도 단일 시작점으로부터 최단 거리를 구할 수 있는 알고리즘이다.
시간 복잡도는 크지만, 음수 간선 사이클 탐지까지 가능한 것이 특징이다.

2. 작동 원리 요약

1. 시작 노드의 거리는 0, 나머지는 무한대로 초기화
2. **(정점 수 - 1)**번 동안 모든 간선을 확인하며 거리 갱신 반복
3. 한 번 더 돌면서 거리 갱신이 일어난다면 → 음수 사이클 존재

3. C# 예제 코드

class Edge
{
    public int From, To, Cost;
    public Edge(int from, int to, int cost)
    {
        From = from;
        To = to;
        Cost = cost;
    }
}

bool BellmanFord(int vertexCount, List<Edge> edges, int start, int[] dist)
{
    for (int i = 0; i < vertexCount; i++)
        dist[i] = int.MaxValue;

    dist[start] = 0;

    for (int i = 0; i < vertexCount - 1; i++)
    {
        foreach (var edge in edges)
        {
            if (dist[edge.From] == int.MaxValue) continue;

            int newDist = dist[edge.From] + edge.Cost;
            if (newDist < dist[edge.To])
                dist[edge.To] = newDist;
        }
    }

    // 음수 사이클 확인
    foreach (var edge in edges)
    {
        if (dist[edge.From] == int.MaxValue) continue;
        if (dist[edge.From] + edge.Cost < dist[edge.To])
            return false; // 음수 사이클 존재
    }

    return true;
}

✅ dist[]: 최단 거리 배열
✅ 반환값: true면 정상, false면 음수 사이클 존재

4. 시간/공간 복잡도

• V: 정점 개수
• E: 간선 개수

5. 다익스트라 vs 벨만-포드

6. 활용 예시

• 금융 시스템 등에서 이익이 무한히 증가하는 루프 탐지
• 도로, 통신망에서 음수 간선 포함 최단 거리 문제
• 단일 시작점 기준 거리 탐색

7. 예시 그래프

정점: 0, 1, 2  
간선: (0 → 1, 1), (1 → 2, -1), (2 → 0, -1)

→ 음수 사이클 존재!

8. 마무리 요약

• 벨만-포드는 느리지만 범용적이다.
• 특히 음수 간선이나 음수 사이클 탐지가 필요한 경우 유일한 해법.
• 코딩 테스트에서도 간혹 그래프에 음수 가중치가 있을 때 등장한다.

🚀 다익스트라 알고리즘 (Dijkstra Algorithm)

1. 개념

다익스트라 알고리즘은 가중치가 있는 그래프에서 한 정점에서 다른 모든 정점까지의 최단 거리를 구하는 알고리즘이다.
음수 간선이 없을 때 사용 가능하며, **우선순위 큐(Heap)**를 이용하면 빠르게 계산할 수 있다.

2. 작동 방식 요약

1. 시작 노드에서 거리를 0으로 초기화, 나머지는 무한대로 설정
2. 아직 방문하지 않은 노드 중 가장 가까운 노드 선택
3. 선택한 노드를 기준으로 인접한 노드의 거리 업데이트
4. 모든 노드를 방문할 때까지 반복

3. C# 예제 코드 (우선순위 큐 사용)

using System;
using System.Collections.Generic;

class Edge
{
    public int To, Cost;
    public Edge(int to, int cost)
    {
        To = to;
        Cost = cost;
    }
}

class Node : IComparable<Node>
{
    public int Vertex, Distance;
    public Node(int v, int d)
    {
        Vertex = v;
        Distance = d;
    }

    public int CompareTo(Node other)
    {
        return Distance.CompareTo(other.Distance);
    }
}

void Dijkstra(int start, List<Edge>[] graph, int[] dist)
{
    int n = graph.Length;
    bool[] visited = new bool[n];
    for (int i = 0; i < n; i++) dist[i] = int.MaxValue;
    dist[start] = 0;

    var pq = new PriorityQueue<Node, int>();
    pq.Enqueue(new Node(start, 0), 0);

    while (pq.Count > 0)
    {
        pq.TryDequeue(out var current, out _);
        int now = current.Vertex;

        if (visited[now]) continue;
        visited[now] = true;

        foreach (var edge in graph[now])
        {
            int cost = dist[now] + edge.Cost;
            if (cost < dist[edge.To])
            {
                dist[edge.To] = cost;
                pq.Enqueue(new Node(edge.To, cost), cost);
            }
        }
    }
}

📌 C# 10 이상에서 PriorityQueue<TElement, TPriority> 사용 가능 (System.Collections.Generic)

4. 시간/공간 복잡도

• V: 정점 수
• E: 간선 수

5. 특징

• 음수 간선이 없는 경우에만 사용 가능
• 단일 시작점 기준 최단 거리
• BFS보다 복잡하지만 더 정확하고 빠름 (가중치 포함 가능)
• 코딩 테스트에서 그래프 문제에 자주 등장

6. 예시

정점: 0, 1, 2, 3  
간선: (0→1, 4), (0→2, 2), (2→1, 1), (1→3, 1), (2→3, 5)

출발: 0 → 도착: 모든 노드  
최단 거리: [0, 3, 2, 4]

7. 마무리 요약

• 다익스트라 알고리즘은 가장 널리 쓰이는 최단 경로 알고리즘
• 음수 가중치가 없다면 무조건 사용 가능
• 우선순위 큐를 활용하면 성능을 크게 향상시킬 수 있음
• 실전에서는 BFS vs 다익스트라의 선택이 중요함 (가중치 유무)

🌐 그래프 탐색 알고리즘 – DFS vs BFS

1. 그래프 탐색이란?

그래프 탐색 알고리즘은 노드와 간선으로 이루어진 구조에서 특정 노드까지 도달하거나 모든 노드를 방문하는 알고리즘이다.
대표적으로 DFS(Depth-First Search)와 BFS(Breadth-First Search)가 있다.

2. DFS (깊이 우선 탐색)

📌 개념

• 가장 깊은 노드까지 계속 들어갔다가, 막히면 다시 돌아오는(backtrack) 방식
• 스택 구조 기반 (재귀 or 직접 스택 사용 가능)

✅ 예시 코드 (C# – 재귀 사용)

void DFS(int node, bool[] visited, List<int>[] graph)
{
    visited[node] = true;
    Console.Write($"{node} ");

    foreach (int neighbor in graph[node])
    {
        if (!visited[neighbor])
            DFS(neighbor, visited, graph);
    }
}

3. BFS (너비 우선 탐색)

📌 개념

• 가까운 노드부터 차례로 탐색, 점점 퍼져 나가는 방식
• 큐(Queue) 구조 기반

✅ 예시 코드 (C#)

void BFS(int start, bool[] visited, List<int>[] graph)
{
    Queue<int> queue = new Queue<int>();
    queue.Enqueue(start);
    visited[start] = true;

    while (queue.Count > 0)
    {
        int node = queue.Dequeue();
        Console.Write($"{node} ");

        foreach (int neighbor in graph[node])
        {
            if (!visited[neighbor])
            {
                visited[neighbor] = true;
                queue.Enqueue(neighbor);
            }
        }
    }
}

4. DFS vs BFS 비교

5. 활용 예시

• DFS: 미로 찾기, 순열/조합, 백트래킹 문제
• BFS: 최단 거리, 최소 이동 횟수, 퍼지는 방식 (불 퍼짐, 바이러스 등)

6. 마무리 요약

• DFS는 재귀적, 깊이 있는 문제 해결에 적합
• BFS는 큐 기반, 최단 거리 탐색에 적합
• 그래프 탐색 문제는 대부분 이 두 알고리즘으로 해결 가능
• 실제 문제에서는 종종 양쪽 모두 시도해봐야 정답이 나올 때도 있음

🔍 탐색 알고리즘 정리 – 선형 탐색 vs 이진 탐색

1. 탐색 알고리즘이란?

탐색 알고리즘은 주어진 데이터에서 원하는 값을 찾는 알고리즘이다.
정렬된 데이터든 아니든, 가장 기본이 되는 핵심 알고리즘으로 코딩 테스트에서도 자주 등장한다.

2. 선형 탐색 (Linear Search)

📌 개념

• 데이터를 처음부터 끝까지 순차적으로 탐색하며 값을 찾는 방식
• 배열이 정렬되지 않아도 사용 가능

✅ 예시 코드 (C#)

int LinearSearch(int[] arr, int target)
{
    for (int i = 0; i < arr.Length; i++)
    {
        if (arr[i] == target)
            return i;
    }
    return -1;
}

⏱️ 시간 복잡도

• 최악/평균: O(n)
• 공간 복잡도: O(1)

💡 특징

• 구현이 매우 단순
• 정렬되지 않은 데이터에서도 작동 가능
• 데이터가 작을 때 적합

3. 이진 탐색 (Binary Search)

📌 개념

• 정렬된 배열을 전제로, 중간값과 비교하며 탐색 범위를 절반씩 줄여가는 탐색
• 훨씬 빠르지만 반드시 정렬되어 있어야 함

✅ 예시 코드 (C#)

int BinarySearch(int[] arr, int target)
{
    int left = 0;
    int right = arr.Length - 1;

    while (left <= right)
    {
        int mid = (left + right) / 2;

        if (arr[mid] == target)
            return mid;
        else if (arr[mid] < target)
            left = mid + 1;
        else
            right = mid - 1;
    }

    return -1;
}

⏱️ 시간 복잡도

• 최악/평균: O(log n)
• 공간 복잡도: O(1)

💡 특징

• 정렬된 배열에서만 사용 가능
• 데이터가 많을수록 성능 차이가 극명함
• 코딩 테스트에서도 자주 등장

4. 비교 요약

5. 선택 가이드

• 정렬되지 않은 배열 → 선형 탐색
• 정렬된 배열이고 데이터가 많음 → 이진 탐색
• 이진 탐색은 C#에서 Array.BinarySearch()로도 지원됨

🏁 마무리 요약

• 탐색은 모든 알고리즘 문제의 기초가 되는 개념
• 이진 탐색을 잘 활용하면 탐색 문제 → log n으로 시간 절약 가능
• 나중에 다룰 DFS, BFS, 다익스트라 등의 고급 탐색 알고리즘의 기반이 되므로 꼭 숙지할 것!

🧠 정렬 알고리즘 비교 요약 & 선택 가이드

✅ 1. 주요 정렬 알고리즘 비교표

🔍 2. 정렬 알고리즘 선택 가이드

📝 마무리 요약

• 정렬 알고리즘은 문제 상황, 데이터의 특성, 성능 요구사항에 따라 적절히 선택해야 한다.
• 현실에서는 퀵 정렬이 가장 널리 사용되며, 정렬 안정성이 필요한 경우 병합 정렬이 많이 쓰인다.
• 코딩 테스트에서 직접 구현해야 할 경우는 삽입 정렬 또는 선택 정렬처럼 코드가 단순한 방식이 요구되기도 한다.