Python/백준
14425_문자열 집합
https://www.acmicpc.net/problem/14425 14425번: 문자열 집합 첫째 줄에 문자열의 개수 N과 M (1 ≤ N ≤ 10,000, 1 ≤ M ≤ 10,000)이 주어진다. 다음 N개의 줄에는 집합 S에 포함되어 있는 문자열들이 주어진다. 다음 M개의 줄에는 검사해야 하는 문자열들이 주어 www.acmicpc.net 단순하게 풀 수 있는 문제인데 리스트로 풀면 시간초과가 나는 문제였다... 새롭게 알게된 사실인데 list자료형의 삽입,탐색등의 시간복잡도는 O(n)이며 딕셔너리 set의 자료형은 O(1)이라서 많은 차이가 난다고 한다. 이를 잘 생각하고 풀어보는것도 괜찮은 것 같다. import sys input = sys.stdin.readline n,m = map(int,in..
17404_RGB거리2
https://www.acmicpc.net/problem/17404 17404번: RGB거리 2 첫째 줄에 집의 수 N(2 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 각 집을 빨강, 초록, 파랑으로 칠하는 비용이 1번 집부터 한 줄에 하나씩 주어진다. 집을 칠하는 비용은 1,000보다 작거나 www.acmicpc.net RGB거리 문제와 동일하지만 첫번째 집과 마지막집이 연결된 형태이다. 첫집과 마지막집의 색이 같아야 하지 않으므로 세 경우를 집어서 생각할 수 있다. 첫집을 R로 칠하고 dp를 채워나가 cost를 만든 것중 마지막집을 G,B로 칠한것중 최소비용 첫집을 G로 칠하고 dp를 채워나가 cost를 만든 것중 마지막집을 R,B로 칠한것중 최소비용 첫집을 B로 칠하고 dp를 채워..
2098_외판원순회 1
https://www.acmicpc.net/problem/2098 2098번: 외판원 순회 첫째 줄에 도시의 수 N이 주어진다. (2 ≤ N ≤ 16) 다음 N개의 줄에는 비용 행렬이 주어진다. 각 행렬의 성분은 1,000,000 이하의 양의 정수이며, 갈 수 없는 경우는 0이 주어진다. W[i][j]는 도시 i에서 j www.acmicpc.net 해당문제를 풀기 위해선 비트마스크, dp , dfs 총 3가지의 알고리즘을 활용해서 풀 수 있다. 처음에 비트마스크와 dp만 가지고 풀어보려다가 많이 헤맸던 문제이다.. 먼저 dp는 2차원 dp로 선언을 한 후 dp[i][j]라면 i는 현재 도시의 위치, j는 현재까지 방문한 도시들을 기록한다. 이때 j를 비트마스크를 이용해서 기록한다. 즉, 현재 도시가 3이..
11723_집합
https://www.acmicpc.net/problem/11723 11723번: 집합 첫째 줄에 수행해야 하는 연산의 수 M (1 ≤ M ≤ 3,000,000)이 주어진다. 둘째 줄부터 M개의 줄에 수행해야 하는 연산이 한 줄에 하나씩 주어진다. www.acmicpc.net 비트마스크를 공부해볼 수 있는 문제였다. 비트마스크란 쉽게 생각해서 배열들을 하나의 수로 나타낼 수 있는 기법이다. 예를들어서 {1 , 3 , 4 } 라는 배열이 있다고 생각해보자. 이를 2진수로 나타내면 1101 이런식으로 나타낼 수 있을 것이다. 1,3,4가 들어있기에 1,3,4번째 2진수가 1로 변환 이진수는 결국 십진수로 나타낼 수 있으므로 1,3,4 가들어있는 배열을 2진수로 나타낼 수 있는 것이다. 그렇다면 문제에서 원하..
2162_선분그룹
https://www.acmicpc.net/problem/2162 2162번: 선분 그룹 첫째 줄에 N(1 ≤ N ≤ 3,000)이 주어진다. 둘째 줄부터 N+1번째 줄에는 양 끝점의 좌표가 x1, y1, x2, y2의 순서로 주어진다. 각 좌표의 절댓값은 5,000을 넘지 않으며, 입력되는 좌표 사이에는 빈칸이 하 www.acmicpc.net CCW 알고리즘과 Union find 알고리즘을 같이 사용하면 풀수 있을꺼 같아서 적용하여 풀었다. 우선 CCW알고리즘을 이용하여 두 선분이교차하는지 하지 않는지 판단하는 함수를 하나 만들고, union find 알고리즘을 활용하여 두 선분이 교차하였다면 한 그룹으로 묶어주는 과정을 진행한다. 이때 주의할 점은 parents 배열을 마지막에 꼭 압축해줘야 한다. ..
11758_CCW
https://www.acmicpc.net/problem/11758 11758번: CCW 첫째 줄에 P1의 (x1, y1), 둘째 줄에 P2의 (x2, y2), 셋째 줄에 P3의 (x3, y3)가 주어진다. (-10,000 ≤ x1, y1, x2, y2, x3, y3 ≤ 10,000) 모든 좌표는 정수이다. P1, P2, P3의 좌표는 서로 다르다. www.acmicpc.net 외적을 통해서 풀면 된다! import sys input = sys.stdin.readline p = [ list(map(int,input().split())) for _ in range(3) ] result = p[0][0] * p[1][1] + p[1][0]*p[2][1] + p[2][0]*p[0][1] - ( p[1][0]*..