Backtracking

Algorithm/Baekjoon Online Judge
[java] 백준 14002 (가장 긴 증가하는 부분 수열 4) Gold 4
문제 원문 링크 : https://www.acmicpc.net/problem/14002 14002번: 가장 긴 증가하는 부분 수열 4 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이 www.acmicpc.net Approach 이 문제는 백준 11053번 가장 긴 증가하는 수열 의 문제에서 가장 긴 부분 수열을 추가로 출력하는 문제이다. 11053번: 가장 긴 증가하는 부분 수열 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20,..
→2020.12.20
Algorithm/Baekjoon Online Judge
[java] 백준 11053 (가장 긴 증가하는 부분 수열) Silver 2
문제 원문 링크 : https://www.acmicpc.net/problem/11053 11053번: 가장 긴 증가하는 부분 수열 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이 www.acmicpc.net Approach LIS(Longest Increasing Subsequence)는 Backtracking을 이용한 DP 방식과 이분탐색 방식이 가능하다. DP 방식은 O(N^2) 의 시간복잡도를 가지며, 이분 탐색은 O(NlogN)의 시간복잡도를 가진다. 이 문제에서는 입력이 1000보다 작으므로 N..
→2020.12.19
Algorithm/Baekjoon Online Judge
[java] 백준 14888 (연산자 끼워넣기) Silver 1
문제 원문 링크: https://www.acmicpc.net/problem/14888 14888번: 연산자 끼워넣기 첫째 줄에 수의 개수 N(2 ≤ N ≤ 11)가 주어진다. 둘째 줄에는 A1, A2, ..., AN이 주어진다. (1 ≤ Ai ≤ 100) 셋째 줄에는 합이 N-1인 4개의 정수가 주어지는데, 차례대로 덧셈(+)의 개수, 뺄셈(-)의 개수, www.acmicpc.net Approach Backtracking 기법을 사용하여 모든 연산자의 모든 조합을 고려하는 BruteForce 문제이다. 연산자를 하나씩 늘려가며 값을 구해나가고 연산자를 다 사용하였을 때의 값이 최댓값/최솟값인지를 판별한다. 사용한 후 남은 연산자의 개수가 몇개 인지를 기록하여야 한다. Code /* no.14888 : 연..
→2020.12.10

• 이전
• 1
• 2
• 다음