목록분할 정복 (6)
전자공학 및 알고리즘
백준 1725 - 히스토그램(C++)
문제 링크입니다. https://www.acmicpc.net/problem/1725 세그먼트 트리를 이용해 풀었습니다. N개의 직사각형의 높이가 주어졌을 때, 히스토그램에서 가장 넓이가 큰 직사각형을 구하는 문제입니다. 직사각형의 높이가 다를수 있기에, 붙어있는 직사각형들의 가장 높은 높이는 가장 직사각형의 높이가 될 것입니다.따라서, 이를 이용해 세그먼트 트리로 풀었습니다. 먼저, 트리에 가장 작은 높이의 위치를 저장해줬습니다.예를 들어, 자식 노드가 (2, 1)이라면, 1이 작은 높이이니 해당 노드는 높이가 1인 위치가 저장될 것입니다. 이렇게 트리에 작은 높이들의 위치가 저장이 되었다면, (0 ~ N-1) 범위에서 가장 넓이가 넓은 직사각형을 찾습니다.방법은 주어진 범위에서 가장 낮은 높이의 위치..
백준 6549 - 히스토그램에서 가장 큰 직사각형(C++)
문제 링크입니다. https://www.acmicpc.net/problem/6549 세그먼트 트리를 이용해 푸는 문제입니다. N개의 직사각형의 높이가 주어졌을 때, 히스토그램에서 가장 넓이가 큰 직사각형을 구하는 문제입니다. 직사각형의 높이가 다를수 있기에, 붙어있는 직사각형들의 가장 높은 높이는 가장 직사각형의 높이가 될 것입니다.따라서, 이를 이용해 세그먼트 트리로 풀었습니다. 먼저, 트리에 가장 작은 높이의 위치를 저장해줬습니다.예를 들어, 자식 노드가 (2, 1)이라면, 1이 작은 높이이니 해당 노드는 높이가 1인 위치가 저장될 것입니다. 이렇게 트리에 작은 높이들의 위치가 저장이 되었다면, (0 ~ N-1) 범위에서 가장 넓이가 넓은 직사각형을 찾습니다.방법은 주어진 범위에서 가장 낮은 높이의..
백준 2407 - 조합(C++)
문제 링크입니다. https://www.acmicpc.net/problem/2407 2407번: 조합 n과 m이 주어진다. (5 ≤ n ≤ 100, 5 ≤ m ≤ 100, m ≤ n) www.acmicpc.net 결과 값이 매우 크기에, 문자열을 통한 계산을 해야하는 문제입니다. nCr = n-1Cr-1 + n-1Cr 을 통해 조합 값을 구할 수 있습니다. nCm의 최댓값은 long long int의 범위를 넘어설 수 있습니다. 따라서 문자열을 통해 합을 계산하고 저장해야합니다. 사진을 통해 알 수 있는 점은 nCr의 값은 n-1Cr-1 + n-1Cr 을 통해 구할 수 있다는 것입니다. 위의 공식을 통해 값을 나눠가며 구하면 됩니다. 값을 나눴을 때, N의 값과 M의 값이 같아지거나, M의 값이 0이면 ..
백준 2263 - 트리의 순회(C++)
문제 링크입니다. https://www.acmicpc.net/problem/2263 2263번: 트리의 순회 첫째 줄에 n(1 ≤ n ≤ 100,000)이 주어진다. 다음 줄에는 인오더를 나타내는 n개의 자연수가 주어지고, 그 다음 줄에는 같은 식으로 포스트오더가 주어진다. www.acmicpc.net 중위 순회, 후위 순회의 특징을 알아야지 풀 수 있는 문제였습니다. 중위 순회의 특징은 부모 노드를 기준으로 왼쪽은 왼쪽 트리를 나타내고, 오른쪽은 오른쪽 트리를 나타냅니다. 후위 순회의 특징은 항상 마지막 수는 트리의 부모를 나타냅니다. 더 자세한 내용은 그림을 확인해주세요. 후위 순회와 중위 순회를 통해서 트리를 찾는 것은 확인했습니다. 이제 구현하는 단계가 남았습니다. 부모 노드가 중위 순회에서 어디..
백준 11444 - 피보나치 수 6(C++)
문제 링크입니다. https://www.acmicpc.net/problem/11444 11444번: 피보나치 수 6 첫째 줄에 n이 주어진다. n은 1,000,000,000,000,000,000보다 작거나 같은 자연수이다. www.acmicpc.net 행렬과 분할 정복을 이용해 푸는 문제입니다. 이 문제를 풀기 전에 피노나치 수열을 행렬로서 나타낼 수 있다는 것을 알아야합니다. 더 알아보고 싶다면 해당 링크를 확인해주세요 https://jow1025.tistory.com/101 위의 정보를 통해서 피보나치가 행렬로 계산이 가능함을 확인할 수 있었습니다. 또한 행렬의 곱셈도 어떤 방식인지 확인할 수 있었습니다. 따라서 N번째 피보나치 수열을 구할 때, N값에 따라서 나눠서 계산해 주면 됩니다. N이 짝수일..
백준 1074 - Z(C++)
문제 링크입니다. https://www.acmicpc.net/problem/1074 1074번: Z 한수는 크기가 2N × 2N인 2차원 배열을 Z모양으로 탐색하려고 한다. 예를 들어, 2×2배열을 왼쪽 위칸, 오른쪽 위칸, 왼쪽 아래칸, 오른쪽 아래칸 순서대로 방문하면 Z모양이다. N > 1인 경우, 배열을 www.acmicpc.net 재귀를 이용한 문제였습니다. 규칙을 찾는 것이 중요했습니다. (R , C)까지 모든 경로를 탐색하는 것이 아닌 계속 구역을 나누면서 더해주는 것이 중요합니다. (R,C)가 처음에 몇분면인지, 그리고 얼마를 더해야하는지도 구해봤습니다. 이번에는 4분면으로 다시 나눌때 어떻게 해야하는지를 확인하겠습니다. 위의 정보를 이해하면 코드를 쉽게 짤 수 있습니다. 자세한 것은 코드를..