본문 바로가기
반응형

Algorithm9

[알고리즘/Algorithm] 너비 우선 탐색 - BFS / BOJ 2178 미로 탐색 안녕하세요,지난번 DFS 포스팅에 이어 마찬가지로 그래프 탐색 알고리즘은 BFS에 대하여 정리해보려고 합니다 !처음 두 알고리즘을 공부할 땐 제가 재귀적 호출에 대하여 어려워했어서, DFS 보다는 BFS를 좀 더 좋아했는데요,이번에는 정리하는 김에 제대로 공부해서 두 알고리즘 모두 잘 이해해서 활용하고 싶습니다.그럼 차근차근 포스팅해보겠습니다 :)BFS: Breadth-First Search 너비 우선 탐색🔹 BFS(너비 우선 탐색)란?BFS는 그래프 탐색 기법의 하나로, 시작 노드에서 가까운 노드부터 탐색해 나갑니다.BFS는 그래프나 트리에서 최단 거리, 단계별 탐색 등에 매우 유용한 알고리즘입니다.Breadth-First-Search로 '너비우선탐색'이라고도 합니다.탐색 방식: 너비 우선 (Brea.. 2025. 7. 14.
[알고리즘/Algorithm] 깊이 우선 탐색 - DFS / BOJ 2606 바이러스 안녕하세요!드디어 그래프 이론을 활용한 알고리즘 공부를 하고 있습니다.이론을 정리하고 문제 푸는 게 재미있지만 시간이 좀 걸리는 작업이기는 하네요 ㅎㅎ제가 한창 알고리즘 공부할 때 정말 재미있게 배웠던 그래프 알고리즘 중,가장 많이 활용되고 기본적으로 쓰이는 탐색 알고리즘을 공부해보겠습니다 :)이번에는 DFS 알고리즘을 정리해보려고 합니다~DFS의 정의 (깊이 우선 탐색)🔹 깊이 우선 탐색/DFS(Depth-First-Search) 란?: 그래프 또는 트리에서 한 정점에서 시작하여, 한 방향으로 갈 수 있는 곳 까지 끝까지 깊이 탐색한 후,더 이상 갈 곳이 없으면 다시 돌아와서(백트래킹) 다른 경로를 탐색하는 알고리즘입니다. 🔹 DFS의 특징항목설명탐색 방식깊이 우선 (먼저 한 쪽 끝까지 파고 듦)자.. 2025. 6. 16.
[자료구조 | Data Structure] 그래프 이론 Graph Theory 안녕하세요,오늘은 알고리즘에 사용되는 자료구조를 정리해보려고 합니다.알고리즘 문제 풀이에 대표적으로 사용되는 자료구조증 하나, 그래프에 대하여 정리해보겠습니다.그래프(Graph), 혹은 그래프 이론(Graph Theory)라고 불리는 이 자료구조는, DFS, BFS 문제를 푸는 데 기초가 되는 이론이고,나아가 위상정렬 등의 문제를 푸는 데도 기초가 됩니다.트리 문제도 그래프 이론에서 출발하죠!그래서 저도 기초를 다시 다지기 위해서 정리해봅니다. :)그래프 이론(Graph Theory) 기초 개념 정리그래프는 현실 세계의 네트워크, 관계, 연결구조를 수학적으로 표현한 자료구조 입니다.소셜 네트워크, 지도, 컴퓨터 네트워크, 알고리즘 문제 등에서 필수적으로 사용됩니다. 그래프란?: 그래프란 정점(Vertex.. 2025. 5. 26.
[알고리즘/Algorithm] 분할정복 Divide and Conquer / BOJ 2630 색종이 만들기 안녕하세요, 이번에는 분할정복(Divide and Conquer)에 대하여 정리해보려고 합니다.동적계획법(Dynamic Programming)도 분할정복으로 문제를 푸는 경우가 많아서,그보다 먼저 정리를 할까 했는데 냅다 문제를 풀어버렸습니다 ㅎㅎ 따라서 이번엔 많은 문제해결에 적용이 되는 분할정복(Divide and Conquer)에 대해 정리해보겠습니다.분할정복 (Divide and Conquer) 이란?분할정복 (Divide and Conquer)이란, 큰 문제를 작은 문제로 분할(Divide)하여 작은 문제부터 해결(Conquer)하는 알고리즘 기법입니다. ◆ 핵심 개념문제를 작은 하위 문제(Subproblem)로 분할(Divide)하위 문제를 재귀적으로 정복(Conquer)하위 문제들의 결과를 .. 2025. 5. 13.
반응형