25/02/04 | TIL 알고리즘 2

📌 탐색 알고리즘

주어진 데이터 집합에서 특정 항목을 찾는 방법을 제공

 

🖇 선형탐색

가장 단순한 탐색알고리즘.배열의 각요소를 하나씩 차례대로 검사하여 원하는 항목을 찾음.

시간복잡도 : 최악의 경우 O(n)

 

🖇 이진탐색

정렬된 배열에서 빠르게 원하는 항목을 찾는 방법.

중간 요소와 찾고자 하는 항목을 비교하여 대상이 중간 요소보다 작으면 왼쪽을, 크면 오른쪽을 탐색

시간 복잡도: 최악의 경우 O(log n)

---

📌  트리나 그래프 탐색 알고리즘

-  정점(Vertex)과 간선(Edge)으로 이루어진 자료 구조

-  방향 그래프(Directed Graph)와 무방향 그래프(Undirected Graph)로 나뉨

-  가중치 그래프(Weighted Graph)는 간선에 가중치가 있음

 

🖇 DFS | 깊이 우선 탐색 (Depth-First Search, DFS)

루트에서 시작하여 가능한 한 깊이 들어가서 노드를 탐색하고, 더 이상 방문할 노드가 없으면 이전 노드로 돌아가는 방식.

시간 복잡도: 최악의 경우 O(V+E) (V는 노드 수, E는 간선 수)

 

🖇 BFS | 너비 우선 탐색 (Breadth-First Search, BFS)

루트에서 시작하여 가까운 노드부터 방문하고, 그 다음 레벨의 노드를 방문하는 방식.

시간 복잡도: 최악의 경우 O(V+E) (V는 노드 수, E는 간선 수)

 

어떤 경우에 DFS/BFS를 사용해야 할까?

 

✅ DFS가 유리한 경우:

- 경로의 모든 경우를 탐색해야 하는 문제(예: 백트래킹, 퍼즐, 미로 탐색).

-  트리 구조에서 탐색할 때, 불필요한 경로 탐색을 피하고 싶은 경우.

-  공간 복잡도를 줄이고 싶은 경우(재귀 최적화 필요).

 

✅ BFS가 유리한 경우:

-  최단 거리(Shortest Path) 문제(예: 길 찾기, 최단 시간 도달).

-  모든 정점을 고르게 탐색해야 하는 경우.

-  큐를 활용하여 탐색 순서를 명확하게 제어해야 하는 경우.

---

📌  최단 경로 알고리즘

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

하나의 시작 정점에서 다른 모든 정점까지의 최단 경로를 찾는 알고리즘

음의 가중치를 갖는 간선이 없는 경우에 사용됩니다.

 

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

음의 가중치를 갖는 간선이 있는 그래프에서도 사용할 수 있는 최단 경로 알고리즘

음수 사이클이 있는 경우에도 탐지할 수 있습니다.

 

🖇 A* 알고리즘 (A-star Algorithm)

특정 목적지까지의 최단 경로를 찾는 알고리즘

휴리스틱 함수를 사용하여 각 정점까지의 예상 비용을 계산하고,

가장 낮은 예상 비용을 가진 정점을 선택하여 탐색합니다.

---

📌  고급 알고리즘

🖇 동적 프로그래밍(Daynamic Programming)

작은 문제 단위로 쪼개서 반복하여 푸는 방식

- 동적 프로그래밍은 큰 문제를 작은 하위 문제로 분할하여 푸는 접근 방식입니다.

-  작은 하위 문제의 해결 방법을 계산하여 저장하고, 이를 이용하여 큰 문제의 해결 방법을 도출합니다.

    이러한 저장 과정을 "메모이제이션(Memoization)"이라고 합니다.

-  동적 프로그래밍은 중복되는 하위 문제들을 효율적으로 해결하기 위해 사용됩니다.

-  일반적으로 재귀적인 구조를 가지며, 하향식(Top-down)과 상향식(Bottom-up) 두 가지 방법으로 구현할 수 있습니다.

-  동적 프로그래밍은 최적 부분 구조와 중복 부분 문제의 특징을 가진 문제들을 효과적으로 해결할 수 있습니다.

 

🖇 그리디 알고리즘 ( Greedy Algorithm ) | 탐욕알고리즘

현재에 집중하는 알고리즘

그리디 알고리즘은 각 단계에서 가장 최적인 선택을 하는 알고리즘입니다.

