백준/자료구조40 백준 1406 c++ "에디터" -PlusUltraCode- https://www.acmicpc.net/problem/1406 [필자 사고]자료구조인 연결리스트를 이용하면 시간 복잡도 O(1)만에 풀 수 있어서 N이 100000이라 시간초과가 안나고 해결할 수 있따.필자는 c++ 에 내장 된 라이브러리인 연결리스트를 이용하여 해당 문제를 타파했따. 아래는 자세한 코드해설이다.[코드 해설]1. Input() 함수역할: 초기 문자열을 받아 myList라는 list 컨테이너에 한 글자씩 저장하고, 명령어 개수 N을 입력받는다.세부 동작:문자열을 순회하면서 각 문자들을 리스트에 push_back()으로 삽입.이후 명령의 수 N을 입력받음.2. Game_Start() 함수역할: 커서의 위치를 추적하면서 N개의 명령을 처리.커서 초기화: auto it = myList.end.. 2025. 5. 27. 백준 17353 c++ "하늘에서 떨어지는 1, 2, ..., R-L+1개의 별" -PlusUltraCode- https://www.acmicpc.net/problem/17353 [필자 사고]이 문제는 세그먼트 자료구조를 이용하는 거다.다만 이 문제만의 특별한 점은 느린 세그먼트 자료구조를 이용하고해당 lazy배열을 열이 2개 행이 4*N 형태로 설정하여 첫번째 열에는 시작점 두번째 열애는 공차를 저장하는 형태로문제를 해결해야 된다. [코드 해설]1. SegmentTree 구조체SegmentTree는 세그먼트 트리와 lazy propagation을 구현한 구조체로, 세그먼트 트리 초기화, 구간 업데이트, 점 단위 쿼리 등을 제공합니다.주요 멤버 변수:segment_tree: 세그먼트 트리의 노드 값을 저장하는 벡터.lazy_updates: lazy propagation 처리를 위한 배열로, 구간 업데이트 정보를 .. 2025. 1. 20. 백준 18135 c++ "겨울나기" -PlusUltraCode- https://www.acmicpc.net/problem/18135[필자 사고]이 문제는 세그먼트 자료구조를 이용하여 푸는 문제이다.이 문제만의 특이점은 경로가 원형으로 되어 있다는 점이다.또한 특정 범위에 들어가면 갯수를 얻는 시스템이다 보니 좌표 압축을 해야 된다. 이 두가지 점만 신경쓰면 해결할 수 있다. [코드 해설]1. 세그먼트 트리 초기화 (Init_Tree 함수)Init_Tree 함수는 세그먼트 트리를 초기화합니다. 배열 arr의 값을 기반으로 세그먼트 트리를 구성하며, 다음과 같은 방식으로 작동합니다:기저 사례: start와 end가 같으면 리프 노드에 arr[start] 값을 설정합니다.재귀 호출: 현재 구간을 절반으로 나누어 왼쪽과 오른쪽 자식 노드를 초기화한 후, 두 자식 노드의 합.. 2025. 1. 20. 백준 15899 c++ "트리와 색깔" -PlusUltraCode- https://www.acmicpc.net/problem/15899 [필자 사고]이 문제는 세그먼트 자료구조를 이용하여 푸는 문제이다. 먼저 위계질서가 정해져 있으므로 DFS를 이용하여 index를 세그먼트화 해야 된다.또한 자신의 값들도 있으므로 세그먼트화 된 index에 맞게 해당 값들도 저장해야 된다. C보다 적은값의 갯수를 묻고 있으므로 c+1로 lowerBound하면 갯수를 구할 수 있다. 또한 정점 V의 서브트리라고 했으니 정점 V를 포함하여 index[a].first 부터 시작하면 된다. 정밀하지 않으면 실수가 많은 문제이다. 또한 많은 알고리즘이 들어가 있어서 배울수 있는 문제이다.[코드 해설]2. 입력 처리 (Input 함수)Input() 함수는 사용자 입력을 받아 데이터를 초기화합니다... 2025. 1. 19. 이전 1 2 3 4 ··· 10 다음
