그리디 알고리즘
그리디 알고리즘(Greedy Algorithm)은 문제를 해결하는 과정에서 항상 현재 상황에서 가장 좋아 보이는 선택을 하는 방법. 즉, 각 단계에서 최적의 선택을 함으로써 최종적으로 최적의 해결책에 도달하려고 하는 알고리즘 설계 기법.
그리디 알고리즘의 특징
즉각적인 최적의 선택: 그리디 알고리즘은 매 순간마다 그 순간에서의 최적의 선택을 한다.
단계별로 최적 선택: 각 단계에서 이루어지는 선택이 전체 문제의 최적 해결책으로 이어진다는 보장이 있어야 함. 그렇지 않은 경우 최적의 해결책을 찾지 못할 수 있음.
다익스트라
다익스트라 알고리즘(Dijkstra's Algorithm)은 그래프에서 한 정점에서 다른 모든 정점까지의 최단 경로를 찾는 알고리즘. 음의 가중치를 가지지 않는 그래프에서 사용할 수 있으며, 네트워크 최적화, 경로 찾기 등 다양한 분야에서 활용. (다익스트라 알고리즘은 완전탐색이 아님)
다익스트라 알고리즘의 특징
단계별 최적 선택: 시작 정점에서부터 점진적으로 최단 거리를 확장해 나감. 매 단계에서 가장 짧은 경로를 가진 정점을 선택하여, 그 정점의 인접 정점으로의 최단 거리를 업데이트.
우선순위 큐 사용: 일반적으로 우선순위 큐(힙)를 사용하여 최단 거리를 가진 정점을 효율적으로 선택.
💬 주저리
그리디 문제는 처음 접근 자체는 어렵지 않은 것 같은데 자꾸 시간초과가 난다 ㅠㅠ 최적의 로직을 떠올리는 것이 쉽지가 않다,,,
다익스트라는 BFS의 심화버전 같은 느낌인데... 정형화?된 기본 틀을 알면 문제 풀이자체는 어렵지 않은 것 같은데 그 틀을 사용하는 게 아직 손에 익지 않는 것 같다.
DFS와 BFS는 로직을 이해했다면 아예 코드를 외워버리는 것도 방법이라고 하셔서 암기를 해봐야겠다...
프로젝트 주차의 선택 가이드라인이 공개되었다. 생각했던 것 보다 기획서 수준으로 자세하게 구성되어있어서 좋았는데 대신 그만큼 선택이나 자유의 폭이 작아지는 것 같은 부분은 아쉽긴했다.
나는 Next로 프로젝트를 진행하고 싶었는데 Next 프로젝트는 SNS라 이전에 비슷한 프로젝트를 진행한 것이 있어서 고민이다. SNS 플젝의 실시간 DM 기능도 구현해보고 싶긴도한데...🤔
항해99 취업 리부트 코스를 수강하고 작성한 콘텐츠 입니다. https://hanghae99.spartacodingclub.kr/reboot
