유자의 코딩모험

2263번: 트리의 순회 첫째 줄에 n(1≤n≤100,000)이 주어진다. 다음 줄에는 인오더를 나타내는 n개의 자연수가 주어지고, 그 다음 줄에는 같은 식으로 포스트오더가 주어진다. www.acmicpc.net 동꿀오소리님 풀이 참고 [백준] 2263번 트리의 순회 - C++ - DGOS | 동꿀오소리 문제 donggoolosori.github.io 문제풀이 이진 트리의 인오더(중위순회)와 포스트오더(후위순회)가 주어졌을 때, 프리오더(전위순회)를 구하는 문제이다. 위 트리의 인오더, 포스트오더, 프리오더를 살펴보자. 중위 순회 : 5 6 8 4 3 1 2 7 후위 순회 : 5 8 4 6 2 1 7 3 전위 순회 : 3 6 5 4 8 7 1 2 굵게 표시해놓은 것이 루트 노드이다. 후위 순회는 [왼쪽 ..

1074번: Z 한수는 크기가 2N × 2N인 2차원 배열을 Z모양으로 탐색하려고 한다. 예를 들어, 2×2배열을 왼쪽 위칸, 오른쪽 위칸, 왼쪽 아래칸, 오른쪽 아래칸 순서대로 방문하면 Z모양이다. 만약, N > 1이 라서 www.acmicpc.net 동꿀오소리님 블로그 참고 [백준] 1074번 Z - C++ - DGOS | 동꿀오소리 문제 donggoolosori.github.io 문제풀이 go의 x, y는 현재 탐색하고자 하는 사분면의 가장 왼쪽 위 좌표이고 size는 현재 사분면의 크기이다. 찾고자 하는 좌표 값 r, c가 현재 사분면 내에 존재한다면 현재 사분면을 다시 4등분해서 1, 2, 3, 4분면을 탐색한다. 만약 r, c가 현재 사분면 내에 존재하지 않는다면 현재 사분면을 탐색할 필요가 ..

1655번: 가운데를 말해요 첫째 줄에는 수빈이가 외치는 정수의 개수 N이 주어진다. N은 1보다 크거나 같고, 100,000보다 작거나 같은 자연수이다. 그 다음 N줄에 걸쳐서 수빈이가 외치는 정수가 차례대로 주어진다. 정수는 -1 www.acmicpc.net 문제풀이 정수를 하나씩 받을 때마다 중앙값을 출력하는 문제다. 이 문제는 우선순위 큐 2개를 이용해서 풀 수 있다. 기본적으로 우선순위 큐가 Heap 구조이므로 Max Heap과 Min Heap 두 개를 선언한다. 비교함수를 따로 정해주지 않으면 기본적으로 내림차순에 따라 정렬한다. (Max Heap) // Min Heap priority_queue minheap; // Max Heap priority_queue maxheap; 중간값을 찾아야 ..

2696번: 중앙값 구하기 첫째 줄에 테스트 케이스의 개수 T(1 ≤ T ≤ 1,000)가 주어진다. 각 테스트 케이스의 첫째 줄에는 수열의 크기 M(1 ≤ M ≤ 9999, M은 홀수)이 주어지고, 그 다음 줄부터 이 수열의 원소가 차례대로 주 www.acmicpc.net 문제풀이 이 문제는 우선순위 큐 2개를 이용해서 풀 수 있다. 기본적으로 우선순위 큐가 Heap 구조이므로 Max Heap과 Min Heap 두 개를 선언한다. 비교함수를 따로 정해주지 않으면 기본적으로 내림차순에 따라 정렬한다. (Max Heap) // Min Heap priority_queue minheap; // Max Heap priority_queue maxheap; 중간값을 찾아야 하므로 두 큐의 크기는 같아야 한다. 우선..

2900번: 프로그램 창영이가 에러를 찾기 위해서 디버깅을 하고 있다. 이 프로그램은 크기가 N이고 0으로 채워져있는 배열을 a를 만들고, 아래 something 함수를 호출한다. void something(int jump) { int i = 0; while (i < N) { a[i] www.acmicpc.net 문제풀이 이 문제는 something이라는 함수를 k번 호출하고 구간 합을 구하는 문제다. something 함수를 잘 보면 jump로 나누어 떨어지는 인덱스마다 1을 증가시키는 함수라는 것을 알 수 있다. jump 인자를 하나씩 입력받으면서 해당 값이 몇 번 나왔는지 카운트한다. 인자가 0부터 시작해서 jump만큼 더해가기 때문에 a[0]은 무조건 k이다. 0을 제외한 jump로 나누어떨어지는..

1005번: ACM Craft 첫째 줄에는 테스트케이스의 개수 T가 주어진다. 각 테스트 케이스는 다음과 같이 주어진다. 첫째 줄에 건물의 개수 N 과 건물간의 건설순서규칙의 총 개수 K이 주어진다. (건물의 번호는 1번부 www.acmicpc.net 문제풀이 이 게임은 건설 순서 규칙에 따라서 건물을 건설해야 한다. 위의 예시를 보자. 1번 건물의 건설이 완료된다면 2번과 3번의 건설을 동시에 진행할 수 있다. 그리고 4번 건물을 짓기 위해서는 2번과 3번 건물이 모두 건설 완료되어야지만 4번 건물의 건설을 시작할 수 있다. 따라서 4번 건물의 건설을 완료하기 위해서는 10초 + 100초 + 10초 = 120초가 소요된다. 120초가 4번 건물을 가장 빨리 지을 때까지 걸리는 최소시간인 것이다. 건물 ..

1516번: 게임 개발 첫째 줄에 건물의 종류 수 N(1 ≤ N ≤ 500)이 주어진다. 다음 N개의 줄에는 각 건물을 짓는데 걸리는 시간과 그 건물을 짓기 위해 먼저 지어져야 하는 건물들의 번호가 주어진다. 건물의 번호는 1부 www.acmicpc.net 문제풀이 이 게임은 건설 순서 규칙에 따라서 건물을 건설해야 한다. dp[i] = i번 건물을 건설 완료하는데 드는 최소 시간 최소 시간을 찾는 것이지만 선행 건물들이 모두 건설완료가 되어야하므로 최댓값을 찾는 것이다. 처음에 선행 정점을 가지지 않는 정점을 큐에 삽입할 때는 dp[i] = t[i]로 초기화해준다. 그리고 나서 다음 순서를 진행할 때 앞순서 건물 건설시간 + 현재 건물 건설시간이 최대인 것을 저장해주면 해당 건물을 건설완료 하는데 드는..

3020번: 개똥벌레 개똥벌레 한 마리가 장애물(석순과 종유석)로 가득찬 동굴에 들어갔다. 동굴의 길이는 N미터이고, 높이는 H미터이다. (N은 짝수) 첫 번째 장애물은 항상 석순이고, 그 다음에는 종유석과 석순이 www.acmicpc.net 문제풀이 동굴의 길이가 N미터이고, 높이는 H미터이다. 이 동굴은 석순과 종유석으로 가득차 있는데 첫 번째 장애물은 항상 석순이고 그 다음부터는 종유석과 석순이 번갈아가면서 등장한다. 개똥벌레는 자신이 지나갈 구간을 정하면 일직선으로 지나가면서 모든 장애물을 파괴한다. 개똥벌레가 파괴해야하는 장애물의 최솟값과 그러한 구간이 총 몇 개 있는지 구하는 문제다. 먼저 석순과 종유석을 따로 배열에 저장한다. obs1은 석순이고 obs2는 종유석이다. 구간은 아래에서부터 시..