문제 개요삼각형의 세 꼭짓점이 주어져 있고, 또 하나의 점 P가 주어졌을 때 이 점이 삼각형의 내부에 있는지 아닌지를 판별하는 문제입니다.해결 원리삼각형의 꼭짓점을 각각 A, B, C라고 하겠습니다. 점 P가 삼각형 내부에 있다면, 삼각형 ABC는 점 P를 기준으로 세 개의 작은 삼각형으로 나눌 수 있습니다. 따라서 다음 등식이 성립합니다.ΔABC = ΔABP + ΔPBC + ΔAPC만약 이 등식이 성립하지 않는다면 점 P는 삼각형 외부에 있는 것입니다. 삼각형의 넓이는 좌표를 이용한 신발끈 공식(Shoelace Formula)으로

시컨트 방법이란?시컨트 방법(Secant Method)은 비선형 방정식의 근을 구하는 대표적인 수치 해석 기법 중 하나입니다. 이 방법은 뉴턴-랩슨 방법(Newton-Raphson Method)과 매우 유사하지만, 한 가지 중요한 차이점이 있습니다. 바로 함수 f(x)의 도함수(미분계수)를 직접 구할 필요가 없다는 점입니다.오직 f(x) 값만을 이용하여 뉴턴의 차분 공식(Divided Difference Formula)을 적용하면, f(x)를 수치적으로 근사할 수 있습니다.먼저 뉴턴-랩슨 공식은 다음과 같습니다.여기에 차분 공식을

정적분(definite integral)은 사다리꼴 공식(트라페조이달 규칙, Trapezoidal Rule)을 이용해 수치적으로 계산할 수 있습니다. 함수 f(x)를 a부터 b까지 적분한다는 것은, 본질적으로 x = a에서 x = b까지 곡선 아래 영역의 넓이를 구하는 것과 같습니다.이 넓이를 구하기 위해 전체 영역을 n개의 작은 사다리꼴로 나눕니다. 각 사다리꼴의 폭을 h라고 하면 (b − a) = nh가 성립합니다. 사다리꼴의 개수를 늘릴수록 넓이 계산 결과는 실제 값에 더 가까워지므로, 정확도를 높이려면 구간을 잘게 나누는 것

심슨 1/3 법칙(Simpsons 1/3 Rule)이란?사다리꼴 공식(Trapezoidal Rule)과 마찬가지로 심슨 1/3 법칙 역시 구간 [a, b]에서의 정적분 값을 구하는 데 사용되는 대표적인 수치 적분 기법입니다.두 방법의 가장 큰 차이점은 다음과 같습니다. 사다리꼴 공식은 전체 구간을 여러 개의 사다리꼴로 나누어 넓이를 근사하는 반면, 심슨 1/3 법칙은 각 사다리꼴 영역을 다시 두 부분으로 나누어 포물선(2차 다항식)으로 근사합니다. 그렇기 때문에 같은 구간 개수 조건에서도 사다리꼴 공식보다 훨씬 정확한 결과를 얻을

선형 회귀(Linear Regression)는 주어진 데이터 포인트 집합으로부터 가장 잘 맞는 직선의 방정식을 찾아내는 통계 기법입니다. 주어진 점들이 하나의 직선을 따른다고 가정하고, 이를 통해 현재 데이터 집합에 존재하지 않는 특정 지점의 값을 예측할 수 있습니다.핵심 공식데이터 포인트들을 이용해 선형 회귀 문제를 풀기 위해서는 다음 공식들을 사용합니다.여기서 m은 기울기(slope)를, c는 y절편(y-intercept)을 의미합니다. 이 식들을 활용하면 다음과 같은 형태의 직선 방정식을 얻을 수 있습니다.y = mx + c입

룽게-쿠타(Runge-Kutta) 방법은 상미분방정식(ODE, Ordinary Differential Equation)을 수치적으로 풀 때 가장 널리 사용되는 대표적인 알고리즘입니다. 이 방법은 x와 y에 대한 dy/dx 함수를 사용하며, 초기값인 y(0)가 반드시 필요합니다. 이를 통해 주어진 x 값에 대응하는 y의 근사값을 구할 수 있습니다.ODE를 풀기 위해서는 다음과 같은 공식들을 순서대로 적용해야 합니다.여기서 h는 구간의 폭, 즉 스텝 크기를 의미합니다.참고: 위 공식들 중 처음 두 항인 k1과 k2만 사용하면, 2차 룽

라그랑주 보간법이란?보간(Interpolation)은 주어진 이산적인 데이터 포인트들 사이에서 새로운 데이터 값을 추정하는 수학적 기법입니다. 그중 라그랑주 보간법(Lagrange Interpolation)은 다항식을 이용해 보간을 수행하는 대표적인 방법으로, 특히 데이터 포인트가 균등하게 분포되어 있지 않은 경우에도 정확한 결과를 얻을 수 있다는 큰 장점이 있습니다.라그랑주 보간법은 다음과 같은 공식을 따릅니다.동작 원리라그랑주 보간법은 각 데이터 포인트마다 하나의 기저 다항식(basis polynomial)을 생성하고, 이들을