각 단계에서 가장 이익이 큰 선택을 하여 결과적으로 최적해에 도달하려는 전략을 따릅니다.

그리디 알고리즘은 지역적인 최적해를 찾는데 초점을 맞추기 때문에 항상 전역적인 최적해를 보장하지는 않습니다.

그리디 알고리즘은 간단하고 직관적인 설계가 가능하며, 실행 시간이 매우 빠른 편입니다.

그리디 알고리즘은 최적해를 찾는 문제에 사용되는 경우가 많지만, 일부 문제에서는 최적해를 보장하지 않을 수 있습니다.

 

🖇  분할 정복 ( Divide and Conquer )

작은 부분부터 착실히 해결해 나가자

큰 문제를 작은 부분 문제로 분할하므로 문제의 크기에 따른 성능 향상이 가능합니다.

재귀적인 구조를 가지므로 문제 해결 방법의 설계가 단순하고 직관적입니다.

분할된 부분 문제들은 독립적으로 해결되므로 병렬 처리에 유리합니다.

하지만 문제를 분할할 때 발생하는 부분 문제들 간의 중복 계산이 발생할 수 있습니다.

이런 경우에는 중복 계산을 피하기 위한 메모이제이션 등의 기법을 활용하여 성능을 향상시킬 수 있습니다.

 

동적프로그래밍과 차이점

작은 문제들을 독립적으로 해결

---

🔎문제 해결 전략

1.  문제 이해: 문제를 정확히 이해하고 요구사항을 파악하는 것이 중요.

     문제 설명을 꼼꼼히 읽고, 입력과 출력의 형식을 이해하고 분석해야 한다.

2. 예제와 테스트 케이스: 문제의 예제와 추가적인 테스트 케이스를 활용하여 문제를 이해하고 해결 방법을 검증.

     예제와 테스트 케이스는 문제의 조건과 제약을 이해하는 데 도움을 줄 수 있다.

3. 알고리즘 설계: 문제를 해결하기 위한 알고리즘을 설계.

    문제의 특성에 맞는 알고리즘을 선택하고, 알고리즘의 구현 방법과 시간 복잡도를 고려.

4. 코드 작성: 알고리즘을 기반으로 코드를 작성.

     코드는 가독성이 좋고, 문제의 요구사항을 정확히 반영해야 한다.

     변수명을 명확하게 지어 가독성을 높이고, 주석을 추가하여 코드를 설명하는 것도 좋은 습관.

5. 효율성: 문제의 제약 조건과 입력 크기에 따라 알고리즘의 효율성을 고려.

     최적화 기법을 사용하고, 시간 복잡도와 공간 복잡도를 최대한 줄이는 방향으로 코드를 작성해야 한다.

6. 디버깅과 테스트: 코드를 작성한 후에는 디버깅을 통해 오류를 찾고 수정해야 한다.

     테스트 케이스를 활용하여 코드의 정확성을 검증하고, 예외 상황을 고려하여 코드를 완성해야 한다.

7. 시간 관리: 코딩 테스트는 제한된 시간 안에 문제를 해결해야 하는 것이 특징.

     따라서 시간을 효과적으로 관리하고, 문제에 맞는 효율적인 접근 방법을 선택하는 능력이 필요.

8. 연습과 경험: 코딩 테스트는 많은 연습과 경험이 필요한 분야.

    다양한 유형의 문제에 노출되고, 해결 방법을 익히며 자신의 실력을 향상시켜야 한다.

    코딩 테스트 관련 문제를 많이 풀고 다른 사람들의 풀이를 학습하는 것도 좋은 방법.

백준 온라인 저지 (https://www.acmicpc.net/): 다양한 난이도의 알고리즘 문제를 제공하며, 많은 사용자들과 소통할 수 있는 커뮤니티도 제공합니다.

프로그래머스 (https://programmers.co.kr/): 코딩 테스트 연습을 위한 문제들을 다양한 난이도로 제공하고 있습니다. 실제 취업 시험에서도 출제되는 문제들을 포함하고 있습니다.

바킹독 (https://blog.encrypted.gg/): 알고리즘 강의 다수 제공하고 있습니다.

LeetCode (https://leetcode.com/): 알고리즘 문제와 코딩 테스트 문제를 다양한 난이도로 제공하고 있으며, 실제 기업 코딩 인터뷰에서 출제되는 문제들을 포함하고 있습니다.