정수 배열에 포함된 모든 0을 배열의 끝으로 이동해야 하는 경우 MoveZeros 메서드를 활용할 수 있습니다. 핵심 아이디어는 배열을 한 번만 순회하면서 0이 아닌 요소들을 배열 앞쪽으로 차례대로 옮긴 뒤, 나머지 빈자리를 모두 0으로 채우는 것입니다.알고리즘 동작 원리배열이 null이거나 길이가 0인 경우에는 별도의 처리 없이 즉시 반환합니다.배열을 순회하면서 0이 아닌 요소를 만나면 count 위치에 해당 값을 저장하고 count를 하나씩 증가시킵니다.순회가 끝난 후 count 인덱스부터 배열 끝까지의 모든 요소를 0으로 채웁

두 문자열 X와 Y에서 X의 각 문자가 다른 문자로 치환되어 Y가 될 수 있고, 그 반대도 가능하다면 이 두 문자열을 동형(isomorphic)이라고 합니다. 예를 들어 ACAB와 XCXY를 살펴보겠습니다. 모든 문자 치환 과정에서는 문자의 순서가 유지되어야 하며, 서로 다른 두 문자가 같은 문자에 매핑될 수는 없습니다. 단, 한 문자가 자기 자신에게 매핑되는 것은 허용됩니다.예제 1입력 − s = egg, t = add출력 − true예제 2입력 − s = foo, t = bar출력 − false위 예제에서 egg와 add는 e→

개요문자열 알고리즘 문제 중 가장 대표적인 유형 중 하나가 바로 중복 문자가 없는 가장 긴 부분 문자열 문제입니다. 이 문제는 주어진 문자열에서 같은 문자가 반복되지 않는 가장 긴 연속 부분 문자열의 길이를 구하는 것이 목표입니다.이 문제는 슬라이딩 윈도우(Sliding Window) 기법을 사용하면 O(N)의 시간 복잡도로 효율적으로 해결할 수 있습니다. 두 개의 포인터 i와 j를 활용하며, 처음에는 두 포인터 모두 문자열의 같은 위치를 가리킵니다. 문자열을 순회하면서 문자를 리스트에 추가하고, 중복 문자가 발견되면 윈도우 왼쪽

C#에서 숫자 배열에 포함된 가장 긴 연속 증가 부분 수열(Longest Continuous Increasing Subsequence)의 길이를 구하는 방법을 알아보겠습니다.알고리즘 개요LongestIncreaingSubsequence 메서드는 배열 안에서 연속된 값들이 증가하는 구간 중 가장 긴 구간의 길이를 정수로 반환합니다. 메서드 내부의 for 루프가 배열을 순차적으로 순회하면서 숫자들의 흐름을 추적하고, 최종 결과는 Math.Max를 통해 계산됩니다.모든 요소를 정확히 한 번씩만 방문하므로 시간 복잡도는 O(N)입니다.별도

피보나치 수열은 0 또는 1로 시작하여 그다음 1이 이어지고, 이후의 각 숫자(피보나치 수)가 바로 앞의 두 숫자를 더한 값이 되는 규칙에 따라 진행되는 수열입니다.탑다운(Top-Down) 접근 방식은 하나의 큰 문제를 더 작고 이해하기 쉬운 단위로 분해하는 데 초점을 맞춥니다. 재귀 호출을 통해 문제를 쪼개어 해결하고, 이미 계산된 결과는 배열(메모이제이션)에 저장해 두었다가 다시 활용함으로써 중복 계산을 제거할 수 있습니다.이 방식은 결과를 저장하기 위해 입력 크기와 같은 크기의 추가 배열 메모리를 생성하므로, 공간 복잡도는 O

피보나치 수열은 0 또는 1로 시작하고 그다음에 1이 이어지며, 이후에는 각 숫자(피보나치 수)가 바로 앞의 두 숫자의 합과 같아진다는 규칙에 따라 전개되는 수열입니다.바텀업(Bottom-Up, 상향식) 접근 방식은 동적 계획법(Dynamic Programming)의 대표적인 기법으로, 가장 작고 기본적인 하위 문제부터 먼저 해결한 뒤, 그 결과를 차곡차곡 쌓아 올려 최종적으로 완전한 해답을 도출하는 방식입니다. 재귀 호출을 사용하지 않기 때문에 스택 오버플로우 걱정 없이 안정적으로 동작합니다.복잡도 분석시간 복잡도 — O(N):

