두 개의 정렬된 배열과 하나의 숫자 x가 주어졌을 때, 각 배열에서 원소를 하나씩 가져와 만든 쌍 중에서 그 합이 x에 가장 가까운 쌍을 찾는 문제입니다. 배열은 A1[0..m-1]과 A2[0..n-1]로 주어지며, 우리는 |A1[i] + A2[j] − x|의 절댓값이 최소가 되는 쌍 A1[i] + A2[j]를 구해야 합니다.예를 들어 A1 = [1, 4, 5, 7], A2 = [10, 20, 30, 40], x = 32라고 한다면, 출력 결과는 1과 30이 됩니다. 1 + 30 = 31이며, 이는 x인 32와의 차이가 1로 가장

두 친구가 서로의 궁합을 시험해 보려고 합니다. 1부터 n까지 번호가 붙은 영화 목록이 주어지면, 두 사람은 각자 영화에 순위를 매기게 됩니다. 이때 두 사람 사이의 호환성 차이(compatibility difference)란, 같은 영화에 대해 서로 매긴 상대적 순위가 얼마나 어긋나는지를 나타내는 불일치 횟수입니다.예를 들어 A = [3, 1, 2, 4, 5], B = [3, 2, 4, 1, 5]라면 결과는 2가 됩니다. 첫 번째 사람은 영화 1을 영화 2와 4보다 앞선 순위로 평가했지만, 두 번째 사람은 그 반대로 평가했기 때문

C++ 네임스페이스란 무엇인가? C++에서는 다양한 네임스페이스(namespace)를 사용하며, 필요하다면 개발자가 직접 네임스페이스를 정의할 수도 있습니다. 가장 대표적인 예가 표준 라이브러리를 담고 있는 std 네임스페이스로, 보통 다음과 같은 구문을 작성합니다: using namespace std; std 네임스페이스가 존재하는 이유 표준 라이브러리에는 컨테이너(container), 알고리즘(algorithm) 등 애플리케이션 개발에 자주 사용되는 공통 기능들이 포함되어 있습니다. 만약 이 이름들이 전역 공간에 그대로 노출되

함수 오버로딩(Function Overloading)은 객체 지향 프로그래밍 언어의 핵심 기능 중 하나입니다. 매개변수의 개수나 타입이 다르다면 동일한 이름의 함수를 여러 개 정의할 수 있습니다. 이번 글에서는 C++ 클래스에서 생성자 오버로딩(Constructor Overloading)을 활용하는 방법을 알아보겠습니다.생성자 오버로딩의 핵심 개념생성자 오버로딩을 올바르게 사용하기 위해서는 다음 세 가지 중요한 규칙을 반드시 이해해야 합니다.오버로딩된 생성자들은 이름은 같지만, 매개변수의 개수가 서로 달라야 합니다.객체 생성 시 전

C++ getline() 함수란? C++의 getline() 함수는 스트림에서 문자를 비형식화(unformatted) 입력으로 추출하여, C 스타일 문자열(c-string)인 s에 저장하는 함수입니다. 추출 작업은 구분 문자(delimiter)를 만나거나, 종료 널 문자(null character)를 포함해 최대 n개의 문자가 s에 기록될 때까지 계속 진행됩니다. 공백을 포함한 한 줄 전체를 입력받을 수 있어, cin >> 연산자로는 처리하기 어려운 문장 단위 입력에 유용하게 활용됩니다. 함수 선언 basic_istre

