기맹기 개발 블로그

BOJ 16724 피리 부는 사나이 난이도 : 골드 3 https://www.acmicpc.net/problem/16724 16724번: 피리 부는 사나이 첫 번째 줄에 지도의 행의 수를 나타내는 N(1 ≤ N ≤ 1,000)과 지도의 열의 수를 나타내는 M(1 ≤ M ≤ 1,000)이 주어진다. 두 번째 줄부터 N개의 줄에 지도의 정보를 나타내는 길이가 M인 문자열이 주 www.acmicpc.net 전략 처음에는 단순히 dfs로 탐색해서 연결된 노드들 단위로 개수를 세면 안될까?라고 접근했다. 하지만 이렇게 하면 탐색 순서에 따라 문제가 생길 수 있다. 문제에서 제시된 예시만 보면 dfs로 탐색해도 괜찮을 것 같지만 이런 경우를 보자 (row, col)로 좌표를 나타내었을 때 (1, 1)을 먼저 탐색했..

BOJ 10775 공항 난이도 : 골드 2 https://www.acmicpc.net/problem/10775 10775번: 공항 예제 1 : [2][?][?][1] 형태로 도킹시킬 수 있다. 3번째 비행기는 도킹시킬 수 없다. 예제 2 : [1][2][3][?] 형태로 도킹 시킬 수 있고, 4번째 비행기는 절대 도킹 시킬 수 없어서 이후 추가적인 도킹은 불 www.acmicpc.net 전략 비행기가 순서대로 주어지고, 중간에 한 비행기가 게이트와 연결되지 않으면 이후 비행기들이 연결될 수 없으므로 그리디 형태로 생각해야 한다. 각 비행기는 1

BOJ 1717 집합의 표현 난이도 : 골드 4 https://www.acmicpc.net/problem/1717 1717번: 집합의 표현 첫째 줄에 n(1 ≤ n ≤ 1,000,000), m(1 ≤ m ≤ 100,000)이 주어진다. m은 입력으로 주어지는 연산의 개수이다. 다음 m개의 줄에는 각각의 연산이 주어진다. 합집합은 0 a b의 형태로 입력이 주어진다. 이는 www.acmicpc.net 전략 크루스칼 알고리즘에서 구현했던 것처럼 parent 배열로 union find를 시도했지만 시간초과가 발생했다. 집합들이 A