4Legs_Archives

문제 링크 : www.acmicpc.net/problem/1849 1849번: 순열 1부터 N까지의 수들이 한 번씩 쓰인 수열이 있다. 그 수열에서 i 앞에 있는 수 들 중, i보다 큰 수들의 개수를 A[i]라고 정의하자. A[i]가 주어져 있을 때, 원래 수열을 구하는 프로그램을 작성하여라 www.acmicpc.net 문제 유형 Segment Tree, 누적 합 문제에서 제시된 예제를 풀어보자. 이러한 과정을 통해 모든 수의 빈칸을 채우면 원하는 수열을 구할 수 있다. 하지만 이를 선형 탐색의 형태로 구현한다면 시간복잡도는 O(N^2)가 되므로, 주어진 시간 제한을 만족할 수 없다. 따라서, 각 수가 들어갈 인덱스를 찾는 데 적어도 O(logN) 의 시간복잡도를 가지도록 구현해야 한다. 전체 시간복잡도..

문제 링크 : programmers.co.kr/learn/courses/30/lessons/72414 코딩테스트 연습 - 광고 삽입 시간을 나타내는 HH, H1, H2의 범위는 00~99, 분을 나타내는 MM, M1, M2의 범위는 00~59, 초를 나타내는 SS, S1, S2의 범위는 00~59까지 사용됩니다. 잘못된 시각은 입력으로 주어지지 않습니다. (예: 04:60:24, 11 programmers.co.kr 문제 유형 Lazy Propagation ※ 이 풀이에서는 공식 해답과 다르게 Lazy Propagation을 사용하였다. 공식 해답의 풀이는 추후 추가 예정 세그먼트 트리(Segment Tree) : Lazy Propagation [선행 개념 : 세그먼트 트리] 세그먼트 트리(Segment..

[선행 개념 : 세그먼트 트리] 세그먼트 트리(Segment Tree) [서론] 크기가 1000인 배열이 있다. 이 배열의 각 원소는 1부터 10까지의 수이다. 이때 i번째 원소부터 j번째 원소까지의 합을 구하고 싶다. 어떤 방법이 좋을까? 가장 먼저 떠오르는 것은 누적합을 4legs-study.tistory.com 이전에 살펴본 세그먼트 트리에서는 트리 값의 갱신을 하나의 인덱스에 대해서만 진행했다. 예를 들어, 인덱스 5에 해당하는 노드의 값을 변경하기 위해 (1-10) -> (1-5) -> (4-5) -> (5) 구간을 거쳐오는 식이다. 하지만 우리는 한 번에 여러 개의 리프 노드에 대한 갱신이 필요할 수도 있다. 그림과 같이 4-10에 대한 구간을 한 번에 갱신하고 싶거나 할 때 말이다. 하지만 ..

문제 링크 : www.acmicpc.net/problem/7626 7626번: 직사각형 첫째 줄에 양의 정수 N이 주어진다. (1 ≤ N ≤ 200,000) 다음 N개 줄에는 공백으로 나누어진 네 값 "x1, x2, y1, y2"가 주어진다. 이 값은 직사각형 [x1,x2] × [y1,y2]를 나타낸다. 모든 좌표는 0보다 크거나 www.acmicpc.net [Swipping] BOJ 3392 화성 지도 문제 링크 : www.acmicpc.net/problem/3392 3392번: 화성 지도 첫째 줄에 화성탐사선 성화가 보낸 지도의 수 N(1 ≤ N ≤ 10,000)이 주어진다. 다음 N개의 줄에는 각 지도의 정보가 주어진다. 지도의 정보는 네 4legs-study.tistory.com 위 문제와 동일한..

문제 링크 : www.acmicpc.net/problem/3392 3392번: 화성 지도 첫째 줄에 화성탐사선 성화가 보낸 지도의 수 N(1 ≤ N ≤ 10,000)이 주어진다. 다음 N개의 줄에는 각 지도의 정보가 주어진다. 지도의 정보는 네 정수 x1, y1, x2, y2 (0 ≤ x1 < x2 ≤ 30,000, 0 ≤ y1 < y2 ≤ 30 www.acmicpc.net 스위핑(Sweeping) 알고리즘으로 해결할 수 있는 대표적인 유형의 문제이다. 스위핑 알고리즘을 간단히 말하자면, 일련의 자료들을 순서대로 한 번 훑으며 정답을 구하는 방법이라 할 수 있다. 개념이 가벼운 만큼 응용된 문제는 꽤 어려운 축에 속한다. 아무튼 이 문제를 스위핑 알고리즘으로 해결하기 위해 다음과 같은 예제를 풀어보자. ..

문제 링크 : www.acmicpc.net/problem/7578 7578번: 공장 어떤 공장에는 2N개의 기계가 2열에 걸쳐 N개씩 배치되어 있다. 이 2개의 열을 각각 A열과 B 열이라고 부른다. A열에 있는 N개의 기계는 각각이 B열에 있는 N개의 기계와 하나씩 짝을 이루어 케이블 www.acmicpc.net 케이블의 교차점은 어떤 조건에서 발생할까? 다음과 같은 예시를 통해 알아보자. A열의 a번째 기계와 연결된 B열의 기계가 a'일 때, 이 기계와 케이블이 교차하기 위한 기계의 위치 (b, b')는 다음 조건을 만족한다. "b a' 또는 b > a AND b' a' 에 주목하자. 이 조건을 이용하면 우리는 두 열..

문제 링크 : www.acmicpc.net/problem/2243 2243번: 사탕상자 첫째 줄에 수정이가 사탕상자에 손을 댄 횟수 n(1≤n≤100,000)이 주어진다. 다음 n개의 줄에는 두 정수 A, B, 혹은 세 정수 A, B, C가 주어진다. A가 1인 경우는 사탕상자에서 사탕을 꺼내는 경우이다. � www.acmicpc.net 문제의 상황에서 맛있는 정도가 1인 사탕이 3개, 2인 사탕이 4개, 5인 사탕이 10개 있다고 가정하자. 이 때, 6번째 사탕과 12번째 사탕의 맛있는 정도는 얼마일까? k번째 사탕의 맛있는 정도를 알기 위해서는 각 사탕들 갯수에 대한 누적합이 필요하다. 사탕이 맛있는 정도를 d라 하자. d = 1 인 사탕은 3개, d = 2인 사탕은 4개이다. d = 2인 사탕까지의..

[서론] 크기가 1000인 배열이 있다. 이 배열의 각 원소는 1부터 10까지의 수이다. 이때 i번째 원소부터 j번째 원소까지의 합을 구하고 싶다. 어떤 방법이 좋을까? 가장 먼저 떠오르는 것은 누적합을 이용한 방법일 것이다. Sk를 Arr[0] ~ Arr[k] 까지의 모든 원소의 합이라 정의할 때, 누적합을 이용해, 구간 (i, j)의 구간합을 Sj - S(i - 1) 로 O(1)에 구할 수 있다. 이 때, Arr의 원소 중 일부가 변경된다면 어떻게 될까? 올바른 구간합을 구하기 위해서는, 누적합을 저장해 놓은 배열을 다시 갱신해야 할 것이다. 배열의 크기가 N이고, 배열값의 변경이 M회 일어날 때 Worst Case에 시간복잡도는 O(NM)이 된다. 이는 N, M의 크기가 어느 정도 커지면 시간 효율..