Per ardua ad astra.

문제 준규는 숫자 카드 N장을 가지고 있다. 숫자 카드에는 정수가 하나 적혀있는데, 적혀있는 수는 $-2^{62}$ 보다 크거나 같고, $2^{62}$보다 작거나 같다. 준규가 가지고 있는 카드가 주어졌을 때, 가장 많이 가지고 있는 정수를 구하는 프로그램을 작성하시오. 만약, 가장 많이 가지고 있는 정수가 여러 가지라면, 작은 것을 출력한다. 입력 첫째 줄에 준규가 가지고 있는 숫자 카드의 개수 N (1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N개 줄에는 숫자 카드에 적혀있는 정수가 주어진다. 출력 첫째 줄에 준규가 가장 많이 가지고 있는 정수를 출력한다. 예제 입력 1 5 1 2 1 2 1 예제 출력 1 1 예제 입력 2 6 1 2 1 2 1 2 예제 출력 2 1 알고리즘 분류 자료 구조..

문제 n개의 정수로 이루어진 임의의 수열이 주어진다. 우리는 이 중 연속된 몇 개의 수를 선택해서 구할 수 있는 합 중 가장 큰 합을 구하려고 한다. 단, 수는 한 개 이상 선택해야 한다. 예를 들어서 10, -4, 3, 1, 5, 6, -35, 12, 21, -1 이라는 수열이 주어졌다고 하자. 여기서 정답은 12+21인 33이 정답이 된다. 입력 첫째 줄에 정수 n(1 ≤ n ≤ 100,000)이 주어지고 둘째 줄에는 n개의 정수로 이루어진 수열이 주어진다. 수는 -1,000보다 크거나 같고, 1,000보다 작거나 같은 정수이다. 출력 첫째 줄에 답을 출력한다. 예제 입력 1 10 10 -4 3 1 5 6 -35 12 21 -1 예제 출력 1 33 예제 입력 2 10 2 1 -4 3 4 -4 6 5 ..

문제 오른쪽 그림과 같이 삼각형이 나선 모양으로 놓여져 있다. 첫 삼각형은 정삼각형으로 변의 길이는 1이다. 그 다음에는 다음과 같은 과정으로 정삼각형을 계속 추가한다. 나선에서 가장 긴 변의 길이를 k라 했을 때, 그 변에 길이가 k인 정삼각형을 추가한다. 파도반 수열 P(N)은 나선에 있는 정삼각형의 변의 길이이다. P(1)부터 P(10)까지 첫 10개 숫자는 1, 1, 1, 2, 2, 3, 4, 5, 7, 9이다. N이 주어졌을 때, P(N)을 구하는 프로그램을 작성하시오. 입력 첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스는 한 줄로 이루어져 있고, N이 주어진다. (1 ≤ N ≤ 100) 출력 각 테스트 케이스마다 P(N)을 출력한다. 예제 입력 1 2 6 12 예제 출력 1..

문제 지원이에게 2진 수열을 가르쳐 주기 위해, 지원이 아버지는 그에게 타일들을 선물해주셨다. 그리고 이 각각의 타일들은 0 또는 1이 쓰여 있는 낱장의 타일들이다. 어느 날 짓궂은 동주가 지원이의 공부를 방해하기 위해 0이 쓰여진 낱장의 타일들을 붙여서 한 쌍으로 이루어진 00 타일들을 만들었다. 결국 현재 1 하나만으로 이루어진 타일 또는 0타일을 두 개 붙인 한 쌍의 00타일들만이 남게 되었다. 그러므로 지원이는 타일로 더 이상 크기가 N인 모든 2진 수열을 만들 수 없게 되었다. 예를 들어, N=1일 때 1만 만들 수 있고, N=2일 때는 00, 11을 만들 수 있다. (01, 10은 만들 수 없게 되었다.) 또한 N=4일 때는 0011, 0000, 1001, 1100, 1111 등 총 5개의 2..

문제 재귀 호출만 생각하면 신이 난다! 아닌가요? 다음과 같은 재귀함수 w(a, b, c)가 있다. if a 20, then w(a, b, c) returns: w(20, 20, 20) if a < b and b < c, then w(a, b, c) returns: w(a, b, c-1) + w(a, b-1, c-1) - w(a, b-1, c) otherwise it returns: w(a-1, b, c) + w(a-1, b-1, c) + w(a-1, b, c-1) - w(a-1, b-1, c-1) 위의 함수를 구현하는 것은 매우 쉽다. 하지만, 그대로 구현하면 값을 구하는데 매우 오랜 시간이 걸린다. (예를 들면, a=15, b=15, c=15) a, b, c가 주어졌을 때, w(a, b, c)를 출력..

문제 오늘도 서준이는 동적 프로그래밍 수업 조교를 하고 있다. 아빠가 수업한 내용을 학생들이 잘 이해했는지 문제를 통해서 확인해보자. 오늘은 n의 피보나치 수를 재귀호출과 동적 프로그래밍으로 구하는 알고리즘을 배웠다. 재귀호출에 비해 동적 프로그래밍이 얼마나 빠른지 확인해 보자. 아래 의사 코드를 이용하여 n의 피보나치 수를 구할 경우 코드1 코드2 실행 횟수를 출력하자. 피보나치 수 재귀호출 의사 코드는 다음과 같다. fib(n) { if (n = 1 or n = 2) then return 1; # 코드1 else return (fib(n - 1) + fib(n - 2)); } 피보나치 수 동적 프로그래밍 의사 코드는 다음과 같다. fibonacci(n) { f[1]

스타트와 링크 문제 오늘은 스타트링크에 다니는 사람들이 모여서 축구를 해보려고 한다. 축구는 평일 오후에 하고 의무 참석도 아니다. 축구를 하기 위해 모인 사람은 총 N명이고 신기하게도 N은 짝수이다. 이제 N/2명으로 이루어진 스타트 팀과 링크 팀으로 사람들을 나눠야 한다. BOJ를 운영하는 회사 답게 사람에게 번호를 1부터 N까지로 배정했고, 아래와 같은 능력치를 조사했다. 능력치 $S_{ij}$는 i번 사람과 j번 사람이 같은 팀에 속했을 때, 팀에 더해지는 능력치이다. 팀의 능력치는 팀에 속한 모든 쌍의 능력치 Sij의 합이다. $S_{ij}$는 $S_{ji}$와 다를 수도 있으며, i번 사람과 j번 사람이 같은 팀에 속했을 때, 팀에 더해지는 능력치는 $S_{ij}$와 $S_{ji}$이다. N=..

모비율의 검정 이 페이지에서는 정당의 지지율, TV 프로그램의 시청률 또는 생산 제품의 불량률 등과 같은 모집단의 비율에 대한 주장을 검정하는 방법을 살펴본다. 단일 모비율에 대한 검정 모비율 `p` 에 대한 추정을 위해 표본 비율 $\hat{p}$ 를 사용한 것과 동일하게, 모비율 `p` 에 대한 가설을 검정하기 위해 표본 비율 $\hat{p}$ 를 사용한다. 그러면 모비율 $p$ 에 대해 다음과 같은 3가지 유형의 귀무 가설을 생각할 수 있다. $$H_{0} : p = p_{0}, \quad H_{0} : p \le p_{0}, \quad H_{0} : p \ge p_{0}$$ 그리고 이에 대한 대립 가설은 각각 다음과 같다. $$H_{0} : p \ne p_{0}, \quad H_{0} : p > ..

모평균의 검정 (σ² : 미지) 이전 글에서는 모집단의 분산을 알고 있는 경우에 모평균과 두 모평균 차에 대한 주장을 검정하는 방법을 살펴보았다. 그러나 대부분의 모집단은 모분산이 알려져 있지 않다. 따라서 모분산을 모르는 경우에 모평균에 대한 주장을 검정하는 방법을 살펴볼 필요가 있다. 모분산이 알려져 있지 않은 경우에는 정규 분포와 매우 흡사한 `t`-분포를 사용한다. 이 페이지에서는 `t`-분포를 이용하여 모분산이 알려져 있지 않은 정규 모집단의 모평균과 두 모평균의 차에 대한 주장을 검정하는 방법을 살펴본다. `t`-검정(`t`-Test) 근대 통계학의 기초가 되는 소표본론에서 많은 업적을 남긴 영국의 통계학자인 윌리엄 고셋(William Sealey Gosset, 1876-1937)이 소표본을 ..

모평균의 검정(σ² : 기지) 일반적으로 모평균에 대한 주장을 검정하기 위해 모집단은 정규 분포를 따른다고 가정한다. 그러면 모분산을 알고 있는 모평균에 대한 주장을 검정하기 위해 사용하는 확률 분포는 정규 분포이다. 특히 이 경우에 사용하는 검정 통계량은 표본 평균 $\overline{X}$ 의 표준화 확률 변수인 `Z` 이다. 이 페이지에서는 모분산이 알려져 있는 단일 정규 모집단의 모평균과 독립인 두 모집단의 모평균 차에 대한 귀무 가설을 검정하는 방법에 대해 살펴본다. 모평균에 대한 검정 모평균에 대한 양측 검정 모분산 $σ^{2}$ 이 알려진 정규 모집단에서 귀무 가설 $H_{0} : μ = μ_{0}$ 라는 주장과 이에 대립하는 대립 가설 $H_{1} : μ \ne μ_{0}$ 를 검정하는 방..

문제 N개의 수로 이루어진 수열 $A_1, A_2, ..., A_N$이 주어진다. 또, 수와 수 사이에 끼워넣을 수 있는 N-1개의 연산자가 주어진다. 연산자는 덧셈(+), 뺄셈(-), 곱셈(×), 나눗셈(÷)으로만 이루어져 있다. 우리는 수와 수 사이에 연산자를 하나씩 넣어서, 수식을 하나 만들 수 있다. 이때, 주어진 수의 순서를 바꾸면 안 된다. 예를 들어, 6개의 수로 이루어진 수열이 1, 2, 3, 4, 5, 6이고, 주어진 연산자가 덧셈(+) 2개, 뺄셈(-) 1개, 곱셈(×) 1개, 나눗셈(÷) 1개인 경우에는 총 60가지의 식을 만들 수 있다. 예를 들어, 아래와 같은 식을 만들 수 있다. 1+2+3-4×5÷6 1÷2+3+4-5×6 1+2÷3×4-5+6 1÷2×3-4+5+6 식의 계산은 연..

통계적 가설 검정 어느 학원에서 합격률이 전국 최고인 85.4% 라는 광고를 한다고 하자. 그러면 이 학원의 주장이 참인지 아니면 거짓인지 확인할 필요가 있을 것이다. 이와 같이 모수에 대한 주장을 검정하기 위해 반대인 주장을 설정하고, 어느 주장이 참인지 검정하는 일반적인 방법을 살펴본다. 가설 검정의 의미 합격률이 전국 최고인 85.4% 라는 광고가 참인지 확인하기 위해서는, 이 주장을 타당한 것으로 인정하고 이와 반대되는 주장을 설정한다. 그리고 이러한 두 주장 중에서 어느 것이 참인지 결정해야 한다. 이 때, 임의로 표본을 선정하고, 검정을 위한 표본 통계량을 이용하여 얻은 정보를 근거로 어느 주장이 참인지 판정한다. 이와 같이 참인지 거짓인지 명확히 밝히고자 하는 모수에 대한 주장을 가설(Hyp..

모비율의 추정 모비율의 신뢰 구간 표본의 크기 `n` 이 충분히 크다면, 모집단의 모비율 `p` 에 대한 점 추정량은 표본 비율 $\displaystyle \hat{p} = \frac{X}{n}$ 이고, $\hat{p}$ 는 다음과 같은 정규 분포에 근사한다. (관련 내용 바로가기) $\displaystyle \hat{p} \approx N(p, \; \frac{pq}{n})$ 또는 $\displaystyle Z = \frac{\hat{p} - p}{\sqrt{\frac{pq}{n}}} \approx N(0, \; 1)$ (단, $q = 1 - p$) 그러므로 다음을 얻는다. $$P(|Z| \le z_{\frac{α}{2}}) \approx 1 - α \\ P \left( \left | \frac{\ha..

모평균의 추정 대부분의 모집단은 분포를 비롯하여 모집단의 특성을 나타내는 모수가 알려져 있지 않다. 따라서 표본을 선정하여 얻은 정보를 이용하여 모집단의 모수를 과학적으로 추론할 필요가 있다. 이와 같이 모집단으로부터 선정한 표본을 통해 얻은 정보를 이용하여 미지의 모수를 추측하는 것을 추정(Estimate)이라 한다. 이 때, 모집단이 정규 분포를 따르면 표본의 크기 `n` 에 관계 없이 표본 평균 $\overline{X}$ 는 정규 분포를 따른다. 그리고 모집단 분포가 정규 분포가 아닌 경우에도 표본의 크기 `n` 이 충분히 크면 표본 평균 $\overline{X}$ 가 근사적으로 정규 분포를 따르는 것을 살펴보았다. 이 페이지에서는 모집단으로부터 표본을 선정하여 과학적인 방법으로 모평균을 추정하는 ..

그래프의 활용 네트워크의 데이터 흐름이나 스케줄링, 논리회로 설계, 정렬, 탐색, 인공지능의 지식 정보 생성 과정 등 그리고 실생활에서 많이 접할 수 있는 도로망 설계나 버스 및 지하철 노선 설계 등과 같이 어떤 문제를 해결하기 위한 모델링 과정에서 그래프 이론은 매우 중요하게 쓰인다. 이러한 모델링에서 최단 경로를 구하거나 정보 탐색을 하는 방법이 많이 쓰인다. 최단 경로 문제(Shortest Path Problem) $|E| > 0$ 인 연결 그래프 $G = (V, \; E)$ 에서 정점 $v_{1}, v_{2} \in V$ 간의 가장 짧은 거리의 경로를 찾는 문제 지도의 어떤 지역 A에서 다른 지역 B로 이동하는 경로나, 네트워크의 어떤 호스트 A에서 다른 호스트 B로 이동하는 경로는 다양할 수 있..

오일러와 해밀턴 연결 그래프에는 하나의 정점에서 다른 정점으로 가는 다양한 길이 존재할 수 있는데, 그 중에서 같은 변을 반복적으로 지나지 않는 길이 경로이다. 순환(Cycle) / 회로(Circuit) 연결 그래프에서 시작하는 정점과 끝나는 정점이 같은 경로 길이(Length) 경로 또는 순환을 구성하는 변의 수 한 그래프에 포함되는 임의의 정점에서 다른 정점 혹은 다시 원래의 정점으로 가는 길은 다양하다. 그중 변을 한 번씩만 지나 다른 정점으로 가는 길은 경로이고, 원래의 정점으로 다시 돌아오는 경로는 순환이다. 예 (1) $a - c - d - f$ (2) $a - e - c - d - b - f$ (3) $a - c - e - a$ (4) $a - e - c - a$ (5) $a - c - d ..

그래프의 표현 그래프는 수학적 기호와 그림뿐 만 아니라 그래프를 이용한 연산이나 데이터의 구조를 나타내기 위해 행렬이나 리스트 형태로 표현하기도 한다. 인접 행렬(Adjacency Matrix : $A_{G}$) 그래프 $G = (E, \; A)$ 에서 $|V| = n$ 일 때, $n \times n$ 행렬 $A_{G} = [a_{ij}]$ $$a_{ij} = \begin{cases} \text{해당 정점에 근접하는 변의 수} &, (v_{i},\; v_{j}) \in E \\ 0 & , (v_{i}, \; v_{j}) \not \in E \end{cases}$$ 관계를 행렬로 표현하는 관계 행렬은 관계 집합에 순서쌍 원소가 있는지 없는지를 1과 0으로 표현하는 행렬로, 부울 행렬의 형태이다. 그래프도 ..

그래프의 종류 그래프는 정점과 변이 어떻게 구성되는지에 따라 종류를 구분한다. 부분 그래프와 신장 부분 그래프 부분 그래프(Subgraph) 그래프 $G = (V, \; E)$ 에 대하여, $V' ⊆ V$ 이고 $E' ⊆ E$ 인 정점과 변으로 구성된 $G \ne G'$ 인 그래프 $G' = (V', \; E')$ 신장 부분 그래프(Spanning Subgraph) 그래프 $G = (V, \; E)$ 에 대하여, $V' = V$ 이고 $E' ⊆ E$ 인 정점과 변으로 구성된 그래프 $G' = (V', \; E')$ 부분 그래프 `G'` 은 어떤 그래프 `G` 에 포함된 정점과 변의 일부 또는 전체로 구성된 그래프이다. 부분 그래프 `G'` 을 구성하는 정점의 집합과 변의 집합은 각각 그래프 `G` 의 정..

그래프의 개념 점과 선을 이용해 개념, 구조 또는 과정 등을 이해하는 데 필요한 주요 요소 간의 관계, 거리, 비용 등을 시각적으로 표현한 도구를 그래프(Graph)라고 한다. 그래프는 글이나 수식으로는 복잡하고 어렵게 표현되는 것을 그림으로 표현하기 때문에 컴퓨터 시스템의 회로나 네트워크 설계나 구조, 프로그램의 알고리즘, 인공지능의 지식 정보의 파생 과정 및 내용 등을 표현하는 데 효율적이고 효과적으로 활용된다. 그래프는 정점과 변으로 표현되기 때문에 정점에 대한 정보와 변에 대한 정보를 정의함으로써 그래프를 정의하고 표현한다. 그래프는 보통 그림 형태로 표현하지만, 집합 표현과 같은 수학적 기호로 표현할 수도 있다. 그래프의 정의와 표현 그래프(Graph : $G = (V, \; E)$ ) 공집합이..

문제 스도쿠는 18세기 스위스 수학자가 만든 '라틴 사각형'이랑 퍼즐에서 유래한 것으로 현재 많은 인기를 누리고 있다. 이 게임은 아래 그림과 같이 가로, 세로 각각 9개씩 총 81개의 작은 칸으로 이루어진 정사각형 판 위에서 이뤄지는데, 게임 시작 전 일부 칸에는 1부터 9까지의 숫자 중 하나가 쓰여 있다. 나머지 빈 칸을 채우는 방식은 다음과 같다. 각각의 가로줄과 세로줄에는 1부터 9까지의 숫자가 한 번씩만 나타나야 한다. 굵은 선으로 구분되어 있는 3x3 정사각형 안에도 1부터 9까지의 숫자가 한 번씩만 나타나야 한다. 위의 예의 경우, 첫째 줄에는 1을 제외한 나머지 2부터 9까지의 숫자들이 이미 나타나 있으므로 첫째 줄 빈칸에는 1이 들어가야 한다. 또한 위쪽 가운데 위치한 3x3 정사각형의 ..

모집단과 표본 기술 통계학에서 통계 목적에 부합하는 모든 자료 집단을 모집단이라고 한다. 예를 들어, 우리나라는 5년 주기로 인구 주택 총조사를 실시한다. 이 때 모든 가구를 대상으로 가족 구성원의 연령을 비롯하여 가구 형태 등을 조사한다. 이와 같이 통계 목적에 부합하는 모든 자료들의 집단을 모집단이라고 하며, 이 모집단 전체를 대상으로 조사하는 것을 전수 조사(Complete Survey)라 한다. 한편, 선거철이 되면 방송이나 신문에서 "신뢰도 95%와 표본 오차 5%에서 A 후보의 지지율이 30% 이다." 라는 내용을 자주 접한다. 이 경우는 모든 유권자(모집단) 중에서 일부(표본)만 대상으로 조사한 결과를 나타낸다. 이와 같이 표본을 대상으로 조사하는 것을 표본 조사(Sampling Survey..

연속 확률 분포 종 모양의 대칭형인 연속 확률 분포를 정규 분포라 한다. 정규 분포(Normal Distribution) 연속 확률 변수 `X` 의 확률 밀도 함수 `f(x)` 가 다음과 같을 때, 확률 변수 `X` 는 모수 `μ` 와 $σ^{2}$ 인 정규 분포(Normal Distribution)를 따른다 하고, $X \sim N(μ, σ^{2})$ 으로 나타낸다. $$f(x) = \frac{1}{\sqrt{2π}σ}e^{-\frac{(x - μ)^{2}}{2σ^{2}}}, \quad -\infty < x < \infty$$ 자연 현상이나 사회 현상에서 얻게 되는 대부분의 자료에 대한 히스토그램은 자료의 수가 클수록 계급 간격이 좁아지고, 아래와 같이 좌우 대칭인 종 모양의 곡선에 가까워진다. 또한 ..

함수의 종류 항등 함수(Identity Function : $I_{A}$ ) 집합 `A` 에 대한 함수 $f : A \rightarrow A$ 가 $f(a) = a$ 로 정의되는 관계 항등 함수가 성립하려면 함수의 정의역, 공역, 치역 집합이 모두 상등이어야 한다. 항등 함수는 정의역의 원소 $x_{1}, x_{2}$ 가 $x_{1} \ne x_{2}$ 일 때 $f(x_{1}) = x_{1} \ne x_{2} = f(x_{2})$ 이므로 단사 함수이고, 모든 공역의 원소 `y` 에 대하여 `f(x) = y` 를 만족하는 정의역 원소 `x` 를 가지므로 전사 함수이다. 따라서 항등 함수는 전단사 함수이다. 예 집합 $A = \{-1, 0, 1 \}$ 에 대한 함수 $f_{1}(x) = x$ 와 $f_{2}..

합성 함수 합성 함수의 정의 삼각 함수 공식 중 $\sin (α + β)$ 와 같은 식이 있다. 이 식은 다음과 같이 두 함수 `f(x)` 와 `g(x, y)` 를 합성한 결과이다. $$f(x) = sin(x), \; g(x, y) = x + y \quad \Rightarrow \quad sin(α + β) = f(g(α, β))$$ 이처럼 최초 입력을 이용해 2개 이상의 함수를 차례로 연산하여 최종 출력을 내어 입력과 출력을 대응하는 함수를 합성 함수라고 한다. 합성 함수(Composite Function : $g \circ f$ ) 두 함수 $f : A \rightarrow B$ 와 $g : B \rightarrow C$ 가 있을 때, 집합 `A` 의 각 원소를 집합 `C` 의 원소에 대응하는 함수 ..

문제 N-Queen 문제는 크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다. N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하는 프로그램을 작성하시오. 입력 첫째 줄에 N이 주어진다. (1 ≤ N < 15) 출력 첫째 줄에 퀸 N개를 서로 공격할 수 없게 놓는 경우의 수를 출력한다. 예제 입력 1 8 예제 출력 1 92 알고리즘 분류 브루트포스 알고리즘 백트래킹 문제 출처 https://www.acmicpc.net/problem/9663 9663번: N-Queen N-Queen 문제는 크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다. N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하는 프로그램을 작성하시오. www.acmicpc.net 문제 해결 ..

문제 자연수 N과 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오. 1부터 N까지 자연수 중에서 M개를 고른 수열 같은 수를 여러 번 골라도 된다. 고른 수열은 비내림차순이어야 한다. 길이가 K인 수열 A가 $A_1 ≤ A_2 ≤ ... ≤ A_{K-1} ≤ A_{K}$ 를 만족하면, 비내림차순이라고 한다. 입력 첫째 줄에 자연수 N과 M이 주어진다. (1 ≤ M ≤ N ≤ 8) 출력 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해야 한다. 예제 입력 1 3 1 예제 출력 1 1 2 3 예제 입력 2 4 2 예제 출력 2..

문제 자연수 N과 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오. 1부터 N까지 자연수 중에서 M개를 고른 수열 같은 수를 여러 번 골라도 된다. 입력 첫째 줄에 자연수 N과 M이 주어진다. (1 ≤ M ≤ N ≤ 7) 출력 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해야 한다. 예제 입력 1 3 1 예제 출력 1 1 2 3 예제 입력 2 4 2 예제 출력 2 1 1 1 2 1 3 1 4 2 1 2 2 2 3 2 4 3 1 3 2 3 3 3 4 4 1 4 2 4 3 4 4 예제 입력 3 3 3 예제 출력 3 1 1 1..

문제 자연수 N과 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오. 1부터 N까지 자연수 중에서 중복 없이 M개를 고른 수열 고른 수열은 오름차순이어야 한다. 입력 첫째 줄에 자연수 N과 M이 주어진다. (1 ≤ M ≤ N ≤ 8) 출력 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해야 한다. 예제 입력 1 3 1 예제 출력 1 1 2 3 예제 입력 2 4 2 예제 출력 2 1 2 1 3 1 4 2 3 2 4 3 4 예제 입력 3 4 4 예제 출력 3 1 2 3 4 알고리즘 분류 백트래킹 문제 출처 https://www...

문제 자연수 N과 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오. 1부터 N까지 자연수 중에서 중복 없이 M개를 고른 수열 입력 첫째 줄에 자연수 N과 M이 주어진다. (1 ≤ M ≤ N ≤ 8) 출력 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해야 한다. 예제 입력 1 3 1 예제 출력 1 1 2 3 예제 입력 2 4 2 예제 출력 2 1 2 1 3 1 4 2 1 2 3 2 4 3 1 3 2 3 4 4 1 4 2 4 3 예제 입력 3 4 4 예제 출력 3 1 2 3 4 1 2 4 3 1 3 2 4 1 3 4 2 1 ..

백트래킹(Backtracking) 개념 모든 경우의 수를 고려하는 알고리즘 상태 공간을 트리(Tree)로 나타낼 수 있을 때 적합한 방식이다. 일종의 트리 탐색 알고리즘(Tree Search Algorithm)이라고 봐도 된다. 방식에 따른 분류 깊이 우선 탐색(Depth First Search, DFS) 너비 우선 탐색(Breadth First Search, BFS) 최선 우선 탐색(Best First Search / Heuristic Search) 경우의 수 구하기는 일반적으로 DFS가 편리하며, 대다수의 문제들은 DFS를 써도 일단 답은 나온다. 하지만, 트리의 깊이(Depth)가 무한대가 될 경우에는 DFS를 사용하면 안된다. 예) 미로 찾기에서 루프(회로)가 발생하는 경우, DFS는 이 가지를 ..