본문 바로가기

백준288

백준 25778 c++ "House Prices Going Up" -PlusUltraCode- https://www.acmicpc.net/problem/25778  [필자 사고]이 문제는 세그먼트 트리 합 관련 기본 문제이다.조심해야 될 점은 없었던거 같고항상 세그먼트 질의문에 a,b중 작은값 큰값 조심하자.[코드 해설]입력 함수 (Input)사용자로부터 입력을 받는 역할을 수행한다.먼저 N (배열의 크기)을 입력받고, 그에 맞게 세그먼트 트리(tree)와 입력 배열(arr)을 크기에 맞게 초기화한다.이후 배열의 요소들을 차례로 입력받아 arr에 저장한다.세그먼트 트리 초기화 함수 (Init_Tree)세그먼트 트리를 구성하는 함수이다.재귀적으로 호출되며, 리프 노드에는 입력 배열의 값을 저장하고, 부모 노드에는 자식 노드들의 합을 저장한다.node, start, end를 매개변수로 받아 현재 세그.. 2025. 1. 9.
백준 1615 c++ "교차개수세기" -PlusUltraCode- https://www.acmicpc.net/problem/1615 [필자 사고]이 문제는 세그먼트 트리의 indexing inversion 의 초기 개념이다.처음 반복문은 오름차순으로 정렬순서로 준비하고 작은 index 부터 조사를 시작해야한다.먼저 1에는 5라는값이 들어가 있기때문에 5라는보다 하나 큰 6이라는 위치에 Query를 던진다.6~N 값에 값이 있따면 sum 을 반환할것이다. 그리고 여기서 중요한건 시작점이 여러개 소환될수 있ㄷ는 것이다.즉 시작점에서는 절대로 겹치지 않아 update문은 Query for 문이 끝난 이후다시 for문을 만들어 Update해야 된다. 이 부분이 실수하기 좋은 부분이다.[코드 해설] 입력 처리 (Input 함수)N과 M을 입력받습니다. N은 노드 수, M은 간선.. 2025. 1. 8.
백준 1981 c++ "배열에서 이동" -PlusUltraCode- https://www.acmicpc.net/problem/1981 [필자 사고]평범한 BFS탐색문제이지만 이분탐색이 들어가 색다른 느낌이 든다.미드값을 가지고 BFS 0부터 mid값부터 시작하여 i부터 mid값+ i 의 숫자들은 모두 false 형태로 바꾸고탐색을 진행하다 성공하면 end값을 더 줄이고 그렇지 않으면 start값을 늘리는 형식.. 이분탐색을 더욱 깊이 있게 배워나가는 시간이였다.[코드 해설] 입력 처리 (Input 함수)사용자로부터 NxN 크기의 2차원 배열(arr)과 그 값들을 입력받는다.배열의 각 값을 읽으면서 최대값(maxValue)과 최소값(minValue)을 갱신한다.BFS를 활용한 경로 검증 (BFS 함수)특정 diff 값을 기준으로 이동 가능한 경로가 존재하는지 확인한다.mi.. 2025. 1. 8.
백준 8111 c++ "0과 1" -PlusUltraCode- https://www.acmicpc.net/problem/8111 [필자 사고]탐색 문제이다. 이 문제에서 핵심 알고리즘은 부모추적 알고리즘과 모듈러 공식 및 BFS탐색 방법인거 같다.모듈로 공식으로 인해 방문 배열을 입력된 숫자의 나머지로 선정할수 있고,부모추적 인덱스 즉 DFS를 이용하여 부모추적을하여 map에서 원하는 글자를 꺼내어 출력을 하면 된다. 한 문제에서 3가지 알고리즘을 배워서 좋은 학습 문제였다. [코드 해설]위 코드를 설명하면 다음과 같습니다:BFS를 이용한 탐색 과정BFS 함수는 큐(myQueue)를 사용하여 모듈로 연산을 기반으로 숫자를 생성하고, 목표 상태(나머지가 0)가 될 수 있는지를 판단합니다.시작은 1 % num으로 하며, 이를 큐에 넣고 방문 표시(visited)를 합니.. 2025. 1. 8.

티스토리툴바