Baekjoon26 [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. [BOJ] 백준 7562번 - 나이트의 이동(with Java) 알고리즘 [BOJ] 2178번 - 미로 탐색 문제와 마찬가지로 각각의 정점에 대한 행과 열 및 방문 여부를 표시하기 위한 별도의 클래스(Vertex)를 생성해주고 문제풀이를 위한 배열들을 초기화하는 과정을 거쳐야 한다. 나이트는 최대 8방향으로 이동할 수 있기 때문에 미로 탐색 문제에서 설명했던 것과 마찬가지로 탐색에 위험부담이 있는 DFS를 사용하지 않고 탐색 효율이 좋은 BFS를 사용한다. 또한, 미로 탐색 문제에서와 동일하게 나이트가 출발점에서 도착점까지 갈 수 있는 최단거리를 찾기 위해서 각각의 정점에 대한 부모 배열을 만들었고, 탐색이 끝난 후에 도착점으로부터 부모 배열을 타고 올라가서 시작 정점을 찾는 방식으로 최단거리를 구하였다. 미로 탐색 문제와의 차이점은 단지 방향이 4개에서 8개로 늘어.. 2021. 7. 11. [BOJ] 백준 2178번 - 미로 탐색(with Java) 알고리즘 인접리스트를 사용해서 문제를 풀었던 [BOJ] 1260번 - DFS와 BFS와는 달리 2차원의 미로에서 최단거리를 찾기 위한 그래프 탐색은 조금 복잡하다. 우선 각각의 정점에 대한 행과 열 및 방문 여부를 표시하기 위해서 'Vertex' 클래스 생성해주고 문제풀이를 위한 배열들을 초기화하는 과정을 거쳐야한다. 이 문제는 위험부담이 있는 DFS와는 달리 효율이 좋은 BFS를 사용하여 풀기로 결정하였다. DFS는 최단거리를 한번에 찾는 경우에 최고의 효율을 보이지만, 그렇지 못하는 경우에는 백트래킹을 통해서 다른 경로를 재탐색해야하는 문제가 발생한다. 반면에 BFS는 그물망을 펼치는 것처럼 모든 경로를 넓지만 천천히 탐색하기 때문에 경로를 재탐색하는 문제가 발생하지 않는다. 따라서 이 문제의 경우에.. 2021. 7. 11. 이전 1 2 3 다음
