문제 개요스택에 저장된 요소 중 최댓값을 O(1) 시간 안에 조회할 수 있는 스택을 구현한다고 가정해 보겠습니다. 여기서 중요한 제약 조건은 별도의 보조 스택과 같은 추가 공간을 사용하지 않아야 한다는 점입니다. 즉, O(1)의 보조 공간만 허용됩니다.접근 방법사용자 정의 스택 클래스를 만들어 현재 최댓값(stack_max)을 멤버 변수로 함께 관리합니다. 각 연산은 다음 규칙에 따라 동작합니다.peek 연산: 스택의 top 값이 현재 최댓값보다 크다면 실제 top 요소는 최댓값이므로 최댓값을 반환하고, 그렇지 않으면 top 값을

금액이 하나 주어졌을 때, 서로 다른 액면가의 지폐를 조합하여 정확히 그 금액을 만들 수 있는 최소 개수의 지폐를 구하는 문제를 생각해 봅시다. 핵심 아이디어는 가장 큰 액면가의 지폐부터 시작해, 주어진 금액 범위 안에서 가능한 한 많은 장수를 사용하는 것입니다.이때 {2000, 500, 200, 100, 50, 20, 10, 5, 2, 1} 각 액면가의 지폐는 무한히 보유하고 있다고 가정합니다. 예를 들어 금액이 800이라면 필요한 지폐는 500 1장, 200 1장, 100 1장, 총 3장이 됩니다.그리디(Greedy) 접근법이

문제 개요의사와 엔지니어로만 구성된 특별한 가족이 있다고 가정해 보겠습니다. 이 가족에는 다음과 같은 규칙이 적용됩니다.모든 사람은 반드시 두 명의 자녀를 둡니다.엔지니어의 첫째 자녀는 엔지니어가 되고, 둘째 자녀는 의사가 됩니다.의사의 첫째 자녀는 의사가 되고, 둘째 자녀는 엔지니어가 됩니다.모든 세대는 항상 엔지니어부터 시작합니다.예를 들어 4세대(level 4)의 2번째 위치(pos 2)에 있는 사람의 직업을 구하면 그 결과는 의사(Doctor)가 됩니다.접근 방법핵심 아이디어는 매우 간단합니다. 한 사람의 직업은 다음 두 가

크기가 각각 m과 n인 정렬된 두 배열 arr1과 arr2가 있다고 가정해 봅시다. 이때 두 배열의 상대 여집합(relative complement)을 구해야 합니다. 상대 여집합이란 arr1에는 존재하지만 arr2에는 없는 모든 원소를 의미합니다.예를 들어 A = [3, 6, 10, 12, 15], B = [1, 3, 5, 10, 16]이라면, A에는 있지만 B에는 없는 원소는 6, 12, 15이므로 결과는 [6, 12, 15]가 됩니다.이 문제는 본질적으로 집합의 차집합 연산과 동일하기 때문에, C++ STL의 set_diffe

양의 정수 L이 있다고 가정해 보겠습니다. L은 포화 이진 트리(perfect binary tree)의 레벨 수를 나타냅니다. 이 트리의 리프 노드는 1부터 n까지 차례대로 번호가 매겨져 있으며, 여기서 n은 리프 노드의 총개수입니다. 또한 각 부모 노드의 값은 두 자식 노드 값의 합이 됩니다. 우리가 작성해야 할 프로그램은 이 포화 이진 트리에 있는 모든 노드 값의 총합을 출력하는 것입니다.예를 들어 트리가 다음과 같다면 −모든 노드의 총합은 30이 됩니다.핵심 아이디어트리를 자세히 살펴보면 결국 전체 노드의 합을 구하

타원의 장축 길이가 2a, 단축 길이가 2b라고 가정해 봅시다. 이때 해당 타원에 내접할 수 있는 가장 큰 원의 면적을 구해야 합니다.예를 들어 a = 5이고 b = 3이라면, 구해야 하는 원의 면적은 28.2734가 됩니다.핵심 아이디어위 그림에서 확인할 수 있듯이, 타원에 내접하는 최대 면적의 원은 그 반지름이 곧 타원의 단축(semi-minor axis) b와 같습니다. 장축 방향으로는 더 크게 확장될 여유가 있지만, 단축 방향으로는 b보다 커질 수 없기 때문입니다.따라서 원의 면적 공식은 다음과 같습니다.A = π ×

문제 소개크기가 n인 배열 A가 주어졌을 때, 배열 안에서 연속된 짝수의 최대 개수를 찾는 것이 목표입니다.예를 들어 배열이 다음과 같다고 해보겠습니다.A = [1, 2, 3, 4, 6, 8, 7]이 경우 인덱스 3부터 5까지의 값인 4, 6, 8이 연속된 짝수 세 개에 해당하므로, 정답은 3이 됩니다.접근 방법이 문제는 선형 탐색 한 번으로 간단하게 해결할 수 있습니다. 핵심 아이디어는 두 개의 카운트 변수를 사용하는 것입니다.max_current: 현재 이어지고 있는 연속 짝수의 개수max_till_now: 지금까지 발견한 연속

