Python
1311_할일정하기1
https://www.acmicpc.net/problem/1311 1311번: 할 일 정하기 1 N명의 사람과 N개의 일이 있다. 각 사람은 일을 하나 담당해야 하고, 각 일을 담당하는 사람은 한 명 이어야 한다. 또한, 모든 사람은 모든 일을 할 능력이 있다. 사람은 1번부터 N번까지 번호가 매 www.acmicpc.net 상당히 어려운 문제였다... 처음에 2차원 배열을 dp로 두고 한줄씩 채우면 뭔가 될꺼 같은데 이전에 방문하지 않았던 점에서 가져오는게 너무 어려워서 머리를 헤매다가 인터넷에서 약간의 힌트를 발견했다. 만약 문제의 예제케이스처럼 3명이 있다면 결국 우리는 [ 1 1 1 ] 와같이 채우는게 목표이다. 그리고 이 과정에는 [ 0 0 1 ] [ 0 1 0 ] [ 0 1 1 ] [ 1 0 ..
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]*..
2166_다각형의 면적
https://www.acmicpc.net/problem/2166 2166번: 다각형의 면적 첫째 줄에 N이 주어진다. 다음 N개의 줄에는 다각형을 이루는 순서대로 N개의 점의 x, y좌표가 주어진다. 좌표값은 절댓값이 100,000을 넘지 않는 정수이다. www.acmicpc.net 주어진 좌표를 가지고 다각형의 넓이를 구하기 위해서는 신발끈 공식을 이용하면 된다. https://ko.wikipedia.org/wiki/%EC%8B%A0%EB%B0%9C%EB%81%88_%EA%B3%B5%EC%8B%9D 신발끈 공식 - 위키백과, 우리 모두의 백과사전 신발끈 공식(―公式)은 좌표평면 상에서 꼭짓점의 좌표를 알 때 다각형의 면적을 구할 수 있는 방법이다. 다각형의 각 꼭짓점의 좌푯값을 교차하여 곱하는 모습이..
1949_우수마을
https://www.acmicpc.net/problem/1949 1949번: 우수 마을 N개의 마을로 이루어진 나라가 있다. 편의상 마을에는 1부터 N까지 번호가 붙어 있다고 하자. 이 나라는 트리(Tree) 구조로 이루어져 있다. 즉 마을과 마을 사이를 직접 잇는 N-1개의 길이 있으며, www.acmicpc.net 역시 이전 글의 풀이와 동일하게 풀 수 있다. 루트 노드를 하나 잡은 후에, 밑에서부터 순회하면서 검사하면 된다. 자세한 설명은 이전 글을 참조하면 될 것 같다. import sys sys.setrecursionlimit(10**5) input = sys.stdin.readline n = int(input()) population = [0]+list(map(int,input().split..