HS_development_log

문제 https://www.acmicpc.net/problem/1074 1074번: Z 한수는 2차원 배열 (항상 2^N * 2^N 크기이다)을 Z모양으로 탐색하려고 한다. 예를 들어, 2*2배열을 왼쪽 위칸, 오른쪽 위칸, 왼쪽 아래칸, 오른쪽 아래칸 순서대로 방문하면 Z모양이다. 만약, 2차원 배열의 크기가 2^N * 2^N라서 왼쪽 위에 있는 칸이 하나가 아니라면, 배열을 4등분 한 후에 (크기가 같은 2^(N-1)로) 재귀적으로 순서대로 방문한다. 다음 예는 2^2 * 2^2 크기의 배열을 방문한 순서이다. N이 주어졌을 때, (r, www.acmicpc.net 재귀적 탐색으로 문제를 작게 쪼개서 풀면되는문제. 알고리즘 4칸이 될때까지 재귀함수를 사용하여 쪼개서 들어간다 4칸이되면 Z순서대로 탐색..

문제 https://www.acmicpc.net/problem/2263 2263번: 트리의 순회 첫째 줄에 n(1≤n≤100,000)이 주어진다. 다음 줄에는 인오더를 나타내는 n개의 자연수가 주어지고, 그 다음 줄에는 같은 식으로 포스트오더가 주어진다. www.acmicpc.net 문제 접근방법이 꽤 어려웠던문제. 포스트오더와 인오더의 특징을 잘 활용해야지 풀 수 있었다. 포스트오더의 특성상 맨 마지막에 오는것이 루트이다. 인오더는 루트를 기준으로 왼쪽 오른쪽이 나뉜다. 따라서 포스트오더로 루트를 찾고 인오더로 왼쪽 오른쪽 노드를 찾아서 계속 작은 트리로 노드를 쪼개서 프리오더를 해주면 된다. 알고리즘 포스트오더의 끝을 루트로 정하고 프리오더로 답을 출력해야하므로 일단 출력한다. 루트를 기준으로 인오더..

문제 https://www.acmicpc.net/problem/1780 1780번: 종이의 개수 N×N크기의 행렬로 표현되는 종이가 있다. 종이의 각 칸에는 -1, 0, 1의 세 값 중 하나가 저장되어 있다. 우리는 이 행렬을 적절한 크기로 자르려고 하는데, 이때 다음의 규칙에 따라 자르려고 한다. 만약 종이가 모두 같은 수로 되어 있다면 이 종이를 그대로 사용한다. (1)이 아닌 경우에는 종이를 같은 크기의 9개의 종이로 자르고, 각각의 잘린 종이에 대해서 (1)의 과정을 반복한다. 이와 같이 종이를 잘랐을 때, -1로만 채워진 종이의 개수, 0으 www.acmicpc.net 종이의 개수를 세는문제 큰 배열을 작은 배열로 쪼개가면서 풀면 된다. 문제설명에서 1. ~~~이 맞다면 ~~~해라 2. ~~~~..

문제 https://www.acmicpc.net/problem/11728 11728번: 배열 합치기 첫째 줄에 배열 A의 크기 N, 배열 B의 크기 M이 주어진다. (1 ≤ N, M ≤ 1,000,000) 둘째 줄에는 배열 A의 내용이, 셋째 줄에는 배열 B의 내용이 주어진다. 배열에 들어있는 수는 절댓값이 109보다 작거나 같은 정수이다. www.acmicpc.net 머지소트에서 마지막에 배열을 합치는 방식을 구현하는 문제이다. 양쪽배열에서 앞에꺼부터 차례대로 확인하면서 출력하면 되는문제라 어렵지않았다. 알고리즘 왼쪽배열과 오른쪽배열을 탐색할 인덱스번호를 따로 만든다. (left, right) a[left]와b[right]중 작은것을 출력하고 출력한쪽의 인덱스를 1늘린다. 만약 left와 right중 ..