문제 개요총 numCourses개의 강좌를 수강해야 하며, 각 강좌에는 0부터 numCourses-1까지 번호가 붙어 있다고 가정해 봅시다. 일부 강좌는 선수 과목이 있을 수 있습니다. 예를 들어 강좌 0을 듣기 위해서는 먼저 강좌 1을 이수해야 한다는 조건은 [0, 1] 쌍으로 표현됩니다. 이때 전체 강좌 수와 선수 과목 쌍의 목록이 주어졌을 때, 모든 강좌를 이수하는 것이 가능한지 판별해야 합니다.예를 들어 입력이 numCourses = 2, prerequisites = [[1, 0]]이라면 결과는 true입니다. 총 2개의 강

문제 소개총 n개의 강좌가 있으며, 각 강좌는 0부터 n-1까지 번호가 매겨져 있다고 가정해 봅시다. 일부 강좌는 선수 과목(먼저 이수해야 하는 과목)이 존재할 수 있습니다. 전체 강좌 수와 선수 과목 쌍의 목록이 주어졌을 때, 모든 강좌를 이수하기 위한 수강 순서를 찾아야 합니다.정답이 되는 순서는 여러 개 존재할 수 있으며, 이 경우 그중 하나만 반환하면 됩니다. 만약 모든 강좌를 이수하는 것이 불가능하다면 빈 배열을 반환해야 합니다.예시입력이 numCourses = 2, prerequisites = [[1, 0]]이라면 결과는

중첩 리스트 평탄화 문제란? 정수들이 중첩된 형태의 리스트가 주어졌다고 가정해 보겠습니다. 각 요소는 정수이거나 리스트일 수 있으며, 그 리스트 안의 요소 역시 정수 또는 또 다른 리스트일 수 있습니다. 우리의 목표는 이러한 중첩 구조를 순회할 수 있는 반복자(iterator)를 구현해 모든 정수를 일렬로 펼쳐내는 것입니다. 예를 들어 입력이 [[1, 1], 2, [1, 1]]이라면, 출력은 [1, 1, 2, 1, 1]이 되어야 합니다. 해결 접근 방법 다음 단계에 따라 문제를 해결할 수 있습니다. 초기화(__init__): 중

이번 글에서는 평균 O(1) 시간 복잡도로 다음 세 가지 연산을 모두 지원하는 자료구조를 파이썬으로 구현해 보겠습니다.insert(val) – 집합에 값 val이 존재하지 않으면 삽입합니다.remove(val) – 집합에 값 val이 존재하면 제거합니다.getRandom() – 현재 집합에 있는 요소 중 하나를 무작위로 반환합니다. 이때 모든 요소가 동일한 확률로 선택되어야 합니다.문제 접근 방법단순히 배열만 사용하면 삭제 시 요소를 찾는 데 O(n)이 걸리고, 딕셔너리만 사용하면 랜덤 추출이 어렵습니다. 따라서 두 자료구조를 조합

문제 개요 고장 난 계산기가 하나 있다고 가정해 봅시다. 이 계산기는 화면에 표시된 숫자에 대해 단 두 가지 연산만 수행할 수 있습니다. 곱하기 2(Double) — 화면의 숫자를 2배로 만듭니다. 1 감소(Decrement) — 화면의 숫자에서 1을 뺍니다. 처음에 계산기에는 숫자 X가 표시되어 있습니다. 목표는 화면에 숫자 Y를 표시하기 위해 필요한 최소 연산 횟수를 구하는 것입니다. 예를 들어 입력이 X = 5, Y = 8이라면 정답은 2입니다. 먼저 1을 빼서 4를 만든 뒤, 2배를 하면 8이 되기 때문입니다. 접근 방식

소셜 그룹에 N명의 사람이 있으며, 각 사람은 0부터 N-1까지의 고유한 정수 ID를 가지고 있다고 가정해 봅시다. 우리에게는 로그 목록이 주어지는데, 각 로그 logs[i] = [time, id_A, id_B]는 음이 아닌 정수 타임스탬프와 서로 다른 두 사람의 ID를 담고 있습니다. 각 로그는 두 사람이 친구가 된 시점을 나타내며, A가 B의 친구라면 B도 A의 친구입니다.여기서 A가 B와 아는 사이라는 것은 A가 B의 직접적인 친구이거나, A가 B와 아는 사이인 누군가의 친구인 경우를 의미합니다. 즉, 친구 관계는 전이적으로

문제 소개 모든 노드가 두 개의 자식을 가지는 무한한 이진 트리가 있다고 가정해 보겠습니다. 각 노드에는 행(row) 순서대로 번호가 매겨지는데, 홀수 번째 행(1행, 3행, 5행, ...)은 왼쪽에서 오른쪽으로, 짝수 번째 행(2행, 4행, 6행, ...)은 오른쪽에서 왼쪽으로 레이블이 붙습니다. 즉, 레이블이 지그재그 형태로 배치되는 것이죠. 이때 트리의 구조는 다음과 같이 그려집니다. 이렇게 구성된 트리에서 특정 노드의 레이블이 주어졌을 때, 루트 노드부터 해당 레이블을 가진 노드까지의 경로에 있는 레이블들을 순서대로 구하는

