brute Force5 [BOJ] 백준 16637번 - 괄호 추가하기(with Java) 알고리즘 브루트포스로 접근해서 풀어보다가 못풀고 시간만 보낼것 같아서 결국 구글링했다. 문제 분류에는 브루트포스만 적혀있지만 DFS + 재귀 조합을 통해서도 풀 수 있었다. '괄호를 채워넣지 않는 경우(1)'와 '괄호를 채워넣는 경우(2)' 2가지로 나눠볼 수 있겠다. (1)의 경우에는 total로 넘겨준 값을 유지하면서 오른쪽의 숫자들을 계속 연산해준다. (2)의 경우에는 total의 바로 뒤에 오는 숫자들에 대해서 먼저 연산해주고, total을 유지한채 다음 DFS를 수행한다. 만약에 주어진 연산자들을 모두 사용하면 total과 max값을 갱신시켜준다. 이후에 다음 DFS를 수행하지 않고 함수를 빠져나오면 된다. 예시 예제로 주어진 입력1의 '3+8*7-9*2'를 살펴보자. 괄호를 추가하지 않고 이 .. 2022. 1. 5. [BOJ] 백준 2468번 - 안전 영역(with Java) 알고리즘 문제를 읽어보면 DFS를 사용하여 연결 요소의 개수를 알아내는 [BOJ] 4963번 - 섬의 개수 문제와 비슷하다고 느껴질 수도 있다. 이 문제의 최대 변수는 '강수량'이다. 문제에서는 '비의 양에 따라서 생기는 안전영역의 최대 개수'를 구하라고 하는데, 입력에는 비의 양이 주어지지 않고 노트에는 잘 와닿지 않는 힌트가 적혀있어서 문제를 완벽하게 이해하지 못한 상태에서 풀게 되었다. 우선 DFS 메소드의 경우에는 '섬의 개수' 문제에서 사용한 방식을 그대로 적용하되, 8방향에서 4방향으로 바꿔주고 'arr[nr][nc]=1'이 아닌 'arr[nr][nc]>height'로 바꿔줘야 빗물의 높이보다 영역의 높이가 높아져서 안전 영역이 생성된다. 이제 메인 메소드를 보자. 빗물의 높이 정보는 나와있지.. 2021. 7. 18. [BOJ] 백준 2231번 - 분해합(with Java) 알고리즘 앞서 접한 [BOJ] 2798번 - 블랙잭 문제의 유형과 비슷하게 브루트 포스 알고리즘을 적용하는 문제이다. 분해합 N의 생성자 M의 최솟값을 구하기 위해서 1부터 입력값 input 바로 전까지의 모든 숫자들에 대해서 생성자가 만들어지는지 확인해보기로 하였다. i값을 받아와서 sum을 초기화해주고 문자열 배열로 바꿔서 각각의 자리수를 sum에 더해주었다. 마지막으로 sum과 Integer의 최대값으로 초기화해준 min의 비교를 통해서 생성자 M의 최솟값을 찾아주었다. 소스코드 문제링크 2231번: 분해합 어떤 자연수 N이 있을 때, 그 자연수 N의 분해합은 N과 N을 이루는 각 자리수의 합을 의미한다. 어떤 자연수 M의 분해합이 N인 경우, M을 N의 생성자라 한다. 예를 들어, 245의 분해합.. 2021. 7. 13. [BOJ] 백준 2798번 - 블랙잭(with Java) 알고리즘 필자는 브루트 포스 알고리즘을 이 문제를 통해서 처음 접했는데, 머릿속에 알고리즘은 그려졌지만 코드로 구현하는 것이 쉽지 않았다. 알고리즘은 단순히 숫자를 3개 뽑아서 합한 값이 M을 넘지 않게 만들어주면 되므로 매우 간단하다. 삼중 for문을 써볼만한 기회가 없어서 그랬던것 같다. 소스코드 문제링크 2798번: 블랙잭 첫째 줄에 카드의 개수 N(3 ≤ N ≤ 100)과 M(10 ≤ M ≤ 300,000)이 주어진다. 둘째 줄에는 카드에 쓰여 있는 수가 주어지며, 이 값은 100,000을 넘지 않는 양의 정수이다. 합이 M을 넘지 않는 카드 3장 www.acmicpc.net 2021. 7. 13. [BOJ] 백준 1059번 - 좋은 구간(with Java) 알고리즘 좋은 구간이 집합 S의 가장 작은 숫자보다 앞에 위치한 경우와 집합 S의 숫자들 사이에 위치한 경우에 대해서 브루트 포스 알고리즘을 적용하면 쉽게 해결할 수 있다. 다만 필자는 숫자의 범위를 정해주는 부분에서 계속 오류가 나서 조금 애를 먹었다. 소스코드 문제링크 1059번: 좋은 구간 [9, 10], [9, 11], [9, 12], [10, 11], [10, 12] www.acmicpc.net 2021. 7. 13. 이전 1 다음
