이진 행렬(2차원 그리드)이 주어졌을 때, 그 안에 있는 섬의 개수를 세는 문제를 살펴보겠습니다. 여기서 섬이란 물로 둘러싸인 영역으로, 가로 또는 세로 방향으로 인접한 땅(1)들이 서로 연결되어 형성된 것을 의미합니다. 대각선 방향의 연결은 고려하지 않으며, 그리드의 네 가장자리는 모두 물로 둘러싸여 있다고 가정합니다.예를 들어 다음과 같은 그리드가 있다고 가정해 보겠습니다.11000110000010000011위 그리드에는 총 3개의 섬이 존재합니다. 왼쪽 위의 2×2 크기 블록, 중앙의 단일 셀, 오른쪽 아래의 L자 형태 블록이

문제 소개정수 k와 n개의 노드로 이루어진 트리가 주어졌을 때, 서로 다른 두 정점 사이의 거리가 정확히 k가 되는 고유한 정점 쌍의 개수를 세는 것이 이 글의 목표입니다.예를 들어 k = 2이고 다음과 같은 트리가 주어진다고 가정해 보겠습니다.이 트리에서 거리가 정확히 2인 정점 쌍은 총 4개이므로, 기대되는 출력값은 4입니다.알고리즘 접근 방법이 문제는 깊이 우선 탐색(DFS)을 활용하면 효율적으로 해결할 수 있습니다. 핵심 아이디어는 각 정점 v에 대해 v로부터 거리가 d인 정점의 개수를 저장하고, 자식 서브트리의 정보를 부모

두 개의 값 n과 m이 주어졌을 때, 크기가 n×m인 직사각형 내부에 배치할 수 있는 크기가 2×1인 직사각형(도미노)의 개수를 구하는 문제입니다. 이때 반드시 고려해야 할 조건은 다음과 같습니다.작은 직사각형끼리 서로 겹쳐서는 안 됩니다.모든 작은 직사각형은 큰 직사각형 내부에 완전히 포함되어야 하며, 큰 직사각형의 가장자리에 닿는 것은 허용됩니다.예를 들어 위 그림처럼 입력이 n = 3, m = 3이라면 출력 결과는 4가 됩니다.풀이 접근 방식크기가 2×1인 직사각형은 정확히 2칸의 면적을 차지합니다. 따라서 배치 가능한 최대

경기장에는 총 n명의 관중이 있으며, 각 관중은 1부터 n까지 번호가 매겨져 있습니다. 이때 다음과 같은 규칙에 따라 관중들이 일어나고 앉는다고 가정해 보겠습니다.시각 t1에 첫 번째 관중이 일어섭니다.시각 t2에 두 번째 관중이 일어섭니다.…시각 tk에 k번째 관중이 일어섭니다.시각 tk+1에 (k+1)번째 관중이 일어서고, 동시에 첫 번째 관중은 앉습니다.시각 tk+2에 (k+2)번째 관중이 일어서고, 두 번째 관중은 앉습니다.…시각 tn에 n번째 관중이 일어서고, (n−k)번째 관중은 앉습니다.시각 tn+1에 (n+1−k)번째

문제 소개 처음 N개의 자연수가 한 번씩 등장하는 순열(permutation) 형태의 배열 A와 하나의 정수 M(M ≤ N)이 주어졌을 때, 중앙값이 정확히 M이 되는 연속 부분 배열(sub-array)이 총 몇 개인지 구하는 문제입니다. 중앙값(median)이란 배열의 원소들을 오름차순으로 정렬했을 때 정중앙에 위치한 값을 의미합니다. 단, 길이가 짝수인 경우에는 두 가운데 원소 중 왼쪽에 있는 값을 중앙값으로 사용한다는 점에 유의해야 합니다. 예시 A = [3, 5, 6, 4, 2], M = 5라고 가정해 보겠습니다. 조건을 만

