아롱이의 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를 구할 수 있을 것이다! 그런데 여기서 하나 고려..

나는 맥북을 쓴다.맥북의 장점은, 윈도우보다 좋다는 것이다. 그리고 무엇보다, C++ 컴파일러가 이미 기본적으로 맥에는 깔려있다!!!!!!!! 먼저 이 사이트에서 VSC를 다운받도록 하자.주변 사람들이 왜 지금까지 VSC를 안썼냐고 경악하던데, 파이썬 코더인 나는 원래 Pycharm을 썼다. https://code.visualstudio.com/ Visual Studio Code - Code Editing. RedefinedVisual Studio Code redefines AI-powered coding with GitHub Copilot for building and debugging modern web and cloud applications. Visual Studio Code is free an..

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..

"파이썬으로 구현하는"시리즈 5분할 정복을 이용한 거듭제곱 가끔씩 백준 문제를 풀다가 보면 어떤 수의 거듭제곱을 매우 빠르게 구해야 할 때가 있다. 물론 나머지 연산을 포함해서. 예를 들어 $2^{100}$을 97로 나눈 나머지를 구한다고 하자.2를 100번 곱하는 식의 $O(N)$ 풀이는 시간초과가 난다. 분할 정복을 이용하면 이를 $O(log N)$으로 줄일 수 있다. 사실 구현은 매우 간단하다. $2^{100}$은 $2^{50}$을 두 번 곱한 것이라고 볼 수 있다. 이런식으로 계속 절반으로 줄여나가면서 계산하는 것이다.def mul(b, n): if n == 1: return b if n == 0: return 1 if n % 2 == 1: t..

https://www.acmicpc.net/problem/12771문제세계 경제는 유가에 많은 부분 의존한다. 그래서 석유를 발견하고 시추하는 새로운 방법이 여전히 연구되고 있다. 석유 기업의 이익은 얼마나 석유를 효율적으로 뽑아낼 수 있는지와 관련이 있다. 국제 석유 컨소시엄(ICPC)는 컴퓨터 시뮬레이션을 통해 석유를 어떻게 최선의 방법으로 뽑아낼 수 있는지 알아낼 수 있을 것으로 전망한다.석유를 효율적으로 뽑아내는 것은 날마다 어려워진다. 새로이 발견된 석유 샘은 하나의 덩어리를 이루지 않고 종종 여러 굴로 나뉘어 있기 때문이다. ICPC는 현재 그림 G.1과 같이 층층이 구성된 석유 샘에 관심을 갖고 있다.분석을 간단히 하기 위해 ICPC는 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이 주어..

https://www.acmicpc.net/problem/11437문제N(2 ≤ N ≤ 50,000)개의 정점으로 이루어진 트리가 주어진다. 트리의 각 정점은 1번부터 N번까지 번호가 매겨져 있으며, 루트는 1번이다.두 노드의 쌍 M(1 ≤ M ≤ 10,000)개가 주어졌을 때, 두 노드의 가장 가까운 공통 조상이 몇 번인지 출력한다.입력첫째 줄에 노드의 개수 N이 주어지고, 다음 N-1개 줄에는 트리 상에서 연결된 두 정점이 주어진다. 그 다음 줄에는 가장 가까운 공통 조상을 알고싶은 쌍의 개수 M이 주어지고, 다음 M개 줄에는 정점 쌍이 주어진다.출력M개의 줄에 차례대로 입력받은 두 정점의 가장 가까운 공통 조상을 출력한다. 풀이LCA는 어떤 트리에서 두 정점이 주어질 때 정점들의 최소 공통 조상을 ..

"파이썬으로 구현하는"시리즈 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/29157문제 무한한 크기의 2차원 격자판이 있다. 성모는 좌측 상단의 점 $(0, 0)$에 있고, 우측 하단의 $(N, M)$에 있는 찬민이를 만나러 가려고 한다. 격자판 위에는 $K$개의 폭탄들이 격자점에 있기 때문에, 성모는 폭탄들을 피해서 이동해야 한다. 성모는 오른쪽, 또는 아래로만 이동할 수 있을 때, 성모가 폭탄을 피해서 찬민이가 있는 곳까지 도착할 수 있는 이동할 수 있는 경우의 수를 구하여라.입력첫 번째 줄에 정수 $N, M, K$가 공백으로 구분되어 주어진다. $(1\leq N, M\leq 1\,000\,000;$ $0\leq K\leq 20)$ 두 번째 줄부터 $K$개의 줄에 걸쳐 각 줄에 폭탄의 위치 $(X_{i}, Y_{i}..