[BOJ] 백준 11437 LCA 파이썬(Python)
2022. 8. 26. 15:02
알고리즘/백준[BaekJoon]
[문제] https://www.acmicpc.net/problem/11437 11437번: LCA첫째 줄에 노드의 개수 N이 주어지고, 다음 N-1개 줄에는 트리 상에서 연결된 두 정점이 주어진다. 그 다음 줄에는 가장 가까운 공통 조상을 알고싶은 쌍의 개수 M이 주어지고, 다음 M개 줄에는 정www.acmicpc.net트리 문제를 풀다가 트리 DP문제를 접하고 문제를 해결하지 못하고 '다른 트리 DP 문제가 무엇이 있을까?'라는 생각에 찾게 된 문제.초기 구상 과정LCA(Lowest Common Ancestor): 최소 공통 조상트리 내부에서 두 개의 노드 사이의 최소로 갈 수 있는 공통 조상을 찾는 문제이다. 간단하게 초반에는 노드의 깊이들을 계산하여 가지고 있고 그 깊이를 기반으로 한땀한땀 올라가면..
[BOJ] 백준 1463 1로 만들기 파이썬(Python)
2022. 8. 23. 15:53
알고리즘/백준[BaekJoon]
[문제] https://www.acmicpc.net/problem/1463 1463번: 1로 만들기첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다.www.acmicpc.net코드import sysinput = sys.stdin.readlinenum = int(input())dp = [-1] * (num + 1)dp[1] = 0for i in range(1, num + 1): if dp[i] != -1: # if i + 1 == num or i * 2 == num or i * 3 == num: break if i + 1 느낀점DP도 시간이 많이 걸리는 경우도 있구나, 이때 Memoization이 성능이 좋은데 한번 구현해봐야겠다.[220823] 지금..
[BOJ] 백준 1943 동전분배 파이썬 (Python)
2022. 8. 23. 15:39
알고리즘/백준[BaekJoon]
[문제] https://www.acmicpc.net/problem/1943 1943번: 동전 분배세 개의 입력이 주어진다. 각 입력의 첫째 줄에 동전의 종류 N(1 ≤ N ≤ 100)이 주어진다. 각 입력의 둘째 줄부터 N+1째 줄까지 각각의 동전의 금액과 개수가 빈 칸을 사이에 두고 주어진다. 단, 원www.acmicpc.net코드import sysinput = sys.stdin.readlinefor tc in range(3): # 동전 종류의 갯수 N = int(input()) coin_info = {} total = 0 for i in range(N): coin, num = map(int, input().split()) coin_info[coin]..
[BOJ] 백준 2591 숫자카드 파이썬 (Python)
2022. 8. 23. 15:30
알고리즘/백준[BaekJoon]
[문제] https://www.acmicpc.net/problem/2591 2591번: 숫자카드1부터 34까지 수가 적힌 카드가 충분히 많이 있다. 이들 중 몇 장을 일렬로 늘어놓고, 그 숫자를 차례로 적었다. 예를 들어 아래와 같이 카드가 놓인 경우 숫자를 차례로 적으면 27123이 된다. 나중www.acmicpc.net코드import sysinput = sys.stdin.readlinenums = list(input().rstrip())grand = ''parent = ''num = ''dp = [0] * len(nums)# dp 초기값 설정dp[0] = 1if (nums[1] != '0' and 1 3: break elif int(num) == 0 and 0 34: ..
[BOJ] 백준 1946 신입사원 파이썬 (Python)
2022. 8. 23. 15:22
알고리즘/백준[BaekJoon]
[문제] https://www.acmicpc.net/problem/1946 1946번: 신입 사원첫째 줄에는 테스트 케이스의 개수 T(1 ≤ T ≤ 20)가 주어진다. 각 테스트 케이스의 첫째 줄에 지원자의 숫자 N(1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N개 줄에는 각각의 지원자의 서류심사 성www.acmicpc.net코드import sysinput = sys.stdin.readlinefor tc in range(int(input())): N = int(input()) cnt = 1 DtoI = [0] * (N + 1) for i in range(1, N + 1): Docu, Interview = map(int, input().split()) ..
[BOJ] 백준 11053 가장 긴 증가하는 부분수열 파이썬(Python)
2022. 8. 23. 15:11
알고리즘/백준[BaekJoon]
[문제] https://www.acmicpc.net/problem/11053 11053번: 가장 긴 증가하는 부분 수열수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이www.acmicpc.net코드import syslength = int(input())nums = list(map(int, input().split()))dp = [1] * lengthresult = 0for a in range(length): for b in range(a): if nums[a] > nums[b]: ..
[BOJ] 백준 13565 침투 파이썬 (Python)
2022. 8. 23. 14:53
알고리즘/백준[BaekJoon]
[문제] https://www.acmicpc.net/problem/13565 13565번: 침투첫째 줄에는 격자의 크기를 나타내는 M (2 ≤ M ≤ 1,000) 과 N (2 ≤ N ≤ 1,000) 이 주어진다. M줄에 걸쳐서, N개의 0 또는 1 이 공백 없이 주어진다. 0은 전류가 잘 통하는 흰색, 1은 전류가 통하지 않www.acmicpc.net첫번째 제출런타임에러?RecursionError를 처음 만났던 문제였다. 재귀호출이 제한된 양을 넘어서면 나타나는 에러로 해결방법은 DFS를 BFS로 수정하거나 제한을 변경하면 된다. DFS를 공부하고 있어서 후자를 선택했다.import syssys.setrecursionlimit(10**6) # 제한을 변경하는 코드또 다른 런타임 에러로 IndexErro..
[BOJ] 백준 16922 로마숫자만들기 파이썬 (Python)
2022. 8. 23. 14:43
알고리즘/백준[BaekJoon]
[문제] https://www.acmicpc.net/problem/16922 16922번: 로마 숫자 만들기2, 6, 10, 11, 15, 20, 51, 55, 60, 100을 만들 수 있다.www.acmicpc.net첫번째 문제 풀이def dfs(step, N): global result if step == N: result.append(sum(tmp)) else: for i in range(4): tmp.append(rom_nums[i]) dfs(step + 1, N) tmp.pop()N = int(input())rom_nums = [1, 5, 10, 50]result = []tmp = []dfs(0,..