직선 위에 N개의 방사 스테이션이 나란히 놓여 있다고 가정해 보겠습니다. 각 스테이션은 음수가 아닌(non-negative) 방사 능력을 가지며, 인접한 스테이션들의 방사 세기를 일정한 규칙에 따라 증가시킵니다.방사 세기가 R인 스테이션 i는 왼쪽의 (i-1)번째 스테이션 방사량을 R-1만큼, (i-2)번째 스테이션 방사량을 R-2만큼 올려 줍니다. 마찬가지로 오른쪽의 (i+1)번째 스테이션은 R-1만큼, (i+2)번째 스테이션은 R-2만큼 증가합니다. 즉, 거리가 한 칸 멀어질 때마다 증가 폭이 1씩 줄어들며, 그 효과가 0 이하

원 위에 n개의 주유소(petrol pump)가 있다고 가정해 봅시다. 각 주유소마다 다음 두 가지 정보가 주어집니다.각 주유소에 저장된 휘발유(연료)의 양한 주유소에서 다음 주유소까지의 거리이때 트럭이 원을 한 바퀴 완주할 수 있는 최초의 출발 지점을 구하는 것이 이 문제의 목표입니다. 단, 트럭은 1리터의 연료로 1단위 거리를 이동할 수 있다고 가정합니다.문제 예시예를 들어 4개의 주유소가 있고, 각각의 (연료량, 다음 주유소까지의 거리)가 아래와 같이 주어졌다고 합시다.(4, 6), (6, 5), (7, 3), (4, 5)이

