본문 바로가기
728x90

Baekjoon/[Code.plus] 알고리즘 기초 2／261

[BOJ/백준] 14391 종이 조각 ● [문제번호 14391] 종이 조각 https://www.acmicpc.net/problem/14391 14391번: 종이 조각 영선이는 숫자가 쓰여 있는 직사각형 종이를 가지고 있다. 종이는 1×1 크기의 정사각형 칸으로 나누어져 있고, 숫자는 각 칸에 하나씩 쓰여 있다. 행은 위에서부터 아래까지 번호가 매겨져 있고, www.acmicpc.net ● 알아야 할 것 : 비트마스크 : 브루트 포스 (Brute Force) ● 풀이 과정 : 주어진 문제를 읽고 조각의 최대 총합이라면, 행렬의 가로로만 자른 것과 행렬의 세로로만 자른 것을 비교하면 되는 거 아닌가? 왜 중간에 잘라야하지? 싶어서 구현했더니 채점중의 %가 나오기도 전에 '틀렸습니다.' 가 나왔다. 중간에 자를 필요가 있는 반례가 무엇일지 아무.. 2021. 9. 9.
[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. 9. 9.
[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 : 재귀 ● 풀이 과정 : 구현을 계속 해도 '시간 초과', '틀렸습니다' 를 반복해서 문제를 다르게 이해했나 생각해서 구글링을 했다. : {기존 배열에서 1개라도 선택했는가} + {부분수열의 원소 총합 = S} 인 경우 부분 수열의 갯수(cnt)를 올린다. 그리고 index가 기존 수열의 끝까.. 2021. 9. 9.
[BOJ/백준] 11723 집합 ● [문제번호 11723] 집합 https://www.acmicpc.net/problem/11723 11723번: 집합 첫째 줄에 수행해야 하는 연산의 수 M (1 ≤ M ≤ 3,000,000)이 주어진다. 둘째 줄부터 M개의 줄에 수행해야 하는 연산이 한 줄에 하나씩 주어진다. www.acmicpc.net ● 알아야 할 것 : NULL ● 풀이 과정 : 문제에서 주어진 내용에 따라 간단하게 구현가능하다. ● 주의 할 것 : 숫자 입력 후 문자열 입력받을 때 공백있는 문자열이 있는 경우, ws 또는 cin.ignore()를 이용해야한다. 하지만 아래 코드에서는 공백없는 문자열을 입력받았으므로 상관없다. ● 참고 할 것 : 숫자 입력 후 공백있는 문자열 입력시 주의사항 https://pirateturtle.. 2021. 9. 9.
728x90

티스토리툴바