본문 바로가기
728x90

전체 글205

[BOJ/백준] 14888 연산자 끼워넣기 ● [문제번호 14888] 연산자 끼워넣기 https://www.acmicpc.net/problem/14888 14888번: 연산자 끼워넣기 첫째 줄에 수의 개수 N(2 ≤ N ≤ 11)가 주어진다. 둘째 줄에는 A1, A2, ..., AN이 주어진다. (1 ≤ Ai ≤ 100) 셋째 줄에는 합이 N-1인 4개의 정수가 주어지는데, 차례대로 덧셈(+)의 개수, 뺄셈(-)의 개수, www.acmicpc.net ● 알아야 할 것 : 브루트 포스 (Brute Force) : 재귀 ● 풀이 과정 : [521 - 브루트 포스 - 순열(연습)] 문제집에 있는 문제 : 어떻게 모든 경우의 수를 탐색할까 하다가 주어진 수의 순서를 바꾸면 안된다. 라는 말을 고려하여 수를 나열해놓고 사이사이에 사칙연산을 하나씩 대입하며.. 2021. 10. 25.
[BOJ/백준] 14225 부분수열의 합 ● [문제번호 14225] 부분수열의 합 https://www.acmicpc.net/problem/14225 14225번: 부분수열의 합 수열 S가 주어졌을 때, 수열 S의 부분 수열의 합으로 나올 수 없는 가장 작은 자연수를 구하는 프로그램을 작성하시오. 예를 들어, S = [5, 1, 2]인 경우에 1, 2, 3(=1+2), 5, 6(=1+5), 7(=2+5), 8(=1+2+5)을 만들 www.acmicpc.net ● 알아야 할 것 : 재귀 : 브루트 포스 (Brute Force) ● 풀이 과정 : 만들 수 있는 부분수열의 합을 체크하는 배열을 만들어 놓고 만들 수 있는 부분수열의 합을 모두 만들어본다. 그 다음 1부터 시작하여 못 만든 자연수를 찾아내 출력하면 된다. ● 주의 할 것 : NULL ●.. 2021. 10. 25.
[BOJ/백준] 1182 부분수열의 합 ● [문제번호 1182] 부분수열의 합 https://www.acmicpc.net/problem/1182 1182번: 부분수열의 합 첫째 줄에 정수의 개수를 나타내는 N과 정수 S가 주어진다. (1 ≤ N ≤ 20, |S| ≤ 1,000,000) 둘째 줄에 N개의 정수가 빈 칸을 사이에 두고 주어진다. 주어지는 정수의 절댓값은 100,000을 넘지 않는다. www.acmicpc.net ● 알아야 할 것 : DFS : 재귀 ● 풀이 과정 : [540 - 브루트 포스 - 비트마스크] 문제집에 있는 문제 : 구현을 계속 해도 '시간 초과', '틀렸습니다' 를 반복해서 문제를 다르게 이해했나 생각해서 구글링을 했다. : {기존 배열에서 1개라도 선택했는가} + {부분수열의 원소 총합 = S} 인 경우 부분 수열.. 2021. 10. 25.
[BOJ/백준] 6603 로또 ● [문제번호 6603] 로또 https://www.acmicpc.net/problem/6603 6603번: 로또 입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스는 한 줄로 이루어져 있다. 첫 번째 수는 k (6 < k < 13)이고, 다음 k개 수는 집합 S에 포함되는 수이다. S의 원소는 오름차순으로 www.acmicpc.net ● 알아야 할 것 : DFS : 재귀 ● 풀이 과정 : [520 - 브루트 포스 - 순열] 문제집에 있는 문제 : 기본적인 DFS문제에서 조합을 위한 중복 방지 조건을 추가 한 듯하다. ● 주의 할 것 : 순열이 아닌 조합이므로 중복 순열은 제거해야한다. 여기 문제에서는 중복 순열을 제거하기 위해 오름차순이라는 조건을 걸어서 해결하였다. ● 참고 할 것 :.. 2021. 10. 25.
[BOJ/백준] 14889 스타트와 링크 ● [문제번호 14889] 스타트와 링크 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 ● 알아야 할 것 : DFS : 재귀 ● 풀이 과정 : [530 - 브루트 포스 - 재귀] 문제집에 있는 동일한 문제 : DFS의 기본 구현 형식에서 크게 벗어나지 않지만, {N/2 명 까지 선택} + {조합} 을 고려하여 구현하면 된다. : bool로 이루어진 team이라는 1차원 배열을 만들어 각 사람(index)이 스타트 팀(true)인지 링크 팀(false)인지를 구분한.. 2021. 10. 5.
[BOJ/백준] 14888 연산자 끼워넣기 ● [문제번호 14888] 연산자 끼워넣기 https://www.acmicpc.net/problem/14888 14888번: 연산자 끼워넣기 첫째 줄에 수의 개수 N(2 ≤ N ≤ 11)가 주어진다. 둘째 줄에는 A1, A2, ..., AN이 주어진다. (1 ≤ Ai ≤ 100) 셋째 줄에는 합이 N-1인 4개의 정수가 주어지는데, 차례대로 덧셈(+)의 개수, 뺄셈(-)의 개수, www.acmicpc.net ● 알아야 할 것 : 브루트 포스 (Brute Force) : 재귀 ● 풀이 과정 : 어떻게 모든 경우의 수를 탐색할까 하다가 주어진 수의 순서를 바꾸면 안된다. 라는 말을 고려하여 수를 나열해놓고 사이사이에 사칙연산을 하나씩 대입하며 재귀하는 방법으로 구현했다. : 맨 처음 숫자만 total에 더하.. 2021. 10. 5.
728x90

티스토리툴바