문제 소개 컨테이너 벽들의 높이가 담긴 배열이 주어졌을 때, 가장 많은 양의 물을 담을 수 있는 컨테이너를 찾는 것이 목표입니다. 벽의 높이는 배열의 요소로 주어지며, 두 벽 사이의 거리는 너비로 간주합니다. 예를 들어 높이가 Arr[i]와 Arr[j]인 두 벽 사이의 너비는 j-i입니다(단, 0 ≤ i < j ≤ N). 여기서 N은 벽의 개수, 즉 배열의 길이입니다. 물은 두 벽 중 낮은 높이까지만 차오릅니다. 따라서 Arr[i] < Arr[j]라면 물의 높이는 Arr[i]가 되고, 물이 담기는 면적은 다음과 같이 계산

그래프 이론에서 고립 정점(isolated vertex)이란 어떤 간선에도 연결되어 있지 않은 정점을 의미합니다. 이 글에서는 정점의 수(nov)와 간선의 수(noe)가 주어졌을 때, 해당 조건으로 그래프를 구성할 경우 나타날 수 있는 고립 정점의 최솟값과 최댓값을 C++로 구하는 방법을 알아보겠습니다. 최소 고립 정점 구하기 고립 정점을 최소화하려면 모든 간선이 서로 다른 정점을 사용하도록 배치해야 합니다. 즉, 두 간선이 같은 정점을 공유하지 않게 하는 것입니다. 하나의 간선은 두 개의 정점만 필요로 하므로 다음과 같이 계산

