n차 정사각 행렬이 주어지고, 행렬의 모든 원소는 서로 다르다고 가정해 봅시다. 이때 우리가 찾아야 할 것은 경로를 따라 이동할 때마다 값이 정확히 1씩 증가하는 조건을 만족하는 최장 경로입니다. 한 칸에서는 왼쪽, 오른쪽, 위, 아래 네 방향으로만 이동할 수 있습니다.예를 들어 다음과 같은 행렬이 있다고 가정하겠습니다.129538467이 경우 출력 결과는 4입니다. 가장 긴 경로는 6→7→8→9이기 때문입니다.문제 해결 접근 방식이 문제를 해결하기 위한 핵심 아이디어는 다음과 같습니다.모든 셀에 대해 해

이번 글에서는 n개의 요소를 가진 배열에서 정확히 k개의 홀수를 포함하는 가장 긴 부분 배열(sub-array)의 길이를 찾는 방법을 알아보겠습니다.예를 들어 배열 A = [2, 3, 4, 11, 4, 12, 7]이고 k = 1이라면, 정답은 4가 됩니다. 이때 해당 부분 배열은 [4, 11, 4, 12]입니다.해결 접근 방식: 슬라이딩 윈도우(Sliding Window)이 문제는 슬라이딩 윈도우 기법을 사용하면 효율적으로 해결할 수 있습니다. 핵심 아이디어는 다음과 같습니다.max := 0, count := 0, start :=

정렬되지 않은 배열 A와 두 개의 숫자 x, y가 주어졌을 때, 배열 A 안에서 x와 y 사이의 최소 거리를 찾는 문제를 살펴보겠습니다. 배열에는 중복된 요소가 포함될 수도 있습니다.예를 들어, 배열이 A = [2, 5, 3, 5, 4, 4, 2, 3]이고 x = 3, y = 2라고 가정해 봅시다. 이 경우 3과 2 사이의 최소 거리는 1입니다.문제 해결 접근 방식이 문제는 다음 단계를 따라 해결할 수 있습니다.배열을 왼쪽에서 오른쪽으로 순회하다가 x 또는 y를 처음 발견하면 탐색을 멈추고, 해당 위치의 인덱스를 prev 변수에 저

문제 이해하기정수 n이 주어졌을 때, n변 볼록 다각형(convex polygon)의 대각선 개수를 구하는 문제입니다. 예를 들어 n = 5인 오각형이라면 대각선의 개수는 5개입니다.접근 방법n변 볼록 다각형에서 각 꼭짓점은 자기 자신과 양옆에 인접한 두 꼭짓점을 제외한 나머지 꼭짓점들과 연결되는 대각선을 그릴 수 있습니다. 따라서 한 꼭짓점에서 그릴 수 있는 대각선은 n - 3개입니다.n개의 꼭짓점이 있으므로 총 대각선 수는 n × (n - 3)이 되지만, 각 대각선은 양쪽 끝 꼭짓점에서 중복으로 계산되기 때문에 최종 공식은 다음

두 개의 정수 N과 M이 주어졌을 때, 아래의 두 가지 연산만을 사용하여 N에서 M까지 도달하는 데 필요한 최소 연산 횟수를 구하는 문제입니다.숫자 x에 2를 곱합니다 → x는 2*x가 됩니다.숫자 x에서 1을 뺍니다 → x는 x-1이 됩니다.예를 들어 N = 4, M = 6이라면 정답은 2입니다. 먼저 N에서 1을 빼면 3이 되고, 그 값에 2를 곱하면 6이 되기 때문입니다. 즉, 두 번의 연산만으로 목표에 도달할 수 있습니다.접근 방법: 문제를 거꾸로 생각하기이 문제는 방향을 뒤집으면 훨씬 간단하게 해결할 수 있습니다. N에서

문제 정의 금액 N이 주어지고, 가치가 각각 1, 10, 25인 세 종류의 동전을 무제한으로 보유하고 있다고 가정해 봅시다. 이때 정확히 N의 금액을 지불하기 위해 필요한 최소 동전 개수를 구하는 것이 목표입니다. 예를 들어 N이 14라면, 10짜리 동전 한 개와 1짜리 동전 네 개, 즉 총 5개의 동전으로 지불할 수 있습니다. 해결 접근 방식 이 문제는 그리디(Greedy) 알고리즘으로 효율적으로 해결할 수 있습니다. 핵심 아이디어는 가능한 한 큰 단위의 동전을 먼저 최대한 많이 사용하고, 남은 금액은 더 작은 단위의 동전으로

문제 개요배열이 등차수열의 요소들을 순서대로 담고 있고, 그중 한 개의 요소가 누락되어 있다고 가정해 보겠습니다. 이때 우리가 해야 할 일은 바로 그 누락된 요소를 찾아내는 것입니다.예를 들어 arr = [2, 4, 8, 10, 12, 14]라면 공차가 2인 등차수열에서 6이 빠져 있으므로, 정답은 6이 됩니다.접근 방법: 이진 탐색 활용요소를 하나씩 순회하는 선형 탐색 대신 이진 탐색(Binary Search)을 활용하면 O(log n)의 시간 복잡도로 문제를 효율적으로 해결할 수 있습니다. 알고리즘의 핵심 로직은 다음과 같습니다

