이 글에서는 하나의 정수 안에 특정 자릿수가 몇 번 등장하는지, 즉 빈도(frequency)를 구하는 방법을 살펴보겠습니다. 예를 들어 주어진 수가 12452321이고 찾으려는 자릿수 D = 2라고 한다면, 2는 세 번 나타나므로 빈도는 3이 됩니다.이 문제는 아주 단순한 아이디어로 해결할 수 있습니다. 먼저 수의 가장 뒤쪽 자릿수(일의 자리)를 하나씩 가져온 뒤, 그 값이 찾고자 하는 자릿수 d와 같은지 비교합니다. 같다면 카운터 값을 1 증가시킵니다. 그다음 수를 10으로 나누어 마지막 자릿수를 제거하고, 수가 모두 소진될 때까

배열에 n개의 서로 다른 요소가 저장되어 있다고 가정해 보겠습니다. 이때 배열 안에서 특정 요소가 몇 번 등장하는지, 즉 빈도(frequency)를 확인해야 하는 경우가 있습니다.예를 들어 A = [5, 12, 26, 5, 3, 4, 15, 5, 8, 4]라는 배열에서 숫자 5의 빈도를 구하면 3이 됩니다.해결 방법이 문제는 매우 간단한 선형 탐색(linear search) 기법으로 해결할 수 있습니다.배열의 왼쪽(첫 번째 요소)부터 차례대로 탐색하면서, 현재 요소가 찾고자 하는 숫자와 같으면 카운터를 1 증가시키고, 같지 않다면

문제 소개 이번 글에서는 C++를 사용해 1!부터 N!까지 팩토리얼의 합에서 일의 자리 숫자를 구하는 방법을 알아봅니다. 예를 들어 N = 3이라면 1! + 2! + 3! = 9가 되므로 결과값은 9이고, N = 4라면 1! + 2! + 3! + 4! = 33이 되어 일의 자리 숫자는 3입니다. 여기서 중요한 규칙성이 하나 있습니다. 5 이상 숫자의 팩토리얼은 항상 일의 자리가 0으로 끝납니다. 실제로 5! = 120, 6! = 720, 7! = 5040처럼 5!부터는 인수 2와 5가 반드시 함께 곱해지기 때문에 끝자리가 항상 0이

문제 개요어떤 수 N이 주어졌을 때, 재귀(recursion)를 이용하여 ln(N!)의 값을 구하는 것이 목표입니다. 여기서 ln()은 자연로그(natural logarithm), 즉 밑이 e인 로그를 의미합니다.이 문제는 로그의 곱셈 법칙을 활용하면 간단하게 해결할 수 있습니다. 팩토리얼을 먼저 계산한 뒤 로그를 취하는 대신, 로그를 각 항으로 분리할 수 있다는 점이 핵심입니다.핵심 공식$$\ln\lgroup N!\rgroup=\ln\lgroup N*(N-1)*(N-2)*\dotsm*2*1\rgroup=\ln(N)+\ln(N-1)

메르센 소수란?수학에서 메르센 소수(Mersenne prime)는 2의 거듭제곱에서 1을 뺀 값이 소수인 수를 의미합니다. 즉, 어떤 정수 n에 대해 Mn = 2n − 1 형태를 만족하는 소수입니다.메르센 소수가 되는 지수 n은 2, 3, 5, 7, ... 순으로 나타나며, 이에 대응하는 메르센 소수는 각각 3, 7, 31, 127 입니다.이번 글에서는 입력으로 주어진 양의 정수 n보다 작거나 같은 모든 메르센 소수를 출력하는 C++ 프로그램을 작성해 보겠습니다.알고리즘 접근 방식문제를 해결하기 위한 핵심 아이디어는 다음

개요미드 스퀘어(Mid-Square, 제곱 중간값) 방법은 의사 난수(pseudorandom number)를 생성하는 고전적인 기법 중 하나입니다. 이 방법은 수학자이자 컴퓨터 과학의 선구자인 존 폰 노이만(John von Neumann)이 1949년 학회에서 발표하면서 널리 알려지게 되었습니다.동작 원리초기 시드(seed) 값을 하나 선택하고, 그 값을 제곱합니다.제곱 결과에서 가운데 자릿수 일부를 추출하고, 추출된 숫자들이 만든 새로운 수를 다음 시드 값으로 사용합니다.예시로 이해하기시드 값으로 3456을 선택합니다. 제곱하면

