이 글에서는 주어진 정사각형 이진 행렬에서 왼쪽 위 칸([0][0])에서 출발하여 오른쪽 아래 칸([n-1][n-1])에 도달하는 경로를 따라 만들 수 있는 최대 10진수 값을 구하는 방법을 알아봅니다.경로를 따라 이동할 때는 오른쪽([i][j+1]) 또는 아래쪽([i+1][j])으로만 움직일 수 있으며, 최종 정수 값은 지나간 칸들의 비트 값을 이용해 계산됩니다.문제 이해하기예제를 통해 문제를 자세히 살펴보겠습니다.입력m = { {1, 1, 1, 1}, {0, 0, 1, 0}, {1, 0, 1, 1},

주어진 이진 문자열에서 부분 문자열(substring)을 찾아, 그 안에서 0의 개수와 1의 개수 차이가 최대가 되는 값을 구하는 문제입니다.예시를 통해 문제를 자세히 살펴보겠습니다.입력 예제str = 10010110출력 결과2설명위 문자열에서 위치 1부터 4까지의 부분 문자열은 0010입니다. 이 구간에서 0은 3개, 1은 1개이므로 차이는 3 − 1 = 2가 되며, 이것이 구할 수 있는 최댓값입니다.추가 입력 예제str = 000005모든 문자가 0인 경우, 전체 문자열을 선택하면 0과 1의 개수 차이는 5 − 0 = 5로 최대

주어진 이진 문자열(binary string)에서 하나의 부분 문자열(substring)을 찾은 뒤, 그 부분 문자열 안에서 0의 개수와 1의 개수 차이가 최대가 되는 값을 구하는 것이 이번 문제의 목표입니다.예시를 통해 문제를 자세히 살펴보겠습니다.입력 예제str = 100100110출력3설명위 문자열에서 특정 구간의 부분 문자열 00100을 살펴보면, 0은 4개, 1은 1개이므로 개수 차이는 4 − 1 = 3입니다. 이 값이 해당 문자열에서 구할 수 있는 최댓값입니다.입력 예제str = 00000출력5모든 문자가 0으로만 이루어

이 문제는 주어진 문자열에서 두 대문자 사이에 존재하는 서로 다른(고유한) 소문자 알파벳의 최대 개수를 찾는 것입니다.예시를 통해 문제를 자세히 이해해 보겠습니다.입력 예시 1str = JKyubDoorG출력3설명대문자 K와 D 사이에는 yub라는 소문자 3개가 존재하므로 개수는 3이 됩니다.또한 대문자 D와 G 사이에는 oor이 존재하지만, o가 중복된 문자이기 때문에 고유한 문자만 세면 2가 됩니다.따라서 최종 출력은 3입니다.입력 예시 2str = ABcefsTaRpaep출력4풀이 접근 방법Max() 함수 안에서 int siz

이 문제의 목표는 주어진 배열에서 각 요소를 최대 k번까지 증가시킬 수 있을 때, 동일한 값으로 만들 수 있는 요소의 최대 개수를 구하는 것입니다. 구체적인 예시를 통해 문제를 살펴보겠습니다. 입력 예제 1 a[] = {1, 3, 8}, k = 4 출력 2 설명 배열의 1을 세 번 증가시키고 3을 한 번 증가시키면 총 4번의 업데이트(k = 4) 안에서 두 개의 4를 만들 수 있습니다. 결과적으로 배열은 {4, 4, 8}이 되며, 같은 값으로 만든 요소의 개수는 2개입니다. 입력 예제 2 arr = {2, 5, 9}, k = 2

문제 설명 초기값을 가진 이진 배열 arr[]와 두 변수 a, b가 주어집니다. 배열의 각 요소를 통과하는 방법은 다음 두 가지입니다. arr[i] == 1인 경우: a에서 1단위를 사용하면 b에는 변화가 없습니다. 반대로 b에서 1단위를 사용하면 a가 1만큼 증가합니다. (단, a의 값은 원래 값보다 커질 수 없습니다.) arr[i] == 0인 경우: a 또는 b 어느 쪽에서든 1단위를 사용할 수 있습니다. 목표는 주어진 조건 안에서 배열의 최대한 많은 요소를 통과하는 것입니다. 예시를 통해 자세히 살펴보겠습니다. 입력 예제

이 글에서는 비트마스킹과 동적 프로그래밍(Dynamic Programming)의 기본 개념을 먼저 학습한 뒤, 실제 문제를 함께 풀어보며 구현 과정에서 생길 수 있는 궁금증을 해결해 보겠습니다.비트마스크(Bitmask)란?비트마스크는 마스크(mask)라고도 불리며, 집합의 부분집합을 인코딩하는 N비트 시퀀스입니다. 마스크의 각 비트는 설정(set, 1)되거나 설정되지 않은(unset, 0) 상태를 가질 수 있으며, 이는 해당 요소가 부분집합에 포함되어 있는지 여부를 나타냅니다.예를 들어, 마스크의 i번째 비트가 1로 설정되어 있다면

바이토닉 정렬(Bitonic Sort)은 최적의 구현을 목표로 설계된 병렬 정렬 알고리즘으로, 하드웨어 및 병렬 프로세서 배열과 함께 사용할 때 가장 뛰어난 성능을 발휘합니다.병합 정렬(merge sort)에 비해 단독 실행 시 효율성은 떨어지지만, 병렬 구현에는 매우 적합합니다. 그 이유는 비교 순서가 사전에 정의되어 있어 각 비교 연산이 정렬 대상 데이터와 독립적으로 수행될 수 있기 때문입니다.바이토닉 정렬이 효과적으로 작동하려면 정렬할 요소의 개수가 반드시 2^n 형태, 즉 2의 거듭제곱이어야 한다는 점에 유의해야 합니다.바이

이 문제에서는 두 개의 정수 a와 b가 주어지며, 우리의 목표는 a부터 b까지 범위에 있는 모든 숫자의 비트 AND(&) 결과를 구하는 것입니다. 즉, a & (a+1) & (a+2) & ... & (b-1) & b의 값을 계산해야 합니다.문제 이해하기예시를 통해 문제를 살펴보겠습니다.입력 − a = 3, b = 8출력 − 0설명 − 3 & 4 & 5 & 6 & 7 & 8 = 0단순한 해결 방법가장 직관적인 방법은 a부터 시작하여 숫자를 하나씩 증가시키면서 b까

문제 개요이 문제에서는 크기가 n인 이진 문자열 배열 bin[]이 주어지며, N개의 이진 문자열 전체에 대한 비트 AND(&) 연산 결과를 구하는 프로그램을 작성해야 합니다. 즉, 배열의 모든 요소를 다음과 같이 AND 연산하는 것입니다.bin[0] & bin[1] & ... & bin[n-2] & bin[n]예시로 문제 이해하기입력:bin[] = {1001, 11001, 010101}출력:000001설명: 세 이진 문자열의 비트 AND 연산 결과는 다음과 같습니다.(1001) & (11001)

이 문제에서는 크기가 n인 배열 arr[]와 정수 k가 하나씩 주어집니다. 우리가 구해야 하는 것은 배열 안에서 인덱스 i부터 j까지에 해당하는 부분 배열(subarray)을 선택해 그 모든 원소의 비트 AND(bitwise AND)를 계산한 뒤, 그 값과 k 사이의 차이, 즉 |k − (비트 AND 값)|이 최소가 되는 경우를 찾아 그 최솟값을 출력하는 것입니다.예제로 문제 이해하기입력: arr[] = {5, 1}, k = 2출력: 1배열 {5, 1}에서 만들 수 있는 부분 배열은 {5}, {1}, {5, 1} 세 가지이며, 각각

이 문제에서는 두 개의 정수 a와 b가 주어지며, a부터 b까지 범위에 있는 모든 수의 비트 OR(|) 값을 구해야 합니다. 즉, a | a+1 | a+2 | … | b-1 | b의 결과를 계산하는 것이 목표입니다. 문제 이해하기 예시를 통해 문제를 살펴보겠습니다. 입력 − a = 3, b = 8 출력 − 15 설명 − 3 | 4 | 5 | 6 | 7 | 8 = 15 단순한 접근 방법 가장 직관적인 방법은 a부터 시작하여 1씩 증가시키면서 b까지 모든 숫자를 차례대로 OR 연산하는 것입니다. 하지만 범위가 넓어질수록 연산 횟수가 그

문제 개요이 문제에서는 크기가 n인 이진 문자열 배열 bin[]이 주어지며, 배열에 포함된 모든 문자열에 대해 비트 OR(Bitwise OR) 연산을 수행한 결과를 구하는 것이 목표입니다.즉, 다음과 같이 모든 문자열의 비트 OR를 계산해야 합니다.bin[0] | bin[1] | ... | bin[n-2] | bin[n-1]예시입력:bin[] = {1001, 11001, 010101}출력:011101설명: 모든 이진 문자열의 비트 OR 결과는 다음과 같습니다.(1001) | (11001) | (010101) = 011101해결 접근

문제 개요 하나의 숫자 N이 주어졌을 때, 비트와이즈 체(Bitwise Sieve)를 활용해 N보다 작은 모든 소수를 찾는 것이 이번 글의 목표입니다. 비트와이즈 체는 널리 알려진 에라토스테네스의 체(Sieve of Eratosthenes)를 최적화한 알고리즘으로, 주어진 수보다 작은 모든 소수를 빠르고 효율적으로 구할 수 있습니다. 문제 예시 입력: N = 25 출력: 2 3 5 7 11 13 17 19 23 비트와이즈 체의 동작 원리 비트와이즈 체는 일반적인 에라토스테네스의 체와 동일한 방식으로 동작합니다. 결정적인 차이점은 불

BK 트리란 무엇인가?BK 트리(BK Tree), 또는 버크하트 트리(Burkhard Tree)는 레벤슈타인 거리(Levenshtein Distance)를 기반으로 맞춤법 검사를 수행하는 데 널리 사용되는 데이터 구조입니다. 자동 수정(AutoCorrect) 기능을 구현할 때도 이 자료구조가 활용됩니다.예를 들어 사전에 여러 단어가 저장되어 있고, 입력된 단어의 철자 오류를 검사해야 한다고 가정해 보겠습니다. 이때 검사 대상 단어와 철자가 유사한 단어들의 집합이 필요합니다. 예컨대 uck이라는 단어가 입력되었다면 올바른 후보로는 t

블록 스왑(Block Swap) 알고리즘은 배열 회전에 사용되는 매우 효율적인 알고리즘입니다. 이 알고리즘을 활용하면 O(n)의 시간 복잡도로 배열 회전 작업을 수행할 수 있습니다.배열 회전 문제에서는 크기가 n인 배열 arr[]와 회전할 원소의 개수를 나타내는 숫자 k가 주어집니다.배열 회전 예시입력 −arr[] = {4, 6, 1, 8, 9, 2}, k = 2 (회전 횟수)출력 −{1, 8, 9, 2, 4, 6}설명 − 회전이 일어나면 맨 앞의 원소 하나가 마지막 위치로 이동하고, 나머지 원소들은 각각 한 칸씩 앞으로 이동합니다

이 문제에서는 두 개의 정수 값과 포인터로 구성된 노드를 가진 연결 리스트(Linked List)가 주어집니다. 우리의 과제는 각 노드에 포함된 두 값 중 더 작은 값들을 모두 찾아 그 합을 계산하는 프로그램을 만드는 것입니다.연결 리스트의 각 노드에는 X와 Y라는 두 개의 요소가 있습니다. 프로그램은 각 노드를 순회하면서 min(X, Y), 즉 두 값 중 최솟값을 구하고, 이 최솟값들을 모두 더한 결과를 반환해야 합니다.문제 예시입력 −(5,2)->(7,9)->(6,3)->(36,24)->(19,26)->

문제 개요이 문제에서는 3개의 배열 X, Y, Z가 주어지며, 각 배열에서 하나씩 요소를 선택해 만들 수 있는 특수 삼중항(special triplet)들의 값의 총합을 구하는 프로그램을 작성해야 합니다.특수 삼중항은 다음 조건을 만족하는 삼중항입니다.(a, b, c)에 대해 a ≤ b 이고 b ≥ c, 즉 삼중항의 가운데 요소가 나머지 두 요소보다 크거나 같아야 합니다.삼중항의 값은 다음 공식으로 계산됩니다.f(a, b, c) = (a+b) * (b+c)즉, 주어진 세 배열에서 각각 하나의 요소를 가져와 위 조건을 만족하는 조합을

문제 개요 자연수 n이 주어졌을 때, 홀수들의 제곱으로 이루어진 수열 1² + 3² + 5² + … + (2n−1)²의 합을 구하는 문제입니다. i번째 홀수는 2i−1로 표현할 수 있으므로, 이 값들을 n개 만큼 모두 더하면 전체 합이 됩니다. 예시 입력: n = 5 출력: 165 설명: 합 = 1² + 3² + 5² + 7² + 9² = 1 + 9 + 25 + 49 + 81 = 165 방법 1: 반복문으로 직접 계산하기 가장 직관적인 접근 방식은 반복문을 사용해 각 항을 하나씩 더하는 것입니다. 변수 i를 1부터 n까지

이 문제에서는 문자열 str이 주어지며, 우리가 만들어야 할 프로그램은 이 문자열과 그 모든 접미사(suffix) 사이의 유사성(similarity) 값들의 합을 구하는 것입니다.여기서 문자열 str의 접미사란 문자열의 앞부분 문자를 하나씩 제거하여 만들 수 있는 모든 문자열을 의미합니다.두 문자열의 유사성은 두 문자열이 공유하는 가장 긴 접두사(prefix)의 길이로 정의됩니다. 예를 들어, str1 = abbac와 str2 = abb의 유사성은 3입니다.반면 str1 = abca와 str2 = ca의 유사성은 0입니다. 유사성은