배열이 처음에는 오름차순으로 증가하다가 어느 지점부터 내림차순으로 감소하는 특수한 구조를 가지고 있다고 가정해 봅시다. 이런 배열에서 최댓값을 효율적으로 찾는 것이 이번 글의 목표입니다.예를 들어 배열이 A = [8, 10, 20, 80, 100, 250, 450, 100, 3, 2, 1]과 같이 구성되어 있다면, 배열은 450까지 계속 증가한 후 다시 감소하기 시작합니다. 따라서 이 배열의 최댓값은 450입니다.모든 요소를 하나씩 확인하는 선형 탐색으로도 해결할 수 있지만, 배열의 정렬된 성질을 활용하면 이진 탐색(Binary S

M × N 크기의 행렬이 주어졌을 때, 이 행렬의 평균 벡터(mean vector)를 구하는 문제를 살펴보겠습니다. 평균 벡터란 각 열(column)별 평균값을 순서대로 나열한 벡터를 의미합니다.문제 이해하기예를 들어 다음과 같은 3×3 행렬이 있다고 가정해 보겠습니다.123456789이 행렬의 평균 벡터는 [4, 5, 6]입니다. 각 열의 평균을 계산하면 다음과 같습니다.첫 번째 열: (1 + 4 + 7) / 3 = 4두 번째 열: (2 + 5 + 8) / 3 = 5세 번째 열: (3 + 6 + 9) / 3 = 6예시에서 알 수

문제 소개 n개의 요소를 가진 배열 A가 있다고 가정해 보겠습니다. 이때 n은 짝수입니다. 우리의 목표는 이 배열의 균형을 맞추기 위해 필요한 값을 구하는 것입니다. 배열의 크기가 짝수이므로 배열을 두 개의 절반으로 나눌 수 있으며, 왼쪽 절반의 합과 오른쪽 절반의 합이 서로 같아지도록 만들어야 합니다. 예를 들어 배열이 A = [1, 2, 3, 2, 5, 3]이라고 해보겠습니다. 왼쪽 절반(1 + 2 + 3)의 합은 6이고, 오른쪽 절반(2 + 5 + 3)의 합은 10입니다. 따라서 양쪽의 합이 같아지려면 합이 작은 쪽에 4를

트리와 각 노드의 가중치, 그리고 하나의 정수 x가 주어졌을 때, |weight[i] − x| 값이 가장 작아지는 노드 i를 찾는 것이 이 문제의 목표입니다.예를 들어 아래와 같은 트리가 있고 x = 15라고 가정해 보겠습니다.이 경우 출력 결과는 3입니다. 각 노드별로 계산해 보면 다음과 같습니다.노드 1: |5 − 15| = 10노드 2: |10 − 15| = 5노드 3: |11 − 15| = 4노드 4: |8 − 15| = 7노드 5: |6 − 15| = 9노드 3의 절대 차이인 4가 다른 모든 노드보다 작으므로 정답은 노드

이진 탐색 트리(Binary Search Tree, BST)가 주어졌을 때, 트리 내에서 가장 작은 값을 가진 노드를 찾는 방법을 알아보겠습니다. 예를 들어 다음과 같은 이진 탐색 트리가 있다고 가정해 봅시다.이 트리에서 최솟값은 1입니다.핵심 아이디어이진 탐색 트리의 가장 중요한 특징은 왼쪽 서브트리에는 항상 부모 노드보다 작은 값들이 위치한다는 점입니다. 따라서 왼쪽 자식 노드가 더 이상 존재하지 않을 때(즉, left가 NULL일 때)까지 계속해서 왼쪽으로 이동하면, 그 위치의 노드가 곧 트리 전체에서 가장 작은 값이 됩니다.

정수로 이루어진 크기 n의 배열이 주어졌을 때, 배열에서 네 개의 원소를 선택하여 얻을 수 있는 곱의 최댓값을 구하는 문제입니다. 예를 들어 배열이 [3, 5, 20, 6, 10]이라면, 10 × 5 × 6 × 20 = 6000이 최대 곱이 됩니다.해결 접근 방법배열에 음수가 포함될 수 있기 때문에 단순히 가장 큰 네 수만 곱하는 것은 정답이 아닐 수 있습니다. 작은 음수 두 개를 곱하면 큰 양수가 되기 때문입니다. 따라서 다음 단계로 문제를 해결합니다.배열을 오름차순으로 정렬합니다.x: 마지막(가장 큰) 네 원소의 곱y: 처음(가

문제 개요문자열 S와 숫자 X가 주어졌다고 가정해 봅시다. 주사위를 굴리는 플레이어는 총 M명이며, 각 플레이어는 X가 아닌 다른 숫자가 나올 때까지 주사위를 계속해서 굴립니다. 문자열 S에서 S[i]는 i번째 주사위 굴림 결과를 나타내며, 우리의 목표는 이 문자열로부터 플레이어의 수 M을 구하는 것입니다.단, 한 가지 제약 조건이 있습니다. 문자열 S의 마지막 문자는 절대 X가 될 수 없습니다. 이는 마지막에 굴린 사람이 반드시 X가 아닌 숫자를 얻고 게임을 마쳤음을 보장합니다.예제예를 들어, 문자열이 3662123이고 X = 6

C++ 프로그래밍에서 배열 감쇠(Array Decay)는 배열의 타입 정보와 크기(차원) 정보가 손실되는 현상을 말합니다. 이 문제는 배열을 함수에 포인터나 값으로 전달할 때 발생합니다. 이 경우 배열 자체가 아니라 배열의 첫 번째 요소 주소(포인터)만 함수에 전달되기 때문에, 함수 내부에서는 원래 배열의 크기를 알 수 없게 됩니다.즉, 함수 안에서 sizeof() 연산자를 사용하면 배열의 실제 전체 크기가 아닌 포인터의 크기가 반환됩니다.배열 감쇠 예제다음 C++ 코드를 통해 배열 감쇠 현상을 확인해 보겠습니다.#include&l

C++에서 map과 unordered_map은 키(key)와 그에 대응하는 값(value)을 저장하는 연관 컨테이너입니다. 이 두 컨테이너는 내부적으로 정렬된 트리(map) 또는 해시 테이블(unordered_map) 구조를 사용하여 데이터를 관리합니다.실무 개발에서는 특정 키가 컨테이너에 이미 존재하는지 확인해야 하는 경우가 자주 발생합니다. 예를 들어, 중복 삽입을 방지하거나 키가 없을 때만 값을 초기화하고 싶을 때가 대표적입니다. 이번 글에서는 주어진 키가 맵에 존재하는지 확인하는 방법을 알아보겠습니다.find() 함수로 키

C++의 set(집합) 컨테이너에서는 값을 인자로 전달하여 해당 요소를 손쉽게 삭제할 수 있습니다. 예를 들어, {10, 20, 30, 50, 60, 80, 90, 100, 120, 200, 500}과 같은 집합이 있을 때 90을 삭제하면 결과는 다음과 같습니다.{10, 20, 30, 50, 60, 80, 100, 120, 200, 500}Set 컨테이너의 특징C++ STL의 set은 다음과 같은 중요한 특성을 가지고 있습니다.각 요소는 집합 내에서 단 한 번만 존재할 수 있습니다. 즉, 중복된 값이 저장되지 않습니다.요소들은 항상

C++의 STL 컨테이너 중 하나인 std::list에 여러 개의 요소가 저장되어 있다고 가정해 보겠습니다. 이때 이 리스트에서 마지막 요소를 삭제해야 하는 상황을 생각할 수 있습니다.예를 들어 리스트의 요소가 [10, 41, 54, 20, 23, 69, 84, 75]와 같이 구성되어 있다면, 마지막 요소는 75입니다. 이 글에서는 C++ 코드를 통해 리스트의 마지막 요소를 삭제하는 방법을 살펴보겠습니다.핵심: pop_back() 함수std::list에는 마지막 요소를 제거하는 전용 멤버 함수인 pop_back()이 제공됩니다. 이