본문 바로가기

분류 전체보기

 (694)
유니온-파인드. [3197] [1. 문제 설명] https://www.acmicpc.net/problem/3197 [2. 풀이 접근] 매일 물 공간과 접촉한 모든 빙판 공간은 녹는다 물에 상하좌우로 인접한 모든 빙판은 현재 물로 되지 않고 다음 차례에 물이 된다. bfs 를 통해 각 턴 마다 빙하가 물이 되는 것을 모델링 할 수 있다. 백조가 위치한 곳은 물이 있기 때문에, 백조==물로 표현해도 된다. 두 백조가 만나는 경우는, 두 백조 사이의 빙판이 없이 연결된 경우 이 때, 두 백조는 같은 집합에 속하게 된다. 유니온 파인드를 통해 두 백조가 같은 집합에 속했는지 확인 할 수 있다. 백조의 2차원 좌표를 1차원 값(id) 으로 표현해야 한다. [3. 코드]
유니온-파인드. [16562] [1. 문제 설명] https://www.acmicpc.net/problem/16562 [2. 풀이 접근] 친구의 친구는 친구다. 두 사람이 친구라면, 같은 집합에 묶을 수 있다. 유니온-파인드 를 통해 거의 상수 시간에 이 작업이 가능하다. 최소 비용으로 모든 사람과 친구가 되야 한다. 유니온-파인드를 통해 각 그룹에는 여러 명의 사람이 존재한다. 각 그룹에서 가장 싼 비용만 골라서 비용을 지불하면 된다. 단, 남은 비용으로 위 비용을 지불 할 수 없다면 "On no" 를 출력해야 한다. [3. 코드]
유니온-파인드 .[10775] [1. 문제 설명] https://www.acmicpc.net/problem/10775 [2. 풀이 접근] 문제 분류는 유니온-파인드 이지만, 구간트리로도 풀 수 있다. 문제의 핵심은 비행기가 도킹 할 수 있는 게이트 구간에서 현재 사용가능한 것 중 최대 게이트 값을 선택하면 되기 때문이다. 그래서 구간 트리로도 풀이가 가능하다. 여기서 유니온-파인드 를 이용해서, 위 질문에 대한 답이 가능하여, 역시 유니온-파인드를 이용한 풀이 역시 가능하다. 기타 설명은 주석 참조 [3. 코드 - 유니온-파인드] [3. 코드 - 구간 트리]
아호-코라식 예제 [1. 문제 설명] https://algospot.com/judge/problem/read/NH [2. 풀이 접근] 종만 북 참조 [3. 코드]
다중 문자열 검색, 아호-코라식 알고리즘 [1. 개요]트라이를 활용하여 해결 할 수 있는 문제 중 하나로, 다중 문자열 검색 문제가 있다.문자열 H 에서 여러 바늘문자열들 의 출현위치를 모두 계산하는 문제단순한 해결법은 KMP 알고리즘을 찾고자 하는 문자열 개수 만큼 반복하는 방법그러나 이보다 더 빠르게 계산 할 수 있는 방법이 있다.트라이에 포함된 문자열들이 접두사를 공유할 경우, 탐색 공간을 줄일 수 있다.## 반드시 접두사를 공유할 필요는 없다.찾고자 하는 문자열들을 모두 트라이에 저장한 뒤,위에서 생성한 트라이를 이용하여 문자열 H 에서 찾고자 하는 모든 문자열을 한꺼번에 찾을 수 있다.먼저 배경지식, 부분 매치 테이블 이란?KMP 알고리즘 수행을 위해, 전처리 한 데이터문자열 H의 어떤 시작위치 에서 찾고자하는 바늘 문자열 과 matc..
구간트리. [10999] [1. 문제 설명] https://www.acmicpc.net/problem/10999 [2. 풀이 접근] 아래 문제에서 접근했던 방법으로는 해결이 안된다. (시간 초과 발생) https://testkernelv2.tistory.com/408 쿼리 연산 시, leaf 노드까지 내려가는 일이 빈번하기 때문이다. 따라서, Lazy propagation 으로 접근하여 해결한다. ... [3. 코드]
Lazy propagation https://book.acmicpc.net/ds/segment-tree-lazy-propagation
구간 트리. [2517] [1. 문제 설명] https://www.acmicpc.net/problem/2517 [2. 풀이 접근] 첫번째 좌표 압축 실력이라는 값은 10억 이하의 값이다. 그러나 주어지는 데이터 개수는 최대 50만개 이다. 또, 고유한 값으로 주어지므로, 좌표 압축을 통해 현실적인 메모리에서 각 실력의 순위를 확인 할 수 있다. iterate 순서 꼴지부터 iterate 해서, 자신 보다 앞에 있으면서 낮은 실력을 갖는 사람의 수를 구하기 => 이 방식으로 하면, 구간 트리를 먼저 만들고, => 구간 트리에서 낮은 순위에 있는 사람의 실력을 점차적으로 제거해나가야 한다. 1등부터 iterate 해서, 자신 보다 앞에 있으면서 낮은 실력을 갖는 사람의 수를 구하기 => 이 방식으로 하면, empty 한 구간 트리에..
구간 트리. [7578] [1. 문제 설명] https://www.acmicpc.net/problem/7578 [2. 풀이 접근] 구간 트리 작성 시 실수했던 부분 update() 시, index 가 이번 구간을 벗어나는 경우, 현재 노드에 저장되어 있는 값을 그대로 반환해야 한다. query() 와 다른 부분 해결 과정 앞에서 부터 순서대로 확인해왔다고 가정하고 351번 기계 (A index 상 4번째) 가 추가됨으로 인해 교차되는 개수를 구할 때, 351번 기계가 B 에 위치한 곳에서 마지막 구간까지, 존재하는 index 개수를 전체 결과에 더하면 된다. [3. 코드]
구간트리. [2243] [1. 문제 설명] https://www.acmicpc.net/problem/2243 [2. 풀이 접근] 전체 사탕 중, N 번째 순위의 사탕의 맛 정도를 출력해야 한다. 1번째 사탕 3개, 3번째 사탕 2개가 있다고 하면, 1, 1, 1, 3, 3 사탕이 있으므로, 3번째 2번째 순위의 사탕은 1번 사탕이 되는 것이다. 사탕 상자에는 1번 사탕, 3번 사탕, 총 2종류의 사탕이 있어서, 3번 사탕이 되는 것이 아니다,. [3. 코드]

티스토리툴바