백준/자료구조39 백준 12844 c++ "XOR" -PlusUltraCode- https://www.acmicpc.net/problem/12844 [필자 사고]이 문제는 세그먼트 트리를 이용해서 푸는 문제이다.Update할 때 구간 전체를 업데이트 해야되므로 lazy전파를 이용해야 시간내에 풀 수 있다.이 문제만의 특이점은 xor연산이라고 생각한다.end-start+1 을 2로 나눴을 때 ==1 인 경우만 tree[node] 의 값을 update해줘야 된다.이 부분만 잘 이해하고 있으면 문제를 풀 수 있게 된다.[코드 해설]1. 입력 처리 (Input 함수)Input 함수는 세그먼트 트리 초기화를 위한 입력값을 처리합니다.N 입력: 세그먼트 트리의 배열 크기 N을 입력받습니다.arr 벡터 초기화: 배열 크기를 N+1로 설정하고 입력 값을 1번 인덱스부터 채웁니다. (1번부터 시작하.. 2025. 1. 16. 백준 4442 c++ "빌보의 생일" -PlusUltraCode- https://www.acmicpc.net/problem/4442 [필자 사고]이 문제는 inverstion Counting 활용 문제이다.먼저 문제에서 주어지는 입력값들은 문자로 되어있어서 필자는map자료구조를 이용하여 해당 값들을 좌표압축을 통해 세그먼트 트리를 손쉽게 작성했다.그 이후 inverstion 알고리즘을 적용하여 원하는 값들을 출력했다.[코드 해설]1. 입력 처리 (Input 함수)목적: 두 개의 문자열 배열을 입력받아 매핑 정보를 생성합니다.첫 번째 입력:NNN: 배열의 크기.arrarrarr: 첫 번째 문자열 배열로, 순서를 유지한 채 저장합니다.두 번째 입력:myMapmyMapmyMap: 두 번째 문자열 배열로, 문자열을 정렬된 순서대로 인덱스를 매핑합니다.예: myMap["appl.. 2025. 1. 15. 백준 14427 c++ "수열과 쿼리 15" -PlusUltraCode- https://www.acmicpc.net/problem/14427 [필자 사고]필자는 수열에서 크기가 가장 작은 값의 인덱스를 출력하라고 했다.처음에는 tree에 pair을 이용하여 자료형을 2개 관리했다. 값과 인덱스근데 생각해보니 최소값을 찾은 노드에 start 나 end를 반환하면 해당 인덱스가 된다.이 사실을 늦게 알아서 코드가 상당히 길어졌다. 다음에는 유동적으로 사고해야 되겠다.[코드 해설]1. 입력 처리 (Input 함수)목적: 배열 크기와 데이터를 입력받아 초기화합니다.NNN: 배열의 크기를 입력받습니다.arr[i]arr[i]arr[i]: 배열의 각 값을 입력받아 저장합니다.세그먼트 트리 treetreetree를 크기 4×N4 \times N4×N으로 초기화합니다.2. 두 노드 중 최소값.. 2025. 1. 15. 백준 4297 c++ "Ultra-QuickSort" -PlusUltraCode- https://www.acmicpc.net/problem/4297 [필자 사고]이 문제는 inverstion Counting 문제를 이용하여 푸는 문제이다.필자는 주어지는 값들이 범위가 크기 때문에 좌표 압축을 통해 인덱스들을 관리했고 그 이후 inverstion 카운팅 알고리즘을 이용하여 해당 갯수들을 출력했다.[코드 해설]. 입력 처리 (Input 함수)목적: 입력 데이터를 받아 배열을 초기화하고, 좌표 압축을 수행합니다.입력으로 크기 NNN과 NNN개의 숫자를 받습니다.입력된 값과 해당 인덱스를 arrarrarr 벡터에 저장합니다.예: arr[i]=(값,인덱스)arr[i] = (\text{값}, \text{인덱스})arr[i]=(값,인덱스)arrarrarr를 값 기준으로 정렬한 뒤, 좌표 압축을 수.. 2025. 1. 15. 이전 1 2 3 4 5 6 ··· 10 다음
