본문 바로가기

분류 전체보기

 (694)
그래프 탐색 솔루션 [1. DFS 개요] 재귀를 이용한 구현 재귀 호출 전 방문처리를 하도록 한다. [2. BFS 개요] 큐에 푸쉬하는 순간 바로 방문처리를 바로 하도록 한다. bfs 탐색 특성 최단 경로. a b c [3. 예제] https://testkernelv2.tistory.com/478 https://testkernelv2.tistory.com/483 https://testkernelv2.tistory.com/575 https://testkernelv2.tistory.com/577 === bfs === https://testkernelv2.tistory.com/579 https://testkernelv2.tistory.com/580 https://testkernelv2.tistory.com/581 https://..
유니온 파인드. [1043] [1. 문제 설명] https://www.acmicpc.net/problem/1043 [2. 풀이 접근] 최초에는 모든 파티에 참가할 수 있다고 할 수 있다. 이 후, 어떤 파티에 진실을 아는 사람이 있는 경우 이 파티를 참가하지 않도록 한다. 또, 어떤 파티에 진실을 아는 사람이 없는 경우 이 파티에는 무조건 참가가 가능하지는 않다. 이 파티에 참가한 사람이 진실을 모르더라도, 다른 파티에 참석하여 진실을 아는 사람과 만나는 경우에는 결국 진실을 알게 될 것이기 때문이다. 따라서 모든 파티에 참가자가 서로 만날 것인가에 대한 여부를 먼저 처리해야 한다. 전처리를 먼저하고 나서 파티 참석 여부를 따져야 한다는 것이다. 전처리는 아래와 같이 진행한다. 진실을 아는 사람들을 하나의 집합에 속하게 한다. 각 ..
이분탐색. [1939] [1. 문제 설명] https://www.acmicpc.net/problem/1939 [2. 풀이 접근] 시도 혹은 시도해보려 했던 오답인 풀이 유니온-파인드 => 공장이 있는 섬과 같은 집합에 속한 섬들이 존재 => 공장1에서 공장2로 갈때 이 섬들을 거쳐서만 갈 수 있다. => 즉, 이 집합에 속한 섬들을 연결 하는 edge 중 최소 weight 를 찾는다. ==> 틀린 이유 # 특정 경로를 선택 하였을 때, 위에서 선택 된 최소 weight 를 갖는 edge 를 거치지 않을 수 있다. BFS 에서 모든 경로 탐색 => BFS 에서 visit 을 업데이트 하지 않으면 모든 경로 탐색이 가능 할까라는 생각에서 출발 => 그래프 유형은 약간 다르지만, visit 을 업데이트 하지 않고 풀이가 가능했던 문..
유니온 파인드 솔루션 [1. 개요] "상호 배타적 집합 == 유니온 파인드 == 분리집합" 전부 같은 표현이며, 보통 "유니온 파인드" 라는 명칭이 고유 명사 처럼 사용된다고 한다. 유니온 파인드 자료구조 구현을 위해서는 세가지 연산이 필요하다. 초기화를 제외한 연산의 시간복잡도는 거의 상수시간이 되도록 작성해야 한다. 초기화 => 각 원소가 각각의 집합에 포함되도록 한다. union => 두 원소를 하나의 집합을 합친다. find => 원소가 속한 집합을 반환한다. 위 자료구조 구현 패턴을 정의하도록 한다. 초기화 구현 패턴 int parents[] => 각 원소에 대해서 parents[i] = i 로 초기화 한다. => 자신의 부모가 자기 자신 => root int ranks[] => 각 원소가 속한 집합(트리)의 높이로..
구간 트리. [10868] [1. 문제 설명] https://www.acmicpc.net/problem/10868 [2. 풀이 접근] 구간의 최대 길이는 100,000 이며, 구간 트리를 구현하는데 필요한 공간복잡도 O(400,000) 으로 합격 구간 트리 구현 패턴을 지켜 작성하도록 한다. [3. 코드]
우선 순위 큐. [1715] [1. 문제 설명] https://www.acmicpc.net/problem/1715 [2. 풀이 접근] 값이 큰 숫자가 덧셈의 피연산자로 최대한 적게 사용 되어야 한다. 전체 숫자 들 중 가장 작은 값 2개만 계속 더해나가야 한다. 매번 숫자들을 정렬할 수 없으니, 최소 힙을 사용하도록 한다. 즉, 매번 최소 힙에서 두개의 숫자를 꺼내 더하고, 힙에 푸쉬하는 작업을 반복하면 된다. [3. 코드]
KMP. [1786] [1. 문제 설명] https://www.acmicpc.net/problem/1786 [2. 풀이 접근] KMP 알고리즘 (Text 에서 Pattern 이 존재하는 모든 시작위치를 반환) T[i...] 에서 P[...n] 이 일치하지만, P[n+1] 에서 불일치 한 경우 다음 탐색 위치를 좀 더 효율적으로 설정하여 탐색 속도를 빠르게 한다. P[...n] 이 일치하였으므로, P[...n] 에서 접두사와 접미사가 같은 곳이 있다면, 탐색 위치를 접두사 길이 만큼 점프할 수 있다. [3. 코드]
BFS. [14502] [1. 문제 설명] https://www.acmicpc.net/problem/14502 [2. 풀이 접근] 그래프 순회가 필요한 이유 이차원 배열에서 바이러스가 퍼져나간다. BFS 를 통해 이러한 과정을 모델링 할 수 있다. 완전 탐색 지도의 최대 크기는 8x8 이며, 여기서 반드시 벽을 놓을 위치 세곳을 정해야 한다. 전체 경우의 수는 64C3 으로 대략 41,664 로 현실적인 경우의 수 인 것을 알 수 있다. => 현실적인 경우의 수 라면, 완전 탐색이 가장 안전한 풀이가 가능하다. 중복문제 벽을 놓을 위치를 정하는 것은 재귀 함수로 구현 할 수 있다. 문제는 벽을 놓을 때, 중복으로 놓은 경우를 막아야 한다는 것이다. 보통 중복으로 세는 경우를 방지하기 위해서는 항상 특정 형태로 답을 세는 것이다..
구간 트리 솔루션 [1. 개요] 구간 트리란? 보통 일차원 배열을 대상으로 특정 구간에 대한 쿼리를 O(logn) 에 할 수 있다. 구간 트리를 대상으로 하는 연산은 크게 3가지로 아래와 같다. 1. init() 2. query() 3. update() 구간 트리 존재 의의 특정 구간의 합은 부분합으로 더 빠르게 O(1) 만에 구할 수 있지만, 어떤 원소의 값이 바뀌면 O(n) 의 시간을 들여 부분 합을 다시 만들어야 한다. 구간 트리는 O(logn) 으로 update 하고, 구간의 합을 O(logn) 으로 구할 수 있다. 구간 트리 구현을 아래와 같이 한가지 패턴으로 작성하도록 한다. u # 구간 트리의 노드 번호, (Root 의 노드 번호는 1 이다.) left # u 의 포함되는 구간의 가장 왼쪽 right # u ..
우선 순위 큐 관련 솔루션 [1. 개요] 우선 순위 큐(=편의 상 힙으로 표기) 는 정렬 상 우선순위가 높은 원소를 먼저 꺼낼 수 있는 큐이다. 최대 힙 최소 힙 힙을 대상으로 하는 push 와 pop 모두 O(logn) 으로 동작한다. 힙 내부 데이터 변경으로 인해 heapify 가 필요할 수도 있지만, 이런 경우에 자주 없다. 다익스트라에서 특정 노드에 대한 가중치가 바뀌는 경우가 대표적이지만, 이 때에는 힙에 다시 푸쉬하는 편이 더 간단하다. heapify 는 보통 O(n) 으로 동작하여 다소 느려, 오히려 더 안 좋을 수 있다(?). 보통의 문제는 크게 최대 힙, 최소 힙 둘 중 하나만 사용하는 경우가 다수이지만, 두 가지 힙 모두 사용하여 풀어야 하는 문제도 간혹 존재한다. 대표적으로 Running median 같은 문제..

티스토리툴바