문제 설명 정렬되지 않은 두 개의 배열을 입력받아, 모든 요소를 하나의 새로운 배열에 담고 오름차순으로 정렬하는 함수를 작성하는 것이 목표입니다. arr1[] = {10, 5, 7, 2} arr2[] = {4, 17, 9, 3} result[] = {2, 3, 4, 5, 7, 9, 10, 17} 알고리즘 접근 방법은 다음과 같습니다.1. 정렬되지 않은 두 배열을 하나의 새로운 배열로 병합합니다.2. 새로 만든 배열을 오름차순으로 정렬합니다. C++ 구현 예제 #include <iostream> #include <al

문제 개요두 개의 배열이 주어졌을 때, 첫 번째 배열과 두 번째 배열의 요소를 번갈아 가며 배치한 새로운 배열(세 번째 배열)을 만들어야 합니다. 이때 한쪽 배열에 요소가 더 많이 남아 있다면, 남은 요소들은 결과 배열의 맨 뒤에 순서대로 추가하면 됩니다.arr1[] = {10, 20, 30, 40} arr2[] = {-10, -20, -30, -40} result[] = {10, -10, 20, -20, 30, -30, 40, -40}위 예시에서 볼 수 있듯이, 첫 번째 배열의 요소와 두 번째 배열의 요소가 한 개씩 교대로 배치되

이 글에서는 C++를 사용하여 두 개의 정렬된 단일 연결 리스트(singly linked list)를 하나의 정렬된 리스트로 병합하는 방법을 알아봅니다. 정렬된 연결 리스트 병합은 면접에서 자주 등장하는 대표적인 알고리즘 문제이며, 재귀적 접근 방식으로 깔끔하게 해결할 수 있습니다. 문제 정의 두 개의 정렬된 단일 연결 리스트가 주어졌을 때, 이 두 리스트를 하나의 정렬된 연결 리스트로 병합하는 함수를 작성해야 합니다. 리스트1: 10->15->17->20 리스트2: 5->9->13->19 결과:

문제 정의정렬된 두 개의 배열이 주어졌을 때, 이 두 배열을 하나의 정렬된 배열로 병합하는 함수를 작성하는 것이 목표입니다.Arr1[] = {10, 15, 17, 20} Arr2[] = {5, 9, 13, 19} Result[] = {5, 9, 10, 13, 15, 17, 19, 20}알고리즘두 배열이 이미 각각 정렬되어 있다는 점을 활용하면, 투 포인터(Two Pointer) 기법으로 선형 시간 안에 병합할 수 있습니다.1. 두 배열을 동시에 순회한다    1.1. arr1[i] < arr2[j]인 경우 &

문제 개요배열 형태로 주어진 두 개의 이진 최대 힙(binary max heap)을 하나의 최대 힙으로 병합하는 것이 목표입니다. 병합된 결과 역시 최대 힙의 성질, 즉 부모 노드가 항상 자식 노드보다 크거나 같은 구조를 유지해야 합니다.Heap1[] = {20, 17, 15, 10} Heap2[] = {19, 13, 7} Result[] = {20, 19, 15, 13, 17, 7, 10}알고리즘두 힙을 병합하는 절차는 다음과 같이 단순합니다.1. 병합 결과를 저장할 새로운 배열을 생성합니다.2. 주어진 두 배열의 요소를 순서대로

문제 개요연결 리스트(Linked List)가 주어졌을 때, 병합 정렬(Merge Sort) 알고리즘을 사용하여 이를 오름차순으로 정렬하는 것이 목표입니다.예를 들어 다음과 같은 연결 리스트가 있다고 가정해 보겠습니다.정렬 전 리스트: 10->20->8->17->5->13->4정렬 후 리스트: 4->5->8->10->13->17->20알고리즘 접근 방식연결 리스트에 병합 정렬을 적용하는 과정은 다음과 같습니다.헤드(head)가 NULL이거나 리스트에 노드가 하나뿐이라면

문제 정의 이중 연결 리스트(doubly linked list)가 주어졌을 때, 병합 정렬(Merge Sort) 알고리즘을 사용하여 노드 값들을 오름차순으로 정렬하는 것이 이번 문제의 목표입니다. 입력 리스트 : 10 -> 20 -> 8 -> 17 -> 5 -> 13 -> 4 정렬 결과  : 4 -> 5 -> 8 -> 10 -> 13 -> 17 -> 20 알고리즘 접근 방식 병합 정렬은 대표적인 분할 정복(Divide and Conquer) 기법으로

문제 설명임의의 순서로 나열된 시간 구간(intervals) 집합이 주어졌을 때, 서로 겹치는 모든 구간을 하나로 합쳐서 결과에 상호 배타적인 구간만 남도록 만드는 것이 이 문제의 목표입니다.예를 들어 주어진 구간 집합이 {{12, 14}, {11, 13}, {20, 22}, {21, 23}}이라면 다음과 같이 병합됩니다.{12, 14}와 {11, 13}은 서로 겹치기 때문에 하나로 합쳐 {11, 14}가 됩니다.{20, 22}와 {21, 23} 역시 서로 겹치기 때문에 {20, 23}으로 병합됩니다.알고리즘스택(stack) 자료구

