'📜 코딩테스트/BAEKJOON\백트래킹' 카테고리의 글 목록

백준 14889번 : 스타트와 링크 (JAVA) 문제 풀이

2021.01.11

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명의 선수를 팀 A, B 로 나눴을 때 -> 모든 경우의 팀 구성을 구한 뒤, 그 팀의 능력치를 다 더해서 차이가 가장 작은 값을 출력 하면 된다. 차이가 0이 되면 더이상 다른 경우의 수를 따져보지 않아도 된다. (시간 복잡도 줄이기) 팀 정하기 선수 1, 2, 3, 4가 있다고 하면, 각 팀에는 2명 씩 나누면 된다. 예를 들어, 팀 A에 선수(1, 2)가 있으면, 자동으로 나머지 팀 B..

📜 코딩테스트/BAEKJOON\백트래킹

백준 14888번 : 연산자 끼워넣기 (JAVA) 문제 풀이

2021.01.11

www.acmicpc.net/problem/14888 14888번: 연산자 끼워넣기 첫째 줄에 수의 개수 N(2 ≤ N ≤ 11)가 주어진다. 둘째 줄에는 A1, A2, ..., AN이 주어진다. (1 ≤ Ai ≤ 100) 셋째 줄에는 합이 N-1인 4개의 정수가 주어지는데, 차례대로 덧셈(+)의 개수, 뺄셈(-)의 개수, www.acmicpc.net 문제 분석 처음의 연산할 숫자의 개수가 주어지고, 둘째 줄에는 연산할 수, 셋째 줄에는 연산자의 개수가 주어진다. 예를 들어 입출력 2를 보면, 3 3 4 5 1 0 1 0 연산자는 + , x 각 1개씩 사용 가능하다. 모든 경우의 연산을 보면, 3 + 4 x 5 = 35 3 x 4 + 5 = 17 결과가 35, 17인 두가지 경우가 나온다. 먼저 재귀 함..

📜 코딩테스트/BAEKJOON\백트래킹

백준 9663번 : N-Queen (JAVA) 문제 풀이

2020.12.22

www.acmicpc.net/problem/9663 9663번: N-Queen N-Queen 문제는 크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다. N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하는 프로그램을 작성하시오. www.acmicpc.net 문제 분석 퀸의 공격 방향 퀸의 특성상 한줄에 하나씩 밖에 둘수가 없게 된다. 일단 먼저 N이 4라고 가정하고, 퀸을 배치해보자. 4 X 4 체스판에 [0][0] 위치에 1번째 퀸을 둔다고 하면, 1번째 퀸, [0][0]에 두는 경우 다른 퀸을 배치하지 못하는 위치(퀸의 공격을 받을 수 있는 곳)은 위의 그림 처럼 된다. 그러면 2번째 퀸을 놓을 수 있는 곳은, [1][2] 와 [1][3] 두 가지 이렇게 [1][2]와 [1]..

📜 코딩테스트/BAEKJOON\백트래킹

백준 15650번 : N과 M(2) (JAVA) 문제 풀이

2020.12.16

www.acmicpc.net/problem/15650 15650번: N과 M (2) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net 문제 분석 저번 N과 M(1) 에서 살짝 변형이 된 문제다. 예제를 먼저 살펴보면 자연수의 범위는 4이고, 2개씩 출력시키면 되는데, 같은 수가 중복되서 연속되면 안되고, 수열도 중복이 되면 안된다. (예를 들어, [1 2] 와 [2 1]은 같다고 본다.) 실행 과정 그림처럼, arr[0]에 for문으로 돌면서 i값을 넣어주고, 다음 arr[1]값은 재귀 호출을 돌면서 채우는 식으로 진행된다. 이 실행 과정을..

📜 코딩테스트/BAEKJOON\백트래킹

백준 15649번 : N과 M(1) (JAVA) 문제 풀이

2020.12.01

www.acmicpc.net/problem/15649 15649번: N과 M (1) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net 이번 문제는 백트래킹 단계의 입문 문제 이다. 백트래킹 문제는, 트리 형태의 노드들을 깊이 우선 탐색 (DFS) 을 수행하면서, 노드의 유망성을 판단하여, 유망하지 못하다고 생각하면 가지치기를 하고(풀이시간 단축), 다시 부모 노드로 돌아가서 다른 자식 노드를 탐색하는 방식이다. 문제 풀이 dfs의 기본 틀은 아래와 같다. 재귀를 끝낼 조건을 정해줘야 하는데, index가 M이랑 같을 시점에 arr 배열의 모..

백준 14889번 : 스타트와 링크 (JAVA) 문제 풀이

백준 14888번 : 연산자 끼워넣기 (JAVA) 문제 풀이

백준 9663번 : N-Queen (JAVA) 문제 풀이

백준 15650번 : N과 M(2) (JAVA) 문제 풀이

백준 15649번 : N과 M(1) (JAVA) 문제 풀이

티스토리툴바