Jumping to the water

▶ 문제 https://www.acmicpc.net/problem/1629 1629번: 곱셈 첫째 줄에 A, B, C가 빈 칸을 사이에 두고 순서대로 주어진다. A, B, C는 모두 2,147,483,647 이하의 자연수이다. www.acmicpc.net ▶ 설명 문제에서 주어진 A,B,C의 범위는 int형의 최대값이기 때문에 pow 메소드를 서서 한 번에 거듭제곱 연산을 처리하려면 시간 초과가 날 수 있다. 지수의 법칙과 모듈로에 대한 이해를 한 다음에 다시 이 문제에 접근하면 짧은 시간안에 결과 값을 얻어낼 수 있다. 지수 법칙 (출처 : mathfactory ) 모듈로 곱셈 (출처 : khan ) 모듈로 연산 연습해보기 ↓ 더보기 (702⋅398) mod 20 의 답은 > 16 (출처 : khan ..

▶ 문제 https://www.acmicpc.net/problem/1780 1780번: 종이의 개수 N×N크기의 행렬로 표현되는 종이가 있다. 종이의 각 칸에는 -1, 0, 1 중 하나가 저장되어 있다. 우리는 이 행렬을 다음과 같은 규칙에 따라 적절한 크기로 자르려고 한다. 만약 종이가 모두 같은 수 www.acmicpc.net ▶ 설명 색종이 만들기 문제의 변형된 문제이다. 색종이 만들기에서는 만족하는 결과가 아니면 4등분으로 분할하는 반면, 이 문제는 9등분으로 분할하여 재귀함수를 통해 다시 탐색하여야 한다. 그림으로 살펴보자면 아래와 같다. 같은 값으로 되어 있지 않아 9등분으로 분할하면 원래 row와 column의 길이에서 3으로 나누어 주어야 한다. 원래 길이가 9라고 한다면 3씩 row와 c..

▶ 문제 https://www.acmicpc.net/problem/1992 1992번: 쿼드트리 첫째 줄에는 영상의 크기를 나타내는 숫자 N 이 주어진다. N 은 언제나 2의 제곱수로 주어지며, 1 ≤ N ≤ 64의 범위를 가진다. 두 번째 줄부터는 길이 N의 문자열이 N개 들어온다. 각 문자열은 0 또 www.acmicpc.net ▶ 설명 쿼드트리란? 자식 노드가 4개인 트리를 말한다. (참고로 자식 노드가 2개면 이진트리라고 한다.) 쿼드트리는 2차원에서 많이 사용하는데 4등분으로 재귀적으로 분할한다는 특징이 있다. 이러한 특징은 분할 정복 알고리즘과 매치된다. 문제 설명 문제를 살펴보면 아래와 같이 흑백을 1과 0으로 표현한다고 되어 있다. 0과 1을 2차원 배열로 입력 받아 저장한 뒤, 모두 같은..

▶ 문제 https://www.acmicpc.net/problem/2630 2630번: 색종이 만들기 첫째 줄에는 전체 종이의 한 변의 길이 N이 주어져 있다. N은 2, 4, 8, 16, 32, 64, 128 중 하나이다. 색종이의 각 가로줄의 정사각형칸들의 색이 윗줄부터 차례로 둘째 줄부터 마지막 줄까지 주어진다. www.acmicpc.net ▶ 설명 단계별 문제 풀기에서 분할정복 카테고리에 있는 첫 문제인 색종이 만들기를 풀어보았다. 전체 상태에서 해결할 수 없을 때 분할하여 해결하는 방식을 분할 정복이라고 한다. 그래서 이 문제도 하나의 종이에서 같은 색이 아닐 경우 4등분으로 분할하여 같은 색으로 되어있는지 재귀함수로 체크하는 방식으로 색의 개수를 늘려나갔고 검색이 끝나면 흰색과 파란색 종이의 ..