https://www.acmicpc.net/problem/17142 17142번: 연구소 3 인체에 치명적인 바이러스를 연구하던 연구소에 승원이가 침입했고, 바이러스를 유출하려고 한다. 바이러스는 활성 상태와 비활성 상태가 있다. 가장 처음에 모든 바이러스는 비활성 상태이고 www.acmicpc.net 연구소에 바이러스가 포진되어 있을 때 바이러스가 전체에 퍼지는데 걸리는 시간의 최솟값을 구하는 문제입니다. 전체 맵의 최대 크기는 50*50 이지만 문제 조건에 바이러스 최대 개수가 10개라 하였으므로 활성바이러스 10C5가지의 경우가 최대 경우의 수입니다. 풀이는 다음과 같습니다. 1. 전체 바이러스 중 활성바이러스를 고른다. (dfs로 조합을 이용해 미리 구해주었습니다.) 2. 활성바이러스를 bfs로 ..
10840번: 구간 성분 (acmicpc.net) 10840번: 구간 성분 첫 두 줄에 신호 서열이 공백 없는 하나의 문자열로 각각 주어진다. 이 문자열은 영문 소문자로만 구성되어 있다. 두 입력 문자열의 크기 N, M의 범위는 1 ≤ N, M ≤ 1,500 이다. www.acmicpc.net 주어진 두 문자열에서 부분 문자열 중 알파벳의 종류와 개수만 같으면 되는 부분 문자열의 최장 길이를 구하는 문제입니다. Ex. abcde / cbaff => 3 단순히 비교하면 두 문자열 길이가 n, m 이라 하면 O(n^2 * m^2) 입니다. (길이 m인 문자열의 부분문자열 1~m까지 길이 같는 건 각각 약 m개 => m^2, n인 것도 마찬가지 => n^2 => 전부 일일이 비교 => n^2 * m^2) 부분..
https://www.acmicpc.net/problem/1007 1007번: 벡터 매칭 평면 상에 N개의 점이 찍혀있고, 그 점을 집합 P라고 하자. 집합 P의 벡터 매칭은 벡터의 집합인데, 모든 벡터는 집합 P의 한 점에서 시작해서, 또 다른 점에서 끝나는 벡터의 집합이다. 또, P에 속 www.acmicpc.net N개의 점을 시점과 종점이 겹치지 않게 벡터를 N/2개를 만들고 벡터들의 합 벡터의 크기를 최소로 만드는 문제입니다. 단순히 20개의 점을 2개씩 묶는다고 생각하면 20C2 * 18C2 * ... 2C2 가 되어 엄청난 경우의 수가 나옵니다 A, B 두 점을 이은 벡터 AB는 결국 원점을 기준으로 OB - OA 입니다. 결국 N개의 점 중 N/2개의 점은 뺄셈을 적용, 나머지는 덧셈을 적..
https://www.acmicpc.net/problem/18353 간단한 최장 부분 수열 문제였습니다. 예전에는 C++로 풀었는데 그냥 파이썬의 bisect 라이브러리 써보고 싶어서 풀었습니다. 문제는 간단합니다. 주어진 배열을 뒤집으면 최장 부분 수열 구하는 문제와 동일합니다. (사실 '초과'가 아닌 '이상'으로 생각하고 풀어서 몇 번 틀렸다.....) python3의 bisect 라이브러리에는 bisect, bisect_left, bisect_right 3가지 경우가 있습니다. 모두 이분탐색으로 찾고자하는 위치를 리턴합니다. 또한 low, high 값을 지정하여 탐색의 시작, 끝 index를 설정할 수 있습니다. bisect는 주어진 리스트에서 찾고자하는 값이 들어갈 수 있는 index를 리턴하고,..
https://www.acmicpc.net/problem/1013 문제가 무슨 말인지 잘 이해가 안 되어 찾아보니 문제에서 설명하는 것이 정규표현식이란 것이었습니다. 정규표현식은 특정 규칙을 가진 문자열 집합을 표현하는 형식입니다. C++11 이후부터 regex 라이브러리를 통해 정규표현식을 제공하고 있습니다. 정규표현식 개념과 문법 예 https://ko.wikipedia.org/wiki/%EC%A0%95%EA%B7%9C_%ED%91%9C%ED%98%84%EC%8B%9D C++의 regex 라이브러리를 이용해 간단히 해결할 수 있었습니다.