일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
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 |
- BOJ
- Greedy
- 세그먼트트리
- 완전탐색
- 백트래킹
- 알고스팟
- Algospot
- 문자열
- BFS
- backtracking
- DP
- 스택
- 종만북
- 분할정복
- 누적합
- 분리집합
- 너비우선탐색
- union-find
- stack
- 백준
- 유니온파인드
- DFS
- 그리디
- 재귀
- 알고리즘문제해결전략
- acm
- 이분탐색
- 동적계획법
- priority_queue
- 다이나믹프로그래밍
- Today
- Total
목록Problem Solving/Algorithms (4)
DAMPER's blog
알고리즘이란? 문제를 해결하는 단계적인 절차를 말한다. 알고리즘을 설계하고 분석하는 기술을 배우는 이유는 무엇일까? 새로운 문제에 직면했을 때 그 문제를 해결하기 위한 방법들을 익혀두기 위함이다. 여러 가능한 방법들이 있을 때 알고리즘 분석을 통해 어떤 방법을 선택할 지 결정할 수 있도록 수치화 하는 능력을 길러야 한다. -> 문제 해결력 제고 알고리즘 분석 요소 알고리즘을 수행했을 때 소요되는 시간 알고리즘을 수행할 때 차지하는 메모리 공간 알고리즘 분석 Time Complexity Analysis (시간 복잡도 분석) input size에 따라서 basic operation이 몇번 수행되는 지 결정하는 절차를 말한다. CPU에서의 실제작동 시간, 명령문의 개수, 프로그래밍 언어, 프로그래머, 포인터의..
![](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부터 ..
이번 글은 세그먼트 트리를 활용 방법 중 하나인 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개만을 표현한다..