Python/백준
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 순서로 탐색을 하게 될 것이다. 이때 검색하는 노드가 얼리어답터라면 그 자식 노드들은 모두 얼리어답터면 안된다. 얼리어답터가 아니라면 그 자식 노드들은 모두 얼리어답터여만 한다. 즉 이전 글의 점화식과는 조금 다르게, 얼..
2213_트리의 독립집합
https://www.acmicpc.net/problem/2213 2213번: 트리의 독립집합 첫째 줄에 트리의 정점의 수 n이 주어진다. n은 10,000이하인 양의 정수이다. 1부터 n사이의 정수가 트리의 정점이라고 가정한다. 둘째 줄에는 n개의 정수 w1, w2, ..., wn이 주어지는데, wi는 정점 i의 www.acmicpc.net 문제에 나온 트리는 1번을 루트노드라고 생각한다면 위와 같은 구성을 가지게 된다. 그렇다면 어떻게 하면 가중치를 더해갈 수 있을지 생각해보자. 먼저 자식부터 검사를 하는 것이 좋을 것이다. 5->4->3->7->6->2->1 순서로 탐색을 한다. 어떤부분을 탐색할때 자식노드와 부모 노드가 있다고 생각하면, 부모노드가 독립집합 안에 속해있다면 자식노드는 속할 수 없고..
15681_트리와쿼리
https://www.acmicpc.net/problem/15681 15681번: 트리와 쿼리 트리의 정점의 수 N과 루트의 번호 R, 쿼리의 수 Q가 주어진다. (2 ≤ N ≤ 105, 1 ≤ R ≤ N, 1 ≤ Q ≤ 105) 이어 N-1줄에 걸쳐, U V의 형태로 트리에 속한 간선의 정보가 주어진다. (1 ≤ U, V ≤ N, U ≠ V) www.acmicpc.net 트리 구조를 받아온 후에, dfs로 노드를 후위순위하면서 뒤에서부터 서브트리의 개수를 더해주면 된다. 각 자식트리의 서브트리를 더해주는 형태라고 생각하면 된다. 처음에 bfs를 사용해서 그때 그때 개수를 구했는데그러며 시간초과가 나니 생각해두면 될 것 같다. import sys from collections import deque sy..
17472_다리만들기2(Python,설명) 반례...?
https://www.acmicpc.net/problem/17472 17472번: 다리 만들기 2 첫째 줄에 지도의 세로 크기 N과 가로 크기 M이 주어진다. 둘째 줄부터 N개의 줄에 지도의 정보가 주어진다. 각 줄은 M개의 수로 이루어져 있으며, 수는 0 또는 1이다. 0은 바다, 1은 땅을 의미한다. www.acmicpc.net 삼성A형 기출문제라서 살짝 긴장하고 풀었다. 어려운 문제였다... 시간도 많이 걸렸지만 스스로 풀어서 되게 뿌듯한 문제였다. 아래와 같은 과정으로 순서대로 해결하여 접근하였다. 1. 문제에서 입력으로 준 지도를 2차원 리스트에 저장 2. 각 좌표를 트리구조처럼 만들기 위해 부모 배열을 만든다. 이때 부모배열또한 2차원으로 자신을 가르키도록 만든다. 3. 해당 구조에 맞는 fi..