백준(BOJ)

[백준/C++] 3273번: 두 수의 합 ( 투 포인터 알고리즘 )

문제 설명 ● 문제 링크: https://www.acmicpc.net/problem/3273 풀이이 문제는 주어진 수열에서 합했을 때 x가 되는 숫자 쌍의 개수를 구하는 문제입니다. 이 글에서는, 투 포인터( two pointer ) 알고리즘을 이용해서 이 문제를 풀었습니다. 이 투 포인터( two pointers ) 알고리즘은 정해진 구간을 탐색할 때, 탐색할 위치를 가리키는 두 개의 포인터를 사용해서, 탐색할 범위를 좁히면서 문제를 해결하는 방식을 말합니다. 예를 들어, 수열 1, 2, 3, 4, 5가 주어지고, 합했을 때 7이 되는 숫자 쌍을 찾는다고 해봅시다. 탐색을 수열의 시작과 끝에서부터 시작합니다. 현재 두 포인터가 가리키는 숫자 1과 5의 합은 7보다 작습니다. 좀 더 큰 숫자를 찾아..

2025. 5. 1.
백준(BOJ)

[백준/C++] 1707번: 이분 그래프 ( 깊이 우선 탐색, Depth-First Search )

문제 설명 ● 문제 링크: https://www.acmicpc.net/problem/1707 풀이이 문제는 주어진 그래프가 이진 그래프( Bipartite Graph )인지 판단하는 문제입니다. 여기서, 이진 그래프는 그래프의 모든 정점을 두 그룹으로 나눌 수 있는 그래프를 말합니다.예를 들어, 아래와 같이, 그래프의 한 정점이 그룹 1에 속했을 때, 그와 인접한 모든 정점을 그룹 2에 속하게 할 수 있다면, 그 그래프가 이진 그래프입니다. 하지만, 다음과 같은 그래프는, 모든 이웃한 정점들을 두 개의 다른 그룹에 분리할 수 없으므로, 이진 그래프가 될 수 없습니다. 그리고, 이렇게 모든 정점을 두 그룹으로 나눌 수 있다면, 모든 정점을 인접한 정점과 다른 색상으로 칠할 수 있다는 얘기가 됩니다...

2025. 5. 1.
백준(BOJ)

[백준/C++] 7562번: 나이트의 이동 ( 너비 우선 탐색, Breath-First Search )

문제 설명 ● 문제 링크: https://www.acmicpc.net/problem/7562 풀이이 문제는 체스의 나이트 말이 주어진 시작 위치부터 목표 위치까지 가는 최소 횟수를 출력하는 문제입니다. 보통 최단 거리를 찾는 문제는, 주어진 문제에서 그래프( graph )를 구성하고, 이 그래프에 대하여 너비 우선 탐색법을 사용하여 해결하는데, 이렇게 하는 이유는, 이 너비 우선 탐색( BFS, Breath-First Search )은 시작 위치에서 가능한 모든 방향으로 탐색을 시작하여, 모두 같은 횟수를 탐색하기 때문입니다. 그래서, 어떤 방향으로 탐색 중, 먼저 목표 위치에 도달하면, 그때까지 움직인 횟수가 최소 횟수가 됩니다. [백준/C++] 24445번: 너비 우선 탐색 2 ( BFS, Brea..

2025. 4. 30.
백준(BOJ)

[백준/C++] 2178번: 미로 탐색 ( 너비 우선 탐색, Breath-First Search )

문제 설명 ● 문제 링크: https://www.acmicpc.net/problem/2178 풀이이 문제는 (1,1)부터 시작해서 (N, M) 위치에 도달하는데 필요한 최소 이동 거리를 구하는 문제입니다. 이 문제에서는 "2667번 단지 번호 붙이기" 문제에서처럼 좌표를 이용해서 문제를 푸는 대신, 입력 데이터로부터 그래프를 구성해서 해결하는 방식을 사용했습니다. [백준/C++] 2667번: 단지 번호 붙이기 ( 깊이 우선 탐색, Depth-First Search )문제 설명 ● 문제 링크: https://www.acmicpc.net/problem/2667 풀이이 문제에서 연속되는 숫자 1들의 집합을 단지라고 합니다. 이 단지들의 수를 출력하고, 각 단지에 속한 숫자 1의 개수를 오름차순으로codin..

2025. 4. 30.
백준(BOJ)

[백준/C++] 2667번: 단지 번호 붙이기 ( 깊이 우선 탐색, Depth-First Search )

문제 설명 ● 문제 링크: https://www.acmicpc.net/problem/2667 풀이이 문제에서 연속되는 숫자 1들의 집합을 단지라고 합니다. 이 단지들의 수를 출력하고, 각 단지에 속한 숫자 1의 개수를 오름차순으로 출력하는 문제입니다. 먼저 입력을 받아봅시다.아래 코드는, 입력된 N개의 문자열( 길이도 N )로부터, N*N 배열에 0과 1을 입력하는 코드입니다.#define SIZE 25bool exist[SIZE][SIZE];int N = 0;cin >> N; // 지도의 크기string str; // 가로 1줄을 문자열로 입력받음for( int i = 0; i > str; for( int j = 0; j 그다음엔, 숫자 1을 만나면 그 1과 연결되어 있는 1들을 찾는 과정입니..

2025. 4. 29.
백준(BOJ)

