못생긴 수(Ugly Number)란? 못생긴 수(Ugly Number)란 소인수가 오직 2, 3, 5뿐인 양의 정수를 의미합니다. 1부터 15 사이에는 총 11개의 못생긴 수가 존재하는데, 바로 1, 2, 3, 4, 5, 6, 8, 9, 10, 12, 15입니다. 반면 7, 11, 13은 자기 자신 외에 약수가 없는 소수이므로 못생긴 수에 해당하지 않으며, 14는 소인수 분해했을 때 7이 포함되기 때문에 역시 제외됩니다. 예를 들어 10번째 못생긴 수를 구하면 그 값은 12가 됩니다. 알고리즘 n번째 못생긴 수를 구하는 핵심 아이디

정수 배열이 주어지고, 특정 구간 [i, j]에 포함된 요소들의 합을 구하는 문제를 생각해 보겠습니다. 이 문제에서는 두 가지 조건을 염두에 두어야 합니다. 첫째, 배열은 불변(immutable)이므로 생성 이후 요소 값이 변경되지 않으며, 둘째, 같은 형태의 구간 합 쿼리가 여러 번 반복해서 들어옵니다. 따라서 쿼리 개수가 많아질 때 실행 시간을 효율적으로 관리하는 것이 핵심입니다.예를 들어 배열이 A = [5, 8, 3, 6, 1, 2, 5]라고 할 때, 쿼리 (A, 0, 3)의 결과는 5 + 8 + 3 + 6 = 22가 됩니다

값 n이 주어졌을 때, n번째 트리보나치(Tribonacci) 수를 구하는 문제를 살펴보겠습니다. 트리보나치 수는 피보나치 수와 유사하지만, 다음 항을 만들 때 이전 두 항이 아닌 세 개의 이전 항을 더한다는 점이 다릅니다.n번째 항 T(n)을 구하는 공식은 다음과 같습니다.T(n) = T(n - 1) + T(n - 2) + T(n - 3)수열은 {0, 1, 1}에서 시작하며, 그 뒤의 항들은 앞의 세 항을 모두 더한 값이 됩니다. 예를 들어 네 번째 항은 0 + 1 + 1 = 2, 다섯 번째 항은 1 + 1 + 2 = 4가 됩니다

날짜(일, 월, 연도)가 주어졌을 때, 그 날짜가 무슨 요일인지 계산해야 하는 경우가 종종 있습니다. 이 문제는 젤러의 알고리즘(Zellers Algorithm)을 사용하면 간단하게 해결할 수 있습니다.젤러의 알고리즘 공식주어진 날짜의 요일을 구하는 젤러의 공식은 다음과 같습니다.w = (d + ⌊13(m+1)/5⌋ + y + ⌊y/4⌋ + ⌊c/4⌋ + 5c) mod 7공식에 사용되는 변수d — 날짜의 일을 나타냅니다.m — 월 코드입니다. 3월부터 12월까지는 그대로 3~12를 사용하고, 1월은 13, 2월은 14로 치환합니다.

등차수열(Arithmetic Progression)의 원소들이 순서대로 담긴 배열이 있다고 가정해 봅시다. 이 배열에는 한 개의 원소가 누락되어 있으며, 우리의 목표는 바로 그 빠진 원소를 찾아내는 것입니다. 예를 들어 arr = [2, 4, 8, 10, 12, 14]와 같은 배열이 주어졌다면, 공차가 2인 등차수열에서 6이 빠져 있으므로 출력값은 6이 되어야 합니다.이진 탐색을 활용한 접근 방법이 문제는 이진 탐색(Binary Search)을 활용하면 O(log n)의 시간 복잡도로 효율적으로 해결할 수 있습니다. 핵심 아이디어는

문제 설명서로 다른 고유한 원소들로 구성된 정렬된 배열이 임의의 지점에서 회전된 상태로 주어졌을 때, 이 배열에서 최댓값을 찾는 문제입니다.예를 들어 {30, 40, 50, 10, 20} 배열은 원래 {10, 20, 30, 40, 50} 순서로 정렬되어 있다가 특정 지점에서 회전한 형태입니다.예시입력 배열이 {30, 40, 50, 10, 20}이라면 최댓값은 50입니다.알고리즘최댓값은 바로 다음 원소가 자신보다 작은 유일한 원소입니다. 만약 그런 원소가 존재하지 않는다면 배열이 회전되지 않았다는 의미이며, 이 경우 마지막 원소가 곧

문제 개요 매우 큰 크기의 정수 배열이 주어졌을 때, 멀티스레딩(multithreading)을 활용하여 배열 내 최댓값을 찾는 것이 이 글의 목표입니다. 데이터가 방대할 경우 단일 스레드보다 여러 스레드로 작업을 분산 처리하는 것이 훨씬 효율적입니다. 예시 입력 배열이 다음과 같다고 가정해 보겠습니다. {10, 14, -10, 8, 25, 46, 85, 1673, 63, 65, 93, 101, 125, 50, 73, 548} 이 배열에서 가장 큰 요소는 1673입니다. 알고리즘 배열의 크기를 total_elements라고 정의합

