알고리즘/분할4 [백준 1780] 종이의 개수 / 자바 / 분할정복(기본) #문제 레벨: S2알고리즘: 분할정복(기본)풀이시간: 20분힌트 참조 유무: 무https://www.acmicpc.net/problem/1780#문제 풀이 이 문제는 피보나치 문제(easy)와 마찬가지로 분할정복의 기초 문제이다. (개인적인 생각으로는 그렇다.)분할정복 문제를 풀게 된다면 반드시 이 문제는 풀어보고 갔으면 좋겠다.분할정복 말은 거창하지만 가장 작은 문제로 쪼갤 수 있을 때까지 쪼갠 후 작은 문제들을 풀이하는 것이다. 이 문제에서는 풀어주세요 ~ 라고 말하는 것처럼 문제를 쪼개는게 직접적으로 나와있다. 큰 정사각형을 모든 수가 같을 때까지 9등분으로 나누면 되는 것이다. 쉽지 않은가. 나머지는 코드 참고 바란다. #풀이 코드 import java.ut.. 2024. 8. 29. [백준 2261] 가장 가까운 두 점 / 자바 / 분할정복 or 라인스위핑 #문제 레벨: P2알고리즘: 분할정복, 라인스위핑풀이시간: 1시간힌트 참조 유무: 유https://www.acmicpc.net/problem/2261#문제 풀이 이 문제는 디게 어렵다. 이분의 블로그를 보고 풀이를 이해했다. 이 분의 글을 보기 전에 이것만 기억해라. 아이디어는 간단하다(라인 스위핑 풀이에 관한). 직사각형을 생각하자. 우린 그 직사각형을 오른쪽으로 밀며 직사각형 안에 있는 점들끼리 비교할 것이다. 그러나 더 좋은 효율을 내기 위해 그 직사각형을 가로 혹은 세로를 점점 줄이면서 탐색하는 것이다. https://st-lab.tistory.com/256 [백준] 2261번 : 가장 가까운 두 점 - JAVA [자바]https://www.acmicpc.net/pr.. 2024. 8. 29. [백준 2263] 트리의 순회 / 자바 /분할정복 문제 레벨: G1알고리즘: 분할정복 풀이시간: 11:23힌트 참조 유무: https://www.acmicpc.net/problem/2263 1 번째 시도 이 문제는 트리가 어떻게 생겼는지 주지 않았다. 그래서 포인트는 중위식에서 무엇을 알 수 있고 후위식에서 무엇을 얻을지 캐치하고 트리를 그려보는 것이다.트리가 이렇게 있다고 한다면,중위 : 4 2 5 1 6 3 7 후위: 4 5 2 6 7 3 1 이렇게 순회할 것이다. 이로서 우린 후위식에서 루트가 어떤 건지 알 수 있고 중위 식에서 루트를 기준으로 왼쪽 노드와 오른쪽 노드가 무엇인지 알 수 있다. +) 위 트리의 전위 : 1 2 4 5 3 6 7import java.io.BufferedReader;impor.. 2024. 7. 2. [백준 2630] 색종이 만들기/ 자바 문제 레벨: S2알고리즘: 구현 + 분할정복풀이시간: 40분힌트 참조 유무: 무https://www.acmicpc.net/problem/2630 1 번째 시도 [알고리즘 설명]이 문제는 분할정복 + 구현의 대표적인 문제이다.직관적으로 나타나 있듯 4개로 나누어 탐색하여야 하고답을 체킹하는 방식 + 4개로 나누는 방식을 잘 구현해야 한다. 필자는 처음 구현할 때 다 나눈 후 답을 체킹하는 방식으로 구현하려고 했다.그러나 구현에 어려움을 겪어 , 답을 체킹하고 아니면 분할하는 방식으로 구현하였다. 나처럼 구현에 어려움을 겪는 분들은 이런 식으로 하면 좋을 것 같다.import java.io.BufferedReader;import java.io.InputStreamReader;import .. 2024. 7. 2. 이전 1 다음
