[백준] 1517 버블 소트, python
https://www.acmicpc.net/problem/1517 버블 소트로 정렬을 할 때, 수의 교체가 몇 번 일어나는지를 세는 문제이다.n*n의 모든 경우를 탐색하며 개수를 세어주면 시간초과가 난다.작은 값이 앞쪽에 와야하므로, 배열에서 현재 선택된 수의 오른쪽 부분에서 현재 수보다 작은 값이라면 교체를 해주어야 한다.예를 들어 배열이 [3,4,2,1]이라 하면, 먼저 배열의 요소를 크기순으로 정렬하여 작은 것부터 순서대로 0,1,2.. 에 매핑시켰다. 이렇게 되면 처음 배열 [2,3,1,0]에서 2는 1과 0, 3은 1과0, 1은 0과 교체해야 한다. 즉 배열에서 i번쨰 값을 k라 하면, i+1부터 배열의 끝까지 k보다 작은 요소의 개수를 세어주면 된다. [백준] 7578 공장 [백준..
[백준] 2357 최솟값과 최댓값, python
https://www.acmicpc.net/problem/2357 세그먼트 트리, python 세그먼트 트리, python세그먼트 트리란? 세그먼트 트리란 완전 이진 트리에 배열의 구간 정보(최대, 최솟값, 합, 곱 등)를 저장하고 빠르게 구간 쿼리를 처리할 수 있는 자료구조이다.완전 이진트리란 리프노드를 제외aiden0413.tistory.com 특정 구간 (a, b) 사이의 최댓값, 최솟값을 m 번 구하는 문제이다.파이썬의 min, max는 시간복잡도가 O(n) 이므로 모든 (a, b) 부분배열에서 min, max 함수를 사용하게 되면 O(n²) 이 되어 시간초과가 나게 된다. 따라서 이 문제는 세그먼트 트리를 이용하여 풀어야 한다.세그먼트 트리란 완전 이진트리에 구간별로 나누어 그 구간 ..