행운의 숫자(Lucky Number)란?행운의 숫자는 특별한 성질을 가진 정수입니다. 자연수 목록에서 각 숫자의 값이 아닌 위치를 기준으로 일부 숫자를 단계적으로 제거하고, 최종적으로 삭제되지 않고 남은 숫자들이 바로 행운의 숫자가 됩니다.삭제는 일정한 규칙에 따라 진행됩니다. 먼저 모든 2번째 숫자를 제거하고, 그다음에는 3번째 숫자를 제거합니다. 이후 단계에서는 살아남은 수열에서 다음 차례의 수에 해당하는 간격마다 숫자를 계속 제거해 나갑니다.삭제 과정 예시1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 1

10진수는 얼마든지 2진수 형태로 변환할 수 있습니다. 10진수를 2진수로 바꾸려면 해당 수가 0 또는 1이 될 때까지 2로 계속 나누면 됩니다. 이때 각 단계에서 발생하는 나머지(remainder)를 별도로 저장한 후, 역순으로 나열하면 원하는 2진수 값을 얻을 수 있습니다.이 글에서 소개하는 알고리즘은 재귀(recursion) 방식을 사용합니다. 재귀를 활용하면 스택 자료구조를 직접 구현하지 않고도 문제를 손쉽게 해결할 수 있습니다. 함수가 재귀적으로 호출될 때 내부적으로 시스템 스택이 사용되기 때문에, 우리는 그 내부 스택을

