아롱이의 PS하는 블로그

https://www.acmicpc.net/problem/2336 풀이일단 문제 설명은 살짝 복잡하지만 잘 읽고 보면, "Inverse Count 문제 유형의 응용이구나"를 알게 된다. 시험이 세 개 있는데, 위에서부터 A, B, C 시험이라고 하자. A에서 1등한 사람부터 살펴볼 것이다.약간의 관찰을 해 보면, A에서 1등한 사람부터 살펴볼 때, 그 사람의 (B에서의 등수, C에서의 등수)가 있을 것인데 이거를 하나씩 추가해나가다 보면, 이미 있던 사람의 B, C 등수보다 둘 다 등수가 크게 되는 경우가 존재하면 그 사람은 굉장한 학생이 아니다.이걸 효과적으로 관리해주기 위해서 세그먼트 트리를 이용한다. A에서 1등한 사람부터 살펴보는 데, 세그먼트 트리의 B에서의 등수 인덱스에 C에서의 등수 값을 넣..

https://www.acmicpc.net/problem/12858 풀이분명 느갱세의 응용 문제라고 들었는데, 느갱세 풀이는 어떻게 하는건지 생각하지도 못하고 오히려 느갱세를 안쓰는 풀이만 생각해버렸다. 먼저 차분 배열 트릭을 이용하면 Range Update를 딱 두 개의 노드에 대해서만 해주어도 된다는 점에서 시작하자.그런데, 잘 생각해보면 어떤 수 a, b, c, d, e의 gcd는 유클리드 호제법에 따라 다음과 같이 구해질 수도 있다. gcd(a, b, c, d, e) = gcd(a, |b-a|, |c-b|, |d-c|, |e-d|) 두 수의 차이는 차분 배열에서 이미 저장하고 있기 때문에, 차분 배열을 그냥 바로 세그트리화 시켜버려서 구간별 gcd를 구할 수 있을 것이다! 그런데 여기서 하나 고려..

https://www.acmicpc.net/problem/1517 문제N개의 수로 이루어진 수열 A[1], A[2], …, A[N]이 있다. 이 수열에 대해서 버블 소트를 수행할 때, Swap이 총 몇 번 발생하는지 알아내는 프로그램을 작성하시오.버블 소트는 서로 인접해 있는 두 수를 바꿔가며 정렬하는 방법이다. 예를 들어 수열이 3 2 1 이었다고 하자. 이 경우에는 인접해 있는 3, 2가 바뀌어야 하므로 2 3 1 이 된다. 다음으로는 3, 1이 바뀌어야 하므로 2 1 3 이 된다. 다음에는 2, 1이 바뀌어야 하므로 1 2 3 이 된다. 그러면 더 이상 바꿔야 할 경우가 없으므로 정렬이 완료된다.입력첫째 줄에 N(1 ≤ N ≤ 500,000)이 주어진다. 다음 줄에는 N개의 정수로 A[1], A[2..

https://www.acmicpc.net/problem/14428문제길이가 N인 수열 A1, A2, ..., AN이 주어진다. 이때, 다음 쿼리를 수행하는 프로그램을 작성하시오.1 i v : Ai를 v로 바꾼다. (1 ≤ i ≤ N, 1 ≤ v ≤ ((10^9)))2 i j : Ai, Ai+1, ..., Aj에서 크기가 가장 작은 값의 인덱스를 출력한다. 그러한 값이 여러개인 경우에는 인덱스가 작은 것을 출력한다. (1 ≤ i ≤ j ≤ N, 1 ≤ v ≤ ((10^9)))수열의 인덱스는 1부터 시작한다.입력첫째 줄에 수열의 크기 N이 주어진다. (1 ≤ N ≤ 100,000)둘째 줄에는 A1, A2, ..., AN이 주어진다. (1 ≤ ((A_i)) ≤ (10^9))셋째 줄에는 쿼리의 개수 M이 주어..

"파이썬으로 구현하는"시리즈 4세그먼트 트리(Segment Tree)Bottom-Up오늘은 파이썬으로 Bottom-Up 세그먼트 트리를 어떻게 구현하는지 알아볼 것이다.지난번에 Top-Down 구현 올리고 계속 올려야지 하다가 1달동안 미뤄졌다;;;;; 다른 블로그들을 보면 Top-Down이 Bottom-Up 보다 이해하기 쉽다고 한다.개인차일 수도 있는데, 나는 개인적으로 Bottom-Up이 훨씬 이해하기도 쉽고 구현도 간단해서 매우매우 좋아한다!! Bottom-Up의 구현에서는 Top-Down과 인덱스 저장 방식이 약간 다르다. 오늘은 [3, 1, 4, 1, 5, 9, 2]의 7개의 원소를 다뤄보도록 하자.Bottom-Up 구현에서는 Top-Down과 달리 7개의 원소가 모두 같은 높이의 리프 노드에..

https://www.acmicpc.net/problem/2243문제수정이는 어린 동생을 달래기 위해서 사탕을 사용한다. 수정이는 평소에 여러 개의 사탕을 사서 사탕상자에 넣어두고, 동생이 말을 잘 들을 때면 그 안에서 사탕을 꺼내서 주곤 한다.각각의 사탕은 그 맛의 좋고 나쁨이 1부터 1,000,000까지의 정수로 구분된다. 1이 가장 맛있는 사탕을 의미하며, 1,000,000은 가장 맛없는 사탕을 의미한다. 수정이는 동생이 말을 잘 들은 정도에 따라서, 사탕상자 안에 있는 사탕들 중 몇 번째로 맛있는 사탕을 꺼내주곤 한다. 예를 들어 말을 매우 잘 들었을 때에는 사탕상자에서 가장 맛있는 사탕을 꺼내주고, 말을 조금 잘 들었을 때에는 사탕상자에서 여섯 번째로 맛있는 사탕을 꺼내주는 식이다.수정이가 보관..