본문 바로가기

백준189

백준 1572 c++ "중앙값" -PlusUltraCode- https://www.acmicpc.net/problem/1572 [필자 사고]이 문제는 중앙값 찾기 . 세그먼트 트리를 이용하여 풀었다.입력값으로 주어지는 숫자가 세그먼트 트리에서 리프노드기준으로 인덱스라고 생각하고 풀면 쉽다.예를들면 입력값이 6이라고 한다면 왼쪽 리프노드부터 6번째 노드에 +1 을 하면 된다.그래서 중앙값을 찾고 싶을때는 getMid를 통해 갯수를 확인하면서 원하는 지점에 방문하면 start 즉 해당 인덱스 값 을 ans 에 더하면 문제를 해결할 수 있다.[코드 해설] 문제 정의길이가 N인 배열 arr에서 길이가 K인 구간을 이동하면서, 각 구간의 중간값을 구하고 이를 모두 더한 값을 출력한다.중간값은 정렬된 구간에서 (K + 1) / 2번째에 위치한 값이다.세그먼트 트리를 이용한 .. 2025. 1. 10.
백준 2104 c++ "부분배열 고르기" -PlusUltraCode- https://www.acmicpc.net/problem/2104\ [필자 사고]퀵정렬? 합병정렬? 과 유사한 개념을 이용하여 재귀형태로 문제를 해결해 나갔다. start==end 가 같다면 해당 val*valu 을 return하고 그렇지 않다면 중심을 기준으로 왼쪽을 갈지 오른쪽을 갈지 결정한 뒤 계속 최대값을 갱신하는 방법이다. 이러한 알고리즘은 한번에 습득하기 보다는 계속 문제를 풀어서 재귀적 사고를 키우는게 방법인거 같다.[코드 해설] 분할 정복을 이용한 최대 직사각형 구하기 (findMaxRectangle 함수)findMaxRectangle 함수는 주어진 범위에서 최대 직사각형의 면적을 구하는 문제를 해결한다.기본 분할주어진 구간 [left, right]을 가운데 mid로 나누어 두 구간 [le.. 2025. 1. 10.
백준 12846 c++ "무서운 아르바이트" -PlusUltraCode- https://www.acmicpc.net/pr[필자 사고]필자는 스택을 이용하여 해당 문제를 해결했다. 과거에 풀어 봤던 히스토그램 문제와 많이 비슷해서 손쉽게 해결할 수 있었다.문제를 풀면서 조심해야 될 점은 스택의 값이 idx가 들어가야 된다는 점.그리고 가로 길이를 잘 계산해야 된다. 필자는 현재 i 에서 스택의 stack.top()를 뺀뒤 -1을 하여 최대값을 계산할 수 있게 코드를 작성했다. 마지막으로 스택에 남아있는 값ㅇ 있을수 있으므로 마무리 점검 또한 했다.[코드 해설] 입력 처리 (Input 함수)배열 arr에 N개의 숫자를 입력받아 저장합니다.N은 배열의 크기(또는 막대기의 개수)를 나타냅니다.게임 시작 (Game_Start 함수)스택을 사용하여 현재 높이보다 낮아지는 구간을 만날 때.. 2025. 1. 10.
백준 11143 c++ "Beads" -PlusUltraCode- #include #include using namespace std;int N;vector tree;vector arr;int M;void Input() { cin >> N; tree.resize(4 * N + 1); arr.resize(N + 1); for (int i = 1; i > arr[i]; }}void Init_Tree(int node, int start, int end) { if (start == end) { tree[node] = arr[start]; return; } int mid = (start + end) / 2; Init_Tree(node * 2, start, mid); Init_Tree(node * 2 + 1, mid + 1, end); tree[node] = tree[node.. 2025. 1. 9.

티스토리툴바