카테고리 없음

[백준/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.
카테고리 없음

[백준/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.
카테고리 없음

[백준/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.
카테고리 없음

[백준/C++] 1920번: 수 찾기 ( 이진 탐색, binary search )

문제 설명 ● 문제 링크: https://www.acmicpc.net/problem/1920 풀이이진 탐색을 통해서 찾고자 하는 숫자 X가 주어진 수들 중에 있는지를 판단하는 문제입니다. 이진 탐색( Binary Search )은 전체 구간을 둘로 나누는 과정을, 각 구간의 크기가 0이 될 때까지 반복하면서, 구간 내에 찾는 숫자가 있는지를 검사하는 방법입니다. 이 알고리즘의 과정은 다음과 같습니다. 전체 구간 G의 중간의 숫자가 찾는 숫자인지 검사한다. 찾는 숫자가 아니면, G구간을 A구간과 B구간으로 나눈다.A구간에 대해 1번의 과정을 반복한다. 이 과정을 나눠진 하위 구간의 크기가 0이 될 때까지 반복한다.A구간에서 찾는 숫자가 없으면, 반대쪽 B구간에 대해서도 A구간과 마찬가지로 탐색한다. 이..

2025. 4. 22.
카테고리 없음

[백준/C++] 1931번: 회의실 배정 ( 데이터 정렬 )

문제 설명 ● 문제 링크: https://www.acmicpc.net/problem/1931 풀이이 문제는 겹치지 않으면서 가장 많이 열 수 있는 회의의 수를 찾는 문제입니다. 이러한 문제의 최적의 스케줄은 가장 빨리 끝나는 회의 A부터 시작해서, 끝나는 시간이 점점 늦어지는 회의 순으로 진행하는 것입니다. 만약, A 회의보다 끝나는 시간이 더 늦은 다른 회의 B부터 시작했을 경우를 가정해 봅시다. 그럼, 그다음 회의 C는 반드시 B회의가 끝나는 시간 이후부터 시작해야 합니다. 그런데, 회의 C는 회의 A의 다음 회의 후보가 되기도 하기 때문에, B로 시작하는 회의의 수가 A로 시작하는 회의의 수보다 많아질 수 없습니다. 그래서, 빨리 끝나는 회의부터 늦게 끝나는 회의 순으로 정렬한 후, 겹치는 회의를..

2025. 4. 22.
카테고리 없음

[C++] 함수 객체( function object, functor ) : operator()를 구현한 타입

함수 객체( function object )함수 객체( function object )는 operator() 함수를 구현한 타입( type )을 말합니다. C++ 표준 라이브러리에서는, 펑터( functor )라고도 불리는, 이 타입을 주로 컨테이너나 알고리즘의 정렬 기준이 필요할 때 사용합니다. 다음 예제에서는 이러한 함수 객체를 사용하는 법을 볼 수 있습니다.class FuncObj{ public: int operator()(int a, int b){ // 이 연산자를 구현한 타입이 함수 객체 return a + b; }};int Func(int a, int b){ // 일반 함수 return a + b;}int main(){ FuncObj func; // 함수 ..

2025. 3. 13.
카테고리 없음

[C++] 배열, 컨테이너, 사용자 정의 데이터를 정렬하기 위한 std::sort

std::sort의 정의와 기초 사용법std::sort는 지정된 범위에 있는 데이터 요소를 기본적인 오름차순 또는 지정한 정렬 기준에 따라 정렬하는 함수입니다.이 함수를 사용하기 위해서는 우선 다음과 같은 헤더파일을 포함해야 합니다.#include 이 함수의 정의는 다음과 같습니다.templatevoid sort( RandomAccessIterator first, RandomAccessIterator last);위의 첫 번째 인자 first는 정렬할 범위의 첫 번째 요소의 주소를 지정하는 임의 액세스 Iterator입니다. 두 번째 인자 last는 정렬할 범위의 마지막 요소 다음 위치의 주소를 지정하는 임의 액세스 Iterator입니다. 정의에 사용된 단어를 보면 복잡한 것 같지만, 실제로 사..

2025. 3. 10.