📍문제 링크 https://school.programmers.co.kr/learn/courses/30/lessons/131705 📍알고리즘 분류 - 백트래킹 📍문제 풀이 - 중복된 수가 있을 수 있는 정수 배열이 주어진다. 정수 배열에서 3개의 숫자를 뽑아서 (조합) 합이 0이 되는 경우의 수를 구하라 백트래킹을 이용해서 조합을 구현할 수 있다 📍코드 (JavaScript) function solution(number) { const chosenNums = []; // 뽑힌 숫자들 (조합) const isUsed = []; // 중복을 막기 위해 사용됐는지 확인할 배열 let answer = 0; // 가짓수 // 백트래킹 function recursive(depth, start) { if (depth ..

📍문제 링크 https://www.acmicpc.net/problem/18233 18233번: 러버덕을 사랑하는 모임 첫 번째 줄에 정수 N, P, E가 공백으로 구분되어 주어진다. (1 ≤ N, P ≤ 20, 1 ≤ E ≤ 1,000,000) 그 다음 줄부터 N개의 줄에 걸쳐 회원 1부터 순서대로 xi와 yi가 공백으로 구분되어 주어진다. (1 ≤ xi www.acmicpc.net 📍알고리즘 분류 - 브루트포스 📍문제 풀이 (백트래킹) DFS를 활용해 nCp 조합을 구하고, 각 경우의 수가 범위를 만족하면서 전체 합이 E인 것을 구하면 된다 1. 조합을 구해야 하므로 백트래킹 코드를 만든다. 스택에는 실제 데이터가 아닌 인덱스만 담는 것이 간편하다 (중복을 제거하기 쉽고, 속도도 빠름) 2. p 가짓수..

📍문제 링크 https://www.acmicpc.net/problem/14889 14889번: 스타트와 링크 예제 2의 경우에 (1, 3, 6), (2, 4, 5)로 팀을 나누면 되고, 예제 3의 경우에는 (1, 2, 4, 5), (3, 6, 7, 8)로 팀을 나누면 된다. www.acmicpc.net 📍알고리즘 분류 - 브루트포스 - 백트래킹 📍문제 풀이 4 이상의 양수 N과 2차원 배열이 주어질 때, 1 ~ N 까지 숫자들을 절반으로 나누는 가짓수를 구하고 각각 비교한다 비교 방법) 집합에서 nP2 (순열) 을 구해서 그 좌표를 2차원 배열의 좌표값으로 사용해 모두 더한 것의 최소값을 비교하여 가장 최소값을 출력 1 ~ N 까지 숫자들을 절반으로 나누기 : 백트래킹 이용하여 배열 구하기 백트래킹으로 ..

📍문제 링크 https://www.acmicpc.net/problem/14502 14502번: 연구소 인체에 치명적인 바이러스를 연구하던 연구소에서 바이러스가 유출되었다. 다행히 바이러스는 아직 퍼지지 않았고, 바이러스의 확산을 막기 위해서 연구소에 벽을 세우려고 한다. 연구소는 크 www.acmicpc.net 📍알고리즘 분류 - 구현 - 그래프 이론 - 브루트포스 알고리즘 - 그래프 탐색 - 너비 우선 탐색 📍문제 풀이 - N(세로) * M(가로) 좌표 평면에 바이러스, 벽, 빈칸이 존재한다. 벽을 딱 3개만 세울 수 있을 때, 확보 가능한 안전영역의 최대넓이를 구하라 - 바이러스는 벽이 없는 상하좌우로 퍼질 수 있다 - 빨간 2 = 바이러스 좌표 - 파란 1 = 벽 - 초록 0 = 벽을 세우는 좌표 ..

📍문제 링크 https://www.acmicpc.net/problem/2961 2961번: 도영이가 만든 맛있는 음식 첫째 줄에 재료의 개수 N(1 ≤ N ≤ 10)이 주어진다. 다음 N개 줄에는 그 재료의 신맛과 쓴맛이 공백으로 구분되어 주어진다. 모든 재료를 사용해서 요리를 만들었을 때, 그 요리의 신맛과 쓴맛은 www.acmicpc.net 📍알고리즘 분류 - 브루트포스 - 비트마스킹 - 백트래킹 📍문제 풀이 - 두 수로 이루어진 배열을 원소로 갖는 이차원 배열이 주어질 때, 첫 번째 원소들의 곱과 두 번째 원소들의 합을 비교한 절대값이 최소가 되는 숫자를 찾아라! - depth를 1부터 N 까지 반복하며 백트래킹을 활용하면 될것 같다. 📍의사 코드 - depth = 1 부터 N 까지 반복하면서, 각..

📍문제 링크 https://www.acmicpc.net/problem/1759 1759번: 암호 만들기 첫째 줄에 두 정수 L, C가 주어진다. (3 ≤ L ≤ C ≤ 15) 다음 줄에는 C개의 문자들이 공백으로 구분되어 주어진다. 주어지는 문자들은 알파벳 소문자이며, 중복되는 것은 없다. www.acmicpc.net 📍알고리즘 분류 - 수학 - 브루트포스 - 조합론 - 백트래킹 📍문제 풀이 - 알파벳 N개가 주어질 때, 모음 최소 1개, 자음 최소 2개를 사용하여 만들 수 있는 암호를 모두 출력하라 - 백트래킹을 이용하여 사전순이 아니면 가지치기 📍의사 코드 - 백트래킹으로 가능한 경우의 수를 배열에 저장하다가, 사전 순이 어긋나면 가지치기 실행 - 사용한 알파벳을 체크할 때 isUsed 배열에 자음인..

📍문제 링크 https://www.acmicpc.net/problem/15666 15666번: N과 M (12) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net 📍알고리즘 분류 - 백트래킹 📍문제 풀이 - N개의 중복을 허용하는 수가 주어질 때, 중복을 허용하여 M개를 고르는 경우의 수를 모두 출력한다 (중복조합) - 비내림차순으로 출력한다 (오름차순 + 중복 허용) 📍코드 (JavaScript) const [in1, in2] = require("fs") .readFileSync("/dev/stdin") .toString() .trim()..

📍문제 링크 https://www.acmicpc.net/problem/15686 15686번: 치킨 배달 크기가 N×N인 도시가 있다. 도시는 1×1크기의 칸으로 나누어져 있다. 도시의 각 칸은 빈 칸, 치킨집, 집 중 하나이다. 도시의 칸은 (r, c)와 같은 형태로 나타내고, r행 c열 또는 위에서부터 r번째 칸 www.acmicpc.net 📍알고리즘 분류 - 구현 - 브루트포스 - 백트래킹 📍문제 풀이 - N * N 크기의 좌표 평면에서 2인 좌표가 최소 M개, 최대 N * N - 1 개, 1 도 몇 개 주어진다. - 1인 좌표를 모두 순회하면서 2인 좌표까지의 맨해튼 거리의 총 합이 최소가 되는 것을 도출하면 된다. - 2인 좌표값이 있는 배열을 백트래킹해나가야 하고, 순서는 상관없다 (조합) -..