lastnamesong

[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..

몇 주 전에 파이썬으로 데이터 사이언스 공부를 하겠다는 마음으로 파이썬 개발환경을 구축하는 방법에 대한 글을 썼는데, 주변 환경이 오묘하게 전개되면서 알고리즘 공부를 시작하게 되었다. 이제 시작이라 잘 모르긴 하지만, 시스템을 제어하는 펌웨어를 개발하거나 로봇 상위제어 알고리즘을 연구하는 입장에서 데이터 처리에 관한 방법을 아는 것보다는 프로그래밍 알고리즘 공부를 하는 편이 더 도움될 수도 있겠다는 생각을 해본다. 그렇다면 더 실제적인 도움이 될 수 있도록 C++로 개발을 하는 것이 파이썬보다는 더 유리할 수 있겠다는 생각이 들었다.굉장히 짧은 경험에 비추어 생각해보면 파이썬은 상위 단에서 시뮬레이션이나 데이터 기반의 제어를 구현할 때에 유리했고, C나 C++은 low-level 단에서의 펌웨어나 스케줄..

코딩테스트를 준비하다 보면 빠지지 않고 등장하는 개념이 있다. 바로 시간복잡도이다. 문제를 풀 때 정답을 맞추는 것도 중요하지만, 주어진 시간 안에 효율적으로 해결하는 것도 필수이기 때문이다. 이번 글에서는 코딩테스트에서 왜 시간복잡도가 중요한지, 어떤 기준으로 따지는지, 그리고 세 가지 유형으로 정의되는 시간복잡도 표기법(Big-O, Big-Theta, Big-Omega)까지 정리해본다.시간복잡도란?시간복잡도란, 입력 크기(n)가 커질 때 알고리즘이 수행하는 연산 횟수가 얼마나 증가하는지를 나타내는 척도이다. 쉽게 말해, 데이터가 많아질수록 이 코드가 얼마나 느려질지를 수치화한 개념이다.  코딩테스트에서는 보통 아래 세 가지 표기법을 알아두면 된다.1. Big-O 표기법 (\(O\))가장 많이 쓰는 표..