C#에서 주어진 문자열을 개별 문자가 아닌 단어 단위로 뒤집는 알고리즘을 살펴보겠습니다. 예를 들어 This is my book이라는 문장이 있다면, 결과는 book my is This가 되어야 합니다.알고리즘 접근 방식핵심 아이디어는 다음과 같습니다. 먼저 char 배열을 입력으로 받는 reverseWords 메서드를 생성하고, 공백 문자에 도달할 때까지 각 단어를 개별적으로 뒤집습니다. 그다음 마지막 단계에서 전체 문자열을 인덱스 0부터 n-1까지 한 번 더 뒤집습니다.이 과정을 단계별로 보면 다음과 같습니다.1단계: 문자열 T

문자열에서 가장 먼저 등장하는 고유 문자(중복되지 않은 문자)의 인덱스를 찾는 것은 코딩 테스트와 면접에서 자주 출제되는 대표적인 문제입니다. 이번 글에서는 C#의 내장 함수를 사용하지 않고, 배열 카운팅 기법만으로 이 문제를 해결하는 방법을 알아보겠습니다.핵심 아이디어해결 방식은 매우 직관적입니다. 알파벳 소문자는 총 26개이므로, 크기 256의 정수형 배열을 하나 생성하여 각 문자의 등장 횟수를 저장합니다.구체적인 절차는 다음과 같습니다.1. 크기가 256인 빈 배열을 새로 만듭니다.2. 문자열 전체를 한 글자씩 순회하면서 해당

핵심 아이디어는 간단합니다. 길이 256짜리 빈 정수 배열을 하나 생성한 뒤, 문자열 전체를 한 글자씩 순회하면서 각 문자의 등장 횟수를 배열에 기록합니다. 개수 집계가 끝나면 문자열을 다시 처음부터 순회하면서 개수가 정확히 1인 첫 번째 문자를 찾아 반환하면 됩니다.알고리즘의 동작 방식각 문자에서 소문자 a의 아스키(ASCII) 값을 빼면 0부터 25 사이의 인덱스가 계산됩니다. 이 인덱스를 배열의 위치로 활용하면 알파벳별 등장 횟수를 손쉽게 저장하고 다시 조회할 수 있습니다. 시간 복잡도는 O(n), 공간 복잡도는 고정 크기 배

코딩 테스트나 기술 면접에서 자주 등장하는 문제 중 하나가 바로 정렬된 배열에서 누락된 숫자 찾기입니다. C#에서는 LINQ 같은 내장 함수를 사용하지 않고도 여러 가지 방법으로 이 문제를 해결할 수 있습니다. 이 글에서는 세 가지 대표적인 접근 방식과 실제로 동작하는 예제 코드를 소개합니다. 세 가지 해결 방법 첫 번째 방법 – 합 공식 활용: 등차수열 합 공식 n(n+1)/2로 0부터 n까지의 기대 합계를 구한 뒤, 배열 요소의 실제 합을 빼면 누락된 숫자가 계산됩니다. 두 번째 방법 – 불리언 배열 활용: 배열 크기보다 1

개요C#에서 LINQ나 기타 내장 함수를 사용하지 않고, 정렬된 배열 안에서 누락된 숫자(missing number)와 반복되는 숫자(repeating number)를 찾는 방법을 소개합니다. 핵심 아이디어는 배열의 값을 인덱스로 활용하는 보조 배열(마커 배열)을 만드는 것입니다.누락된 숫자 찾기원본 배열보다 크기가 1 큰 불리언(bool) 배열을 새로 생성합니다. 원본 배열을 처음부터 끝까지 순회하면서, 발견된 숫자를 인덱스로 삼아 새 배열의 해당 위치를 true로 표시합니다. 이후 새 배열을 다시 순회하여 처음으로 false인

최소 점프(Minimum Jumps) 문제란?배열의 각 요소는 해당 위치에서 최대 그 값만큼 앞으로 점프할 수 있다는 의미를 가집니다. 이때 목표는 배열의 첫 번째 인덱스에서 마지막 인덱스까지 이동하는 데 필요한 최소 점프 횟수를 구하는 것입니다.첫 번째 요소에서 출발하여 도달 가능한 모든 요소를 재귀적으로 탐색하면 답을 구할 수 있습니다. 즉, 첫 요소에서 끝까지 가는 최소 점프 수는 첫 요소에서 도달 가능한 각 요소에서 끝까지 가는 최소 점프 수 + 1 중 가장 작은 값이 됩니다.예를 들어 다음 배열을 살펴보겠습니다.Array

n×n 크기의 정사각형 행렬을 90도 회전하는 것은 코딩 테스트와 실무에서 자주 만나게 되는 대표적인 배열 조작 문제입니다. 이 글에서는 별도의 추가 배열 없이 제자리(in-place)에서 행렬을 반시계 방향으로 90도 회전시키는 C# 구현 방법을 소개합니다. 알고리즘의 핵심 원리 n×n 행렬은 총 n/2개의 동심원 형태의 사각형 레이어로 나눌 수 있습니다. 중첩 루프(nested loop)를 사용해 바깥쪽 레이어부터 안쪽 레이어까지 하나씩 처리하며, 각 레이어 안에서는 4개의 요소가 하나의 순환(cycle)을 이루며 이동합니다

