메모/알고리즘
-
[프로그래머스] Python - 완주하지 못한 선수메모/알고리즘 2022. 1. 27. 23:32
코딩테스트 연습 - 완주하지 못한 선수 수많은 마라톤 선수들이 마라톤에 참여하였습니다. 단 한 명의 선수를 제외하고는 모든 선수가 마라톤을 완주하였습니다. 마라톤에 참여한 선수들의 이름이 담긴 배열 participant와 완주한 선수 programmers.co.kr 프로그래머스 완주하지 못한 선수 문제다. 리스트를 순회해서 remove 함수로 하나씩 제거해가며 푸는 방식을 처음 선택했었는데 remove 함수의 시간복잡도가 O(n)이다보니 반복문에 중첩하면 시간이 오래 걸린다. 이 후에 딕셔너리에 빈도 수를 측정하는 방식을 선택하여 해결했다. 더보기 def solution(participant, completion): hash = dict() for _p in participant: if _p in has..
-
[백준] 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..