장난감 가격들이 배열 형태로 주어져 있고, 손에 들고 있는 금액 K가 있습니다. 목표는 이 금액으로 구매할 수 있는 장난감의 최대 개수를 구하는 것입니다. 배열의 각 요소는 장난감 하나의 가격을 의미하므로, 배열의 크기가 곧 전체 장난감의 수가 됩니다.핵심 아이디어가장 효율적인 방법은 가격 배열을 오름차순으로 정렬하는 것입니다. 저렴한 장난감부터 우선적으로 구매해야, 한정된 예산으로 최대한 많은 장난감을 살 수 있기 때문입니다. 이는 대표적인 그리디(Greedy) 알고리즘 문제입니다.입출력 예시 1toyprices[] = { 10,

양의 정수 N이 주어졌을 때, 부등식 x² + y² < N을 만족하는 음수가 아닌 정수 쌍(x, y)의 개수를 구하는 것이 이 글의 목표입니다. 여기서 (0,1)과 (1,0)처럼 순서가 다른 쌍은 서로 다른 쌍으로 계산합니다.이 문제는 브루트 포스 방식으로 해결할 수 있습니다. x를 0부터 x² < N까지, y를 0부터 y² < N까지 순회하면서 각 조합마다 x² + y² < N 조건을 검사하고, 조건을 만족할 때마다 쌍의 개수를 하나씩 증가시키면 됩니다.입력 및 출력 예시예시 1n = 4고유한 쌍의 개수 =

문제 소개 0과 1로만 구성된 이진 문자열이 하나 주어집니다. 또한 어떤 사람이 current_pos 변수에 저장된 위치, 즉 숫자 직선 위의 한 점에서 출발한다고 가정합니다. 문자열을 앞에서부터 한 글자씩 읽어 나가면서, 문자가 0이면 한 칸 왼쪽(current_pos − 1)으로, 1이면 한 칸 오른쪽(current_pos + 1)으로 이동합니다. 목표는 문자열 전체를 다 처리한 뒤, 그동안 방문했던 서로 다른 지점의 개수를 구하는 것입니다. 이 문제는 각 지점의 방문 횟수를 기록하는 방식으로 해결할 수 있습니다. 어떤 지점의

이진 탐색 트리(Binary Search Tree, BST)가 입력으로 주어졌을 때, 모든 노드의 값이 특정 범위(start ~ end) 안에 속하는 하위 트리(subtree)의 개수를 구하는 것이 목표입니다. 예를 들어 start가 5이고 end가 50이라면, BST에서 모든 노드의 값이 5 이상 50 이하인 하위 트리의 개수를 세어야 합니다. 예제 입력 1 아래와 같은 트리와 범위 [3-6]이 주어집니다. 출력 − 범위 내에 있는 트리 개수 − 2 설명 − 노드 4와 6만 해당됩니다. 이 노드들

오픈 소스란 무엇인가?오픈 소스는 소프트웨어 분야에서 일반적으로 오픈 소스 소프트웨어(OSS, Open Source Software)라고 불리는 개념입니다. OSS는 인터넷에서 자유롭게 이용할 수 있으며, 누구나 사용하고, 수정하고, 테스트하고, 추가로 개발할 수 있는 소프트웨어를 의미합니다. 수정이 가능하다는 특성 덕분에 전 세계 다양한 사용자들이 편리하게 활용할 수 있으며, 사용자는 자신의 필요에 따라 소프트웨어 패치를 추가하거나 제거할 수 있습니다.오픈 소스는 프로그래머, 개발자, 테스터 등이 코드와 아이디어를 기여하며 함께

끝없이 진화하는 컴퓨팅의 세계컴퓨팅 분야는 끊임없이 혁신을 거듭하고 있습니다. 매일 새로운 기기가 등장하면서 이전 세대의 제품들은 급변하는 기술 환경에 더 이상 적합하지 않게 됩니다. 방 하나를 가득 채울 만큼 거대한 컴퓨터가 연산 하나에 몇 시간씩 걸리던 시대는 이미 지나갔습니다.진공관에서 트랜지스터와 집적회로를 거쳐 터치스크린 기기에 이르기까지, 기술의 발전은 컴퓨팅 방식 자체를 바꿔놓았습니다. 새로운 기기를 위한 프로그래밍 스타일 역시 달라졌습니다. 전통적인 방식의 프로그래밍으로는 더 이상 최신 기기를 다룰 수 없으며, 탑재되

문제 개요 정수 N과 K가 주어집니다. 0과 1로만 구성된 길이 N의 이진 문자열 중에서, 인접한 1이 정확히 K번 나타나는 문자열의 개수를 구하는 것이 목표입니다. 예를 들어 N=3, K=2라면, 길이 3의 모든 이진 문자열 중에서 인접한 1이 두 번 나타나는 문자열의 개수를 세어야 합니다. 111 — 인접한 1이 두 번 나타납니다 (K번). 011, 110 — 인접한 1이 한 번만 나타납니다. 해결 아이디어: 다이나믹 프로그래밍(DP) 이 문제는 이전에 계산한 결과값을 저장해 두는 방식, 즉 다이나믹 프로그래밍으로 효율적으로

HH:MM 형식의 24시간제 디지털 시계가 주어졌을 때, 주어진 시간(시, 분) 동안 시계의 네 자리 숫자가 모두 동일한 경우가 몇 번 발생하는지 세는 문제입니다. 문제 이해 24시간 형식에서 시(HH)와 분(MM)의 모든 숫자가 같은 경우는 하루에 단 3번뿐입니다. 00:00 (자정) 11:11 22:22 33:33이나 44:44는 24시간제에서 존재하지 않는 시간이므로 제외됩니다. 입력으로 주어진 총 시간(시간 + 분) 범위 안에 이 3가지 시각이 몇 번 포함되는지 확인하면 됩니다. 입력 및 출력 예시 예시

문제 개요 서로 다른 크기를 가진 두 종류의 물건, 즉 큰 장난감과 작은 장난감이 있다고 가정해 봅시다. 물건의 종류는 사용자가 자유롭게 정할 수 있으며, 여기서는 이해를 돕기 위해 크기 속성에 따라 구분되는 장난감을 예로 들겠습니다. 이 문제의 목표는 작은 장난감을 교환해서 얻을 수 있는 큰 장난감의 최대 개수를 계산하는 것입니다. 교환 규칙은 다음과 같습니다. a : 큰 장난감 1개를 얻기 위해 필요한 작은 장난감의 개수 b : 큰 장난감 1개를 포기했을 때 돌려받는 작은 장난감의 개수 만약 b가 a보다 크다면(b >

문제 개요 정렬되지 않은 정수 배열이 주어졌을 때, 다음 두 조건을 모두 만족하는 요소들의 최대 개수를 구하는 것이 목표입니다. 각 요소의 세트 비트(set bit) 개수가 서로 동일해야 합니다. 조건을 만족하는 요소들은 배열 안에서 반드시 연속적(contiguous)으로 배치되어 있어야 합니다. 여기서 세트 비트란 이진수 표현에서 값이 1인 비트를 의미합니다. 입출력 예시 예시 1 입력 − int arr[] = { 5, 8, 1, 2, 9, 12 } 출력 − 같은 수의 세트 비트를 가진 연속 배열 요소의 최대 개수: 3 설

문제 개요임의의 크기를 가진 정수 배열이 주어졌을 때, 인접한 두 요소의 차이가 0 또는 1이 되는 가장 긴 연속 부분 배열(subarray)의 길이를 찾는 것이 이번 문제의 목표입니다.예제 1입력: int arr[] = { 2, 1, 5, 6, 3, 4, 7, 6 }출력: 인접 요소 간의 차이가 0 또는 1인 최대 길이 부분 배열: 2설명: 배열에서 인접 요소 간의 차이가 0 또는 1을 만족하는 구간은 {2, 1}, {5, 6}, {3, 4}, {7, 6}입니다. 모든 구간의 길이가 2이므로 부분 배열의 최대 길이는 2가 됩니다.

배열이 하나 주어졌을 때, 인접하게 선택된 요소들 간의 차이가 0 또는 1이 되도록 요소를 고른 부분 수열(subsequence) 중 가장 길이가 긴 것을 찾는 것이 이 글의 목표입니다. 여기서 부분 수열이란 배열에서 요소의 상대적인 순서를 유지하면서 일부 요소를 생략해 만든 나열을 의미합니다. 문제 이해하기 입력 − int arr[] = { 2, 1, 5, 6, 3, 4, 7, 6 } 출력 − 인접 요소 간 차이가 0 또는 1인 최장 부분 수열의 길이: 4 설명 − 원래 순서를 유지한 채 {5, 6, 7, 6}을 선택하면 인접 요

임의의 크기를 가진 정수 배열이 주어졌을 때, 인접한 요소 간의 차이가 0 또는 1이 되도록 요소들을 선택하는 부분 수열(subsequence) 중 가장 긴 것의 길이를 구하는 것이 과제입니다. 여기서 부분 수열이란 배열에서 원소들의 상대적인 순서를 유지하면서 일부 원소를 생략하여 만든 수열을 의미합니다. 예제 입력 및 출력 입력 − int arr[] = { 2, 1, 5, 6, 3, 4, 7, 6 } 출력 − 인접 요소 간의 차이가 0 또는 1인 최대 길이 부분 수열의 길이: 3 설명 − 배열에서 순서를 유지하면서 {5, 6

문제 개요이 문제는 주어진 힘(strength) P로 최대 몇 명까지 처치할 수 있는지 구하는 것이 목표입니다.무한히 많은 사람들이 한 줄로 서 있고, 각 사람에게는 1부터 시작하는 번호(index)가 붙어 있습니다. s번째 사람의 힘은 s2이며, 힘이 s인 사람을 처치하면 자신의 힘도 s만큼 감소합니다.예제를 통해 문제를 자세히 살펴보겠습니다.입력P = 20출력3풀이 과정1번째 사람의 힘 = 1 × 1 = 1 < 20 → 처치 가능 남은 힘 = 20 − 1 = 19 2번째 사람의 힘 = 2 × 2 = 4 < 19 → 처

이번 문제는 문자열에서 주어진 부분 수열(subsequence)을 제거할 수 있는 최대 횟수를 구하는 것입니다. 하나의 문자열 s가 주어졌을 때, 이 문자열에서 abc라는 부분 수열을 최대 몇 번까지 제거할 수 있는지 찾아야 합니다.문제 이해하기예시를 통해 문제를 자세히 살펴보겠습니다.입력s = dnabcxy출력1설명 − 주어진 문자열(dnabcxy)에서 abc 부분 수열은 한 번만 발견할 수 있으므로 출력은 1입니다.입력s = zcabcxabc출력2 (zcabcxabc)풀이 접근 방식Max() 함수에서 int 타입의 변수 i, a

문제 개요 주어진 점들을 여러 선분에 배정했을 때, 적어도 하나의 점을 포함하게 되는 선분의 개수를 최대화하는 것이 이번 글에서 다룰 문제입니다. 크기가 n1인 배열 a1[]과 두 정수 A, B가 주어집니다. 배열 a1[]의 각 원소를 이용해 총 n1개의 선분을 만들 수 있으며, i번째 선분은 시작점 a1[i] – A, 끝점 a1[i] + B로 정의됩니다. 또 다른 배열 a2[]에는 n2개의 점이 주어집니다. 이 점들을 선분에 배정하여, 점이 하나라도 배정된 선분의 개수가 최대가 되도록 만들어야 합니다. 단, 하나의 점은 하나의 선

이 문제는 밑변의 길이가 s인 직각 이등변 삼각형(두 변의 길이가 같은 삼각형) 안에 한 변의 길이가 a인 정사각형을 최대 몇 개까지 배치할 수 있는지 구하는 것이 목표입니다.예시를 통해 문제를 자세히 살펴보겠습니다.입력 예시s = 5, a = 1출력 결과10해설: 삼각형 밑변에 들어갈 수 있는 정사각형의 개수는 밑변 길이를 정사각형 한 변의 길이로 나눈 뒤 1을 빼면 됩니다. 즉, 밑변의 정사각형 개수는 5 ÷ 1 − 1 = 4개입니다.맨 아래 줄에 4개의 정사각형을 배치하면, 그 위에는 밑변이 (s − a)인 새로운 이등변 삼각

이 문제의 목표는 동일한 문자로만 구성된 길이 K인 부분 문자열(substring)이 문자열 안에 몇 번 나타나는지 그 최대 개수를 구하는 것입니다. 하나의 문자열 s와 정수 K가 주어졌을 때, 길이가 K이면서 모든 문자가 같은 부분 문자열의 등장 횟수를 세고, 그중 가장 많이 나타난 횟수를 출력해야 합니다.예제를 통해 문제를 자세히 살펴보겠습니다.입력 예시 1s = tuuxyyuuc, K = 2출력 예시 12설명길이가 2이면서 동일한 문자로 구성된 부분 문자열은 uu와 yy입니다. 이때 yy는 1번만 등장하지만, uu는 2번 등장