n개의 서로 다른 작업이 있다고 가정해 보겠습니다. 각 작업에는 0부터 n-1까지 번호가 붙어 있으며, 일부 작업은 반드시 먼저 완료해야 하는 선행 작업(prerequisite)을 가질 수 있습니다. 예를 들어 [2, 1]이라는 쌍은 작업 2를 수행하려면 먼저 작업 1을 끝내야 한다는 의미입니다. 전체 작업의 개수와 선행 관계 쌍의 목록이 주어졌을 때, 모든 작업을 완료할 수 있는 순서를 찾아야 합니다. 올바른 순서가 여러 개 존재한다면 그중 하나만 반환하면 되며, 모든 작업을 완료하는 것이 불가능한 경우(순환 종속성이 존재하는 경

크기가 N인 배열 A와 크기가 M인 배열 B, 그리고 N×M 크기의 이진 행렬이 주어졌다고 가정해 보겠습니다. 이진 행렬에서 1은 원래 행렬의 해당 위치에 양의 정수가 있었다는 뜻이고, 0은 그 자리가 0이었음을 의미합니다. 목표는 A[i]가 i번째 행의 최댓값이 되고 B[j]가 j번째 열의 최댓값이 되도록 원래 행렬을 다시 만들어 내는 것입니다.예를 들어 입력이 A = [4, 2, 3], B = [3, 1, 0, 0, 4, 0, 5]와 같다면, 알고리즘은 아래와 같은 행렬을 결과로 출력합니다.문제 해결 접근 방식핵심 아이디어는 매

소문자로만 구성된 문자열 S가 주어지고, 두 명의 플레이어가 이 문자열을 놓고 게임을 진행한다고 가정해 보겠습니다. 게임 규칙은 다음과 같습니다.자신의 차례에 문자열의 문자들을 재배열하여 회문(palindrome)을 만들 수 있다면 해당 플레이어가 즉시 승리합니다.반대로 문자열에서 문자를 하나 제거해야만 하는 상황이라면 그 차례에는 승리할 수 없습니다.두 플레이어 모두 항상 최적의 전략으로 게임을 진행하며, 플레이어 1이 선공입니다. 이때 최종 승자가 누구인지 구해야 합니다.예를 들어 입력이 pqpppq라면 출력은 플레이어 1입니다

두 개의 배열 A와 B가 있다고 가정해 보겠습니다. 배열 A의 크기는 행(row)의 개수를 의미하며, A[i]는 i번째 행에 있는 상자의 개수를 나타냅니다. 배열 B는 공(ball)들의 목록으로, B[i]는 각 공에 적힌 숫자입니다. 이때 i번째 공(값이 B[i])은 처음 위치부터 세었을 때 B[i]번째에 해당하는 상자에 놓이게 됩니다. 따라서 우리가 구해야 할 것은 각 B[i]에 대응하는 상자의 행과 열입니다.문제 예시입력이 A = [3, 4, 5, 6], B = [1, 3, 5, 2]라고 한다면, 출력은 [(1, 1), (1,

마르코프 체인이란?마르코프 체인(Markov Chain)은 여러 개의 상태(state)와 한 상태에서 다른 상태로 이동할 확률로 구성된 무작위 확률 과정(random process)입니다. 이는 방향 그래프(directed graph)로 나타낼 수 있으며, 이때 노드(node)는 각각의 상태를 의미하고, 에지(edge)에는 한 노드에서 다른 노드로 이동할 확률이 저장됩니다.마르코프 체인의 핵심 성질은 다음과 같습니다.한 상태에서 다른 상태로 이동하는 데 걸리는 시간은 항상 단위 시간(unit time)입니다.모든 노드에서 나가는 에

문제 개요오름차순으로 정렬된 양의 정수 배열이 주어졌을 때, 이 배열의 어떤 부분 집합의 합으로도 표현할 수 없는 가장 작은 양의 정수를 찾아야 합니다. 단, 시간 복잡도 O(n) 안에 문제를 해결해야 한다는 조건이 있습니다.예를 들어 입력이 A = [1, 4, 8, 12, 13, 17]이라면 출력은 2가 됩니다. 배열에 1은 존재하지만, 2를 만들 방법이 없기 때문입니다(1 다음 요소가 4이므로 1+4=5만 가능).해결 아이디어핵심 원리는 다음과 같습니다. 현재까지 만들 수 있는 합의 범위가 [1, answer − 1]이라고 가정

문제 개요두 개의 문자열 s1과 s2가 주어졌을 때, s2의 모든 문자를 포함하는 s1 내부의 가장 작은 부분 문자열(윈도우)을 찾아야 합니다.예를 들어 입력이 s1 = I am a student, s2 = mdn이라면 출력은 m a studen이 됩니다. 이 부분 문자열은 m, d, n 세 문자를 모두 포함하면서 길이가 가장 짧기 때문입니다.해결 접근 방식: 슬라이딩 윈도우 + 해시 카운팅이 문제는 슬라이딩 윈도우(Sliding Window) 기법과 문자 빈도수 카운팅을 조합하면 효율적으로 해결할 수 있습니다. 핵심 아이디어는 다

정수 N이 주어졌을 때, N 미만에 존재하는 모든 절단 가능 소수(Truncatable Prime)의 합을 구하는 문제를 살펴보겠습니다. 절단 가능 소수는 자릿수를 한쪽 방향에서부터 차례대로 제거해도 남은 수가 계속해서 소수로 유지되는 특별한 성질을 가진 소수입니다.절단 가능 소수의 정의왼쪽 절단 가능 소수(Left-truncatable prime): 맨 앞자리 숫자부터 한 자리씩 제거했을 때, 생성되는 모든 수가 소수인 경우오른쪽 절단 가능 소수(Right-truncatable prime): 맨 뒷자리 숫자부터 한 자리씩 제거했을

문제 소개중복된 값이 포함될 수도 있는 n개의 요소를 가진 배열 A가 주어졌다고 가정해 보겠습니다. 임의의 부분 집합 s에 대해 max(s)는 해당 집합의 최댓값, min(s)은 최솟값을 의미합니다. 우리가 구해야 할 것은 배열의 모든 부분 집합에 대해 max(s) − min(s)를 계산한 값들의 총합입니다.예를 들어 입력이 A = [1, 3, 4]라면 출력은 9가 됩니다.예시 검증[1, 3, 4]의 모든 부분 집합과 각각의 max(s) − min(s) 값은 다음과 같습니다.{1}, {3}, {4} : 각각 0{1, 3} : 3 −

문제 이해하기세 개의 정렬된 배열 A, B, C가 있다고 가정해 봅시다(각 배열의 크기는 서로 달라도 괜찮습니다). 각 배열에서 하나의 원소씩 선택해 만든 세 쌍 (A[i], B[j], C[k])에 대해, |max(A[i], B[j], C[k]) − min(A[i], B[j], C[k])|, 즉 최댓값과 최솟값의 차이가 가장 작아지는 경우를 찾아야 합니다.예를 들어 입력이 다음과 같다고 해보겠습니다.A = [2, 5, 6, 9, 11], B = [7, 10, 16], C = [3, 4, 7, 7]이때 A[i] = 6, B[j] =

정수로 이루어진 배열 A가 주어졌을 때, 어떤 값 sum[i]를 기준으로 배열 전체를 합이 sum[i]와 동일한 연속된 부분 배열들로 나눌 수 있다면, 그러한 조건을 만족하는 모든 합계 값을 찾아야 합니다. 만약 어떤 합으로도 배열을 균등하게 나눌 수 없다면 -1을 반환합니다.문제 예시예를 들어 입력이 A = [2, 4, 2, 2, 2, 4, 2, 6]이라면 출력은 [6, 8, 12]가 됩니다. 이 배열은 합이 6, 8, 12인 부분 배열들로 각각 나눌 수 있기 때문입니다.합이 6일 때: {2, 4}, {2, 2, 2}, {4, 2

문제 개요 N×M 크기의 2차원 행렬 A가 하나의 3D(입체) 도형을 나타낸다고 가정해 보겠습니다. 이때 좌표 (i, j) 위치에 있는 기둥의 높이는 A[i][j] 값입니다. 우리가 구해야 하는 것은 이 입체 도형의 전체 표면적입니다. 예를 들어 입력이 N = 3, M = 3, A = [[1, 4, 5], [3, 3, 4], [1, 3, 5]]라고 한다면, 출력 결과는 72가 됩니다. 해결 접근 방식 표면적을 계산하는 핵심 아이디어는 다음 세 가지로 정리할 수 있습니다. 윗면과 아랫면: 모든 격자 칸에는 윗면과 바닥면이 하나씩 존

문제 설명 문자열 s가 24시간 형식(HH:MM)의 시간을 나타낸다고 가정해 보겠습니다. 이때 HH(시)는 0~23, MM(분)은 0~59 범위에 속합니다. 우리가 찾아야 하는 것은 문자열로 읽었을 때 회문(palindrome), 즉 거꾸로 읽어도 동일한 시간 중 현재 시간 이후로 가장 가까운 시간입니다. 만약 더 이상 존재하지 않는다면 -1을 반환합니다. 예를 들어 입력이 22:22라면 출력은 23:32가 됩니다. 23:32는 거꾸로 읽어도 23:32이므로 회문에 해당하기 때문입니다. 풀이 접근 방법 핵심 아이디어는 매우 간단합

길이가 p이고 너비가 q인 보드가 하나 있다고 가정해 봅시다. 이 보드를 총 p×q개의 정사각형 조각으로 잘라야 하며, 이때 전체 자르기 비용을 최소화하는 것이 목표입니다. 각 가로·세로 선을 자를 때 드는 비용은 미리 주어집니다.예를 들어 입력이 다음과 같다면,X_slice = [3, 2, 4, 2, 5], Y_slice = [5, 2, 3]출력 결과는 65가 됩니다.접근 방식: 그리디(Greedy) 알고리즘핵심 아이디어는 간단합니다. 비용이 큰 컷부터 먼저 실행하는 것입니다.어떤 선을 자를 때 그 비용은 현재까지 만들어진 직교

문제 개요서로 다른 양의 정수로 이루어진 배열 A가 있다고 가정해 봅시다. 두 명의 플레이어 P와 Q가 이 배열로 게임을 진행합니다. 각 턴마다 플레이어는 배열에서 두 수 a와 b를 골라 그 차이의 절댓값 |a − b|를 확인하고, 해당 값이 배열에 존재하지 않으면 새로운 숫자로 추가합니다. 더 이상 새로운 숫자를 추가할 수 없게 된 플레이어가 패배합니다. 플레이어 P가 항상 먼저 시작한다고 할 때, 최종 승자가 누구인지 구하는 것이 목표입니다.예를 들어 입력이 A = [8, 9, 10]이라면 출력은 P가 됩니다.해결 전략: 최대공