본문 바로가기

알고리즘53

[백준 1074] Z 분할정복 문제이다. "Z" 방향으로 탐색을 하면서, 주어진 좌표가 몇 번째에 탐색이 되는지 출력하는 문제이다. 0 1 2 3 이라고 하면, 0 -> 1 -> 2 -> 3 순으로 탐색이 되며, 분할 탐색을 해가면서 각 좌표마다 입력 값과 비교하여, 결과를 출력한다. 출처 : https://www.acmicpc.net/problem/1074 문제 한수는 2차원 배열 (항상 2^N * 2^N 크기이다)을 Z모양으로 탐색하려고 한다. 예를 들어, 2*2배열을 왼쪽 위칸, 오른쪽 위칸, 왼쪽 아래칸, 오른쪽 아래칸 순서대로 방문하면 Z모양이다.만약, 2차원 배열의 크기가 2^N * 2^N라서 왼쪽 위에 있는 칸이 하나가 아니라면, 배열을 4등분 한 후에 (크기가 같은 2^(N-1)로) 재귀적으로 순서대로 방문한다.. 2019. 3. 21.
[백준 2448] 별 찍기 - 11 생각보다 난 별 찍기를 못하는 것 같다.꽤 오랜시간 동안, 해맨 문제. 출처 : https://www.acmicpc.net/problem/2448 문제 예제를 보고 규칙을 유추한 뒤에 별을 찍어 보세요. 입력 첫째 줄에 N이 주어진다. N은 항상 3×2k 수이다. (3, 6, 12, 24, 48, ...) (k ≤ 10) 출력 첫째 줄부터 N번째 줄까지 별을 출력한다. 예제 입력 1 24 예제 출력 1 * * * ***** * * * * * * ***** ***** * * * * * * ***** ***** * * * * * * * * * * * * ***** ***** ***** ***** * * * * * * ***** ***** * * * * * * * * * * * * ***** ***** ***.. 2019. 3. 20.
[백준 2447] 별 찍기 - 10 분할정복 문제이지만, 생각보다 까다로웠던 문제...이해가 부족한만큼 더 공부해야겠다. 출처 : https://www.acmicpc.net/problem/2447 문제 예제를 보고 규칙을 유추한 뒤에 별을 찍어 보세요. 입력 첫째 줄에 N이 주어진다. N은 항상 3의 제곱꼴인 수이다. (1, 3, 9, 27, ...) (N=3k, 0 ≤ k < 8) 출력 첫째 줄부터 N번째 줄까지 별을 출력한다. 예제 입력 1 27 예제 출력 1 *************************** * ** ** ** ** ** ** ** ** * *************************** *** ****** ****** *** * * * ** * * ** * * * *** ****** ****** *** ******.. 2019. 3. 20.
[백준 1992] 쿼드트리 분할정복 문제.. 왼쪽 위 -> 오른쪽 위 -> 오른쪽 아래 -> 왼쪽 아래 순으로 탐색을 나아가면 된다.다를시에는 size /= 2 및 괄호 출력 종이의 개수를 풀었다면, 무난하게 풀 수 있는 문제이다. 출처 : https://www.acmicpc.net/problem/1992 문제 흑백 영상을 압축하여 표현하는 데이터 구조로 쿼드 트리(Quad Tree)라는 방법이 있다. 흰 점을 나타내는 0과 검은 점을 나타내는 1로만 이루어진 영상(2차원 배열)에서 같은 숫자의 점들이 한 곳에 많이 몰려있으면, 쿼드 트리에서는 이를 압축하여 간단히 표현할 수 있다. 주어진 영상이 모두 0으로만 되어 있으면 압축 결과는 "0"이 되고, 모두 1로만 되어 있으면 압축 결과는 "1"이 된다. 만약 0과 1이 섞여 있으.. 2019. 3. 20.
[백준 2263] 트리의 순회 인덱스 위치를 헷갈려서, 그리고 이유 모를 시간초과 문제로 몇 차례 실패했던 문제이다.종이에 쓰면서, 이해를 하려고 노력하니 이해가 되었지만....아직 100퍼센트 이해가 되지 않은 것 같아, 노력이 필요하다 문제 : https://www.acmicpc.net/problem/2263 문제 n개의 정점을 갖는 이진 트리의 정점에 1부터 n까지의 번호가 중복 없이 매겨져 있다. 이와 같은 이진 트리의 인오더와 포스트오더가 주어졌을 때, 프리오더를 구하는 프로그램을 작성하시오. 입력 첫째 줄에 n(1≤n≤100,000)이 주어진다. 다음 줄에는 인오더를 나타내는 n개의 자연수가 주어지고, 그 다음 줄에는 같은 식으로 포스트오더가 주어진다. 출력 첫째 줄에 프리오더를 출력한다. 예제 입력 1 3 1 2 3 1 .. 2019. 3. 20.
[백준 1780] 종이의 개수 NXN크기 행렬의 종이를 정해진 규칙에 따라서 잘라야 하기 때문에, 0 1 -1 1 0 1 => 행렬의 size/3 씩 분할 탐색을 한다.0 -1 0 0 -> 1 -> -1 -> 1 -> 0 -> 1 -> 0 -> -1 -> 0 순이다. (x축 부터) bool 변수 same을 두어, 이전과 현재 행렬의 요소가 같은지 검사해 나간다. 출처 : https://www.acmicpc.net/problem/1780 문제 N×N크기의 행렬로 표현되는 종이가 있다. 종이의 각 칸에는 -1, 0, 1의 세 값 중 하나가 저장되어 있다. 우리는 이 행렬을 적절한 크기로 자르려고 하는데, 이때 다음의 규칙에 따라 자르려고 한다. 만약 종이가 모두 같은 수로 되어 있다면 이 종이를 그대로 사용한다.(1)이 아닌 경우에는 종.. 2019. 3. 20.

티스토리툴바