하고싶은거 다 해 하고싶은거 다 해

알고리즘/이론

• 벨만-포드 알고리즘

  알고리즘/이론 2021. 1. 8. 01:29

  벨만-포드 알고리즘 📄 설명 벨만-포드 알고리즘은 다익스트라 알고리즘과는 다르게 음수 간선의 존재를 확인할 수 있습니다. 시작점에서 각 정점까지 가는 최단 거리의 상한을 적당히 예측한 뒤 예측값과 실제 최단 거리 사이의 오차를 반복적으로 줄여나가는 방식으로 동작합니다. dist[v]

  Read More
• 다익스트라 알고리즘

  알고리즘/이론 2021. 1. 6. 23:55

  다익스트라 알고리즘 📄 설명 다익스트라 알고리즘은 가중치가 있는 그래프에서 최단 거리를 찾는 알고리즘입니다. 음수 가중치가 있는 그래프에서는 정확한 최단 거리를 구할 수 없으므로 사용하면 안됩니다.(그럴 땐 벨만-포드) 단일 정점에서 다른 정점으로의 최단거리를 구하는 알고리즘이기 때문에 모든 정점들 간의 최단거리를 알고 싶다면 플로이드-와샬 알고리즘을 사용하는 것이 구현이 편합니다 우선순위큐를 이용한 정렬을 이용하기 때문에 O(ElogV)의 시간 복잡도를 가지게 됩니다. 💡동작 과정 각각의 정점마다 현재까지 발견한 최소 경로를 저장할 dist 배열을 만듭니다. 최단 경로를 구해야 하기 때문에 처음에는 모든 값을 아주 큰 값으로 초기화 시킵니다. 여기서는 1번 정점을 시작점으로 정했기 때문에 dist[1]..

  Read More
• 알고리즘 풀이 기초

  알고리즘/이론 2020. 12. 21. 22:29

  문제 해결 과정 문제 읽고 이해하기 계획 세우기 알고리즘 선택 자료구조 선택 계획 검증하기 키보드를 잡기 전에 계획을 검증하자 시간 복잡도, 공간 복잡도 확인 구현하기 회고하기 어떤 방식으로 접근했는가 문제의 해답을 찾는 결정적이었던 깨달음은 무엇인가 틀렸다면 오답 원인 기록하기 문제 접근하기 예전에 비슷한 문제를 풀어본 적이 있는가 문제의 목적을 보고 적절한 접근 방법을 선택하기 위해서는 어떤 문제가 최적화 문제인지, 경우의 수를 구하는 문제인지, 검색 문제인지 등을 분류하는 방법을 익히고, 각 알고리즘들이 어느 경우에 사용될 수 있는지 체계적으로 공부해야 함. 무식하게 풀 수 있는가 단순한 알고리즘을 기반으로 문제를 구성한 뒤, 좀 더 효율적인 자료구조를 사용하거나, 계산 과정에서 같은 정보를 두 번..

  Read More