[항해99 취업 리부트 코스 학습일지] 4주차 알고리즘 학습 Day 3

Q. 오늘 진행된 강의에서 학습한 내용은 무엇인가요?

그리디(Greedy) 알고리즘

개요

그리디 알고리즘은 탐욕 알고리즘이라고도 하며, 최적해를 구하는 데에 사용되는 근사적인 방법입니다. 여러 경우 중 하나를 결정해야 할 때마다 그 순간에 최적이라고 생각되는 것을 선택해 나가는 방식으로 진행하여 최종적인 해답에 도달합니다. 그리디 알고리즘은 그 순간마다 지역적으로 최적의 선택을 하지만, 이 선택이 항상 전역적으로 최적임을 보장하지는 않습니다.

특징

• 지역 최적성: 각 단계에서 지역적으로 최적의 선택을 합니다.
• 전역 최적성 보장 X: 지역 최적성이 항상 전역 최적성을 보장하지 않습니다.
• 단순성: 구현이 간단하고 이해하기 쉽습니다.

적용 가능한 문제

그리디 알고리즘은 다음과 같은 조건을 만족하는 문제에 효과적으로 적용할 수 있습니다:

1. Greedy Choice Property (탐욕 선택 속성): 현재의 선택이 나중에 영향을 미치지 않는 경우.
2. Optimal Substructure (최적 부분 구조): 문제의 최적해가 부분 문제의 최적해로 구성되는 경우.

예시 문제

1. 거스름돈 문제: 최소 동전 개수로 거스름돈을 주기.
2. 활동 선택 문제: 가장 많은 활동을 할 수 있도록 선택하기.
3. 최소 신장 트리 문제 (Kruskal's Algorithm): 그래프에서 최소 비용으로 모든 노드를 연결하기.

 

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

개요

다익스트라 알고리즘은 도로 교통망 같은 그래프에서 꼭짓점 간의 최단 경로를 찾는 알고리즘입니다. 특정 출발 노드에서 다른 모든 노드까지의 최단 경로를 구하는 데 사용됩니다.

특징

• 그리디 알고리즘의 일종: 매 단계에서 가장 짧은 경로를 선택하여 진행합니다.
• 비음수 가중치: 그래프의 간선 가중치가 음수가 아니어야 합니다.
• 우선순위 큐: 효율적인 구현을 위해 주로 우선순위 큐(Heap)를 사용합니다.

동작 과정

1. 초기화: 출발 노드에서 자신으로의 거리는 0, 다른 모든 노드로의 거리는 무한대로 설정합니다.
2. 반복:
   • 방문하지 않은 노드 중에서 최단 거리의 노드를 선택합니다.
   • 선택된 노드의 이웃 노드를 탐색하여 최단 거리를 갱신합니다.
   • 모든 노드가 방문될 때까지 반복합니다.

그리디 알고리즘과 다익스트라 알고리즘 모두 최적의 선택을 위해 사용되지만, 각각의 사용 조건과 특성을 잘 이해하고 적절한 문제에 적용하는 것이 중요, 그리디 알고리즘은 단순하지만, 항상 전역 최적해를 보장하지는 않으므로 참고해야할 듯하다. 다익스트라 알고리즘은 비음수 가중치 그래프에서 최단 경로를 구하는 데 효과적이다.

 

 

Q. 이번 주 진행된 팀 스터디에서 얻은 인사이트는 무엇인가요?

최단 경로 문제를 먼저 풀어보고 -> 문제 4 다익스트라 문제를 풀어보는 방향으로 해야할 듯하다.

그리고 BFS 와 다익스트라 같은 알고리즘 템플릿을 익히기, 문제 4난이도가 조금 있는편... 

 

(오늘 문제 중 다익스트라 문제가 난이도가 많이 높았던 것 같음..)

 

항해99 취업 리부트 코스를 수강하고 작성한 콘텐츠 입니다.

https://hanghae99.spartacodingclub.kr/reboot

IT 커리어 성장 코스 항해99, 개발자 취업부터 현직자 코스까지