본문 바로가기

분류 전체보기

 (698)
Union-Find. [20040] [1. 문제 설명] Cycle 이 발생한 순서를 출력한다. (없는 경우 0을 출력) [2. 풀이 접근] 그래프에서 Cycle 을 감지하는 여러 방법이 있다. A. dfs, bfs 중 한번 방문한 정점을 재 방문 하는 경우 (from->to->from 으로 가는 것은 제외) B. union-find 를 이용하여 union 하지 않은 경우 union-find 자료구조는 최초 모든 집합은 자기 자신이 root 인 상태이며, 두 집합이 합쳐지면서, (두 정점이 서로 연결되면서) 그래프를 만들어 나가는데, union 이 실패한다는 것은 두 노드가 이미 같은 집합(트리)에 있다는 것을 말하며, 이미 서로 연결되었다는 것을 의미하기도 한다. (=> 직접 연결되었다는 것이 아니라, 다른 정점을 거쳐 연결된다.) [3...
Union-Find. [4195] [1. 문제 설명] 친구 네트워크란 친구 관계만으로 이동할 수 있는 사이를 말한다. 친구 관계가 생길 때 마다, 두 사람의 친구 네트워크에 몇 명이 있는지 구하도록 한다. [2. 풀이 접근] 문제를 아래와 같이 변형 해볼 수 있다. => 친구 네트워크 == 두 정점이 연결 혹은 두 정점이 같은 집합 => 두 개의 집합이 합쳐질 때마다, => 집합에 속한 원소의 개수를 출력하도록 한다. 즉, 두 노드(집합) 을 합칠 때 마다, 합쳐진 집합에 속한 원소 개수를 출력하면 된다. union find 로 접근한다. 문자열 id 를 정수형 id 로 변환해야 한다. map 을 사용할 경우 O(1) 에 정수형 id 를 얻을 수 있다. union 시, 균형 잡힌 tree 를 만들기 위한 rank 배열 이외 에 집합의 개..
shell script 기초 [1. 개요] 다양한 unix 계열 명령어를 조합하여 실행 할 수 있다. bash 창에서 직접 입력해나가는 것이 아니라 명령어(혹은 명령어 조합)들을 미리 파일에 작성해두고, shell 은 이 파일을 읽어서 명령을 수행한다. [2. 작성 방법] A. Simple example #!/bin/bash # test.sh echo hello 첫번째 라인이 의미하는 바는 이 스크립트를 실행 할 인터프리터를 명시하는 것이다. 따라서 다음과 같이 작성 할 수 도 있다. #!/usr/local/bin/python num=3 for i in range(num): print(i) 최초 작성 한 파일에 퍼미션에는 실행 권한이 없으므로, chmod 명령어를 이용해서 실행 권한을 부여한다. 또는, 다음과 같이 명령어를 작성하여..
partition 에 대해서 [1. 개요] mysql 에서 파티션이란 논리적으로 하나의 큰 table 을 여러개의 작은 table로 분할하여 관리하는 것을 말한다. 마치, elasticsearch 에서 각 index 를 날짜 별로 나누어서 관리하는 것과 비슷하다. (multitenancy) 파티션을 사용했을 때의 장점은 여러가지가 있으며, 보통 용량이 큰 table 을 좀 더 효율적으로 관리할 수 있게 한다. row 가 매우 많은 table 에서는 select, delete, ... 등등 기본적인 쿼리 시간이 굉장히 오래 걸린다. (특히, index 를 사용하더라도) 이 경우 파티션을 대상으로 쿼리를 진행하면, 좀 더 빠르게 쿼리를 처리 할 수 있다. 서버 용량 관리 측면에서도 매우 효과적이다. 파티션은 보통 table 을 생성 할..
Union-Find. [1976] [1. 문제 설명] N 개의 도시가 있고, 각 도시 사이는 연결될 수도 안될 수도 있다. 여행 일정이 주어졌을 때, (방문할 도시들의 순서) 이 여행 경로가 가능한지 확인한다. 여행 일정을 만족하기 위해, 다른 도시를 경유해서 갈 수도 있다. ex) 여행 계획이 E C B C D 라면 E-A-B-C-B-C-B-D라는 여행경로를 통해 목적을 달성할 수 있다. [2. 풀이 접근] 이 문제에서 bfs 등으로 여행 경로를 확인하기에는 무리가 있다. 왔던 길을 되돌아가도 되기 때문이다. 그래서 일반적인 그래프 순회로 풀이하기에는 까다로울 수 있다. 여기서는 상호 배타적 집합을 통해 풀 수 있다. 여행 계획에 있는 도시들이 모두 같은 집합에 있다면, 여행 계획을 만족하는 경로가 반드시 존재하기 때문이다. (왔던 길..
Union-Find. [1717] [1. 문제 설명] 초기에 0~n 이 각각의 집합을 이루고 있다. 합집한 연산과 두 원소가 같은 집합에 포함되어있는지 확인하는 연산을 수행 같은 집합에 포함되어있는 연산이 있을 때, YES 또는 NO 를 출력 [2. 풀이 접근] union find 이론 설명 링크로 대체 == union 시 주의 할 점 u 가 속한 집합, u 의 root 를 v 의 root 로 재설정해야 한다. (u 가 속한 집합이 v 가 속한 집합의 높이보다 항상 작도록 만드는 경우) 이후, find 시 parents 배열은 알아서 재조정된다. [3. 코드]
트리. [4803] [1. 문제 설명] 그래프는 정점과 간선으로 이루어져 있다. 두 정점 사이에 경로가 있다면, 두 정점은 연결되어 있다고 한다. 연결 요소는 모든 정점이 서로 연결되어 있는 정점의 부분집합이다. 그래프는 하나 또는 그 이상의 연결 요소로 이루어져 있다. 트리는 사이클이 없는 연결 요소이다. 트리는 정점이 n개, 간선이 n-1개 있다. => 정점이 n 개 간선이 n-1 개 인 그래프는 트리이다? => FALSE 트리에서 임의의 두 정점에 대해서 경로는 유일하다. 그래프가 주어졌을 때, 트리의 개수를 세는 프로그램을 작성하시오. [2. 풀이 접근] A. DFS 무방향 연결 그래프에서 임의의 트리를 하나 만들 수 있다. 어떤 정점에서 DFS 로 그래프를 한번 순회하면 된다. (혹은 BFS) 트리에서 임의의 두 ..
04. 탐욕법 - 예제3 [1. 문제 설명] [2. 풀이 접근] 적당한 사람을 배정 해야 할 때 vector 를 정렬해서 사용했을 시 문제점 탐색은 O(logn) 이 가능하나, 배정했으므로 vector 에서 제거해야 한다. 이 때, vector 특성 상 제거하는데, O(n) 시간이 소요된다. 이진검색트리인 set 혹은 multiset 을 사용한 경우 탐색과 제거 모두 O(logn) 에 할 수 있다. 그런데 set 은 중복 값을 저장 할 수 없으나 multiset 은 중복 값을 저장 할 수 있다. [3. 코드]
04. 탐욕법 - 예제2 [1. 문제 설명] n 개의 문자열들의 길이가 주어질 때, n 개의 문자열들을 순서와 상관없이 합쳐서 한개의 문자열로 만들 때 필요한 비용의 최소 값 ex) {al, go, spot} 을 합칠 때 {al+go}+spot => al+go 비용: 4, algo+spot 비용 8 => 총 비용 12 [2. 풀이 접근] 한 문자열이 전체 비용에 미치는 영향에 대해서 생각해보면 병합되는 문자열들의 총 길이가 전체 비용에 더해진다. 병합의 대상이 되는 문자열의 길이가 매번 전체 비용에 누적된다고 볼 수 있다. 위 예제에서 "al" 은 "al" + "go" 에서 전체 비용에 더해지고 "algo" + "spot" 에서 전체 비용에 더해진다 볼 수 있다. 그래서, 항상 길이가 짧은 두 문자열이 병합의 대상이 되게 하는 ..
04. 탐욕법 - 예제1 [1. 문제 설명] n 개의 도시락이 있고, i번째 도시락을 데우는데 m[i] 초, 먹는데는 e[i] 초가 걸린다. 도시락을 먹기 위해서는 도시락을 먼저 데워야 한다. 도시락을 여러번에 나누어 데울수는 없다. 모든 사람이 도시락을 다 먹을 때 까지 걸리는 최소 시간 [2. 풀이 접근] 스케줄링 문제는 보통 탐욕법으로 풀 수 있다. (모든 경우는 아님) 전체 시간 = n-1 개의 도시락을 데우는 시간 + 마지막 도시락을 먹는데 걸리는 시간 먹는데 오래 걸리는 도시락부터 데우면 된다. 먹는데 오래 걸리는 도시락을 먼저 데우면, 다른 도시락을 데우는 시간 동안 이 도시락을 먹을 수 있기 때문이다. === 탐욕적 선택 속성 증명 먹는데 가장 오래 걸리는 샤브샤브 도시락을 먼저 데우는 최적해가 반드시 하나 있음을..

티스토리툴바