전체보기272 유니온 파인드란?? (Union-Find) 유니온 파인드(Union-Find)란 ? CS에서 서로소 집합을 찾는 기능을 구현하기 위해 중요한 역할을 하며 많은 서로소 부분 집합들로 나눠진 원소들에 대한 정보를 저장하고 조작하는 자료 구조이다. (MakeSet으로 각각의 요소를 생성하였다) (union 연산을 수 차례 수행하여 집합을 생성하였다) 출처 : 위키피디아 크게 세 가지 기능으로 분류를 할 수 있다. 1. Union function Union(x, y) // x와 y를 같은 집합으로 묶는 작업이다. xRoot := Find(x) // x의 최상단 부모를 찾음 (x의 집합이 어디인가?) yRoot := Find(y) // y의 최상단 부모를 찾음 (y의 집합이 어디인가?) xRoot.parent := yRoot // x와 y를 묶는다. 2... 2019. 5. 12. [백준 1717] 집합의 표현 Union_Find (유니온 파인드)의 개념을 알고 있으면 금방 풀 수 있는 문제이다.연산 명령이 0이면 Union 함수를 사용하여 같은 집합으로 묶어주면 되고연산 명령이 1이면 Find 함수를 사용하여 최상위 부모가 같은지 확인하여구현하여 풀 수 있는 문제이다. ※ 입력과 출력이 매번 있기 때문에 cin cout 보다는 ※ ※ scanf 과 printf를 쓰는 것이 바람직하다. ※ 참고하면 좋은 글 : 유니온 파인드란?? 출처 : https://www.acmicpc.net/problem/1717 문제 초기에 {0}, {1}, {2}, ... {n} 이 각각 n+1개의 집합을 이루고 있다. 여기에 합집합 연산과, 두 원소가 같은 집합에 포함되어 있는지를 확인하는 연산을 수행하려고 한다.집합을 표현하는 프.. 2019. 5. 12. [백준 3015] 오아시스 재결합 스택을 활용한 문제 중에서는 쉬운 축에 속하지는 않지만 로직을 알고보면 금방 구현할 수 있는 문제이다. 우선 (1 ≤ N ≤ 500,000) N 제한이 50만이기 때문에for문으로 검사를 하면 25억번의 연산 => 25초가 걸리게 된다.(시간초과) 그래서 간단하게 스택을 사용하도록 하면대부분의 스택 연산에는 O(n)만에 연산이 가능하기 때문에거의 1초 내로 풀 수 있게 된다. 자세한 설명은 소스코드를 보면 이해가 쉽다. 출처 : https://www.acmicpc.net/problem/3015 문제 오아시스의 재결합 공연에 N명이 한 줄로 서서 기다리고 있다. 이 역사적인 순간을 맞이하기 위해 줄에서서 기다리고 있던 백준이는 갑자기 자기가 볼 수 있는 사람의 수가 궁금해 졌다. 두 사람 A와 B가 서로 .. 2019. 5. 12. [백준 9935] 문자열 폭발 스택 입문으로 풀기에는 쉬운 문제는 아니다. 보자마자, 떠오르는 방법으로 구현을 해봤지만 보기 좋게 틀린 문제이다.또한 질문게시판에서 반례를 찾아봤지만, 문제의 조건에 맞지 않는 반례 때문에 헤매기도 하였다.( 조건 : 폭발 문자열에서 같은 문자는 2번 이상 나올 수 없습니다) stack st 을 사용하여first에는 문자열의 해당하는 위치second에는 폭발 문자열에 해당하는 인덱스를 삽입하며 진행한다. 기존 문자열 : mirkovC4nizCC44 폭발 문자열 : C4 1. if(a[i] == b[0]) // m i r k o v ... 이때 C에서 (a[6] == b[0]) 이기 때문에 st.push(make_pair( i, 0 )을 시켜준다. ** 폭발 문자열의 첫번째 문자는 매번 검사해줘야 한다 .. 2019. 5. 12. [백준 11725] 트리의 부모 찾기 DFS 혹은 BFS 탐색을 사용하여 풀 수 있는 전형적인 문제이다. 가중치가 없는 양방향으로 백트래킹이 필요한 트리이기 때문에 vector tree를 사용하여출처 : 위키백과tree[2].push_back(7)tree[7].push_back(2)...을 사용했다. stack st; // 지나쳐온 노드를 저장하는 stack vector tree[100001]; // tree[i] = j (i번째 노드와 j번째 노드는 연결되어있다) int depth[100001]; // 깊이를 나타낸다 (방문 여부도 검사 가능) int parent[100001]; // 인덱스별 부모를 저장하기 위한 배열 출처 : https://www.acmicpc.net/problem/11725 문제 루트 없는 트리가 주어진다. 이때, 트.. 2019. 5. 11. [백준 3111] 검열 아직 도전하기에는 쉬운 문제는 결코 아닌 듯 했다. 2개의 Stack을 사용하여, 하나는 왼쪽부터 검사 또 다른 하나는 오른쪽부터 검사를 하여 없애고자 하는 문자열을 모두 없애는 기능을 구현하는 것인데, 필자의 소스코드에는 왼쪽과 오른쪽을 합쳐 없애야 하는 알파벳을 사라지게 하는 부분을 아직 구현을 하지 못해 contest solution을 올렸다. http://hsin.hr/2009/index.html위 사이트에 들어가면 다양한 Testcase를 제공하니반례를 찾을 때 매우 유리하다. 출처 : https://www.acmicpc.net/problem/3111 문제 김상근은 창영마을에서의 권력을 유지하기 위해 신문을 검열하려고 한다.상근이는 텍스트 T에서 A라는 단어를 다음과 같은 알고리즘을 이용해서 모.. 2019. 5. 11. 이전 1 ··· 36 37 38 39 40 41 42 ··· 46 다음