[백준/C++] 2606번: 바이러스 ( 깊이 우선 탐색, Depth-First Search )

문제 설명 ● 문제 링크: https://www.acmicpc.net/problem/2606 풀이이 문제는 1번 컴퓨터에서 시작하여, 도달할 수 있는 컴퓨터의 숫자를 알아내는 문제입니다. 컴퓨터의 번호를 정점( vertex )으로 하고, 컴퓨터 간의 연결을 간선( edge )으로 보면, 컴퓨터 네트워크를 일종의 그래프( graph )로 볼 수 있습니다. 그러면, 이 문제는 입력된 그래프에서 1번 정점부터 시작하여 도달할 수 있는 정점의 개수를 구하는 문제로 생각할 수 있습니다. 그리고, 이러한 문제를 해결하는 방법을 크게 깊이 우선 탐색( Depth-First Search )과 너비 우선 탐색( Breath-First Search )으로 나눌 수 있는데, 여기에선 깊이 우선 탐색( DFS )을 사용했습..

2025. 4. 28.
백준(BOJ)

[백준/C++] 24445번: 너비 우선 탐색 2 ( BFS, Breath-First Search )

문제 설명 ● 문제 링크: https://www.acmicpc.net/problem/24445 풀이이 문제는, 너비 우선 탐색( Breath-first Search, BFS ) 방식에 따라, 각 정점을 방문하는 순서를 출력하는 문제입니다. 여기서 말하는, 너비 우선 탐색은 자식 정점이 아니라 이웃하는 정점을 먼저 탐색하는 방식입니다. 위의 이미지에서 너비 우선 탐색의 정점을 탐색하는 경로는 다음과 같습니다.먼저 루트(root)인 1부터 탐색을 시작해서, 자식 정점인 2를 탐색합니다. 그리고, 그다음은 2의 자식 정점인 4를 탐색하는 것이 아니라, 이웃 정점인 3을 탐색합니다. 그다음은 2 레벨 탐색으로, 2의 자식 정점인 4, 5를 탐색하고, 3의 자식 정점이자, 5 정점의 이웃 정점인 6, 7을..

2025. 4. 27.
백준(BOJ)

[백준/C++] 24480번: 깊이 우선 탐색 2 ( DFS, Depth-First Search )

문제 설명 ● 문제 링크: https://www.acmicpc.net/problem/24480 풀이이 문제는, 깊이 우선 탐색( Depth-first Search, DFS ) 방식에 따라, 각 정점을 방문하는 순서를 출력하는 문제입니다. 여기서 말하는, 깊이 우선 탐색은 이웃하는 정점이 아니라 자식 정점을 먼저 탐색하는 방식입니다. 이미지를 보면서 설명을 읽는 것이 쉽게 이해할 수 있을 것 같습니다. 위의 이미지에서, 모든 정점을 탐색하는, 깊이 우선 탐색의 경로는 다음과 같습니다. 먼저 루트( root )인 1부터 탐색을 시작해서, 자식 정점인 2를 탐색합니다. 그다음은 이웃 정점인 3이 아니라, 2의 자식 정점인 4를 탐색하고, 차례로 4의 자식 정점인 8까지 "자신 정점 우선"으로 탐색을 합..

2025. 4. 26.
백준(BOJ)

[백준/C++] 1725번: 히스토그램 ( 스택 stack 활용법 )

문제 설명 ● 문제 링크: https://www.acmicpc.net/problem/1725 풀이이 문제는 주어진 히스토그램에 넣을 수 있는 가장 큰 직사각형의 넓이를 구하는 문제입니다. 이 문제를 푸는 아이디어는, 입력되는 막대의 높이가 줄어들면, 넣을 수 있는 직사각형의 높이가 줄어들므로, 줄어들기 전의 직사각형의 넓이가 가장 큰 값의 후보가 된다는 것입니다. 예를 들어, 간단한 경우를 생각해 보죠. [ 4, 4, 4, 1 ]의 히스토그램이 입력되었을 때, 가장 큰 직사각형의 넓이를 구하는 과정을 생각해 보면, 4가 세 번 입력될 때까지, 직사각형의 높이는 4입니다. 그런데, 아직은 계산을 할 필요가 없습니다. 다음에 4보다 크거나 같은 높이의 막대가 입력되면, 최대 넓이가 더 늘어나기 때문입니다...

2025. 4. 26.
백준(BOJ)

[백준/C++] 17298번: 오큰수 ( NGE, 스택 활용법 )

문제 설명 ● 문제 링크: https://www.acmicpc.net/problem/17298 풀이이 문제는 입력된 A의 오큰수( Next Greater Element ) NGE(A)를 구하는 문제입니다.이 NGE(A)는, 문제설명에도 있듯이, 숫자 A보다 크면서, A가 입력된 후에 입력되는, ( 위치 상으로 ) 가장 가까운 숫자를 말합니다. 이 문제는 스택( stack )을 이용하면, 손쉽게 풀 수 있습니다. [백준/C++] 28278번: 스택 2 ( stack 자료구조 사용하기 )문제 설명 ● 문제 링크: http://www.acmicpc.net/problem/28278 풀이문제에서는 스택( stack )을 구현해서 문제를 풀라고 되어있지만, std::stack 클래스를 사용해서 문제를 풀었습니다..

2025. 4. 26.