판교의 메타몽

문제 링크 GeeksForGeeks : Union-Find (Click) 문제 요약 아래 2개의 메서드를 완성하라. Union : 2개의 부분집합을 하나로 합치기 isConnected : 2개의 부분 집합이 하나의 부분 집합인지 true or false로 출력하기 문제 풀이 class Solution { public int find(int x, int par[]) { while(x != par[x]) { x = par[x]; } return x; } //Function to merge two nodes a and b. public void union_(int a, int b, int par[], int rank[]) { a = find(a, par); b = find(b, par); if(a==b) re..

문제 링크 The problem link : Geeks For Geeks - Transitive closure of a Graph(클릭) 문제 요약 N*N 배열 graph가 주어집니다. 이 배열은 방향이 있는 그래프를 뜻합니다. graph[i][j]가 의미하는 것은, i 정점에서 j 정점까지 연결되어있는 (= 방향이있는) 간선이 있음을 뜻합니다. 정점 i에서 j까지 (다른 정점을 거쳐서라도) 도달할 수 있는지를 가리키는 그래프를 출력하세요. 핵심 요약 문제 조건을 보면 예상 시간복잡도와 공간복잡도를 이렇게 언급했다. Expected Time Complexity: O(N^3) // 시간복잡도 Expected Auxiliary Space: O(N^2) // 공간복잡도시간 복잡도를 보면 힌트가 나오는데, 이 ..

문제 링크 The problem link : LeetCode 841. Keys and Rooms 문제 요약 0번째부터 n-1까지 라벨이 붙여진 방이 있습니다. 0번째 문을 제외한 나머지 문은 잠겨있습니다. 방에 들어갔을때, 해당 방에 존재하는 key를 사용할 수 있게됩니다. 이렇게되면 key를 사용해 해당 방에 들어갈 수 있습니다. 당신의 목적은 0번째부터 n-1까지의 모든 방을 들어가는 겁니다. 가능할 경우 true를, 그렇지 않을 경우 false를 출력하세요. 예시 입력값 : rooms = [[1,3],[3,0,1],[2],[0]] 출력값 : false 해설 : 2번째 방(=[2])에 들어갈 수 없기 때문에 false입니다. 조건 - n == rooms.length - 2

문제 링크 The problem link : LeetCode 1971. Find if Path Exists in Graph 문제 요약 노드의 개수 n, 간선들이 연결되어있는지 알려주는 배열 edges, 출발지 source, 목적지 destination이 주어집니다. 해당 그래프에서 source와 destination이 연결되어있는지 확인하고, 연결되어있을 경우 true를 반환하세요. Input: n = 3, edges = [[0,1],[1,2],[2,0]], source = 0, destination = 2 Output: true Explanation: There are two paths from vertex 0 to vertex 2: - 0 → 1 → 2 - 0 → 2 문제 풀이 class Soluti..

문제 링크 : https://www.acmicpc.net/problem/14502 14502번: 연구소 인체에 치명적인 바이러스를 연구하던 연구소에서 바이러스가 유출되었다. 다행히 바이러스는 아직 퍼지지 않았고, 바이러스의 확산을 막기 위해서 연구소에 벽을 세우려고 한다. 연구소는 크 www.acmicpc.net 이 문제에서 핵심적으로 구현해야하는 요소는 다음 두 가지다. (1) 벽을 3개 세울 곳 (2) 바이러스가 다 퍼진 후 안전구역의 크기 처음에 벽을 3개 세울 곳을 고민하다보면 자연스럽게 '브루트 포스'가 떠오를텐데, 이렇게되면 시간 초과가 나지 않을까 고민하는 사람도 있을것이다. 하지만 이 문제는 브루트 포스를 활용해도 시간초과가 나지 않는다. 배열의 사이즈는 최대 8*8이기 때문이다. (1) ..

문제 링크 : https://www.acmicpc.net/problem/1043 1043번: 거짓말 지민이는 파티에 가서 이야기 하는 것을 좋아한다. 파티에 갈 때마다, 지민이는 지민이가 가장 좋아하는 이야기를 한다. 지민이는 그 이야기를 말할 때, 있는 그대로 진실로 말하거나 엄청나게 www.acmicpc.net 문제 풀이는 다음과 같다. 1. 먼저 필요한 변수들을 선언해주고 값을 저장해준다. int n,m,t,p,pn,ans=0; bool ch[51]; // 진실을 아는지 여부 bool res[51]; // 과장된 이야기를 할 수 있는 파티 여부 cin >> n >> m; vector party[m+1]; queue q; memset(ch,false,sizeof(ch)); // 배열 초기화 memse..