분할정복5 [백준 1799] 비숍 / 자바 / 백트래킹 + 분할정복 #문제레벨: G1알고리즘: 백트래킹 + 분할정복풀이시간: 1시간힌트 참조 유무: 유https://www.acmicpc.net/problem/1799#문제 풀이완전탐색을 할 경우 2의 100승으로 무조건 시간초과입니다. 그렇다 하면 조금 더 긍정적으로 생각해보겠습니다. 흰색칸 비숍과 검정칸 비숍은 서로 영향을 줄 수 없습니다. 그래서 우린 흰색칸 비숍과 검정칸 비숍을 나누어서 탐색하게 된다면2^50 + 2^50 으로 아까보다 나아졌습니다. 그래도 우린 시간초과에 걸립니다. 그렇다면 우리에겐 dp가 남아있습니다. 위 문제를 dp로 풀 경우를 생각하면 비트마스킹 dp을 생각해볼 수 있습니다. 이차원배열을 100자리의 비트마스킹으로 표현하는 것입니다. 그러나 대각선의 겹치는 비숍이 있는지 검사하기에는 까다로울 .. 2025. 1. 18. [백준 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. [백준] 별 찍기 -10 / 자바 문제 레벨: G5알고리즘: 풀이시간: 1시간힌트 참조 유무: 무https://www.acmicpc.net/problem/24471 번째 시도 [풀이 사고 과정]처음 주어진 패턴으로 부분요소들을 크게 업데이트 해가는 문제구나 라는 생각즉, 재귀함수 문제라 생각풀이는 코드 주석 참조import java.io.BufferedReader;import java.io.InputStreamReader;public class Main { public static void main(String[] args) throws Exception { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); .. 2024. 5. 23. 이전 1 다음
