📝문제 설명📢입출력 예시 ✏️문제 풀이우리는 지금까지 백트래킹 문제를 해결 했을 때 재귀함수로 호출하기 때문에depth가 마지막까지 도달했을 때 즉, 재귀함수(stack)의 마지막 부분부터 로직을 처리하였다. 이번 문제는 연산을 맨 앞부터 수행해야 한다는 점이 지금까지 풀었던 문제와 약간 다른 문제다.그러므로 생각해야될 것은 1. 연산을 수행했으면 그 다음 재귀함수에게 값을 어떻게 전달해 줄 것인가?2. 연산을 어떻게 앞부터 수행할 것인가?3. 연산이 완료 되었으면 어떻게 최소, 최대 값을 비교할 것인가? 1번을 먼저 해결하기 위해서는 재귀함수에게 연산 후의 값을 매개변수로 전달해주는 식으로 해야한다.2번을 해결하기 위해서는 1번에서 해결한 문제인 매개변수로 값을 전달해줄 때 switch나 if문으로..

📝문제 설명 📢입출력 예시 ✏️문제 풀이우선 N 값마다 만들 수 있는 팀의 경우의 수를 생각해보자N = 4 인 경우                       N = 6인 경우(0, 1) VS (2, 3)                         (0, 1, 2) VS (3, 4, 5)(0, 2) VS (3, 4)                         (0, 1, 3) VS (2, 4, 5)(0, 3) VS (1, 2)                         (0, 1, 4) VS (2, 3, 5)                                                 (0, 1, 5) VS (2, 3, 4)                                        ..

📝문제 설명 📢입출력 예시 ✏️문제 풀이백트래킹의 대표적인 문제로 백트래킹의 근본 문제라고 볼 수 있다.N-Queen 문제 이해가 잘 안된다면 밑의 링크를 통해 어떤 방식으로 접근해야 되는지 알아보자.https://namu.wiki/w/%EC%97%AC%EB%8D%9F%20%ED%80%B8%20%EB%AC%B8%EC%A0%9C 여덟 퀸 문제여덟 퀸 문제는 1848년 막스 베첼이 처음으로 제안한 퍼즐 문제로, 수학 과 컴퓨터과학 에서 알고리즘 문제namu.wiki 우리가 고려해야 될 점은 단 2가지이다.1. 재귀함수를 어떻게 호출할 것인가. (매개변수 설정)2. 같은 행,열, 대각선에 있는지 어떻게 판단할 것인가. 내가 보기엔 이 두가지만 해결하면 문제를 풀 수 있을 것 같았다. 사실 이 문제는 내 지..

📝문제 설명 📢입출력 예시 ✏️문제 풀이이 문제 또한 예제 2번의 출력을 보며 규칙을 이해해보자.(1,2)와 (2,1)은 같은 경우로 취급하여 출력을 안한다.똑같이 (2,4)은 (4,2)와 같은 경우로 취급하여 출력을 안한다. 이제 그림으로 이해해보자 그림을 잘 보면 depth 0일 때의 재귀함수에서 depth 1로 넘어갈 때십의자리수의 값에서 +1 한만큼 일의자리수에 넣어주는 것을 볼 수 있다. 이러면 다음 재귀함수로 넘어갈 때 십의 자리수에 채워진 어떤 변수 값을 depth 1로 +1만큼 더하고 가져가야 한다. package Baekjoon.BackTracking;import java.io.BufferedReader;import java.io.IOException;import java.io.Inp..

📝문제 설명 📢입출력 예시 ✏️문제 풀이예제 2번을 보면서 고민을 해보자.예제 2번의 출력의 경우의 수는 아래 그림과 같다.  규칙을 보면 십의자리수에 있는 숫자는 일의자리수에 올 수 없다는 것을 알 수 있다.백트래킹 문제는 재귀함수로 풀어지기 때문에 visited 배열을 사용하여 십의 자리숫자에 있는 자리를 true로 처리하여 방문하지 못하게 막아 놓으면 될 것 같다. depth 값을 추가하여 배열의 인덱스 네비게이션 역할을 할 것이다.십의 자리수가 채워지는 재귀함수에는 depth를 0,일의 자리수가 채워지는 재귀함수는 depth를 1로 하여 값을 채워보자. package Baekjoon.BackTracking;import java.io.BufferedReader;import java.io.IOEx..

📝문제 설명  📢입출력 예시 ✏️문제 풀이1. 다리는 1:1 매칭으로만 연결 가능하다.2. 크로스로 다리가 겹치면 안된다. N M개에서 다리를 놓을 포인트를 정해야 하고 즉, M개 중 N개를 선택해야 한다. 이는 조합 공식으로 mCn을 사용하면 된다. 예를 들어 (1,2,3,4)에서 (2,1,4)를 뽑았다 가정하면 이는 (1,2,4)나 (4,2,1) 처럼 순서가 다르게 뽑혀도 조합은 뽑는 순서를 고려하지 않기에 이 모두 1개의 경우로 본다. 위 그림처럼 왼쪽은 불가능하고 왼쪽은 가능하다. 왼쪽에서는 (2,1,4)가 오른쪽에서는 (1,2,4)가 뽑혔지만 조합의 경우는 이 둘 다 하나의 경우로 본다.결국 조합 공식을 사용하면 서로 다른 다리가 겹치는 경우는 제외될 수밖에 없다. 공식으로 확인하자면 r! ..

이항 계수란?조합의 수학적 표현으로, n개의 원소 중에서 r개의 원소를 선택하는 경우의 수를 의미한다.2를 상징하는 '이항'이라는 말이 붙은 이뉴는 하나의 아이템에 대해서는 '뽑거나', '안뽑거나' 두 가지의 선택만이 있기 때문이다.예를들어 5개의 카드에서 3개의 카드를 중복 없이 순서에 상관없이 뽑는 경우의 수를 계산할 때 조합을 사용할 수 있다. 수학에서 이항계수는 이항(두개의 항) 정리에서 계수로 나타나는 양의 정수를 뜻하는데, 보통 n ≥ k ≥ 0의 정수 쌍으로 나타낸다.계수: 일반적으로 어떤 변수에 곱해진 인자ax^2 + b: 계수는 a, 변수는 x, 차수는 2, 상수는 b를 의미한다. 이항계수는 위와 같이 나타낼 수 있는데 이는 우리가 아는 아래와 같은 조합 공식을 볼 수 있다.여기서 (n/..

📝문제 설명 📢입출력 예시 ✏️문제 풀이처음에는 boolean 배열을 사용해 true, false 처리를 하여 인덱스 값을 응용해 사용하려 했지만, 제거 되는 문자가 적어질 수록 조건이 까다로워 다른 방법을 생각 K번째 사람들 제거하는 방법이면, 큐를 사용해 K-1번만큼 앞에 있는 숫자들을 뒤로 보내고, K번째를 poll하여 출력한다. K = 3 일때{1 2 3 4 5 6 7} 이렇게 있다면 K=1 {2 3 4 5 6 7 1}K=2 {3 4 5 6 7 1 2}K=3 {4 5 6 7 1 2} -> 3출력 K=1 {5 6 7 1 2 4}K=2 {6 7 1 2 4 5}K=3 {7 1 2 4 5} -> 6출력 이런 식으로 뒤로 보내는 방법을 사용했다. import java.io.BufferedReader;i..