핵심 아이디어n×n 크기의 행렬 전체를 반시계 방향으로 90도씩 k번 회전해야 하는 상황을 생각해 봅시다. n×n 행렬은 총 n/2개의 동심원 형태 사각형(레이어)으로 나눌 수 있으며, 중첩 루프를 사용해 각 사각형을 한 번에 하나씩 처리할 수 있습니다.각 사각형 내부에서는 4개의 요소가 하나의 순환(cycle)을 이루며 이동합니다. 따라서 매 순환마다 해당 4개의 요소를 반시계 방향으로 서로 교환(swap)하면 행렬 전체가 자연스럽게 회전하게 됩니다.요소 이동 규칙반시계 방향 회전 시 각 요소는 다음과 같이 이동합니다.위치 (n-

행렬을 나선형(spiral) 순서로 출력한다는 것은 행렬의 가장 바깥쪽 테두리부터 시작해 시계 방향으로 한 바퀴 돌고, 그다음에는 그보다 안쪽 고리(inner ring)로 이동하여 같은 과정을 반복하는 것을 의미합니다. 모든 내부 행렬과 외부 행렬이 처리될 때까지 다음 단계를 순서대로 수행하면 됩니다.나선형 순회의 기본 원리1단계 − 첫 번째 행(윗줄)의 요소들을 왼쪽에서 오른쪽으로 출력합니다.2단계 − 마지막 열의 요소들을 위에서 아래로 출력합니다.3단계 − 마지막 행(아랫줄)의 요소들을 오른쪽에서

문제 접근 방식2차원 격자(grid) 맵을 선형으로 스캔하면서, 어떤 노드의 값이 1이면 그 노드를 깊이 우선 탐색(Depth First Search, DFS)을 시작하는 루트 노드로 간주합니다. DFS가 진행되는 동안 방문한 모든 노드는 0으로 설정하여 방문 처리를 합니다.DFS를 트리거하는 루트 노드의 개수를 세면 그 값이 곧 섬의 총 개수가 됩니다. 각 DFS 시작점이 하나의 섬을 식별하기 때문입니다. 즉, 상하좌우로 연결된 1들은 하나의 덩어리(섬)로 묶이고, 서로 분리된 덩어리의 수가 정답이 됩니다.알고리즘 단계1단계: 격

C#에서 재귀 호출을 활용하면 주어진 숫자의 거듭제곱을 효율적으로 계산할 수 있습니다. 이 글에서는 밑이 되는 숫자 x와 지수 n을 받아 거듭제곱 값을 반환하는 FindPower 함수를 만드는 방법을 단계별로 살펴봅니다.거듭제곱 계산 알고리즘의 원리이 알고리즘의 핵심 아이디어는 다음과 같습니다.숫자 x와 지수 n을 매개변수로 받으며, x는 밑(base), n은 곱셈을 반복할 횟수를 의미합니다.n이 0이 되면 1을 반환하며 재귀 호출을 종료합니다.n이 짝수라면 절반 지수의 결과를 제곱하여(x * x 형태) 반환합니다.n이 홀수라면 결

역추적(Backtracking) 기법은 첫 번째 위치의 문자를 고정하고, 나머지 문자들을 첫 번째 문자와 차례로 교환(swap)하는 방식으로 모든 순열을 탐색합니다.예를 들어 ABC라는 문자열이 있다면, 첫 번째 반복에서 A를 A, B, C와 각각 교환하여 ABC, BAC, CBA 세 가지 문자열이 생성됩니다.이후 두 번째 문자 B를 고정하는 방식으로 나머지 문자들에 대해서도 동일한 과정을 반복합니다. 각 단계가 끝날 때마다 다시 스왑하여 이전 상태로 되돌아가는 역추적 작업을 수행하는 것이 핵심입니다.예를 들어 ABC에서 두 번째

복잡해 보이는 이 문제는 사실 더 작고 단순한 하위 문제(subproblem)들로 나누어 해결할 수 있습니다. 역추적(Backtracking) 기법의 핵심은 바로 여기에 있습니다. 하나의 큰 문제를 반복적으로 쪼개어 가장 단순한 형태까지 분해한 뒤, 각 단계에서 가능한 선택지를 하나씩 시도하고 결과를 누적하는 방식입니다.접근 방식이 문제는 다음과 같은 흐름으로 해결합니다.1. 입력받은 숫자 문자열에서 첫 번째 자릿수를 하나씩 가져옵니다.2. 해당 숫자에 매핑된 문자들을 딕셔너리(Map)에서 조회합니다. 예를 들어 2는 abc, 3은

목표 합계(Target Sum) 문제는 주어진 배열의 요소들을 조합하여 그 합이 특정 목표값과 일치하는 부분집합을 찾는 고전적인 알고리즘 문제입니다. 백트래킹(backtracking) 기법은 최악의 경우 모든 순열을 탐색하게 되지만, 단순 재귀 방식으로 부분집합 합(subset sum) 문제를 해결하는 것보다 일반적으로 더 나은 성능을 보입니다. 문제 정의 n개의 양의 정수로 이루어진 배열 A와 목표값 sum이 주어졌을 때, 요소들의 합이 sum과 정확히 일치하는 부분집합이 존재하는지 판별하고, 가능한 모든 조합을 구하는 것이 목표

고유한 부분집합(Distinct Subsets) 문제는 주어진 배열의 원소들로 만들 수 있는 서로 다른 조합을 모두 찾아내는 문제입니다. 목표 크기가 2라면 배열에서 2개의 원소를 선택하는 모든 조합을, 목표 크기가 3이라면 3개의 원소를 선택하는 모든 조합을 구합니다. 예를 들어 배열이 [1, 2, 3]이고 목표 크기가 2라면 "1,2", "1,3", "2,3" 세 가지 조합이 결과로 출력됩니다. 백트래킹의 동작 원리 이 문제는 백트래킹(Backtracking) 기법으로 효율적

이 글에서는 C#의 백트래킹(Backtracking) 기법을 활용하여 1부터 n까지의 숫자 중 정확히 k개의 서로 다른 숫자를 골랐을 때 그 합이 목표값(target)과 일치하는 모든 고유한 조합을 찾는 방법을 살펴봅니다. 문제 예시 예를 들어 n이 5이고 k가 2라고 가정해 보겠습니다. 이 경우 크기가 2인 숫자 조합 중 합이 5가 되는 조합을 찾아야 하며, 결과는 1,4와 2,3 두 가지입니다. 알고리즘 접근 방식 백트래킹은 재귀 트리를 따라 해답을 탐색하다가 조건에 맞지 않으면 이전 단계로 되돌아가는 기법입니다. 구현 절차는

C#에서 주어진 합계에 해당하는 고유한 숫자 조합 찾기주어진 숫자의 합이 되는 고유한 숫자 조합을 찾으려면 백트래킹(Backtracking) 기법을 활용하는 것이 효과적입니다. 먼저 유효한 수열을 저장할 출력 리스트(output list)를 만들고, 재귀 트리 탐색 경로에서 발견된 현재 수열을 저장할 현재 리스트(current list)를 생성합니다.백트래킹 함수는 목표값(target)에 도달할 때까지 재귀 호출을 반복하며, 탐색 중 합계가 목표값을 벗어나면 이전 단계로 되돌아갑니다. 언제든지 남은 목표값이 정확히 0이 되면, 후보

C#에서 백트래킹(backtracking) 기법을 활용하면 주어진 숫자 k에 대해 여는 괄호 {와 닫는 괄호 }로 만들 수 있는 모든 유효한 조합을 효율적으로 찾을 수 있습니다. 이 문제는 재귀 호출을 통해 가능한 모든 경우를 탐색하되, 유효하지 않은 경로는 미리 잘라내는(backtrack) 방식으로 해결합니다.알고리즘 접근 방식백트래킹 함수를 생성하고, 다음 규칙에 따라 현재 문자열을 갱신해 나갑니다.아직 배치할 여는 괄호가 남아 있다면(여는 괄호 개수 < n) 여는 괄호 {를 추가할 수 있습니다.닫는 괄호의 개수가 여는 괄

개요체스의 나이트(knight)는 L자 형태로 움직이는 말입니다. 체스판 위에서 어떤 칸도 두 번 방문하지 않으면서 모든 칸을 지나가는 문제를 나이트 투어(Knights Tour)라고 부릅니다. 이 글에서는 C#을 사용해 나이트가 시작 위치에서 목표 위치까지 도달하는 데 필요한 최소 이동 횟수를 BFS(너비 우선 탐색) 알고리즘으로 구하는 방법을 살펴보겠습니다.나이트 투어의 두 가지 유형나이트 투어는 경로가 끝나는 방식에 따라 두 가지로 나뉩니다.닫힌 경로(Closed Tour): 나이트가 시작 칸에서 나이트 이동 거리만큼 떨어진

개요오름차순으로 정렬된 배열이 어느 한 지점에서 회전(rotated)되었다면, 배열이 총 몇 번 회전되었는지는 최솟값 요소가 위치한 인덱스를 찾으면 알 수 있습니다. 예를 들어 {3, 4, 5, 6, 7, 8, 9, 10, 1, 2} 배열에서 최솟값 1은 인덱스 8에 있으므로, 이 배열은 8번 회전된 것입니다.접근 방식회전 횟수를 구하려면 일반적인 이진 탐색(Binary Search)을 변형한 알고리즘을 재귀적으로 적용합니다. 먼저 중간(mid) 요소의 인덱스를 구한 뒤, 다음 조건에 따라 탐색 범위를 좁혀 나갑니다.찾으려는 값이