막내의 막무가내 프로그래밍 & 일상

www.acmicpc.net/problem/1074 1074번: Z 한수는 2차원 배열 (항상 2^N * 2^N 크기이다)을 Z모양으로 탐색하려고 한다. 예를 들어, 2*2배열을 왼쪽 위칸, 오른쪽 위칸, 왼쪽 아래칸, 오른쪽 아래칸 순서대로 방문하면 Z모양이다. 만약, 2차원 www.acmicpc.net solved.ac 에서 레벨에 맞는 문제를 골라서 가끔 풀고있습니다. 그 중 한 문제입니다. 풀고서 다른 분들의 풀이를 봤는데 다양하게 푸는 것 같고 효율성 관련하여 에러가 난다는 말씀이 많았습니다. 문제를 제출하고 45초 동안이나 테스트케이스를 돌리는걸 보니 효율성이 중요한 듯 합니다. 저는 분할정복을 사용하여 문제를 해결했습니다. 4분의 1조각 씩 쪼개면서 2x2(num이 2일때) Z모양으로 탐색을..

www.acmicpc.net/problem/1629 1629번: 곱셈 첫째 줄에 A, B, C가 빈 칸을 사이에 두고 순서대로 주어진다. A, B, C는 모두 2,147,483,647 이하의 자연수이다. www.acmicpc.net 백준 분할정복 단계별풀기 네번째 곱셈 문제를 풀어봤습니다. 처음 단순하게 곱하고 나눠주고 반복문 돌렸다가 시간복잡도 때문에 시간초과가 났습니다. 분할정복 단계므로 분할해서 재귀를 사용해 풀었습니다. 밑 공식대로 풀면 됩니다. 풀이는 다음과 같습니다. [Java] import java.util.Scanner; public class Main { public static void main(String[] args) { Scanner sc = new Scanner(System.in..

www.acmicpc.net/problem/1780 1780번: 종이의 개수 N×N크기의 행렬로 표현되는 종이가 있다. 종이의 각 칸에는 -1, 0, 1의 세 값 중 하나가 저장되어 있다. 우리는 이 행렬을 적절한 크기로 자르려고 하는데, 이때 다음의 규칙에 따라 자르려고 한다. www.acmicpc.net 백준 분할정복 단계별풀기 3단계 문제입니다. 이전에 푼것들과 동일한데 이번에는 4등분이 아닌 9등분을 합니다. 기존 4번 분할하던것을 9분할로만 변경하면 해결됩니다. 풀이는 다음과 같습니다. [Java] import java.util.Scanner; public class Main { private static int[][] map; private static int zero = 0; private ..

www.acmicpc.net/problem/1992 1992번: 쿼드트리 첫째 줄에는 영상의 크기를 나타내는 숫자 N 이 주어진다. N 은 언제나 2의 제곱수로 주어지며, 1≤N ≤64의 범위를 가진다. 두 번째 줄부터는 길이 N 의 문자열이 N 개 들어온다. 각 문자열은 0 또는 www.acmicpc.net 백준 분할정복 단계별풀기 두번째 문제입니다. 이전에 푼 색종이 만들기에서 압축 시 괄호만 해주는거 말고는 거의 동일하다고 볼 수 있습니다. 풀이는 다음과 같습니다. [Java] import java.util.Scanner; public class Main { private static int[][] map; private static StringBuilder sb = new StringBuilder..

programmers.co.kr/learn/courses/30/lessons/68936?language=java 코딩테스트 연습 - 쿼드압축 후 개수 세기 [[1,1,0,0],[1,0,0,0],[1,0,0,1],[1,1,1,1]] [4,9] [[1,1,1,1,1,1,1,1],[0,1,1,1,1,1,1,1],[0,0,0,0,1,1,1,1],[0,1,0,0,1,1,1,1],[0,0,0,0,0,0,1,1],[0,0,0,0,0,0,0,1],[0,0,0,0,1,0,0,1],[0,0,0,0,1,1,1,1]] [10,15] programmers.co.kr 프로그래머스 월드 코드 챌린지 시즌1 LV2 문제인 쿼드압축 후 개수 세기 문제를 풀어봤습니다. ㅎㅎ 0또는 1을 담은 n^2 의 정사각형을 4분의 1 조각으로 계..