lastnamesong

[C++] 넓이 우선 탐색 (BFS)그래프나 트리 같은 구조를 다룰 때는 특정한 규칙을 따라 데이터를 탐색해야 하며, 그중 너비 우선 탐색 (Breadth-First Search)은 가장 널리 사용되는 탐색 방법 중 하나이다.lastnamesong.tistory.comBFS를 활용할 수 있는 문제 중 하나로 백준 온라인 저지의 2178번 "미로 탐색" 문제를 풀이해본다.미로 탐색 문제에서 BFS는 시작점에서 가까운 정점부터 탐색하므로, 목표 지점에 도달했을 때 찾은 경로는 항상 최단 경로가 된다.문제 분석 및 해결 전략이 문제는 최단 거리 (최소 이동 횟수)를 구하는 문제이므로 BFS가 적합하다. BFS는 탐색하는 순간 최단 거리임을 보장하기 때문에, 도착점에 처음 도달한 순간이 답이 된다. 이게 가능한..

[C++] 깊이 우선 탐색 (DFS)프로그래밍에서 탐색 (Searching)과 순회 (Traversal)는 매우 중요한 개념이다. 그래프나 트리 같은 구조를 다룰 때는 특정한 규칙을 따라 데이터를 탐색해야 하며, 그중 깊이 우선 탐색 (Depth-First Searchlastnamesong.tistory.comDFS를 활용할 수 있는 문제 중 하나로 백준 온라인 저지의 13023번 "ABCDE" 문제를 풀이해본다.문제는 아래와 같다. 사람 수가 많지 않다면 그래프를 직접 그려보며 풀이하는 것을 생각해볼 수 있다.문제 분석 및 해결 전략그래프를 그릴 수 있다는 것은 완전 탐색 알고리즘을 사용해볼 수 있다는 것이다. 여기에 이 친구 관계를 보면 재귀적으로 풀 수 있다는 생각을 할 수 있다. 그러면 DFS를 ..

[C++] 깊이 우선 탐색 (DFS)그래프나 트리 같은 구조를 다룰 때는 특정한 규칙을 따라 데이터를 탐색해야 하며, 그중 깊이 우선 탐색 (Depth-First Search)은 가장 널리 사용되는 탐색 방법 중 하나이다.lastnamesong.tistory.comDFS를 활용할 수 있는 문제 중 하나로 백준 온라인 저지의 2023번 "신기한 소수" 문제를 풀이해본다.신기한 소수의 정의와 문제의 입력과 출력이 아래와 같이 정의된다.문제 분석 및 해결 전략숫자의 각 자리를 확장하면서 조건을 만족하는지를 확인해야 하므로, DFS를 활용한 재귀 함수의 사용이 적절하다는 생각을 해볼 수 있다. 우선, 한 자리의 소수는 정해져있으므로 2, 3, 5, 7에서 시작하는 것을 생각할 수 있다.다음으로는 자리수를 확장하..

프로그래밍에서 탐색 (Searching)과 순회 (Traversal)는 매우 중요한 개념이다. 그래프나 트리 같은 구조를 다룰 때는 특정한 규칙을 따라 데이터를 탐색해야 하며, 그중 너비 우선 탐색 (Breadth-First Search, BFS)은 깊이 우선 탐색 (DFS)과 함께 가장 널리 사용되는 탐색 방법 중 하나이다.이번 글에서는 BFS가 무엇이고, 어느 때 사용하는지 정리하며, 큐 (Queue) 자료구조를 활용한 BFS의 구현 방법을 정리한다.너비 우선 탐색이란?너비 우선 탐색 (BFS)은 그래프의 한 정점에서 시작하여 인접한 정점들을 먼저 모두 탐색한 후, 그다음 인접한 정점들을 탐색하는 방식으로 진행된다. 즉, 특정 노드에서 가까운 노드를 먼저 방문한 후 점점 멀리 있는 노드를 방문하는 방..

프로그래밍에서 탐색 (Searching)과 순회 (Traversal)는 매우 중요한 개념이다. 그래프나 트리 같은 구조를 다룰 때는 특정한 규칙을 따라 데이터를 탐색해야 하며, 그중 깊이 우선 탐색 (Depth-First Search, DFS)은 가장 널리 사용되는 탐색 방법 중 하나다.DFS가 무엇이고, 어느 때 사용하는지 정리하며, 스택과 재귀함수 (recursive)로 구현된 코드를 통해 이해를 도울 수 있도록 한다.깊이 우선 탐색이란?깊이 우선 탐색 (DFS)는 그래프 완전 탐색 방법 중 하나이다. 시작 노드에서 한 쪽 분기를 정하여 가볼 수 있는 최대 깊이까지 탐색을 마치고 다른 쪽 분기에서 다시 탐색을 수행하는 알고리즘이다. 모든 노드를 찾는 것이 핵심이지 경로를 고려하는 알고리즘은 아니기 때..

C++에서 데이터를 효율적으로 관리하기 위해 스택 (Stack)과 큐 (Queue)는 필수적인 자료구조다. 각각의 특성과 동작 방식이 다르며, 벡터 (Vector)와도 차이가 있다. 이전 글에서 배열과 리스트, 벡터에 대해 정리했던 적이 있으니 아래 글을 참고할 수 있다. [C++] 배열과 리스트, 벡터알고리즘에 대해서 공부하기에 앞서 데이터를 저장할 수 있는 다양한 형태에 대해서 파악할 필요가 있겠다. C++에서 데이터를 다루기 위해 쓰는 컨테이너에는 배열과 리스트, 벡터가 있으며 이lastnamesong.tistory.com이 글에서는 스택과 큐의 개념과 활용법을 설명하고, 벡터와 비교하여 어떤 상황에서 적절한지를 살펴본다.스택과 큐는 데이터가 들어가고 나가는 방법 (또는 통로)에 따라 차이가 있다...

알고리즘 문제를 풀다보면 \( O(n^2) \) 또는 그 이상의 시간 복잡도를 갖는 완전 탐색 방법으로는 해결하기 어려운 경우가 많다. 특히, 배열에서 특정 조건을 만족하는 부분을 찾아야 하는 문제에서는 효율적인 탐색 방법이 필요하다. 이러한 상황에서 유용하게 활용되는 기법이 바로 투포인터(Two Pointers) 알고리즘이다.이번 글에서는 투포인터 알고리즘이 무엇이고, 어떤 장점을 갖는지 알아본 후에 예제를 투포인터 알고리즘으로 풀이해본다.- 투포인터란?투포인터 알고리즘은 배열이나 리스트에서 두 개의 포인터를 사용하여 문제를 해결하는 기법이다. 보통 포인터를 좌우에서 움직이거나, 특정 조건에 따라 조정하면서 원하는 결과를 찾는다. 투포인터 기법은 연속적인 부분을 탐색할 때 효과적으로 사용될 수 있으며,..

알고리즘에 대해서 공부하기에 앞서 데이터를 저장할 수 있는 다양한 형태에 대해서 파악할 필요가 있겠다. C++에서 데이터를 다루기 위해 쓰는 컨테이너에는 배열과 리스트, 벡터가 있으며 이들은 가장 기본적이면서도 중요한 컨테이너다. 각 컨테이너는 서로 다른 특성을 가지며, 상황에 따라 적절한 선택이 필요하다. 이번 글에서는 배열, 리스트, 벡터의 차이점과 각각의 장단점을 살펴본다.배열과 리스트, 벡터를 구분하는 차이점은 크기 변경 가능 여부와 삽입/삭제 속도, 메모리 구조 등이 있다.- 배열 (Array)배열은 고정된 크기의 연속된 메모리 블록을 사용하는 자료구조다. C++에서는 전통적인 C 스타일 배열과 std::array를 제공한다.#include #include using namespace std;i..