배열 A가 주어졌다고 가정해 봅시다. 이 배열에는 대부분의 숫자가 정확히 두 번씩 등장하지만, 딱 하나의 숫자만 한 번 등장합니다. 우리의 목표는 바로 이 유일한 요소를 찾아내는 것입니다.예를 들어 A = [1, 1, 5, 3, 2, 5, 2]라면 출력은 3이 되어야 합니다. 다른 숫자들은 모두 두 번씩 나타나지만 3만 한 번 등장하기 때문입니다.XOR 연산의 핵심 원리이 문제는 XOR(배타적 논리합) 연산을 활용하면 매우 우아하게 해결할 수 있습니다. XOR에는 다음과 같은 중요한 성질이 있습니다.같은 수를 XOR하면 0이 됩니다

문제 개요2차원 행렬 mat과 값 K가 주어졌을 때, 원소들의 합이 정확히 K와 같으면서 면적이 가장 넓은 직사각형 부분 행렬(submatrix)을 찾는 것이 목표입니다.예를 들어 다음과 같은 4×4 행렬이 있다고 가정해 보겠습니다.28-56-778-311-1443-43110여기서 K = 9라면, 답은 왼쪽 위 좌표가 (1, 0), 오른쪽 아래 좌표가 (3, 2)인 부분 행렬입니다.-77811-144-431실제로 이 부분 행렬의 합은 (-7) + 7 + 8 + 11 + (-14) + 4 + (-4) + 3 + 1 = 9로 조건을 만

문제 개요0부터 9 사이의 숫자들이 담긴 배열이 주어졌을 때, 이 숫자들 중 일부를 골라 임의의 순서로 이어 붙여 만들 수 있는 수 중에서 3의 배수이면서 가장 큰 값을 찾는 것이 목표입니다. 결과값이 매우 커질 수 있으므로 문자열 형태로 반환해야 하며, 만들 수 있는 3의 배수가 존재하지 않는다면 빈 문자열을 반환합니다.예를 들어 입력이 [7, 2, 8]이라면, 출력은 87입니다.접근 방법이 문제는 각 숫자를 3으로 나눈 나머지를 기준으로 분류하는 그리디(Greedy) 알고리즘으로 효율적으로 해결할 수 있습니다. 어떤 수가 3의

문제 개요 n개의 숫자로 이루어진 두 배열 A와 B가 주어졌다고 가정해 봅시다. 배열 B의 요소들을 스스로 안에서 재배열했을 때, (A[i] + B[i]) % n으로 계산되는 수열이 사전순(lexicographically)으로 가장 작아지도록 만들어야 합니다. 최종적으로 이렇게 얻을 수 있는 사전순 최소 수열을 반환하면 됩니다. 예를 들어 입력이 A = {1, 2, 3, 2}, B = {4, 3, 2, 2}라면, 출력은 [0, 0, 1, 2]가 됩니다. 접근 방법 이 문제는 그리디(Greedy) 기법으로 해결할 수 있습니다. 각