텍스트 에디터(Text Editor)텍스트 에디터는 프로그램 코드를 직접 작성하는 데 사용되는 필수 도구입니다. 대표적인 에디터로는 Windows 메모장(Notepad), OS Edit 명령어, Brief, Epsilon, EMACS, 그리고 vim 또는 vi 등이 있습니다.텍스트 에디터의 종류와 버전은 운영체제마다 다를 수 있습니다. 예를 들어 Windows에서는 주로 메모장을 사용하며, vim이나 vi는 Windows뿐 아니라 Linux와 UNIX 환경에서도 활용할 수 있습니다.에디터로 작성한 파일을 소스 파일(source fi

C++에서 배열이나 벡터의 요소 순서를 무작위로 섞어야 할 때가 종종 있습니다. 이럴 때 STL(표준 템플릿 라이브러리)에서 제공하는 random_shuffle()과 shuffle() 함수를 활용하면 간단하게 해결할 수 있습니다. 배열 대신 vector를 사용해도 사용 방법은 동일합니다.random_shuffle() 함수란?random_shuffle()은 지정된 범위 [first, last) 내의 요소들을 무작위로 재배치하는 함수입니다. 각 요소의 위치를 임의로 선택된 다른 위치와 서로 교환하는 방식으로 동작합니다.이 함수에는 사용

C++ STL에서 upper_bound() 함수는 정렬된 컨테이너에서 특정 값보다 큰 첫 번째 원소를 찾는 데 사용되는 핵심 알고리즘입니다. 이 글에서는 upper_bound()의 동작 원리, 문법, 그리고 실제 활용 예제까지 자세히 살펴보겠습니다.upper_bound()란 무엇인가?upper_bound() 함수는 컨테이너 내에서 전달된 값(val)보다 크다고 판단되는 첫 번째 원소를 가리키는 반복자(iterator)를 반환합니다. 만약 해당하는 원소가 존재하지 않으면, 컨테이너의 끝(end)을 가리키는 반복자를 반환합니다.이 함수

n개의 원소를 가진 배열 A[]가 주어졌을 때, 크기가 n+1인 또 다른 배열 B[]를 구성해야 합니다. 이때 배열 B는 인접한 두 원소의 최대공약수(GCD)가 원래 배열의 값과 일치해야 하며, 즉 GCD(B[i], B[i+1]) = A[i] 조건을 만족해야 합니다. 만약 가능한 답이 여러 개라면, 그중 배열 원소의 합이 가장 작은 하나를 출력하면 됩니다.예를 들어 A = [1, 2, 3]이라면, 결과 배열은 [1, 2, 6, 3]이 됩니다. 실제로 GCD(1, 2) = 1, GCD(2, 6) = 2, GCD(6, 3) = 3으로

양수로만 이루어진 크기 n의 배열 A[]가 있다고 가정해 보겠습니다. 이때 새로운 배열 B를 만들어야 하며, 각 요소 B[i]는 A[i] 자기 자신을 제외한 A[]의 나머지 모든 요소들의 XOR 값이 되어야 합니다.예를 들어 A = [2, 1, 5, 9]라면, 결과는 B = [13, 14, 10, 6]이 됩니다.접근 방법이 문제는 전체 XOR 값을 단 한 번만 계산하는 아이디어로 효율적으로 해결할 수 있습니다. 먼저 배열 A의 모든 요소를 XOR한 값을 변수 x에 저장합니다. 그다음 각 요소 A[i]에 대해 B[i] = x XOR

문제 설명(2 × n − 1)개의 정수로 이루어진 배열이 주어집니다. 우리는 이 배열에서 정확히 n개의 요소를 선택하여 각각의 부호를 변경(-1을 곱하기)할 수 있습니다. 이때 얻을 수 있는 배열 합의 최댓값을 구하는 것이 목표입니다.예시입력 배열이 {-2, 100, -3}이라고 가정해 보겠습니다. 이 경우 -2와 -3의 부호를 변경하면 최대 합을 얻을 수 있습니다.부호 변경 후 배열은 {2, 100, 3}이 되며, 이 배열의 최대 합은 105입니다.해결 알고리즘배열 내 음수의 개수를 셉니다.모든 요소의 절댓값을 더하여 전체 합을

문제 설명 N개의 정수로 이루어진 배열이 주어집니다. 배열 요소를 재배치하여 다음 요소가 이전 요소보다 크도록, 즉 arr[i+1] > arr[i] 조건을 만족하는 인접 쌍의 개수를 최대화해야 합니다. 예시 입력 배열이 {300, 400, 400, 300}이라면, 재배치된 배열은 다음과 같습니다. {300, 400, 300, 400} 이 배치에서는 arr[i+1] > arr[i] 조건을 만족하는 인덱스가 2개입니다(400 > 300이 두 번 성립). 따라서 정답은 2입니다. 알고리즘 배열의 모든 요소가 서로 다르

문제 설명크기가 N으로 동일한 두 개의 배열이 주어졌을 때, 각 배열에서 원소를 하나씩 선택하여 최대한 많은 쌍(pair)을 만들어야 합니다. 단, 다음 조건을 만족해야 합니다.각 배열의 원소는 최대 한 번만 사용할 수 있습니다.쌍을 이루는 두 원소의 절댓값 차이는 주어진 값 K 이하여야 합니다.예시입력이 다음과 같다고 가정해 보겠습니다.arr1[] = {3, 4, 5, 2, 1}arr2[] = {6, 5, 4, 7, 15}k = 3일 때, 절댓값 차이가 3 이하인 다음과 같은 4개의 쌍을 만들 수 있습니다.(1, 4), (2, 5

문제 정의 최소 힙(minimum heap)이 주어졌을 때, 해당 힙에 포함된 요소 중 최댓값을 찾는 것이 목표입니다. 예시 입력으로 다음과 같은 힙이 주어진다고 가정해 보겠습니다. 이 경우 힙 내 최댓값은 55입니다. 접근 방식 및 알고리즘 최소 힙에서는 부모 노드가 항상 자식 노드보다 작거나 같은 값을 가집니다. 따라서 자식을 가지는 비단말(내부) 노드는 절대 최댓값이 될 수 없습니다. 결국 최댓값은 반드시 단말 노드(leaf node) 중에 존재하므로, 단말 노드들만 순회하며 최댓값을 탐색하면 됩니다. 배열 기반 힙에서

문제 개요하나의 정수 n이 주어졌을 때, n의 이진 표현에서 서로 인접한 두 개의 1 사이에 존재하는 0의 최대 개수를 구하는 것이 이번 문제의 목표입니다. 만약 이진 표현에 1이 두 개 미만으로 존재한다면 -1을 반환해야 합니다.예시입력값이 35라고 가정해 보겠습니다. 35의 이진 표현은 다음과 같습니다.00100011위 이진수에서 가장 오른쪽의 두 1은 서로 붙어 있어 사이의 0이 없지만, 그 앞의 1과의 사이에는 0이 3개 존재합니다. 따라서 정답은 3이 됩니다.알고리즘 접근 방법이 문제는 비트 시프트 연산자를 활용하면 효율적

이 글에서는 n×n 크기의 정방 행렬(정사각 행렬)이 주어졌을 때, 행렬 전체를 효율적으로 탐색하여 최댓값과 최솟값을 찾는 방법을 다룹니다.문제 설명n*n 차수의 정방 행렬이 주어졌을 때, 행렬에 포함된 요소들 중 최댓값과 최솟값을 구하는 것이 목표입니다.예시다음과 같은 행렬이 주어졌다고 가정해 보겠습니다.{{15, 17, 19}, {5, 1, 7}, {14, 5, 16}} 결과: 최솟값은 1, 최댓값은 19입니다.알고리즘행렬의 각 행에서 한쪽 끝에 있는 요소와 반대쪽 끝에 있는 요소, 즉 두 개의 요소를 선택합니다.선택한 두 요소

문제 개요양의 정수 n개로 이루어진 배열이 주어졌을 때, 배열에서 임의의 두 원소를 골라 수행한 비트 AND(bitwise AND) 연산 결과 중 최댓값을 찾는 것이 목표입니다.예시입력 배열이 {10, 12, 15, 18}이라면, 만들 수 있는 비트 AND 값 중 최댓값은 12입니다. 실제로 12 AND 15 = 12이며, 다른 모든 쌍의 결과는 이보다 작습니다.알고리즘 접근 방법비트 AND 연산은 두 비트가 모두 1일 때만 1이 됩니다. 따라서 결과를 최대화하려면 가능한 한 높은 자리 비트(MSB)부터 1로 만드는 것이 유리합니다

문제 설명사변형의 네 변 a, b, c, d가 주어졌을 때, 이 변들을 이용해 만들 수 있는 사변형의 최대 면적을 구하는 것이 목표입니다.알고리즘이 문제는 고대 인도의 수학자 브라마굽타(Brahmagupta)가 제시한 공식을 활용해 해결할 수 있습니다.브라마굽타 공식:면적 = √((s-a)(s-b)(s-c)(s-d))위 공식에서 s는 준둘레(semi-perimeter)를 의미하며, 다음과 같이 계산됩니다.s = (a + b + c + d) / 2왜 이 공식이 최대 면적을 보장할까?네 변의 길이가 고정되어 있을 때, 모든 꼭짓점이 하

문제 정의크기가 같은 두 배열 A[]와 B[]가 주어졌을 때, 동일한 크기의 세 번째 배열을 만드는 것이 과제입니다. 결과 배열에는 두 배열에서 선택한 총 n개의 최대값 요소가 포함되어야 하며, A[]에서 선택한 요소들이 먼저 오고 그다음 B[]에서 선택한 요소들이 각각 원래 배열에서 나타난 순서 그대로 배치되어야 합니다. 또한 두 배열에 공통으로 존재하는 요소가 있다면 결과 배열(res[])에는 한 번만 포함되어야 하고, 이 경우 우선권은 A[]에 주어집니다.예시입력 배열이 다음과 같다고 가정해 보겠습니다.arr1[] = {9,

문제 설명 정수 배열 arr[]과 두 개의 정수 X, Y가 주어집니다. 길이가 최소 X 이상, 최대 Y 이하인 모든 부분 배열 가운데 평균값이 가장 큰 부분 배열을 찾아 그 평균을 구하는 것이 목표입니다. 예시 입력 배열이 {2, 10, 15, 7, 8, 4}이고 X = 2, Y = 3일 때, 길이 2짜리 부분 배열 {10, 15}를 선택하면 최대 평균 12.5를 얻을 수 있습니다. (10 + 15) / 2 = 12.5 접근 방법 길이가 X부터 Y 사이인 모든 부분 배열을 하나씩 살펴보며 그중 가장 큰 평균값을 기록합니다. 매번