본문 바로가기

백준189

백준 14727 c++ "퍼즐 자르기" -PlusUltraCode- https://www.acmicpc.net/problem/14727 [필자 사고]이 문제는 히스토 그램과 유사한 알고리즘을 이용하는 문제이다.필자는 스택을 일용하였고 현재 인덱스의 높이가 스택의 탑 인덱스의높이보다 작을경우 while문을 시작한다.현재 인덱스 전의 가로 길이를 구하고 topIdx의 높이를 구하여 넓이를 갱신하는 과정이다.[코드 해설]스택 myStack을 사용하여 직사각형의 최대 넓이를 계산현재 높이가 이전에 스택에 저장된 높이보다 작아질 때, 스택의 가장 위에 있는 인덱스를 사용하여 직사각형의 넓이를 계산한다.이때 스택에 남아 있는 높이는 이전까지의 연속된 높이 중 최소값을 나타낸다.현재 높이와 비교하여 스택을 처리배열 arr의 현재 인덱스에서, 스택의 가장 위에 있는 인덱스가 가리키는 .. 2025. 1. 11.
백준 9463 c++ "순열 그래프" -PlusUltraCode- https://www.acmicpc.net/problem/9463 [필자 사고]이 문제는 교차점 구하는 문제를 응용한거라 본다.교차점의 핵심은 시작위치에서 끝위치의 인덱스를 기준으로 +1을하여 Query를 작성한다.idx+1 보다 큰 값들의 갯수가 증가되어 있지 않다면 교차점이 없는거다.그 후 Update를 이용하여 해당 idx에 +1을 하여 내가 여기 왔습니다 와 같은 영역 표시를 해준다.위와 같은 과정을 반복하면 교차점들을 구할 수 있다.[코드 해설] InitArrAndTree 함수: 배열 및 세그먼트 트리 초기화배열 arr와 세그먼트 트리 tree를 초기화한다.입력된 숫자를 읽어 배열 arr에 저장하고, 두 번째 입력으로 각 숫자의 순서를 map 자료구조 myMap에 저장한다.이때, 숫자 num의 .. 2025. 1. 10.
백준 32322 c++ "Hotel Rooms" -PlusUltraCode- https://www.acmicpc.net/problem/32322[필자 사고]기본적인 세그먼트 트리를 선언할줄 아냐 묻는 문제이다.조심해야 될 부분은 쿼리를 묻는 부분이 항상 작은데에서 큰범위가 아닐 수도 있다는 점과초기화 한 쿼리 N을 항상 query 나 update 의 end값에 넣어야 된다는 점이 있다.[코드 해설]세그먼트 트리 초기화 (Init_Tree 함수)Init_Tree 함수는 배열의 각 위치를 초기화하며, 모든 값을 1로 설정합니다.세그먼트 트리의 리프 노드는 배열의 각 원소를 나타내며, 내부 노드는 해당 구간의 합을 저장합니다.구간 [start, end]를 반으로 나누어 재귀적으로 초기화합니다.리프 노드: start == end일 때 트리의 해당 위치를 1로 설정합니다.내부 노드: 왼쪽.. 2025. 1. 10.
백준 1321 c++ "군인" -PlusUltraCode- https://www.acmicpc.net/problem/1321 [필자 사고]이 문제는 세그먼트 트리를 이용하여 몇번째 인지 구하는 문제이다.이전 풀었떤 구슬 문제나 중앙값 문제 등등 모두 같은 계열의 문제이다.늘 해오던 습관은 항상 세그먼트 배열 크기를 1000000*4인 형태로 초기화 하고 update 나 query등 start 와 end 의 범위를 1~ 1000000 으로 설정했는데요번에는 start ==1 end ==N 으로 잡으니 오류가 났다.그 이유는 트리를 처음 초기화 한 숫자 즉 1000000 에 쿼리나 update init 등등 맞혀야 된다는 말이다.즉 end == 1000000 으로 해야된다 .만약 tree초기화를 300*4 로 하게 되면 query 등등의 end 값은 300 으로 해.. 2025. 1. 10.

티스토리툴바