[백준/C++] 17136번: 색종이 붙이기(G2) 문제 https://www.acmicpc.net/problem/17136 17136번: 색종이 붙이기 과 같이 정사각형 모양을 한 다섯 종류의 색종이가 있다. 색종이의 크기는 1×1, 2×2, 3×3, 4×4, 5×5로 총 다섯 종류가 있으며, 각 종류의 색종이는 5개씩 가지고 있다. 색종이를 크 www.acmicpc.net 사용한 알고리즘 2022.01.29 - [PS/Algorithm] - [알고리즘 개념정리] 6. 완전탐색/백트래킹 -> 백트래킹. 모든 경우를 따지지 않고 가지치기하는 문제 풀이 5x5색종이부터 1x1색종이까지 차례대로 붙어본다. 붙일 수 있다면(범위가 10x10이내, 사용횟수 use값이 5 이내) 색종이를 붙인 후 재귀함수로 들어간다. 색종이를 붙일때는 matrix 값을 0으로 바.. 2022. 1. 31. [백준/C++] 2661번: 좋은수열(G4) 문제 https://www.acmicpc.net/problem/2661 2661번: 좋은수열 첫 번째 줄에 1, 2, 3으로만 이루어져 있는 길이가 N인 좋은 수열들 중에서 가장 작은 수를 나타내는 수열만 출력한다. 수열을 이루는 1, 2, 3들 사이에는 빈칸을 두지 않는다. www.acmicpc.net 사용한 알고리즘 2022.01.29 - [PS/Algorithm] - [알고리즘 개념정리] 6. 완전탐색/백트래킹 -> 백트래킹. 모든 경우에 대해 따져주지 않아도 되는 가지치기 문제 풀이 나쁜 수열에는 마지막에 어떤 숫자를 추가하더라도 나쁜 수열이다. 따라서 우리는 좋은 수열들에 대해서만 추가적으로 숫자를 붙여가며 좋은 수열인지 테스트하면 된다. *solve함수 지금까지 만든 수열이 좋은 수열일 때만 .. 2022. 1. 31. [백준/C++] 1182번: 부분수열의 합(S2) 문제 https://www.acmicpc.net/problem/1182 1182번: 부분수열의 합 첫째 줄에 정수의 개수를 나타내는 N과 정수 S가 주어진다. (1 ≤ N ≤ 20, |S| ≤ 1,000,000) 둘째 줄에 N개의 정수가 빈 칸을 사이에 두고 주어진다. 주어지는 정수의 절댓값은 100,000을 넘지 않는다. www.acmicpc.net 사용한 알고리즘 2022.01.29 - [PS/Algorithm] - [알고리즘 개념정리] 6. 완전탐색/백트래킹 -> 백트래킹. 모든 상태에 대해 어떤 조건을 따져주는 문제 풀이 현재 보고있는 원소를 '포함시킨다/포함시키지 않는다' 라는 두가지 경우로 나누어 생각해보면 된다. 소스코드 #include typedef long long ll; using na.. 2022. 1. 30. [백준/C++] 15650번: N과 M (2)(S3) 문제 https://www.acmicpc.net/problem/15650 15650번: N과 M (2) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net 사용한 알고리즘 2022.01.29 - [PS/Algorithm] - [알고리즘 개념정리] 6. 완전탐색/백트래킹 -> 백트래킹. 가능한 모든 경우를 단순히 생성하는 문제이다. 재귀로 상태를 전이시켜가며 문제를 풀어보자. 풀이 처음에는 숫자를 넣을 인덱스만 인자로 전달했었다. 그렇게 하면 현재 넣을 숫자가 무엇인지 반복문을 돌면서 알아내야 한다. 따라서 필요한 상태는 현재 넣을 숫자와 현재.. 2022. 1. 30. [백준/C++] 1747번: 소수&팰린드롬(S1) 문제 https://www.acmicpc.net/problem/1747 1747번: 소수&팰린드롬 어떤 수와 그 수의 숫자 순서를 뒤집은 수가 일치하는 수를 팰린드롬이라 부른다. 예를 들어 79,197과 324,423 등이 팰린드롬 수이다. 어떤 수 N (1 ≤ N ≤ 1,000,000)이 주어졌을 때, N보다 크거나 같고, www.acmicpc.net 사용한 알고리즘 2022.01.29 - [PS/Algorithm] - [알고리즘 개념정리] 6. 완전탐색/백트래킹 -> 완전 탐색 각각의 경우들을 좀 더 복잡하게 따져주는 문제이다. 보통 각 경우를 나타내는 무언가를 인수로 받아서 그 경우에 대한 테스트를 진행하는 함수를 따로 작성한다. 시간 복잡도 문제를 풀기에 앞서, 이 문제를 완전탐색 알고리즘으로 풀.. 2022. 1. 29. [백준/C++] 6604번: Matrix Chain Multiplication(S4) 문제 https://www.acmicpc.net/problem/6604 6604번: Matrix Chain Multiplication For each expression found in the second part of the input file, print one line containing the word "error" if evaluation of the expression leads to an error due to non-matching matrices. Otherwise print one line containing the number of elementary multipli www.acmicpc.net 사용한 알고리즘 2022.01.27 - [PS/Algorithm] - [알고리즘 개념정리].. 2022. 1. 27. 이전 1 2 3 4 5 6 7 다음
