문제 1717번: 집합의 표현 첫째 줄에 n(1≤n≤1,000,000), m(1≤m≤100,000)이 주어진다. m은 입력으로 주어지는 연산의 개수이다. 다음 m개의 줄에는 각각의 연산이 주어진다. 합집합은 0 a b의 형태로 입력이 주어진다. 이는 a가 �� www.acmicpc.net 문제 풀이 0부터 N까지 집합을 이룰 때, 합집합 연산과 두 원소가 같은 집합에 포함되어 있는지를 확인하고 반환하는 문제이다. 이는 `Union-Find`를 이해하고 구현하면 문제를 쉽게 해결할 수 있다. 즉, 해당 자료구조를 그대로 구현하면 문제를 풀 수 있다. 코드 from sys import stdin def find(target): if target == parent[target]: return target re..
문제 16916번: 부분 문자열 첫째 줄에 문자열 S, 둘째 줄에 문자열 P가 주어진다. 두 문자열은 빈 문자열이 아니며, 길이는 100만을 넘지 않는다. 또, 알파벳 소문자로만 이루어져 있다. www.acmicpc.net 문제 풀이 문자열 S, P가 주어질 때 P가 S의 부분 문자열인지 판단하여 결과를 반환하는 문제이다. 두 문자열의 길이는 100만 미만이므로 단순히 `print(int(p in s))`와 같이 풀게 되면 시간 초과가 발생한다. 따라서 `KMP 알고리즘`을 활용하여 필요 없는 곳의 탐색을 건너뛰도록 하여야 시간 내에 통과할 수 있다. 문제를 풀기 위해서는 `KMP 알고리즘`을 이해하고 구현하면 쉽게 해결할 수 있다. 코드 def make_table(): length = len(p) ta..
문제 6087번: 레이저 통신 크기가 1×1인 정사각형으로 나누어진 W×H 크기의 지도가 있다. 지도의 각 칸은 빈 칸이거나 벽이며, 두 칸은 'C'로 표시되어 있는 칸이다. 'C'로 표시되어 있는 두 칸을 레이저로 통신하기 위해서 www.acmicpc.net 문제 풀이 레이저와 레이저 사이의 통신을 하기 위해 최소한의 거울을 설치하여 통신이 가능하도록 하는 거울의 개수를 반환하는 문제이다. 문제를 풀기 위해서는 레이저가 방향을 바꾸지 않고 최대한 나아갈 수 있는 경우와, 방향을 바꾸는 경우를 생각하여 문제를 접근하면 다음과 같은 로직을 생각할 수 있다. BFS로 탐색을 시작한다. 방향을 바꾸지 않고 갈 수 있는 경로들을 최대한 탐색한다. 범위를 벗어나지 않거나, 벽이 아닌 경우를 말한다. 방향이 바뀌게..
문제 16234번: 인구 이동 N×N크기의 땅이 있고, 땅은 1×1개의 칸으로 나누어져 있다. 각각의 땅에는 나라가 하나씩 존재하며, r행 c열에 있는 나라에는 A[r][c]명이 살고 있다. 인접한 나라 사이에는 국경선이 존재한다. 모�� www.acmicpc.net 문제 풀이 이전에 다룬 안전 영역, 단지번호붙이기 문제와 같이 `Floodfil`을 활용하여, 접근 가능한 영역을 판단하고 그에 따라 처리하는 문제이다. 이 문제에서는 방문 가능한 영역에 대한 조건과 방문 후에 기존 인구에 대한 처리 부분이 추가된 문제이다. 현재 국가로부터 방문 가능한 인접 국가는 `L