문제 설명두 개의 문자열 str1(길이 m)과 str2(길이 n)가 주어집니다. 목표는 str1에서 문자를 삭제하거나 삽입하여 str1을 str2로 변환할 때, 필요한 삭제와 삽입 연산의 횟수를 최소화하는 것입니다.str1 = tutorialspoint str2 = tutorials str1을 str2로 변환하려면 5개의 문자, 즉 point를 str1에서 삭제하면 됩니다.접근 방법핵심 아이디어는 두 문자열의 최장 공통 부분 수열(LCS, Longest Common Subsequence)을 활용하는 것입니다. LCS에 포함된 문자

문제 정의길이가 n인 문자열이 주어졌을 때, 최소한의 문자를 삭제하여 해당 문자열을 회문(palindrome)으로 만드는 것이 목표입니다.예를 들어 주어진 문자열이 abcda라면, 첫 번째 문자와 마지막 문자를 제외한 나머지 중 2개의 문자를 삭제하면 회문을 만들 수 있습니다.b와 c를 삭제하면 ada가 되어 회문입니다.c와 d를 삭제하면 aba가 되어 회문입니다.b와 d를 삭제하면 aca가 되어 회문입니다.세 경우 모두 삭제 횟수는 2회로, 이것이 이 문자열에서 가능한 최소 삭제 횟수입니다.접근 방식 및 알고리즘이 문제의 핵심 아

문제 설명 배열 arr이 주어졌을 때, 이 배열을 좋은(good) 배열로 만들기 위해 제거해야 하는 최소 요소 개수를 구하는 것이 과제입니다. 여기서 좋은 배열이란, 수열 a₁, a₂, a₃ … aₙ의 모든 원소 a[i]에 대해 i ≠ j인 다른 원소 a[j]가 존재하여 a[i] + a[j]가 2의 거듭제곱이 되는 경우를 말합니다. 예시 arr1[] = {1, 1, 7, 1, 5} 위 배열에서 원소 5를 하나만 삭제하면 배열은 좋은 배열이 됩니다. 삭제 후에는 어떤 쌍을 골라도 arr[i] + arr[j]가 2의 거듭제곱이 됩니다

문제 개요크기가 n인 배열 arr와 값 x가 주어졌을 때, 배열에 최소 몇 개의 요소를 추가해야 중앙값(median)이 x와 같아지는지 구하는 것이 이 문제의 목표입니다.여기서 중앙값이란 배열의 요소들을 비내림차순(오름차순)으로 정렬했을 때 (n-1)/2번째 위치에 있는 요소를 의미합니다. 예를 들어 다음 배열의 중앙값은 20입니다.arr1[] = {10, 20, 30, 40}만약 arr[] = {1, 2, 3}이고 x = 4라고 가정해 보겠습니다. 이 경우 배열에 4개의 요소({4, 4, 4, 4})를 추가하여 {1, 2, 3,

문제 설명 자연수 N이 주어집니다. 1부터 N까지의 연속된 숫자들 가운데 일부를 제거했을 때, 남은 숫자들의 XOR(배타적 논리합) 값이 최대가 되도록 만들어야 합니다. 이때 제거해야 하는 숫자의 최소 개수를 구하는 것이 이 문제의 목표입니다. 알고리즘 모든 조합을 일일이 시도하는 대신, N의 값에 따라 답이 규칙적으로 결정된다는 점을 활용하면 매우 효율적으로 해결할 수 있습니다. 1. n이 1 또는 2라면 어떤 요소도 제거할 필요가 없습니다. 따라서 답은 0입니다. 2. n보다 크거나 같은 2의 거듭제곱 수를 찾습니다. 이 값을

문제 설명선행 0(leading zero)이 없는 숫자 N이 주어졌을 때, 인접한 두 자릿수를 서로 교환하는 연산을 반복하여 N을 25로 나누어 떨어지게 만들어야 합니다. 이때 필요한 최소 연산 횟수를 구하는 것이 목표입니다. 단, 연산 과정에서 어떤 시점에도 숫자 앞에 0이 위치해서는 안 됩니다. 아무리 교환해도 25의 배수를 만들 수 없다면 -1을 출력합니다.예를 들어 N = 5071이라면, 다음과 같이 4번의 이동만으로 25의 배수를 만들 수 있습니다.5071 → 5701 → 7501 → 7510 &