MinimumStepstoOneTopdownApproach는 하향식(Top-down) 동적 계획법 기법으로, 정수 n과 정수 배열(dp 배열)을 입력으로 받습니다. 이 문제는 주어진 수 n을 다음 세 가지 연산만 사용하여 1로 만들 때 필요한 최소 연산 횟수를 구하는 것입니다. n이 3으로 나누어떨어지면 3으로 나눕니다. n이 2로 나누어떨어지면 2로 나눕니다. 언제든 가능한 연산으로, n에서 1을 뺍니다. 예를 들어 n이 10이라면 10 → 9 → 3 → 1 순서로 진행되며, 총 3단계가 필요합니다. 알고리즘 동작 과정 초기

C#에서 동적 계획법(Dynamic Programming)의 상향식(Bottom-up) 접근 방식을 활용하면 1까지의 최소 단계(Minimum Steps to One) 문제를 효율적으로 해결할 수 있습니다. 이 문제는 주어진 정수 n을 1로 만들기 위해 필요한 최소 연산 횟수를 구하는 것으로, 사용할 수 있는 연산은 다음 세 가지입니다.n에서 1을 뺀다n이 2로 나누어떨어질 경우 2로 나눈다n이 3으로 나누어떨어질 경우 3으로 나눈다상향식(Bottom-up) 접근 방식의 동작 원리상향식 접근 방식은 재귀 호출 없이 반복문을 사용하여

CoinChangeTopDownApproach 메서드는 총 4개의 매개변수를 받습니다. n은 만들어야 할 금액(amount)을 의미하고, coins 배열에는 해당 금액을 계산하는 데 사용할 수 있는 동전들의 종류가 담겨 있습니다. t는 동전의 총 개수이며, dp 배열은 한 번 계산된 값들을 저장하여 중복 연산을 방지하는 역할을 합니다.동작 흐름은 다음과 같습니다. 먼저 금액이 0이면 더 이상 동전이 필요 없으므로 0을 반환합니다. 그다음 dp 배열에 이미 계산된 값이 있다면 재귀 호출 없이 즉시 해당 값을 반환하여 성능을 높입니다.

동전 교환 문제란? 동전 교환(Coin Change) 문제는 주어진 금액을 만들기 위해 필요한 최소 동전 개수를 구하는 대표적인 동적 계획법(Dynamic Programming) 문제입니다. 이 글에서는 상향식(Bottom-Up) 접근 방식을 활용하여 C#으로 이 문제를 해결하는 방법을 알아보겠습니다. 상향식(Bottom-Up) 접근 방식의 동작 원리 CoinChangeBottomUpApproach 메서드는 다음과 같이 3개의 매개변수를 입력받습니다. n : 만들어야 할 목표 금액 coins : 사용 가능한 동전 종류가 담긴 배열

재귀 호출 없이 반복(Iterative) 방식으로 이진 트리가 좌우 대칭인지 판별하려면 두 개의 큐(Queue)를 활용하는 것이 핵심입니다. 한 큐에는 왼쪽 자식 노드를, 다른 큐에는 오른쪽 자식 노드를 저장한 뒤, 두 큐에서 노드를 꺼내며 짝지어 비교하는 구조입니다.동작 원리트리가 비어 있다면(null) 루트 노드를 기준으로 하는 수직 축에 대해 항상 대칭이라고 볼 수 있으므로 true를 반환합니다. 트리가 존재한다면 아래 순서대로 검사를 진행합니다.루트 노드가 null이면 즉시 true를 반환합니다.두 개의 큐를 생성하고, 첫

트리가 대칭(symmetric)이라는 것은 트리가 자기 자신의 거울상(mirror image)과 동일한 구조를 가진다는 의미입니다. 재귀적 접근 방식을 사용하면 이러한 대칭 여부를 효율적으로 판별할 수 있습니다.재귀 방식의 기본 원리재귀를 이용해 트리의 대칭 여부를 확인하는 과정은 다음과 같습니다.먼저 트리가 null인지 검사합니다. 트리가 null이면 대칭으로 간주하고 true를 반환합니다.트리가 null이 아니라면 isSymmetricMirror 메서드를 호출합니다.isSymmetricMirror 메서드의 동작 방식isSymme

개요이진 탐색 트리(Binary Search Tree)를 반전(invert)한다는 것은 트리의 모든 노드에 대해 왼쪽 자식과 오른쪽 자식의 위치를 서로 바꿔, 원본 트리의 거울상(mirror image)을 만드는 것을 의미합니다.이 작업은 재귀(Recursion)를 활용하면 매우 간결하게 구현할 수 있습니다. 동작 순서는 다음과 같습니다.InvertABinarySearchTree 메서드를 호출하며 노드를 매개변수로 전달합니다.노드가 null이면 그대로 null을 반환합니다. 이것이 재귀 호출의 종료 조건(base case)입니다.노

