세 개의 연결 리스트가 주어졌을 때, 이 세 리스트에 모두 존재하는 공통 원소를 찾는 문제를 생각해 봅시다. 예를 들어 리스트가 [10, 12, 15, 20, 25], [10, 12, 13, 15], [10, 12, 15, 24, 25, 26]라면, 세 리스트에 공통으로 포함된 원소는 10, 12, 15입니다.이 문제는 해싱(Hashing) 기법을 활용하면 효율적으로 해결할 수 있습니다. 전체 풀이 과정은 다음과 같습니다.알고리즘 접근 방식빈 해시 테이블을 생성한 뒤, 첫 번째 리스트의 모든 원소를 순회하면서 해시 테이블에 삽입하고

정수 N이 주어졌을 때, 길이 N의 모든 이진 문자열 중 최소 3개의 연속된 1을 포함하는 문자열의 개수를 구하는 문제입니다. 예를 들어 n = 4라면 조건을 만족하는 문자열은 0111, 1110, 1111 세 가지이므로 출력값은 3이 됩니다.동적 계획법(Dynamic Programming)을 활용한 풀이이 문제는 동적 계획법을 사용하면 효율적으로 해결할 수 있습니다.DP(i, x)는 길이 i의 문자열 중에서, 위치 i+1부터 i+x까지 x개의 연속된 1을 가지는 문자열의 개수를 의미합니다. 이때 점화식은 다음과 같습니다.DP(i,

개요세 개의 정렬된 배열이 주어졌을 때, 이 배열들에 모두 존재하는 공통 요소를 효율적으로 찾는 방법을 알아보겠습니다. 예를 들어 다음과 같은 세 개의 배열이 있다고 가정해 보겠습니다.A1 = [10, 12, 15, 20, 25]A2 = [10, 12, 13, 15]A3 = [10, 12, 15, 24, 25, 26]이 경우 세 배열의 공통 요소는 10, 12, 15입니다.알고리즘 접근 방식배열이 모두 정렬되어 있기 때문에, 각 배열에 포인터를 하나씩 두고 동시에 순회하는 투 포인터(Three Pointer) 기법을 사용할 수 있습

문제 개요하나의 숫자 n이 주어졌을 때, 1부터 n 사이의 정수 중에서 각 자릿수가 오직 0과 1로만 구성된 숫자가 몇 개 있는지 찾는 것이 이번 문제의 목표입니다.예를 들어 n = 15라면, 조건을 만족하는 수는 1, 10, 11로 총 3개입니다. 반면 2부터 9까지의 수와 12~15 사이의 수들은 0과 1 이외의 자릿수를 포함하므로 제외됩니다.해결 접근 방식이 문제는 재귀 함수를 이용해 해결할 수 있습니다. 핵심 아이디어는 다음과 같습니다.현재 값 p에서 뒤에 0을 붙인 수(p × 10)와 뒤에 1을 붙인 수(p × 10 + 1

문제 개요 두 개의 정수 x와 n이 주어졌을 때, x의 32비트 이진 표현에서 길이가 n 이상인 첫 번째 연속된 1의 구간을 찾아 그 시작 위치를 반환하는 것이 목표입니다. 만약 조건을 만족하는 구간이 존재하지 않는다면 -1을 반환합니다. 예를 들어 x = 35, n = 2라고 하면 결과는 31이 됩니다. 35를 32비트 정수로 나타내면 다음과 같습니다. 00000000000000000000000000100011 맨 왼쪽 비트를 인덱스 0으로 볼 때, 길이가 2인 연속된 1은 인덱스 31에서 시작하므로 정답은 31입니다. 접근 방

정수 N이 주어졌을 때, 1 < x < N 범위 내에서 x와 x+1이 서로 같은 개수의 양의 약수를 가지는 정수 x의 개수를 구하는 문제입니다. 예를 들어 N = 3이라면 출력 결과는 1이 됩니다. 왜냐하면 1의 약수는 {1}, 2의 약수는 {1, 2}, 3의 약수는 {1, 3}으로, 여기서 조건을 만족하는 경우가 존재하기 때문입니다.이 문제를 해결하기 위해서는 먼저 N 이하의 모든 수에 대해 약수의 개수를 계산하여 배열에 저장합니다. 그다음 반복문을 실행하면서 x와 x+1이 동일한 개수의 양의 약수를 가지는 정수 x의

두 개의 이중 연결 리스트(doubly linked list)가 주어졌을 때, 두 리스트에 공통으로 존재하는 노드의 총 개수를 구하는 것이 이번 글의 목표입니다.예를 들어 첫 번째 리스트가 [15, 16, 10, 9, 7, 17]이고, 두 번째 리스트가 [15, 16, 40, 6, 9]라면, 값이 15, 16, 9인 노드 세 개가 양쪽에 모두 존재하므로 공통 노드의 개수는 3이 됩니다.접근 방법가장 직관적인 방법은 중첩 반복문(nested loop)을 사용하는 것입니다.바깥쪽 반복문으로 첫 번째 리스트의 각 노드를 순회합니다.안쪽

정수 X가 주어졌을 때, 0에서 출발하여 X에 도달하기 위해 필요한 최소 점프 횟수를 구하는 문제입니다. 첫 번째 점프의 길이는 반드시 1이며, 그 이후의 각 점프는 바로 앞 점프보다 정확히 1씩 길어집니다. 또한 매 점프마다 왼쪽 또는 오른쪽 어느 방향으로든 이동할 수 있습니다.예를 들어 X = 8이라면 답은 4가 됩니다. 다음과 같은 경로가 가능하기 때문입니다.0 → -1 → 1 → 4 → 8문제 해결의 핵심 아이디어이 문제를 잘 관찰해 보면 다음과 같은 규칙성을 발견할 수 있습니다.항상 오른쪽 방향으로만 점프했다면, n번의 점

문제 이해 노드가 여러 개 있는 이진 트리가 주어졌다고 가정해 봅시다. 우리의 목표는 두 노드 u와 v 사이의 거리를 구하는 것입니다. 여기서 거리란 두 노드를 연결하는 경로에 있는 간선(edge)의 수를 의미합니다. 예를 들어 트리가 아래와 같은 형태라고 할 때, (4, 6) 사이의 거리는 4, (5, 8) 사이의 거리는 5입니다. 접근 방식: LCA(최소 공통 조상) 활용 이 문제를 해결하는 핵심 아이디어는 LCA(Lowest Common Ancestor, 최소 공통 조상)를 이용하는 것입니다. 두 노드 사이의 유일한 경로는

문제 소개 자연수 n이 주어졌을 때, 이 수를 네 부분 (a, b, c, d)으로 나누되 a = c이면서 b = d를 만족하는 분할 방법이 몇 가지 있는지 구하는 문제입니다. 예를 들어 n = 20이라면 정답은 4가 됩니다. 실제로 가능한 조합은 다음과 같습니다. [1, 1, 9, 9] [2, 2, 8, 8] [3, 3, 7, 7] [4, 4, 6, 6] 접근 방식 네 부분의 합이 n이 되어야 하고 a = c, b = d이므로 식을 정리하면 다음과 같습니다. a + b + c + d = n → 2a + 2b = n → a + b

문제 소개 몇 개의 노드로 구성된 이진 트리가 있다고 가정해 보겠습니다. 이때 구해야 할 것은 루트(root) 노드에서 특정 노드 u까지의 거리, 즉 두 노드를 연결하는 경로의 길이입니다. 예를 들어 다음과 같은 이진 트리가 있다고 합시다. 위 트리에서 루트(1)와 노드 6 사이의 거리는 2입니다. 루트 → 3 → 6 순서로 두 개의 간선을 지나기 때문입니다. 마찬가지로 루트와 노드 8 사이의 거리는 3이 됩니다. 접근 방식 이 문제는 재귀(recursion) 기반 탐색으로 깔끔하게 해결할 수 있습니다. 핵심 아이디어는 다음과 같

숫자 n이 주어졌을 때, 1부터 n 사이에 존재하는 모든 소수의 곱을 구하는 문제입니다. 예를 들어 n = 7이라면 소수는 2, 3, 5, 7이므로 곱은 2 × 3 × 5 × 7 = 210이 됩니다.접근 방법범위 내의 모든 소수를 효율적으로 찾기 위해 에라토스테네스의 체(Sieve of Eratosthenes) 알고리즘을 사용합니다. 이 알고리즘은 다음과 같은 순서로 동작합니다.2부터 n까지의 모든 수를 일단 소수(true)로 표시합니다.가장 작은 소수인 2부터 시작하여, 각 소수의 배수들을 모두 소수가 아닌 것(false)으로 표

문제 개요0부터 n-1 사이의 정수로 이루어진 배열이 있다고 가정해 봅시다. 어떤 숫자든 여러 번 반복해서 나타날 수 있으며, 이때 추가 공간을 사용하지 않고 반복되는 숫자들을 모두 찾아야 합니다.예를 들어 n = 7이고 배열이 [5, 2, 3, 5, 1, 6, 2, 3, 4, 5]라면, 중복된 숫자는 5, 2, 3입니다.알고리즘 원리이 문제의 핵심은 배열의 모든 값이 0부터 n-1 범위 안에 있다는 점입니다. 덕분에 각 값 자체를 배열의 인덱스로 활용할 수 있으며, 별도의 방문 여부 배열이나 해시 테이블 없이도 각 숫자의 등장 여

정수 N이 주어졌을 때, 홀수 자리에 있는 숫자들의 합과 짝수 자리에 있는 숫자들의 합을 각각 구해야 합니다. 예를 들어 숫자가 153654라면 odd_sum(홀수 자리 합)은 9, even_sum(짝수 자리 합)은 15가 됩니다. 이 문제는 가장 오른쪽 자릿수부터 한 자리씩 추출하면서 해결할 수 있습니다. 원래 수의 자릿수 개수가 홀수라면 마지막 자릿수는 홀수 자리에, 짝수라면 짝수 자리에 놓입니다. 한 자리를 처리할 때마다 상태를 홀수에서 짝수로, 짝수에서 홀수로 뒤집어 주면 다음 자릿수가 어느 쪽 합에 더해질지 자연스럽게 결

크기가 n인 정렬된 배열이 있다고 가정해 봅시다. 이 배열에는 빈도(등장 횟수)가 n/2보다 크거나 같은 요소가 반드시 하나 존재합니다. 예를 들어 배열이 [3, 4, 5, 5, 5]라면, 5가 세 번 등장하므로 출력 결과는 5가 됩니다. 핵심 아이디어 이런 유형의 배열을 잘 관찰해 보면 매우 간단한 규칙을 발견할 수 있습니다. 정렬된 배열에서 n/2번 이상 등장하는 요소는 반드시 인덱스 n/2 위치에 존재한다는 것입니다. 그 이유는 다음과 같습니다. 어떤 값이 n개짜리 배열에서 최소 n/2번 등장하려면, 정렬된 상태에서 그 값들은

문제 정의세 개의 정렬된 배열 A, B, C가 있다고 가정해 봅시다. 각 배열에서 하나씩 요소를 선택했을 때, max(|A[i] – B[j]|, |B[j] – C[k]|, |C[k] – A[i]|) 값이 최소가 되도록 하는 조합을 찾는 것이 목표입니다.예를 들어 A = [1, 4, 10], B = [2, 15, 20], C = [10, 12]라고 하면, 출력 결과는 10, 15, 10입니다. 이 세 값은 각각 배열 A, B, C에서 가져온 요소입니다.접근 방법배열 A, B, C의 크기를 각각 p, q, r이라고 합시다. 세 배열이

문제 개요정수로 이루어진 배열이 주어졌을 때, (a, b)와 (c, d)처럼 두 쌍을 이루는 서로 다른 네 개의 정수를 찾아 a + b = c + d 조건을 만족하도록 하는 것이 목표입니다. 가능한 답이 여러 개라면 그중 하나만 출력하면 됩니다.예를 들어 배열이 A = [7, 5, 9, 3, 6, 4, 2]라고 한다면, (7, 3)과 (6, 4)와 같은 쌍을 찾을 수 있습니다. 실제로 7 + 3 = 10이고 6 + 4 = 10이므로 조건을 만족합니다.접근 방법: 해싱(Hashing) 기법이 문제는 해시 테이블(맵)을 활용하면 효율적

정수로 이루어진 배열 A가 있고 그 크기가 n이라고 가정해 봅시다. 우리의 목표는 O(n)보다 적은 시간 안에 배열에 포함된 모든 요소의 빈도(출현 횟수)를 구하는 것입니다. 단, 요소들의 값은 특정 값 M 이하로 제한되어 있다는 전제 조건이 붙습니다.이 문제는 일반적인 해시맵이나 선형 순회 방식으로도 풀 수 있지만, 배열이 이미 정렬되어 있다면 더 효율적인 방법을 사용할 수 있습니다. 핵심 아이디어는 이진 탐색(binary search)에서 착안한 분할 정복(divide and conquer) 기법입니다.알고리즘 접근 방식배열이

두 수의 최대공약수(GCD)를 구하는 문제 중에는 한쪽 숫자가 비정상적으로 큰 경우가 있습니다. 특히 aⁿ 형태의 값은 a와 n이 각각 최대 10⁹까지 커질 수 있기 때문에, long을 포함한 일반적인 정수 자료형으로는 저장조차 할 수 없습니다.예를 들어 a = 10248585, n = 1000000, c = 12564라면 GCD(aⁿ, c)의 결과는 9입니다. 그렇다면 실제로 aⁿ을 계산하지 않고도 이 값을 어떻게 구할 수 있을까요?핵심 아이디어: 모듈러 지수 연산aⁿ이 너무 크기 때문에 유클리드 호제법을 곧바로 적용할 수 없습니

문자열 s와 문자열 배열 A가 주어졌을 때, 배열 안에 현재 문자열과 길이는 같으면서 정확히 한 글자만 다른 문자열이 존재하는지 판별하는 문제입니다.예를 들어 문자열이 banana이고 배열이 [bana, orange, banaba, banapy]라고 가정해 보겠습니다. 이때 결과는 true입니다. 배열 속 banaba는 banana과 길이가 같고 n 위치의 한 글자(b vs n)만 다르기 때문입니다.해결 접근 방법이 문제는 비교적 단순한 완전 탐색(brute force) 방식으로 해결할 수 있습니다. 핵심 단계는 다음과 같습니다.배