본문 바로가기

분류 전체보기

 (689)
dfs. [2644] [1. 문제 설명] https://www.acmicpc.net/problem/2644 [2. 풀이 접근] 그래프 구축 모든 부모 자식 간의 관계에 대해서, 그래프를 무방향 그래프로 구축해야 한다. 부모->자식으로 가는 방향 그래프로 구축한다면, 임의의 두 사람 u, v 에 대해서 촌수를 구할 수 없다. u 가 자식이고, v 가 부모인 경우, u->v 인 edge 는 존재하지 않기 때문이다. 따라서, 그래프는 무방향 그래프로 구축해야 한다. DFS 종료 시 처리 u 에서 dfs 를 시작하였는데, v 를 만나지 못했다면, 재귀를 종료하고 되돌아가는 시점에서, 현재까지 방문한 모든 정점에 대해서 다시 미방문 처리하지 않아도 된다. 이 정점들은 v 와는 아무 관련이 없기 때문이다. u 에서 dfs 시작 후, a..
dfs. [1987] [1. 문제 설명]] https://www.acmicpc.net/problem/1987 [2. 풀이 접근] [3. 코드]
KMP. [1305] [1. 문제 설명] https://www.acmicpc.net/problem/1305 [2. 풀이 접근] 간단한 방법 광고 문구 길이를 1부터 시작해서 반복 각 시작 위치부터 광고문구 길이를 n 이라 했을 때, 문자열이 반복되는지 확인해야 함 시간복잡도 = O(N3) 시간 초과. kmp 알고리즘 중 부분 매치 테이블을 이용한 풀이 핵심은, n 글자 일치 했을 때, 접두사==접미사인 가장 긴 문자열의 길이를 구하는 것 자세한 설명은 주석 참조 [3. 코드]
dfs - 예제1 [1. 문제 설명] https://algospot.com/judge/problem/read/WORDCHAIN [2. 풀이 접근] [3. 코드]
DFS - 오일러 서킷, 트레일 [1. 개요] dfs 를 이용하여 해결 할 수 있는 문제 중 오일러 서킷은 다음과 같은 문제를 말한다. 그래프의 모든 edge 를 정확히 한번만 사용해서 시작점으로 되돌아 오는 경로 무방향 그래프, 방향 그래프 모두에서 해결 가능하다. 기본적으로 오일러 서킷이 존재 할 수 없는 경우 그래프가 두 개 이상의 컴포넌트로 나뉜 경우 차수가 홀수 인 정점이 존재하는 경우 => 어떤 점으로 들어갔는데, 이 점의 차수가 1이면 나올 수 없다. => 이 점이 시작점이 아닌 경로의 끝점인 경우, 오일러 서킷을 완성 할 수 없다. 오일러 서킷이 존재 하는 경우 모든 정점의 차수가 짝수 => 단, 방향 그래프에서는 incoming edge 개수와 outgoing edge 개수가 같아야 한다. 모든 edge 가 하나의 컴포..
유니온-파인드. [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..

티스토리툴바