알고리즘/Class 324 백준 BOJ 1992번 접근 방법 이전에 풀었던 1780번과 유사한 문제다. 다른 점이 있다면 이전에 푼 것은 9분할, 이번 문제는 4분할 한다는 점이다. https://edvedv.tistory.com/28?category=1038364 백준 BOJ 1780번 접근 방법 이 문제는 분할정복으로 풀면 된다. 분할정복은 따로 설명할 필요도 없이 쉬운 개념인데, 복잡한 큰 문제를 해결할 수 있는 단순한 부분 문제로 나누어 처리한 후 다시 합쳐서 해결하 edvedv.tistory.com 똑같이 재귀함수로 분할 정복하면 쉽게 풀 수 있다. 다만 출력을 괄호로 묶어서 하는 것만 신경써주면 된다. 코드 import java.util.*; public class Main { public static int[][] arr; public st.. 2022. 8. 22. 백준 BOJ 1931번 접근 방법 탐욕(Greedy) 알고리즘의 대표적인 문제다. 그리디 알고리즘은 간단하게 뒤는 생각하지 않고 각 단계에서 가장 최선의 선택을 하는 기법이다. 각 단계의 최선의 선택이 전체적으로도 최선이길 바라는 기법인데, 당연하게도 모든 경우에서 적용할 수는 없다. 그리디 알고리즘을 사용할 수 있는 유형의 문제들이 있는데, 바로 활동 선택 문제와 분할 가능 배낭 문제다. 이번 문제는 이 중에서 활동 선택 문제로, 한 자원이 하나의 활동만 작업할 수 있을 때 최대한 많은 활동을 할 수 있는 수를 선택하는 문제다. 이 문제에서는, 이전의 선택 결과가 이후의 결과에 영향을 미치지 않기 때문에 적용할 수 있다. 그렇다면, 그리디 알고리즘을 이 문제에 어떻게 적용해야 하는가? 먼저 생각해야 할 것은, 이전의 선택 결.. 2022. 8. 22. 백준 BOJ 1927번 접근 방법 최소 힙을 구현하는 문제다. 힙(Heap) 힙은 최댓값 및 최솟값을 찾아내는 연산을 빠르게 하기 위해 고안된 완전이진트리를 이용한 자료구조다. 힙은 부모 노드의 값과 자식노드의 값 사이에 대소관계가 성립한다. 대소관계에 따라 힙에는 두가지 종류가 있는데, 최대 힙과 이 문제에서 구현해야 할 최소 힙이다. 최대 힙 : 부모노드의 키값이 자식노드의 키값보다 항상 큰 힙 최소 힙 : 부모노드의 키값이 자식노드의 키값보다 항상 작은 힙 키값의 대소관계는 부모노드와 자식노드 간에만 성립하고, 형제 노드 간에는 성립하지 않는다. 힙을 구현할 때는 일반적으로 배열로 구현하게 되는데, 몇가지 특징이 있다. 구현의 용이함을 위해 루트 노드의 인덱스는 1 부터 시작한다. 왼쪽 자식 노드 인덱스 = 부모 노드 인.. 2022. 8. 21. 백준 BOJ 1780번 접근 방법 이 문제는 분할정복으로 풀면 된다. 분할정복은 따로 설명할 필요도 없이 쉬운 개념인데, 복잡한 큰 문제를 해결할 수 있는 단순한 부분 문제로 나누어 처리한 후 다시 합쳐서 해결하는 방법이다. 문제로 돌아와서, 해결 과정은 아래와 같다. 종이가 모두 동일한 숫자인지 검사한다. 아니라면 9개의 영역으로 나눈다. 각 영역별로 1, 2번을 반복한다. 코드 import java.util.*; public class Main { public static int[][] paper; public static int A = 0; // -1 public static int B = 0; // 0 public static int C = 0; // 1 public static void main(String[] arg.. 2022. 8. 20. 이전 1 2 3 4 5 6 다음
