(14888) 연산자 끼워넣기

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

• format_list_bulleted BackJoon/Algorithm
• · 2023. 4. 10.
• textsms

(15651) N과 M(3)

문제 문제 자연수 N과 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오.1부터 N까지 자연수 중에서 M개를 고른 수열같은 수를 여러 번 골라도 된다. 입력 첫째 줄에 자연수 N과 M이 주어진다. (1 ≤ M ≤ N ≤ 7) 출력 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다.수열은 사전 순으로 증가하는 순서로 출력해야 한다. 문제 풀이 해당 문제는 백트래킹이라기 보다는 재귀함수를 이해를 얼마나 하였냐에 따라 문제 난이도가 나뉘는 문제이다. 현재 출력되는 값을 보면 같은 값이 출력이 되고 있는데, 해당 방식으로 출력 된다는 것은 순서나 반복여부를 따지지 않고 길이에..

• format_list_bulleted BackJoon/Algorithm
• · 2023. 4. 10.
• textsms

(9663) N-Queen

문제 문제 N-Queen 문제는 크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다.N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하는 프로그램을 작성하시오. 입력 첫째 줄에 N이 주어진다. (1 ≤ N < 15) 출력 첫째 줄에 퀸 N개를 서로 공격할 수 없게 놓는 경우의 수를 출력한다. 문제 풀이 해당 문제는 백트래킹 알고리즘으로 해결 할 수 있는 문제이다. 문제에 앞서 체스판에서 퀸은 가로, 세로, 대각선을 모두 움직일 수 있는 말이라는 것을 알고 있어야 문제를 이해가능하다. 그렇다면 하나의 퀸을 두고, 다른 퀸을 두려고 하면 같은 대각선인지, 같은 열과 행인지를 검사하면 된다. 기본적으로 row의 경우에는 재귀함수를 통해 매번 새로운 값으로 비교를 하니 문제는 없다. 그렇..

• format_list_bulleted BackJoon/Algorithm
• · 2023. 4. 10.
• textsms

(15650) N 과 M(2)

문제 문제 자연수 N과 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오.1부터 N까지 자연수 중에서 중복 없이 M개를 고른 수열고른 수열은 오름차순이어야 한다. 입력 첫째 줄에 자연수 N과 M이 주어진다. (1 ≤ M ≤ N ≤ 8) 출력 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다.수열은 사전 순으로 증가하는 순서로 출력해야 한다. 문제 풀이 해당 문제는 순열중에서 조합과 관련된 문제이다. 조합은 순열과 달리 순서의 배치에 따라 다른 집합으로 보지 않기 때문에 중복된 숫자가 나올 수 없다. 그렇기 때문에 이러한 특성을 기억을 하고 재귀호출시 어떻게 해야 하는지..

• format_list_bulleted BackJoon/Algorithm
• · 2023. 4. 10.
• textsms

(15649) N과 M(1)

문제 문제 자연수 N과 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오.1부터 N까지 자연수 중에서 중복 없이 M개를 고른 수열 입력 첫째 줄에 자연수 N과 M이 주어진다. (1 ≤ M ≤ N ≤ 8) 출력 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다.수열은 사전 순으로 증가하는 순서로 출력해야 한다. 문제 풀이 해당 문제는 백트래킹 알고리즘으로 해결 할 수 있는 문제이다. 입력 되는 n 값 까지의 값을 담을 수 있는 길이가 n 인 배열를 만들고 방문여부를 확인 할 수 있는 visited boolean 배열도 같이 선언한다. arr = new int[n]; vi..

• format_list_bulleted BackJoon/Algorithm
• · 2023. 4. 10.
• textsms

(11727)2xn 타일링 2

문제 문제 2×n 직사각형을 1×2, 2×1과 2×2 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오.아래 그림은 2×17 직사각형을 채운 한가지 예이다. 입력 첫째 줄에 n이 주어진다. (1 ≤ n ≤ 1,000) 출력 첫째 줄에 2×n 크기의 직사각형을 채우는 방법의 수를 10,007로 나눈 나머지를 출력한다. 문제 풀이 해당 문제는 DP 알고리즘을 통해 해결 할 수 있는 문제이다. 기본 적으로 각 길이에 따른 해결 할 수 있는 경우의 수는 몇개인가를 미리 고민을 해봐야 풀 수 있다. 먼저 길이가 2 x 1 인 직사각형을 채우는 방법은 1개이다. 2 x 2 는 3개이다. 2 x 3 은 5개이다. 여기까지의 정보로 우리는 dp[i -1] + dp[i -2] * 2 식이 성립된다는 것을 알 수있다..

• format_list_bulleted BackJoon/Algorithm
• · 2023. 4. 9.
• textsms