문제 개요쌍(pair)으로 이루어진 배열 A가 주어졌을 때, 최대 K개의 쌍을 선택하여 얻을 수 있는 최대 비용을 구하는 문제입니다.여기서 비용(cost)은 다음 두 값의 곱으로 정의됩니다.선택된 모든 쌍의 첫 번째 원소의 합선택된 쌍들 중 두 번째 원소의 최솟값예를 들어 (4, 8), (10, 3), (3, 6) 세 쌍을 선택했다면 비용은 (4+10+3)×3 = 51이 됩니다(K=3인 경우).입력 예시입력이 다음과 같다면,A = [(15, 5), (65, 25), (35, 20), (20, 5), (35, 20), (15, 18)

문제 이해하기 N개의 서로 다른 직사각형에 대한 너비와 높이 정보가 주어졌을 때, 직사각형을 서로 안에 삽입(중첩)하는 과정을 거친 후 마지막에 남게 되는 직사각형의 최소 개수를 구하는 것이 목표입니다. 두 직사각형 R1과 R2의 너비를 각각 W1, W2, 높이를 H1, H2라고 할 때, W1 < W2이고 H1 < H2를 만족하면 R1은 R2 안에 완전히 들어갈 수 있습니다. 따라서 가장 작은 직사각형은 두 번째로 작은 직사각형 안에, 그 직사각형은 다시 더 큰 직사각형 안에 차례대로 중첩시킬 수 있습니다. 예를 들어 입

수직선 위에 서 있는 사람의 초기 위치가 숫자 N으로 주어지고, 왼쪽으로 이동할 확률이 L이라고 가정해 봅시다. 이때 점 N에서 출발하여 정확히 N번 이동한 후, 수직선상의 각 지점에 도달할 확률을 모두 구하는 것이 이 문제의 목표입니다. 매 이동은 왼쪽 또는 오른쪽으로 한 칸씩 이루어집니다.예를 들어 입력이 n = 2, l = 0.5라면 출력은 [0.25, 0, 0.5, 0, 0.25]가 됩니다.해결 접근 방법이 문제는 동적 계획법(Dynamic Programming)을 활용하면 효율적으로 해결할 수 있습니다. 이동 횟수별로 각

가중치가 부여된 무방향 그래프가 하나 주어져 있다고 가정해 봅시다. 그래프에는 N개의 서로 다른 노드와 M개의 간선이 존재하며, 그중 일부 노드는 좋은 노드(good node)로 분류되어 있습니다. 우리가 구해야 하는 것은 서로 다른 두 좋은 노드로 이루어진 모든 쌍 가운데, 두 노드 사이의 거리가 가장 짧은 값입니다.예를 들어 그래프에서 노란색으로 칠해진 노드들을 좋은 노드라고 생각해 보겠습니다. 좋은 노드 쌍과 그 사이의 거리가 각각 (1 → 3)은 11, (3 → 5)는 13, (1 → 5)는 24라면, 이 중 가장 작은 값인

문제 개요문자열 s와 길이가 모두 같은 여러 단어로 이루어진 리스트 words가 주어졌다고 가정해 봅시다. 이때 s 안에서 words에 포함된 각 단어를 정확히 한 번씩 사용하여 연결한(단어 사이에 다른 문자가 끼어 있지 않은) 부분 문자열의 시작 인덱스를 모두 찾아야 합니다.예를 들어 입력 문자열이 wordgoodgoodgoodword이고 words가 [word, good]라면 출력은 [0, 12]입니다. 인덱스 0에서 시작하는 부분 문자열은 wordgood, 인덱스 12에서 시작하는 부분 문자열은 goodword이기 때문입니다.

다음과 같은 함수가 주어졌다고 가정해 봅시다. f(x) = (x6 + x2 + 9894845) % 971 주어진 x 값에 대해 f(x)의 값을 구하는 것이 목표입니다. 예를 들어 입력이 5라면 결과는 469가 됩니다. 접근 방법 x가 커지면 x6처럼 거듭제곱한 값이 급격히 커져 자료형의 표현 범위를 벗어나는 오버플로우가 발생할 수 있고, 연산 속도도 느려집니다. 이를 해결하려면 모듈러 거듭제곱(modular exponentiation), 즉 빠른 거듭제곱(fast exponentiation) 기법을 사용해야 합니다. 이 방법은 분할

C++의 다형성(polymorphism)은 객체 지향 프로그래밍의 핵심 개념 중 하나입니다. 이 글에서는 비가상(non-virtual) 멤버 함수 내부에서 가상(virtual) 함수가 호출될 때 어떤 일이 일어나는지 알아보겠습니다. 두 가지 경우로 나누어 실행해 본 뒤, 그 원리를 분석해 보겠습니다. 첫 번째 경우: 가상 함수 없이 프로그램을 실행합니다. 두 번째 경우: 비가상 함수 내부에서 가상 함수를 호출하며 프로그램을 실행합니다. 첫 번째 경우: 가상 함수 없이 실행 먼저 virtual 키워드 없이 기본 클래스와 파생 클래

들어가며C++에서는 파생 클래스가 기본 클래스의 가상 함수를 재정의할 때, 원래보다 더 엄격한 접근 지정자(private 등)를 적용하는 것이 문법적으로 가능합니다. 그렇다면 이런 코드는 실제로 어떻게 동작할까요? 이 글에서는 몇 가지 예제를 통해 파생 클래스 메서드의 접근 권한을 제한했을 때 발생하는 현상과 그 이유를 자세히 분석해 보겠습니다.예제 1: 파생 클래스에서 display()를 private으로 재정의먼저 기본 클래스의 display() 함수는 public으로 선언하고, 파생 클래스에서는 같은 함수를 private으로

C++ 프로그램이 컴파일될 때 변수와 객체가 메모리의 어느 위치에 저장되는지 아는 것은 메모리 관리를 이해하는 데 매우 중요합니다. C++에서 객체는 크게 두 가지 메모리 영역에 저장됩니다.1. 스택(Stack)블록({}) 내부에서 선언된 모든 지역 변수와 객체는 스택 영역에 저장됩니다. main 함수 역시 하나의 함수이므로, 그 안에서 선언된 요소들도 모두 스택에 저장됩니다.2. 힙(Heap)힙 영역은 객체가 동적으로 할당될 때 사용되는 공간입니다. 런타임 중에 new 연산자를 통해 생성된 객체는 모두 힙에 저장됩니다.블록 내 객

C++에서 멤버 변수나 멤버 함수가 하나도 없는 빈 클래스를 정의했을 때, 그 크기가 과연 0일까요? 결론부터 말하면 그렇지 않습니다. C++ 표준은 크기가 0인 객체(또는 클래스)의 존재를 허용하지 않습니다. 만약 빈 클래스의 크기가 0이라면, 서로 다른 두 객체가 메모리상에서 동일한 위치를 가질 수 있게 되어 심각한 문제가 발생하기 때문입니다. 이러한 이유로 C++ 표준은 빈 클래스라도 최소한 1바이트의 크기를 갖도록 규정하고 있습니다. 일반적으로 빈 클래스의 크기는 1바이트입니다. 다음 예제를 통해 직접 확인해 보겠습니다.예제

C++에서 동적 메모리 할당(new)을 통해서만 객체를 생성할 수 있고, 스택에 직접 객체를 선언하는 것은 허용되지 않는 클래스를 만들어야 하는 경우가 있습니다. 스마트 포인터나 참조 카운팅 기반 객체처럼 힙 할당을 강제하고 싶을 때 유용한 기법인데요, 이번 글에서는 그 구현 방법을 예제와 함께 자세히 살펴보겠습니다. 핵심 원리: private 소멸자 활용 방법은 의외로 간단합니다. 바로 소멸자(destructor)를 private 영역에 선언하는 것입니다. 소멸자가 private이면 컴파일러는 스택 기반의 일반 객체 생성 코드를

C++의 많은 내장 STL 함수들은 원하는 값이 저장된 메모리 주소(포인터)를 반환합니다. 하지만 이 주소는 컨테이너 내부의 실제 인덱스와는 직접적인 관련이 없습니다.대표적인 예로 최댓값 요소를 찾는 std::max_element() 함수가 있습니다. 이 함수는 해당 요소의 인덱스가 아니라 메모리상의 주소를 반환하죠. 그런데 실무에서는 이 주소로부터 인덱스를 얻어야 하는 경우가 종종 발생합니다. 이번 글에서는 STL 함수가 반환한 포인터에서 인덱스를 계산하는 두 가지 방법을 살펴보겠습니다.1. begin() 반복자를 빼서 인덱스 계

이미지 처리 분야에서 가우시안 필터(Gaussian Filter)는 노이즈를 효과적으로 줄이는 데 널리 사용되는 대표적인 기법입니다. 이미지 블러링(blurring)이나 에지 검출 전의 전처리 단계 등 다양한 용도로 활용되며, 그 핵심에는 2차원 가우시안 커널(kernel)이 있습니다. 이 글에서는 C++을 이용해 5×5 크기의 2D 가우시안 커널을 직접 생성하는 방법을 살펴보겠습니다. 2D 가우시안 분포 공식 2차원 가우시안 커널의 각 요소는 다음 수식으로 계산됩니다. $$G(x,y)= \frac{1}{2\pi\sigma^{2

이번 글에서는 C++ STL 함수를 활용해 테스트 케이스를 생성하는 방법을 살펴보겠습니다. 배열 기반 프로그램의 테스트 케이스를 일일이 손으로 작성하면 매우 번거롭고 비효율적일 수 있습니다. C++은 이런 작업을 간편하게 처리해 주는 두 가지 함수를 제공합니다.generate() 메서드C++의 std::algorithm::generate() 함수는 생성자 함수(gen)를 반복 호출하여 반환된 값으로 first부터 last까지 범위의 모든 요소에 값을 할당합니다. 매개변수는 세 가지입니다.first: 값을 채우기 시작할 초기 위치를

이 글에서는 C++ STL에서 제공하는 complex 클래스를 활용하여 점(Point) 클래스를 만드는 방법을 살펴보고, 이를 기하학 관련 문제에 적용해 보겠습니다. 복소수는 STL의 complex 헤더(#include <complex>)에 포함되어 있어 별도의 구현 없이 바로 사용할 수 있습니다.Point 클래스 정의하기복소수를 점처럼 다루기 위해 complex<double> 타입에 point라는 이름을 붙이고, 복소수 클래스의 real() 함수를 x좌표로, imag() 함수를 y좌표로 매핑합니다. 이렇게 하

이 글에서는 C++의 map 컨테이너와 그 사용법에 대해 자세히 알아보겠습니다.map 컨테이너란?map은 요소들을 해시 매핑 방식으로 저장하는 연관 컨테이너(associative container)입니다. 각 요소는 키(key)와 값(value)의 쌍으로 구성되며, 서로 다른 두 요소가 동일한 키를 가질 수 없습니다. 즉, 키는 항상 고유해야 하며 이를 통해 값에 빠르게 접근할 수 있습니다.map의 주요 메서드C++ map 컨테이너에서 제공하는 기본적인 메서드는 다음과 같습니다.begin() — 맵의 첫 번째 요소를 가리키는 반복자