문제 개요주어진 배열 arr[]에서 특정 인덱스 i를 기준으로 접두사 합(prefix sum)과 접미사 합(suffix sum)이 서로 같아지는 지점을 찾고, 그중 최댓값을 구하는 문제입니다.여기서 접두사 합은 배열의 시작부터 인덱스 i까지의 원소 합을 의미하고, 접미사 합은 인덱스 i부터 배열의 끝까지의 원소 합을 의미합니다. 이렇게 두 값이 일치하는 지점을 평형 지점(equilibrium point)이라고 부르며, 해당 지점에서의 합계가 바로 평형 합계입니다.예시입력 배열이 다음과 같다고 가정해 보겠습니다.Arr[] = {1,

프로그래밍에서 데이터 타입(data type)은 사용자가 사용하려는 데이터의 종류와 성격을 의미합니다. 컴파일러나 인터프리터는 이 데이터 타입을 기준으로 데이터를 처리하며, 메인 메모리에 그에 맞는 저장 공간을 할당하게 됩니다.데이터의 성격에 따라 데이터 타입은 크게 두 가지로 나눌 수 있습니다. 하나는 기본 데이터 타입(Fundamental Data Type)이고, 다른 하나는 파생 데이터 타입(Derived Data Type)입니다. 두 데이터 타입 모두 프로그래밍에서 널리 사용되며, 데이터 위에 비즈니스 로직을 구현할 때 동등

문제 개요 하나의 문자열이 주어졌을 때, 그 안의 부분 문자열 중에서 문자들을 재배열해 회문(Palindrome)을 만들 수 있는 것의 최대 길이를 구하는 것이 이 문제의 목표입니다. 예시 입력 문자열이 5432112356이라면 정답은 6입니다. 가장 긴 회문 부분 문자열이 321123이며, 이는 재배열하면 123321이라는 회문이 되고 그 길이가 6이기 때문입니다. 알고리즘 회문은 좌우가 대칭되는 구조이므로, 짝수 길이의 회문이 되려면 포함된 모든 문자가 반드시 짝수 번씩 등장해야 합니다. 이 성질을 활용하면 다음과 같이 문제를

문제 개요 N명의 플레이어가 참가하는 토너먼트가 열린다고 가정해 봅시다. 이때 구해야 할 것은 우승자가 치를 수 있는 경기 수의 최댓값입니다. 단, 이 토너먼트에는 특별한 규칙이 있습니다. 두 플레이어는 각자 지금까지 치른 경기 수의 차이가 1 이하일 때만 서로 대결할 수 있습니다. 이 제약 조건 때문에 단순히 모든 경우를 세는 방식으로는 문제를 풀기 어렵습니다. 예시 플레이어가 3명이라면, 다음과 같이 2번의 경기만으로 우승자를 결정할 수 있습니다. 경기 1: 플레이어 1 vs 플레이어 2 경기 2: 경기 1의 승자 vs 플레

문제 개요주어진 배열의 값들을 이용해 삼각형(피라미드) 형태를 만들 때, 만들 수 있는 최대 높이를 구하는 문제입니다. 단, 피라미드의 각 레벨은 아래에서 위로 올라갈수록 더 적은 수의 원소로 구성되며, 상위 레벨의 합은 하위 레벨보다 커야 한다는 조건을 만족해야 합니다.예시입력 배열이 {40, 100, 20, 30}이라고 가정해 보겠습니다. 이 경우 정답은 2가 됩니다.그 이유는 맨 아래 층에 100과 20을 배치하고, 그 위 층에는 40 또는 30 중 하나를 배치할 수 있기 때문입니다. 즉, 두 층으로 이루어진 피라미드를 완성할

문제 설명 N개의 원소로 구성된 배열 arr[]가 주어집니다(0 ≤ arr[i] ≤ 1000). 이 문제의 목표는 오직 Ugly Number(추한 수)로만 이루어진 부분 배열(sub-array) 중 가장 긴 것의 길이를 찾는 것입니다. 여기서 Ugly Number란 소인수(prime factor)가 2, 3, 5뿐인 수를 의미합니다. 예를 들어 이러한 수열에는 다음과 같은 수들이 포함됩니다: 1, 2, 3, 4, 5, 6, 8, 9, 10, 12, 15… 예시 입력 배열이 {1, 2, 7, 9, 120, 810, 374}라고 가정

문제 설명n개의 막대 길이가 배열로 주어집니다. 어떤 사람이 막대를 하나 선택하면, 현재 가장 긴 막대의 절반((max + 1) / 2)을 할당받고, 남은 부분((max − 1) / 2)은 다시 되돌려 놓습니다. 막대는 항상 충분하다고 가정할 때, 배열 q[]로 주어지는 M개의 쿼리에 대해 각 qi번째 사람(1부터 시작하는 유효한 번호)이 받게 될 가장 긴 막대의 길이를 구하는 것이 목표입니다.예시입력 : a[] = {6, 5, 9, 10, 12}q[] = {1, 3}출력 : 12 9첫 번째 사람은 최대 길이인 12를 받습니다.배열

문제 개요0과 1로만 이루어진 문자열이 주어집니다. 이 문자열을 여러 개의 세그먼트(연속된 부분 구간)로 나누되, 각 세그먼트에 포함된 1의 개수가 0의 개수보다 많아야 한다는 조건을 만족해야 합니다. 목표는 이 조건을 충족하는 세그먼트들을 골라 그 길이의 합을 최대화하는 것입니다.예시입력 문자열이 10111000001011일 때 정답은 12입니다.첫 번째 세그먼트: 길이 7 → 1011100 (1이 4개, 0이 3개)두 번째 세그먼트: 길이 5 → 01011 (1이 3개, 0이 2개)전체 길이 = 7 + 5 = 12주목할 점은 모

문제 개요이 문제에서는 문자 배열이 주어집니다. 우리가 작성해야 할 프로그램은 첫 번째 요소와 마지막 요소가 서로 동일한 부분 배열(subarray)의 최대 길이를 출력하는 것입니다.예시로 문제 이해하기입력 − array = {t, u, t, o, r, i, a, l, s, p, o, i, n, t}출력 − 14설명 −부분 배열 {t, u, t, o, r, i, a, l, s, p, o, i, n, t}는 t로 시작하고 t로 끝나므로 조건을 만족하며, 그 길이는 14입니다.접근 방법이 문제를 해결하려면 배열 속 각 문자가 처음 등장

이 문제에서는 n개의 요소로 이루어진 배열이 주어지며, arr[i] >= arr[j]를 만족하는 모든 배열 쌍에 대해 최대 모듈로(나머지) 값을 찾는 프로그램을 작성하는 것이 목표입니다. 즉, arr[i] >= arr[j] 조건을 만족하는 쌍들 중에서 arr[i] % arr[j] 값이 가장 커지는 경우를 찾아야 합니다. 먼저 예제를 통해 문제를 자세히 살펴보겠습니다. 입력 − arr[] = {3, 5, 9} 출력 − 4 풀이 − 가능한 모든 쌍 (arr[i], arr[j])에 대한 나머지

이 문제에서는 두 개의 정수 N과 M이 주어집니다. N은 1번 그룹의 인원 수, M은 2번 그룹의 인원 수를 의미합니다. 우리의 과제는 두 그룹의 인원으로 만들 수 있는 3인 팀의 최대 개수를 찾는 프로그램을 작성하는 것입니다.팀을 구성할 때는 두 그룹에서 사람을 선택하여 최대한 많은 팀을 만들어야 하며, 각 팀에는 반드시 두 그룹의 사람이 각각 최소 한 명씩 포함되어야 합니다.문제 이해를 위한 예시입력 − N = 5, M = 3출력 − 2설명 −팀은 다음과 같이 구성됩니다.팀 1: 1번 그룹 인원 → 2명 ; 2번 그룹 인원 →

문제 설명정수 N이 주어지며, 이 값은 정점(Vertex)의 개수를 나타냅니다. 이 문제의 목표는 N개의 정점을 가진 이분 그래프(Bipartite Graph)에서 만들 수 있는 최대 간선(Edge) 수를 구하는 것입니다.이분 그래프란?이분 그래프는 그래프의 모든 정점을 서로 겹치지 않는 두 개의 집합으로 나눌 수 있는 그래프를 말합니다.그래프의 정점들이 두 개의 집합으로 분할됩니다.같은 집합에 속한 정점들 사이에는 간선이 절대 존재하지 않으며, 모든 간선은 반드시 서로 다른 집합에 속한 정점들을 연결합니다.예시N = 10인 경우,

문제 정의트리(Tree)는 항상 이분 그래프(Bipartite Graph)입니다. 트리의 노드들을 레벨별로 번갈아 배치하면 두 개의 서로소인 집합으로 나눌 수 있기 때문입니다.다시 말해, 인접한 레벨의 노드들은 서로 다른 색을, 같은 레벨의 노드들은 같은 색을 갖도록 두 가지 색으로 전체 노드를 칠할 수 있습니다. 이 문제의 목표는 트리에 간선을 추가하더라도 이분 그래프의 성질이 유지되도록 추가할 수 있는 최대 간선 수를 계산하는 것입니다.예제트리의 간선이 다음과 같은 정점 쌍으로 주어져 있다고 가정합니다.{1, 2}, {1, 3}