백준
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..
2533_사회망서비스 (메모리초과,재귀오류?)
https://www.acmicpc.net/problem/2533 2533번: 사회망 서비스(SNS) 페이스북, 트위터, 카카오톡과 같은 사회망 서비스(SNS)가 널리 사용됨에 따라, 사회망을 통하여 사람들이 어떻게 새로운 아이디어를 받아들이게 되는가를 이해하는 문제가 중요해졌다. 사회망 www.acmicpc.net 문제는 이전 글에서 풀었던 문제와 유사하게 풀 수 있었다. 역시 트리의 밑에서부터 순차적으로 진행 할것이다. 즉, 예제에서 준 다음과 같은 트리라면 5>6>2>3>7>8>4 순서로 탐색을 하게 될 것이다. 이때 검색하는 노드가 얼리어답터라면 그 자식 노드들은 모두 얼리어답터면 안된다. 얼리어답터가 아니라면 그 자식 노드들은 모두 얼리어답터여만 한다. 즉 이전 글의 점화식과는 조금 다르게, 얼..