본문 바로가기
728x90

전체 글202

[BOJ/백준] 16197 두 동전 ● [문제번호 16197] 두 동전 https://www.acmicpc.net/problem/16197 16197번: 두 동전 N×M 크기의 보드와 4개의 버튼으로 이루어진 게임이 있다. 보드는 1×1크기의 정사각형 칸으로 나누어져 있고, 각각의 칸은 비어있거나, 벽이다. 두 개의 빈 칸에는 동전이 하나씩 놓여져 있고, www.acmicpc.net ● 알아야 할 것 : BFS : 구조체 (struct) ● 풀이 과정 : 처음에 Queue를 2개 써서 풀어보려고 시도를 해보았다. 하지만 다음 회차에 이동할 자리가 {동전1 : 벽 / 동전2 : 빈 칸}인 경우 처리하기가 어려워지고 지저분해져서 고민을 했다. : 구글링을 통해 알아낸 아이디어는 Queue의 자료형을 pair 2개로 하는 것이었다. 그래서 잘 .. 2021. 10. 25.
[BOJ/백준] 14500 테트로미노 ● [문제번호 14500] 테트로미노 https://www.acmicpc.net/problem/14500 14500번: 테트로미노 폴리오미노란 크기가 1×1인 정사각형을 여러 개 이어서 붙인 도형이며, 다음과 같은 조건을 만족해야 한다. 정사각형은 서로 겹치면 안 된다. 도형은 모두 연결되어 있어야 한다. 정사각형의 변 www.acmicpc.net ● 알아야 할 것 : 브루트 포스 (Brute Force) ● 풀이 과정 : [500 - 브루트 포스] 문제집에 있는 문제 : 풀이 과정이나 떠올리기 어려워서 구글링을 했다. BFS 방법 + 'ㅗ' 형태 예외 처리를 하는 코드가 꽤 있었지만, 브루트 포스에 맞게 하드코딩했다. : 각 형태에 마다 나올 수 있는 모습을 고려한다. (총 19가지) 각 형태마다 범위.. 2021. 10. 25.
[BOJ/백준] 15658 연산자 끼워넣기 (2) ● [문제번호 15658] 연산자 끼워넣기 (2) https://www.acmicpc.net/problem/15658 15658번: 연산자 끼워넣기 (2) 첫째 줄에 수의 개수 N(2 ≤ N ≤ 11)가 주어진다. 둘째 줄에는 A1, A2, ..., AN이 주어진다. (1 ≤ Ai ≤ 100) 셋째 줄에는 합이 N-1보다 크거나 같고, 4N보다 작거나 같은 4개의 정수가 주어지는데, 차례대 www.acmicpc.net ● 알아야 할 것 : 브루트 포스 (Brute Force) : 재귀 ● 풀이 과정 : 14888 연산자 끼워넣기 문제에서 연산자의 총 갯수가 N-1보다 크거나 같고, 4N보다 작거나 같다는 조건이 추가된다. 그런데 조금 생각해보니 14888 연산자 끼워넣기 문제를 풀 때 이러한 경우까지 커.. 2021. 10. 25.
[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.
728x90

티스토리툴바