머리글2021 KAKAO BLIND RECRUITMENT의 합승 택시 요금을 풀면서 무지와 어피치가 합승을 할 수 있다는 점에 주목하여 플로이드-워셜 알고리즘을 사용했지만, 효율성 테스트에서 낮은 점수를 받았다. 이를 계기로 다익스트라 알고리즘과 플로이드-워셜의 차이를 다시 정리하고, 각 알고리즘의 적절한 사용 전략을 세울 필요성을 느꼈다.다익스트라(Dijkstra) 알고리즘은 하나의 정점에서 출발하여 다른 모든 정점으로의 최단 경로를 구하는 알고리즘이고, 플로이드-워셜(Floyd-Warshal) 알고리즘은 모든 정점에서 다른 모든 정점으로의 최단 경로를 구하는 알고리즘이다.Dijstra vs FloydWarshall출처 : https://loosie.tistory.com/146다익스트라(Dijkstra..

들어가며코딩 테스트를 준비하는 개발자라면 누구나 한 번쯤 마주치는 그래프 탐색과 최단 경로 문제. 이 글에서는 코딩 테스트에서 자주 출제되는 핵심 알고리즘들을 Python 코드와 함께 정리했습니다.💡 Tip: 이 알고리즘들은 시험장에서 바로 떠올리기 어려울 수 있으므로, 반드시 외워두시기 바랍니다.1. 그래프 탐색 알고리즘1.1 BFS (Breadth-First Search, 너비 우선 탐색)BFS는 가까운 노드부터 탐색하는 알고리즘으로, 큐(Queue) 자료구조를 사용합니다. 미로 찾기, 최단 거리 탐색 등에 자주 등장합니다.from collections import dequedef bfs(graph, start): visited = set() queue = deque([start]) ..

이미지 출처 - https://www.geeksforgeeks.org/backtracking-meaning-in-dsa/"모든 가능성을 탐색해야 하지만 불필요한 경로는 빠르게 포기하는 지혜가 필요합니다. 백트래킹은 마치 미로에서 막다른 길을 만났을 때 이전 갈림길로 되돌아가는 전략적 탐색과 같습니다."목차백트래킹이란?완전탐색과 백트래킹의 차이백트래킹의 적용 조건백트래킹의 동작 원리재귀 함수를 활용한 백트래킹 구현핵심 예제: 순열 구하기시간복잡도 분석백트래킹 문제 유형과 판단 기준실전 구현 팁대표적인 백트래킹 문제결론백트래킹이란?백트래킹(Backtracking)은 해를 찾는 도중에 막히면(해가 아니면) 되돌아가서 다시 해를 찾아가는 알고리즘입니다. 가능한 모든 경로를 탐색하되, 특정 조건을 만족하지 않는 ..

이미지 출처 - https://skilled.dev/course/depth-first-search"그래프를 탐색하는 것은 미로를 탐험하는 것과 같습니다. DFS는 한 길을 끝까지 탐색한 후 다시 돌아와 다른 길을 탐색하는 방식으로, 깊이 있는 탐험을 선호하는 여행자와 같습니다."목차그래프 탐색의 기본 개념DFS란 무엇인가?DFS와 BFS의 차이점재귀 함수의 이해DFS의 동작 원리시간 복잡도 분석DFS 구현에 필요한 자료구조실전 문제 분석: 백준 2667번코드 구현 가이드복습 전략 및 추천 문제결론그래프 탐색의 기본 개념그래프 탐색이란 그래프 구조에서 모든 노드(정점)를 체계적으로 방문하는 과정입니다. 컴퓨터 과학에서 가장 기본적이면서도 중요한 알고리즘 중 하나로, 다양한 실생활 문제 해결에 응용됩니다.그..

이미지 출처 - https://skilled.dev/course/breadth-first-search"모든 길을 가장 효율적으로 탐색하는 방법을 찾는 것은 알고리즘의 핵심 과제입니다. BFS는 마치 물결이 퍼지듯 가까운 곳부터 체계적으로 탐색하는 방법을 제공합니다."목차BFS란 무엇인가?BFS vs DFS: 핵심 차이점BFS의 동작 원리시간 복잡도 분석필요한 자료구조실전 문제 분석: 백준 1926번코드 구현 단계별 가이드최적화 전략과 주의사항학습 전략 및 추천 문제결론BFS란 무엇인가?BFS(Breadth-First Search, 너비 우선 탐색)는 그래프나 트리 구조에서 모든 노드를 효율적으로 방문하기 위한 알고리즘입니다. 시작 노드에서부터 가까운 노드를 먼저 방문하고, 멀리 있는 노드를 나중에 방문하..