최소공배수(LCM)란?수학에서 최소공배수(Least Common Multiple, LCM)는 두 숫자 모두를 나누어떨어뜨릴 수 있는 가장 작은 양의 정수를 의미합니다.최소공배수는 소인수분해 등 여러 가지 방법으로 구할 수 있습니다. 이 글에서 소개하는 알고리즘은 더 큰 수에 1, 2, 3… n을 차례대로 곱해 가면서, 그 결과가 두 번째 숫자로도 나누어떨어지는지 확인하는 방식을 사용합니다.입력 및 출력입력:두 숫자: 6과 9출력:최소공배수: 18알고리즘LCMofTwo(a, b)입력: 두 숫자 a와 b (단, a > b라고 가정

수학에서 최대공약수(Greatest Common Divisor, GCD)란 두 정수를 모두 나누어 떨어지게 만들 수 있는 가장 큰 정수를 의미합니다. 단, 여기서 다루는 두 수는 반드시 0이 아니어야 한다는 조건이 있습니다.이 글에서는 고전적인 방법인 유클리드 호제법(Euclidean Algorithm)을 이용해 두 수의 GCD를 구하는 과정을 알고리즘과 실제 코드 예제를 통해 살펴보겠습니다.입력 및 출력 예시입력: 두 수 51과 34 출력: 최대공약수(GCD): 1751과 34를 동시에 나눌 수 있는 가장 큰 수가 17이므로, 두

로드 커팅(Rod Cutting)은 동적 계획법(Dynamic Programming)의 대표적인 문제 중 하나입니다. 길이가 n인 막대(로드) 하나와, 각 길이별 판매 가격이 정리된 가격표가 주어졌을 때, 막대를 여러 조각으로 잘라 시장에 판매하여 얻을 수 있는 최대 수익을 구하는 것이 목표입니다.막대를 어느 위치에서 자르느냐에 따라 수익이 달라지므로, 가능한 모든 절단 위치를 고려하고 그 결과를 비교하여 최적의 해를 찾아야 합니다.점화식 정의f(n)이 길이가 n인 막대를 잘라서 얻을 수 있는 최대 가격을 반환하는 함수라고 정의해

최단 공통 초수열(Shortest Common Supersequence, SCS)은 주어진 두 시퀀스의 모든 요소를 포함하는 가장 짧은 시퀀스를 의미합니다. 다시 말해, 두 문자열이 모두 이 초수열의 부분 수열(subsequence)이 되도록 만드는 문자열이라고 할 수 있습니다.두 문자열 사이에 공통 문자가 전혀 없다면, 단순히 두 문자열을 이어 붙이는 것만으로 초수열을 얻을 수 있습니다. 하지만 공통 문자가 존재하는 경우에는 공통 부분을 한 번만 사용하도록 두 문자열을 교차 병합해야 하며, 이때 초수열의 길이는 두 문자열 길이의

어떤 수의 모든 자릿수가 바로 앞자리의 숫자보다 작지 않을 때, 그 수를 감소하지 않는 수(non-decreasing number)라고 합니다. 예를 들어 111, 112, 123, 789, 569처럼 왼쪽에서 오른쪽으로 갈수록 숫자가 유지되거나 커지는 수가 여기에 해당합니다. 이 글에서는 N자리 수 전체에서 감소하지 않는 수가 총 몇 개 존재하는지 동적 계획법(DP)으로 구하는 방법을 알아보겠습니다. 길이가 n이고 마지막 자릿수가 d인 감소하지 않는 수의 개수를 세는 함수를 count(n, d)라고 정의하면, 다음과 같은 점화식

무방향 그래프에서 정점 커버(vertex cover)란 그래프의 모든 간선 (u, v)에 대해 u 또는 v 중 적어도 하나가 반드시 집합에 포함되도록 하는 정점들의 부분집합을 의미합니다.이 문제는 일반 그래프에서는 NP-난해(NP-hard)하지만, 이진 트리(binary tree) 형태의 그래프라면 동적 계획법을 활용해 매우 효율적으로 해결할 수 있습니다.문제 접근 방식이 문제는 두 가지 하위 문제로 나눌 수 있습니다.1. 루트 노드를 정점 커버에 포함하는 경우루트가 커버 집합에 속하면 루트와 자식들을 연결하는 모든 간선이 자동으로

못생긴 숫자란 무엇일까요?못생긴 숫자(Ugly Number)는 소인수가 오직 2, 3, 5로만 이루어진 양의 정수를 의미합니다. 예를 들어 1부터 15 사이에는 총 11개의 못생긴 숫자가 존재하는데, 바로 1, 2, 3, 4, 5, 6, 8, 9, 10, 12, 15입니다.반면 7, 11, 13은 자기 자신을 소인수로 가지는 소수이므로 못생긴 숫자에 해당하지 않습니다. 마찬가지로 14도 소인수 분해 시 7이 포함되기 때문에 못생긴 숫자에서 제외됩니다.이번 글에서는 이러한 정의를 바탕으로 n번째 못생긴 숫자를 효율적으로 찾는 프로그램

서로 다른 여러 작업(job) 목록이 주어지며, 각 작업에는 시작 시간, 종료 시간, 그리고 수행 시 얻을 수 있는 수익(profit)이 함께 표시되어 있습니다. 이 문제의 목표는 서로 시간이 겹치지 않는 작업들의 부분 집합을 찾아 총 수익을 최대화하는 것입니다.이 알고리즘은 동적 계획법(Dynamic Programming)에 기반을 두고 있습니다. 하위 문제의 결과를 테이블에 저장해 둔 뒤, 저장된 값을 재활용하면서 전체 문제를 상향식(bottom-up) 방식으로 해결합니다.기본 구현의 시간 복잡도는 O(n²)입니다. 다만, 이진

줄 바꿈 문제란?여러 개의 단어로 이루어진 시퀀스가 주어지고, 각 줄에 들어갈 수 있는 최대 문자 수에는 제한이 있습니다. 이때 줄 바꿈 위치를 적절히 조정하여 모든 줄이 깔끔하게 인쇄되도록 만드는 것이 이 문제의 목표입니다.단순히 글자 수 제한만 지키는 것으로는 부족합니다. 어떤 줄은 여백이 많고 어떤 줄은 여백이 거의 없다면 전체적인 모양이 지저분해 보입니다. 따라서 이 알고리즘은 각 줄의 남는 공간(여분의 공백)을 최대한 비슷하게 분배하여 줄과 줄 사이의 균형을 맞춥니다.최종적으로 이 알고리즘은 한 줄에 몇 개의 단어를 배치할

개요컴퓨터는 사람이 일반적으로 사용하는 중위(infix) 표기식을 그대로 계산하기 어렵습니다. 따라서 연산자 우선순위를 명확하게 반영할 수 있도록 후위(postfix) 또는 전위(prefix) 표기식으로 변환한 뒤 계산을 수행합니다. 이 글에서는 중위 표기식을 전위 표기식으로 변환하는 방법을 단계별로 살펴보겠습니다.변환 절차중위 표기식을 전위 표기식으로 바꾸는 과정은 다음 네 단계로 진행됩니다.중위 표기식을 뒤집습니다. 이때 여는 괄호 ( 와 닫는 괄호 ) 도 함께 뒤집힌다는 점에 유의해야 합니다.괄호 방향을 교환합니다. 뒤집힌 식

중위 표기법(infix notation)은 사람이 읽고 이해하기 가장 자연스러운 수식 표현 방식입니다. 연산자의 우선순위를 쉽게 파악할 수 있고, 괄호를 사용해 계산 순서를 명확하게 지정할 수도 있습니다. 반면 컴퓨터는 연산자와 괄호를 사람처럼 직관적으로 판단하지 못하기 때문에, 수식을 효율적으로 처리하려면 후위 표기법(postfix notation)으로 변환하는 과정이 필요합니다. 중위 표기식을 후위 표기식으로 변환할 때는 스택(stack) 자료구조를 활용합니다. 식을 왼쪽에서 오른쪽으로 한 문자씩 스캔하면서 피연산자(opera