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 라이브러리를 이용해 간단히 해결할 수 있었습니다.
https://www.acmicpc.net/problem/10164 10164번: 격자상의 경로 입력의 첫째 줄에는 격자의 행의 수와 열의 수를 나타내는 두 정수 N과 M(1 ≤ N, M ≤ 15), 그리고 ○로 표시된 칸의 번호를 나타내는 정수 K(K=0 또는 1 < K < N×M)가 차례로 주어지며, 각 값은 공백으 www.acmicpc.net 정답률은 30%대이지만 그렇게 어렵지 않은 문제였습니다. 중,고등학교 때 격자 길찾기 문제랑 똑같은 문제입니다. 시작점에서 가로 세로로 1을 모두 그리고 위, 왼쪽에 있는 값을 더해나가는 원리로 똑같이 하면 됩니다. 공식을 이용한 방법도 있습니다. a가 n개, b가 m개, c가 k개, ...., 이런 식으로 있다고 하면 얘네를 나열할 수 있는 경우의 수는 (n..
https://www.acmicpc.net/problem/2352 2352번: 반도체 설계 첫째 줄에 정수 n(1 ≤ n ≤ 40,000)이 주어진다. 다음 줄에는 차례로 1번 포트와 연결되어야 하는 포트 번호, 2번 포트와 연결되어야 하는 포트 번호, …, n번 포트와 연결되어야 하는 포트 번호가 주 www.acmicpc.net 지난 번에 어떤 문제를 이분 탐색으로 풀려다가 자꾸 실패해서 다르게 풀었었는데 그래서 이분 탐색 문제를 하나 더 풀었습니다. 반도체들이 어떻게 하면 가장 많이 연결할 수 있을 지 구하는 문제입니다. 해당 문제는 최장 부분 수열 구하는 문제와 동일합니다. 예를 들어 주어진 그림과 같이 1-4 / 2-2 / 3-6 / 4-3 / 5-1 / 6-5 와 같이 연결되어 있다면 연결 끝부..