전체 글
-
[백준] Python - 색종이와 가위메모/알고리즘 2021. 11. 2. 22:37
20444번: 색종이와 가위 첫 줄에 정수 n, k가 주어진다. (1 ≤ n ≤ 231-1, 1 ≤ k ≤ 263-1) www.acmicpc.net 색종이와 가위 문제다. 이진탐색 문제라고는 하지만 이진탐색을 쓸 필요는 없다. 색종이를 잘랐을때 입력한 값 만큼의 사각형이 나오는지 판단하는 문제이다. 여기서 규칙이 하나 생기는데 x를 가로로 자르는 횟수, y를 세로로 자르는 횟수, n을 총 자르는 횟수, k를 잘랐을 때 나오는 사각형의 총 개수라고 하면 1) x + y = n 2) (x+1)(y+1) = k가 성립한다. 여기서 1)에서 x = n - y를 2)에 대입하면 x에 대한 2차 방정식이 나온다. 사각형의 개수는 무조건 자연수일 수 밖에 없으니 이 2차 방정식을 근의 공식을 통해 해가 자연수로 나오..
-
[백준] Python - 트리메모/알고리즘 2021. 10. 10. 04:59
1068번: 트리 첫째 줄에 트리의 노드의 개수 N이 주어진다. N은 50보다 작거나 같은 자연수이다. 둘째 줄에는 0번 노드부터 N-1번 노드까지, 각 노드의 부모가 주어진다. 만약 부모가 없다면 (루트) -1이 주어진다 www.acmicpc.net 트리의 리프 노드의 개수를 확인하는 문제다. 내 개인 서버에서는 잘 돌아가는데 백준 테스트 케이스에서 어떤 경우가 있는지 몰라서 예제만 확인했더니... 에러를 해결하지 못했다. 그래서 어떤 알고리즘으로 찾아 힌트를 봤더니 dfs를 쓴다 했다. 깊이 우선 탐색을 재귀로 짜서 리프노드에 도달하면 갯수 +1 하고 리턴, 삭제노드의 부모가 자식이 1개면 갯수 +1 이런식으로 구현했다. 더보기 from sys import stdin n = int(stdin.read..
-
[백준] Python - 최소 스패닝 트리메모/알고리즘 2021. 10. 9. 17:52
1197번: 최소 스패닝 트리 첫째 줄에 정점의 개수 V(1 ≤ V ≤ 10,000)와 간선의 개수 E(1 ≤ E ≤ 100,000)가 주어진다. 다음 E개의 줄에는 각 간선에 대한 정보를 나타내는 세 정수 A, B, C가 주어진다. 이는 A번 정점과 B번 정점이 www.acmicpc.net 최소 신장나무, 최소 스패닝 트리, MST 등등으로 불리는 트리 알고리즘이다. 처음에 어떻게 풀어야할까 막막해서 여러 풀이 방법과 집합 알고리즘을 참고했다. 더보기 #https://github.com/CASPER-REPSAC/algorithm-stack/tree/gsniper777/baekjoon/1197 from sys import stdin v, e = list(map(int, stdin.readline().sp..
-
[백준] Python - 트리 순회메모/알고리즘 2021. 9. 24. 16:24
1991번: 트리 순회 첫째 줄에는 이진 트리의 노드의 개수 N(1 ≤ N ≤ 26)이 주어진다. 둘째 줄부터 N개의 줄에 걸쳐 각 노드와 그의 왼쪽 자식 노드, 오른쪽 자식 노드가 주어진다. 노드의 이름은 A부터 차례대로 알파 www.acmicpc.net 이진 트리 순회 문제다. 트리 순회보다 트리 생성하는게 시간이 더 걸렸다... 파이썬 코드 확인 더보기 from sys import stdin class Node: def __init__(self,node): self.info = node self.left = None self.right = None class Tree: def __init__(self): self.root = None def createTree(self,treeDict,treeNod..
-
[백준] Python - 최대힙메모/알고리즘 2021. 9. 19. 13:43
11279번: 최대 힙 첫째 줄에 연산의 개수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 연산에 대한 정보를 나타내는 정수 x가 주어진다. 만약 x가 자연수라면 배열에 x라는 값을 넣는(추가하는) 연산이고, x가 www.acmicpc.net 최대 힙에서 최댓값을 뽑아오는 문제다. 우선순위 큐를 이용한다. 처음에는 재귀함수로 구현했는데 시간초과가 나서 어떻게 할까 고민하면서 알고리즘 자료 + 다른 사람 코드 해서 조금 바꿔봤다. 아래는 파이썬 코드 더보기 import sys n = int(sys.stdin.readline()) hArr = [0 for i in range(0, n)] size = 0 def push(num): global size global hArr size += ..