N×N 크기의 정방행렬이 하나 주어졌다고 가정해 보겠습니다. 이때 해야 할 일은 행렬의 어느 한 열에서든 최대 차이(maximum difference)를 만들어 내는 두 요소의 쌍(pair)을 찾는 것입니다. 예를 들어 다음과 같은 3×3 행렬이 있다고 합시다. 123535967 이때 출력 결과는 8입니다. 0번째 열의 (1, 9) 쌍이 9 − 1 = 8이라는 차이를 만들어 내는데, 이것이 모든 열 중에서 가장 큰 차이이기 때문입니다. 접근 방법 핵심 아이디어는 매우 단순합니다. 각 열을 순회하면서 해당 열의 최댓값과 최솟

배열에 등비수열(기하수열)의 원소들이 순서대로 저장되어 있고, 그중 한 개의 원소가 누락되어 있다고 가정해 보겠습니다. 우리의 목표는 바로 이 누락된 원소를 찾아내는 것입니다. 예를 들어 배열이 arr = [1, 3, 27, 81]이라면 공비가 3인 등비수열에서 9가 빠져 있으므로, 출력 결과는 9가 되어야 합니다. 접근 방식: 이진 탐색 활용 이 문제는 이진 탐색(binary search)을 활용하면 O(log n)의 시간 복잡도로 효율적으로 해결할 수 있습니다. 처음부터 끝까지 모든 원소를 하나씩 확인하는 선형 탐색(O(n))

세 개의 정수 a, b, x가 주어졌을 때, ab 값에 가장 가까운 x의 배수를 구하는 문제입니다.예를 들어 a = 5, b = 4, x = 3이라면 결과는 624입니다. 54 = 625인데, 625에 가장 가까운 3의 배수가 624이기 때문입니다.해결 접근 방법이 문제는 간단한 수학적 접근으로 해결할 수 있습니다. 다음 단계를 순서대로 따르면 됩니다.먼저 목표값을 계산합니다: num := abnum을 x로 나눈 값의 내림(버림)을 구합니다: f := floor(num / x)왼쪽(작은 쪽) 후보와 오른쪽(큰 쪽) 후보를 각각 계산

문제 개요두 정수 N과 K가 주어졌을 때, 처음 N개의 자연수로 이루어진 순열 P 중에서 GCD(P[i], i) > 1 조건을 만족하는 원소가 정확히 K개가 되는 경우를 찾아야 합니다. 여기서 조건은 1 ≤ i ≤ N 범위의 모든 인덱스에 대해 검사합니다.예를 들어 N = 3, K = 1이라면 출력은 2, 1, 3이 됩니다. 이때 gcd(2, 1) = 1, gcd(1, 2) = 1, gcd(3, 3) = 3이므로 조건을 만족하는 원소는 마지막 하나뿐입니다.접근 방법이 문제는 간단한 아이디어로 해결할 수 있습니다.마지막 K개의

문제 정의숫자 n이 주어졌을 때, 이 숫자의 자릿수를 재배열하여 만들 수 있는 순열(permutation) 중에서 3으로는 나누어떨어지지만 6으로는 나누어떨어지지 않는 값을 찾아야 합니다. 만약 그런 값을 만들 수 없다면 -1을 반환합니다.예를 들어 n이 336이라면, 자릿수를 바꾼 363이 정답이 될 수 있습니다. 363은 각 자릿수의 합이 12이므로 3의 배수이고, 일의 자리가 3으로 홀수이기 때문에 6의 배수는 아닙니다.해결 아이디어어떤 수가 6으로 나누어떨어진다는 것은 그 수가 3과 2로 모두 나누어떨어진다는 뜻입니다. 즉,

문제 설명n개의 정수로 이루어진 배열 A가 있다고 가정해 봅시다. 우리는 배열 안에서 소수인 원소 K를 찾아야 하며, 가능한 모든 후보 K 중에서 A[i] mod K의 값이 최대가 되도록 해야 합니다. 만약 조건을 만족하는 수를 찾지 못하면 -1을 반환합니다.예를 들어, A = [2, 10, 15, 7, 6, 8, 13]일 때 출력은 13입니다. 배열에는 2, 7, 13이라는 세 개의 소수가 존재하며, 각 소수에 대한 나머지 연산의 최댓값은 다음과 같습니다.K = 2일 때: 15 mod 2 = 1K = 7일 때: 6 mod 7 =

