일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
1 | 2 | 3 | 4 | 5 | 6 | |
7 | 8 | 9 | 10 | 11 | 12 | 13 |
14 | 15 | 16 | 17 | 18 | 19 | 20 |
21 | 22 | 23 | 24 | 25 | 26 | 27 |
28 | 29 | 30 | 31 |
- DFS
- 누적합
- Greedy
- 백준
- 재귀
- acm
- DP
- 유니온파인드
- 완전탐색
- 알고스팟
- 동적계획법
- 백트래킹
- stack
- 그리디
- 다이나믹프로그래밍
- 스택
- BFS
- BOJ
- priority_queue
- 너비우선탐색
- union-find
- 이분탐색
- backtracking
- 종만북
- 알고리즘문제해결전략
- 문자열
- 분리집합
- Algospot
- 세그먼트트리
- 분할정복
- Today
- Total
목록Problem Solving (85)
DAMPER's blog
https://www.acmicpc.net/problem/1007 1007번: 벡터 매칭 평면 상에 N개의 점이 찍혀있고, 그 점을 집합 P라고 하자. 집합 P의 벡터 매칭은 벡터의 집합인데, 모든 벡터는 집합 P의 한 점에서 시작해서, 또 다른 점에서 끝나는 벡터의 집합이다. 또, P에 속 www.acmicpc.net 평면상의 좌표 N개가 주어지고, 점 2개씩 짝지어 벡터를 이룰 수 있다. 각 점들을 1번만 사용하고 2개씩 매칭하여 N/2 개의 벡터를 만들 수 있다. 이렇게 만든 N/2개의 벡터들을 다 더한 벡터의 길이가 최소가 되도록 만들면 된다. sol1. 재귀 완전탐색으로 탐색하면서 벡터를 만들어 갔다. 현재 위치가 N이 되는 순간 벡터 요소의 제곱들의 합을 비교하여 최소값을 찾았다. 최적화를 한..
![](http://i1.daumcdn.net/thumb/C150x150/?fname=https://blog.kakaocdn.net/dn/lmvFM/btrGn9Ii4We/y1C3aq65KuCPDXpsch5Ak0/img.png)
이번 글은 세그먼트 트리 활용중 하나인 K번째 원소 찾기 입니다. https://www.acmicpc.net/problem/12899 12899번: 데이터 구조 첫째 줄에 사전에 있는 쿼리의 수 N 이 주어집니다. (1 ≤ N ≤ 2,000,000) 둘째 줄부터 N개의 줄에 걸쳐 각 쿼리를 나타내는 2개의 정수 T X가 주어집니다. T가 1이라면 S에 추가할 X가 주어지는 것입니 www.acmicpc.net 문제에는 두 가지 종류의 쿼리가 존재한다. 유형 1 : 데이터베이스 S에 자연수 X를 추가한다. 유형 2 : S에 포함된 숫자 중 X번째로 작은 수를 응답하고 그 수를 삭제한다. 쿼리는 최대 200만개 까지 가능하니 한 쿼리를 최대 O(NlogN)에 처리해야 한다. 다행히도(?) X의 범위는 1부터 ..
![](http://i1.daumcdn.net/thumb/C150x150/?fname=https://blog.kakaocdn.net/dn/7Yhe3/btrF3ZNVQ4h/xhNTOakoR96KBrSkzSQSQ0/img.png)
무향 그래프에서 단절점(Cut vertex) 찾기 단절점이란 해당 정점과 인접한 간선들을 모두 지웠을 때 해당 컴포넌트가 두 개 이상으로 나뉘어지는 정점을 말합니다. 아래 그림을 예시로 들었을 때, 1번 정점과 인접한 간선을 모두 지웠을 때, 0번 정점이 떨어져나가 하나의 컴포넌트가 됩니다. 그러므로 1번 정점은 단절점입니다. 마찬가지 이유로 3번, 5번 정점도 단절점입니다. 단절점을 찾는 방법으로 여러가지가 있지만 DFS 탐색 1회만으로 그래프의 모든 단절점을 찾을 수 있습니다. 먼저 아무 정점으로부터 DFS 트리를 만듭니다. 이 때 임의의 정점 u와 연결된 정점들은 모두 u의 조상이거나 자손입니다. 만약 u와 인접한 간선들을 모두 지웠을 때 그래프가 나눠지지 않는 경우는 u의 자손들이 u의 선조와 역..
이번 글은 세그먼트 트리를 활용 방법 중 하나인 Counting Inversions 이다. 길이가 N이고 1부터 N까지의 수를 1개씩 가지고 있는 순열이 있다고 하자. Counting Inversions는 각 수에서 오른쪽으로 자기 자신보다 작은 수의 갯수의 합(또는 왼쪽으로 자기 자신보다 큰 수의 갯수의 합)을 말한다. 예를 들어, A ={4, 1, 3, 2} 라는 수열이 있다고 하자. 4-1, 4-3, 4-2, 3-2 총 4개의 inversion이 존재한다. 이를 세그먼트 트리로 해결할 수 있는데, 저번 글에서 우리는 먼저 세그먼트 트리를 구성해놓고, 최소값을 찾으러 갔다. 하지만 이 문제에서는 먼저 세그먼트 트리를 구성하는 것이 아니라, 세그먼트 트리를 구성하면서 답을 찾아가는 것이다. 배열에 수열..
![](http://i1.daumcdn.net/thumb/C150x150/?fname=https://blog.kakaocdn.net/dn/NiBvW/btrDoT2W4qa/VeF08L9XfKrCKlkqmnkqFk/img.png)
PS분야에서 정말 다양하게 쓰이고 있는 자료구조로 자유자재로 쓰고싶은 마음에 이번 기회에 정리하고자 한다. 세그먼트 트리는 흔히 일차원 배열의 특정 구간에 대한 쿼리를 빠르게 답하는 데 사용한다. 물론 다차원 배열의 특정 구간에 대한 세그먼트 트리도 구현이 가능하다. 가장 기본적인 예로 어떤 배열의 부분 구간의 최소치를 구하는 연산을 여러번 하는 것이다. 배열 A = {1, 2, 1, 4, 6, 1, 5, 8}가 있다면 구간[2, 4]의 최소값은 1이고 구간[6, 7]의 최소값은 5이다. 이 문제를 세그먼트 트리를 통해 O(qlogn)에 해결할 수 있다. 세그먼트 트리의 기본적인 아이디어는 주어진 배열의 구간들을 표현하는 이진 트리를 만드는 것이다. 루트는 전체 구간을 표현하고, 리프는 1개만을 표현한다..
https://www.acmicpc.net/problem/13140 13140번: Hello World! N이 주어질 때 hello + world = N을 만족하는 서로 다른 한 자리 자연수(0 포함) d, e, h, l, o, r, w를 구해서 아래 그림과 같은 형태로 출력하는 프로그램을 작성하여라. 단, h와 w는 0이 될 수 없다. www.acmicpc.net 문제 설명 복면산 문제와 같은 문제이다. hello + world = N을 만족하는 d, e, h, l, o, r, w 7글자에 서로다른 숫자를 대입해서 N이 나오는가를 묻는 문제이다. 재귀 완전탐색으로 7글자에 대한 수를 0부터 9까지 넣는 과정을 진행했는데, w와 h에는 0이 들어갈 수 없으므로 이 부분을 처리해주면 된다. 1 2 3 4 ..