문제 개요이진 트리(binary tree)의 루트 노드가 주어졌을 때, 해당 트리에 속한 모든 서브트리 중에서 평균값이 가장 큰 서브트리의 평균을 구하는 문제입니다.예를 들어 아래와 같은 트리가 있다고 가정해 보겠습니다.이 경우 출력 결과는 6입니다. 그 이유는 다음과 같습니다.노드 5를 루트로 하는 서브트리: (5 + 6 + 1) / 3 = 4노드 6만 있는 서브트리: 6 / 1 = 6노드 1만 있는 서브트리: 1 / 1 = 1세 값 중 가장 큰 값인 6이 정답이 됩니다.풀이 접근 방식이 문제는 후위 순회(postorder tra

루트가 있는 이진 트리가 주어졌을 때, 가장 깊은 리프(잎) 노드들의 최소 공통 조상(Lowest Common Ancestor, LCA)을 반환하는 문제입니다. 문제를 풀기 전에 다음 세 가지 정의를 먼저 이해해야 합니다.기본 개념 정리이진 트리에서 리프 노드란 자식 노드를 하나도 가지지 않는 노드를 의미합니다.루트 노드의 깊이는 0이며, 어떤 노드의 깊이가 d라면 그 노드의 자식 노드들은 모두 깊이 d+1을 가집니다.노드 집합 S의 최소 공통 조상이란, S에 속한 모든 노드를 자신의 서브트리 안에 포함하면서 깊이가 가장 큰(가장

노드에 0부터 n-1까지 라벨이 붙은 방향 그래프(directed graph)가 있다고 가정해 보겠습니다. 이 그래프의 각 간선은 빨간색 또는 파란색으로 칠해져 있으며, 자기 자신을 향하는 간선(self-edge)이나 두 노드 사이의 평행 간선(parallel edge)도 존재할 수 있습니다. red_edges의 각 [i, j]는 노드 i에서 노드 j로 향하는 빨간색 방향 간선을 의미하고, 마찬가지로 blue_edges의 각 [i, j]는 노드 i에서 노드 j로 향하는 파란색 방향 간선을 의미합니다.우리가 구해야 할 것은 길이가 n

문제 설명 1부터 N까지 번호가 매겨진 N개의 도시가 있다고 가정해 봅시다. connections 배열에는 여러 개의 연결 정보가 담겨 있으며, 각 연결은 [city1, city2, cost] 형태로 city1과 city2를 직접 연결하는 데 드는 비용을 나타냅니다. 목표는 모든 도시 쌍 사이에 경로(길이 1인 직접 연결도 포함)가 존재하도록 도시들을 잇는 것이며, 이때 총 비용은 선택한 연결들의 비용 합계가 됩니다. 모든 도시를 연결하는 것이 불가능하다면 -1을 반환해야 합니다. 예를 들어 그래프가 다음과 같다고 해보겠습니다.

정수 배열 nums가 주어졌다고 가정해 봅시다. 여기서 한 번의 이동(move) 연산이란 임의의 요소 하나를 선택하여 그 값을 1만큼 감소시키는 것을 의미합니다.배열 A가 다음 두 조건 중 하나를 만족하면 지그재그(zigzag) 배열이라고 부릅니다.모든 짝수 인덱스의 요소가 양옆의 인접 요소보다 큰 경우, 즉 A[0] > A[1] < A[2] > A[3] < A[4] > ... 와 같은 형태모든 홀수 인덱스의 요소가 양옆의 인접 요소보다 큰 경우, 즉 A[0] < A[1] > A[2] <

문제 소개 두 명의 플레이어가 이진 트리 위에서 턴제 게임을 진행한다고 가정해 보겠습니다. 트리의 루트 노드와 전체 노드 개수 n이 주어지며, n은 항상 홀수입니다. 또한 각 노드는 1부터 n까지 서로 겹치지 않는 고유한 값을 가집니다. 게임은 다음 규칙에 따라 진행됩니다. 첫 번째 플레이어가 1 ≤ x ≤ n 범위의 값 x를 하나 정하고, 해당 노드를 빨간색으로 칠합니다. 두 번째 플레이어는 y ≠ x를 만족하는 값 y를 정하고, 해당 노드를 파란색으로 칠합니다. 이후 첫 번째 플레이어부터 번갈아 가며 턴을 진행합니다. 각 턴에

스냅샷 배열(Snapshot Array)이란?스냅샷 배열은 배열의 상태를 여러 시점별로 기록하고, 나중에 특정 시점(스냅샷)의 값을 다시 조회할 수 있는 자료구조입니다. 이 문제에서는 다음 네 가지 인터페이스를 구현해야 합니다.SnapshotArray(int length) — 주어진 길이만큼 배열 형태의 자료구조를 초기화합니다. 초기에는 모든 요소가 0입니다.set(index, val) — 주어진 인덱스의 요소를 val 값으로 설정합니다.snap() — 현재 배열 상태의 스냅샷을 찍고, snap_id(지금까지 snap()이 호출된

문제 개요 d개의 주사위가 있고, 각 주사위는 1부터 f까지의 숫자가 적힌 면을 가지고 있다고 가정해 보겠습니다. 이때 주사위를 굴려서 윗면에 나온 숫자들의 합이 목표값(target)과 일치하도록 만드는 경우의 수를 전체 경우의 수(f^d) 가운데서 구하고, 그 결과를 10^9 + 7로 나눈 나머지를 반환해야 합니다. 예를 들어 d = 2, f = 6, target = 7이 입력으로 주어진다면 출력은 6이 됩니다. 6면체 주사위 두 개를 던져 합이 7이 되는 조합은 1+6, 2+5, 3+4, 4+3, 5+2, 6+1로 총 6가지이기

두 가지 핵심 기능을 제공하는 파일 시스템을 설계해야 한다고 가정해 보겠습니다.createPath(path, value) — 새로운 경로를 생성하고 가능한 경우 해당 경로에 값을 연결한 뒤 True를 반환합니다. 경로가 이미 존재하거나 부모 경로가 존재하지 않으면 False를 반환합니다.get(path) — 주어진 경로에 연결된 값을 조회하여 반환하며, 경로가 존재하지 않으면 -1을 반환합니다.경로 형식 이해하기경로는 슬래시(/) 뒤에 하나 이상의 영문 소문자가 이어지는 문자열이 하나 이상 연결된 형태입니다. 예를 들어 /progr

문제 개요문자열 s가 주어지면, 이 문자열의 부분 문자열에 대해 여러 개의 쿼리를 수행해야 합니다. 각 쿼리 queries[i]는 [left, right, k]의 세 요소로 구성되며, 부분 문자열 s[left] ~ s[right]를 자유롭게 재배열한 뒤, 최대 k개의 문자를 원하는 소문자 영어 알파벳으로 교체할 수 있습니다. 이러한 연산을 거친 후 해당 부분 문자열이 회문(palindrome)이 될 수 있다면 쿼리의 결과는 true, 그렇지 않다면 false입니다. 모든 쿼리의 결과를 순서대로 담은 배열 answer[]를 구하는 것

문제 개요 문자열 s가 주어졌을 때, s에 등장한 순서 그대로 모든 단어를 세로 방향으로 읽어야 합니다. 결과는 문자열 리스트로 반환하며, 각 행의 길이를 맞추기 위해 필요한 만큼 공백으로 채웁니다(단, 뒤쪽 공백은 허용되지 않습니다). 각 단어는 하나의 열에만 배치되고, 하나의 열에는 하나의 단어만 존재합니다. 예를 들어 입력 문자열이 HOW ARE YOU라면, 각 단어의 첫 번째 글자(H, A, Y), 두 번째 글자(O, R, O), 세 번째 글자(W, E, U)를 차례로 읽어 출력은 [HAY, ORO, WEU]가 됩니다. 해결

문제 개요정수로 이루어진 비어 있지 않은 배열이 하나 주어집니다. 배열의 모든 원소는 정확히 세 번씩 등장하지만, 단 하나의 원소만 딱 한 번 등장합니다. 이때 그 유일한 원소를 찾아야 합니다. 예를 들어 배열이 [2,2,3,2]라면 출력 결과는 3이 됩니다.해결 접근 방식이 문제는 비트 연산과 모듈로(나머지) 계산을 활용하면 효율적으로 해결할 수 있습니다. 각 숫자를 이진수로 표현했을 때 비트별로 1이 나타난 횟수를 누적하고, 그 값을 3으로 나눈 나머지를 구하면 세 번 등장한 숫자들의 기여는 모두 사라지고 한 번만 등장한 숫자의

문자열이 하나 주어졌을 때, 해당 입력이 유효한 IPv4 주소인지, IPv6 주소인지, 아니면 둘 다 아닌지 판별해야 합니다. 이 글에서는 문제의 조건을 정리하고, 파이썬으로 이를 해결하는 알고리즘과 예제 코드를 소개합니다.IPv4와 IPv6 주소 형식 이해하기IPv4 주소 형식IPv4 주소는 점으로 구분되는 십진수 표기법(dotted-decimal notation)으로 표현됩니다. 즉, 0부터 255 범위의 십진수 네 개가 점(".")으로 구분된 형태입니다. 예를 들어 192.168.254.1은 유효한 IPv4