이진 탐색 트리(Binary Search Tree, BST)는 모든 왼쪽 자식 노드가 부모 노드보다 작고, 모든 오른쪽 자식 노드가 부모 노드보다 큰 값을 가지는 트리 구조입니다. 이 글에서는 C#의 재귀(Recursion)를 활용하여 주어진 이진 트리가 유효한 이진 탐색 트리인지 확인하는 방법을 알아보겠습니다.검증 알고리즘의 핵심 원리유효성 검사는 다음과 같은 순서로 진행됩니다.먼저 현재 노드에 값이 존재하는지 확인합니다. 노드가 null이라면 더 이상 검사할 대상이 없으므로 유효한 이진 탐색 트리로 간주하고 true를 반환합니다

이진 트리에서 루트 노드부터 리프 노드까지 이어지는 경로를 따라 노드 값들을 모두 더했을 때, 그 합이 목표값과 정확히 일치하는 경로가 존재하는지 확인하는 것은 자주 등장하는 대표적인 트리 탐색 문제입니다. C#에서는 재귀(Recursion)를 활용하면 간결하고 효율적으로 해결할 수 있습니다.동작 원리HasPathSum 메서드는 두 개의 매개변수를 받습니다. 하나는 트리의 노드이고, 다른 하나는 찾고자 하는 합(sum)입니다. 먼저 해당 노드가 null인지 검사하여, null이라면 false를 반환합니다. 노드가 null이 아니라면

배열에 포함된 0, 1, 2를 추가 메모리 공간 없이 한 번의 순회로 정렬해야 하는 경우가 자주 있습니다. 이 문제는 유명한 네덜란드 국기(Dutch National Flag) 알고리즘을 사용하면 효율적으로 해결할 수 있습니다. 핵심 아이디어는 세 개의 포인터를 활용하여 배열을 세 개의 영역으로 나누는 것입니다.알고리즘 동작 원리low, mid, high라는 세 개의 포인터를 사용합니다. low와 mid는 배열의 시작 지점에서, high는 배열의 마지막 요소를 가리키도록 초기화합니다.arr[mid] == 0인 경우: arr[mid]

개요배열에 포함된 0과 1을 별도의 배열 같은 추가 메모리 공간 없이 정렬하려면 투 포인터(Two Pointers) 기법을 활용할 수 있습니다. 이 방법은 원본 배열 자체를 제자리(in-place)에서 수정하기 때문에 공간 복잡도가 O(1)로 매우 효율적입니다.알고리즘 동작 방식두 개의 포인터 low와 high를 선언합니다. low 포인터는 배열의 시작 위치를 가리키고, high 포인터는 주어진 배열의 끝 위치를 가리킵니다.arr[low]가 0이면 교환(swap)이 필요하지 않습니다.arr[low]가 1이면 교환이 필요합니다. 이때

배열 회전 문제란?배열과 숫자 k가 주어졌을 때, 배열을 k번 회전하는 것이 이 문제의 목표입니다. 예를 들어 k가 3으로 주어지면 배열을 세 번 회전해야 합니다.가장 효율적인 해결 방법은 reverse(뒤집기) 함수를 활용하는 것입니다. 이 함수는 배열과 시작 인덱스(start), 끝 인덱스(end)를 매개변수로 받아 해당 구간의 요소들을 서로 교환하며 뒤집습니다.해결 접근 방식총 세 번의 뒤집기를 통해 원하는 결과를 얻을 수 있습니다.1단계: 전체 배열(0부터 배열 끝까지)을 대상으로 reverse 메서드를 호출합니다.2단계:

배열이 이미 정렬되어 있다면, 투 포인터(Two Pointers) 기법을 활용하여 중복을 효율적으로 제거할 수 있습니다.알고리즘 동작 원리두 개의 포인터 i와 j를 사용합니다. 여기서 i는 느린 포인터(slow-runner), j는 빠른 포인터(fast-runner) 역할을 합니다.nums[i]와 nums[j]가 같은 동안에는 j를 계속 증가시켜 중복 값을 건너뜁니다.nums[j] != nums[i]인 지점을 만나면 중복 구간이 끝난 것이므로, 해당 값을 nums[i + 1]에 복사합니다. 그런 다음 i를 증가시키고, j가 배열의

개요배열이 이미 정렬되어 있다면 두 개의 포인터(투 포인터) 기법을 활용해 효율적으로 중복을 제거할 수 있습니다. 느린 포인터 i와 빠른 포인터 j를 두고, nums[i] == nums[j]인 동안에는 j를 계속 증가시켜 중복된 값을 건너뜁니다.그러다가 nums[j] != nums[i]인 지점을 만나면 중복 구간이 끝난 것이므로, 해당 값을 nums[i + 1]에 복사합니다. 이후 i를 하나 증가시키고, j가 배열의 끝에 도달할 때까지 같은 과정을 반복합니다.순회가 끝나면 필터링된 배열의 앞부분에서 유효한 인덱스(index)까지의