문제 개요숫자 n이 주어졌을 때, 1부터 n 사이에 존재하는 모든 소수의 곱을 구하는 프로그램을 작성해야 합니다. 예를 들어 n = 7이라면 소수는 2, 3, 5, 7이고, 2 × 3 × 5 × 7 = 210이므로 결과값은 210이 됩니다.접근 방법: 에라토스테네스의 체주어진 범위 내의 모든 소수를 효율적으로 찾기 위해 에라토스테네스의 체(Sieve of Eratosthenes) 알고리즘을 활용합니다. 이 방법은 다음과 같은 단계로 진행됩니다.크기가 n+1인 불리언 배열을 생성하고 모든 요소를 true로 초기화합니다.2부터 √n까지

문자열이 하나 주어졌을 때, 그중 가장 먼저 반복되는 문자를 찾는 문제를 생각해 보겠습니다. 예를 들어 문자열이 Hello Friends라면, 첫 번째 반복 문자는 l입니다. l이 연달아 두 번 나타나기 때문입니다.이 문제는 해싱(hashing) 기법을 사용하면 효율적으로 해결할 수 있습니다. 해시 집합(hash set)을 하나 생성한 뒤, 문자열의 각 문자를 왼쪽부터 차례대로 검사합니다. 해당 문자가 아직 집합에 없다면 삽입하고, 이미 존재한다면 그 즉시 그 문자를 반환하면 됩니다.알고리즘 동작 원리해시 기반 탐색은 평균적으로 O

문자로 구성된 행렬 mat[][]가 있다고 가정해 보겠습니다. 이 행렬에는 세 종류의 문자가 등장합니다. Z는 좀비(zombie), P는 식물(plant), *는 아무것도 없는 빈 땅(bare land)을 의미합니다. 좀비는 자신과 인접한 칸에 있는 식물을 공격할 수 있으며, 우리의 목표는 좀비의 공격으로부터 안전한 식물 셀이 몇 개인지 구하는 것입니다. 예를 들어 다음과 같은 행렬이 주어졌다고 합시다. 이 행렬에서 좀비에게 공격받지 않는 안전한 식물은 단 2개뿐입니다. 문제 해결 접근 방법 풀이 자체는 매우 직관적입니다. 행렬을

문제 개요프로그래밍 연습 문제에서 자주 등장하는 유형 중 하나는 판매 가격과 이익률(또는 손실률)이 주어졌을 때 상품의 원가를 역으로 계산하는 것입니다. 예를 들어 어떤 물건을 1,020원에 팔아 20%의 이익을 남겼다면, 처음 몇 원에 사들였는지 구해야 하는 상황입니다.원가 계산 공식원가는 아래 수식을 사용하면 간단하게 구할 수 있습니다.이익이 발생한 경우:$$Cost\ Price=\frac{Sell\ Price∗100}{100+percentage\ profit}$$손실이 발생한 경우:$$Cost\ Price=\fra

두 개의 정수 P와 Q가 주어졌을 때, 다음 두 조건을 동시에 만족하는 가장 작은 정수 K를 구하는 문제입니다.K % P = 0 → K는 P의 배수Q % K = 0 → K는 Q의 약수만약 이러한 K가 존재하지 않으면 -1을 출력해야 합니다. 예를 들어 P = 2, Q = 8이라면 K = 2가 됩니다. 2 % 2 = 0이고, 8 % 2 = 0이기 때문입니다.접근 방법핵심 아이디어는 매우 간단합니다. 조건을 만족하는 K가 존재하려면 Q가 반드시 P로 나누어 떨어져야 합니다.K는 P의 배수이면서 동시에 Q의 약수여야 합니다. 만약 P의

이 글에서는 배열의 모든 요소에 대해 가장 가까운 더 큰 값을 찾는 방법을 살펴봅니다. 어떤 요소 x보다 크면서 배열 안에 실제로 존재하는 값이 있다면, 그 값이 해당 요소의 다음으로 큰 값(next greater value)이 됩니다. 만약 그런 값이 존재하지 않으면 -1을 반환합니다.예를 들어 배열이 [10, 5, 11, 6, 20, 12]라면, 각 요소의 다음으로 큰 값은 [11, 6, 12, 10, -1, 20]이 됩니다. 여기서 20은 배열 내에 자신보다 큰 값이 없으므로 -1이 출력됩니다.C++ STL의 set을 활용한

두 개의 정수 n과 m이 주어졌을 때, n에 가장 가까우면서 m으로 나누어 떨어지는 수를 찾는 문제를 생각해 볼 수 있습니다. 만약 조건을 만족하는 수가 여러 개라면 절댓값이 가장 큰 수를 선택해야 하며, n이 m으로 완전히 나누어 떨어지는 경우에는 n 자체를 그대로 반환하면 됩니다.예를 들어 n = 13, m = 4라고 한다면, 4의 배수 중 13에 가장 가까운 수는 12이므로 출력 결과는 12가 됩니다.해결 알고리즘이 문제는 다음 단계를 통해 간단하게 해결할 수 있습니다.몫 q := n / m 을 구하고, n1 := m × q