목록코팅테스트/백준 문제 모음 (296)
For Programmer
백준 1520번 파이썬 문제풀이(내리막길)
dfs + dp 의 무서운 조합이다. 아무리 생각해도 구현을 하지 못해서 정답을 찾아봤는데 보고나서도 직접 디버깅하면서 어떻게 돌아가는지 확인했다. dp는 아무리 해도 어렵다.. 자세한 설명은 주석으로 달아 놨다. import sys sys.setrecursionlimit(2000) M, N = map(int, input().split()) miro = [list(map(int, input().split())) for _ in range(M)] dr = [-1, 0, 1, 0] # 상 우 하 좌 dc = [0, 1, 0, -1] # 상 우 하 좌 # 해당 좌표에서부터 도착지까지 갈 수 있는 경우의 수를 -1로 초기화 visited = [[-1] * N for _ in range(M)] def dfs(r,..
백준 16562번 파이썬 문제풀이(친구비)
해당 문제는 연결요소의 개수가 몇개있냐 그리고 연결요소의 리스트들을 저장해놓고 그 중 가작 적은 금액을 요구하는 학생들을 구하라는 문제이다. well-known 문제이며 간단히 dfs로 구현 가능하다. import sys sys.setrecursionlimit(3000) N, M, K = map(int, input().split()) wanted = [0] + list(map(int, input().split())) graph = [[] for _ in range(N + 1)] for i in range(M): a, b = map(int, input().split()) graph[a].append(b) graph[b].append(a) visited = [False] * (N + 1) friends = ..
백준 2644번 파이썬 문제풀이(촌수 계산)
일반적인 트리문제이다. 해당 문제에서는 깊이와 부모 노드를 따로 구해놓고 이것을 비교해서 같은 부모가 있으면 제일 가까운 부모를 기준으로 다시 깊이를 계산하는 하여 더하는 식으로 구현 하였다. N = int(input()) p1, p2 = map(int, input().split()) M = int(input()) graph = [[] for _ in range(N + 1)] for _ in range(M): a, b = map(int, input().split()) graph[a].append(b) depth = [0 for i in range(N + 1)] parent = [0 for i in range(N + 1)] p1_parent = [] # p1 부모 저장 p2_parent = [] # p2 ..
https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AWXVyCaKugQDFAUo SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com 해당 문제 파이썬으로 풀기에는 아주 쉬운 문제이다. 단, 조금 어렵게 변형하면 이분탐색으로 풀지 않으면 시간초과나게 만들 수도 있기 때문에 해당 문제를 이분탐색으로 구현하였다. T = int(input()) for tc in range(1, T + 1): N = int(input()) s, e = 1, N ans = -1 while s
https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AWIeUtVakTMDFAVH SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com 무슨 문제를 이렇게 이해하기 어렵게 내는지.... 우선 문제풀이는 N개 중에 조합으로 N // 2개씩 뽑으면 된다. 예를들어 4개라면 0~3 중 (0,1) | (2,3) , (0,2) | (1,3) 이런식으로 생각하면 되는데 문제는 N이 6개일 때다. 3개를 뽑았다면 (0,1,2) | (3,4,5) 를 뽑았다면 여기서 다시 2개씩 조합으로 뽑아서 더해야하는 건지 아니면 2개만 사용하는건지.. 정답은..
https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV2b7Yf6ABcBBASw SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com 간단한 DFS 문제이다. 주석으로 설명해놨다. T = int(input()) # 조합 dfs 이용 def dfs(depth, start, height): global max_ # 1개이상 N개 이하로 뽑은 경우 if 0 = max_: # 저장되어있는 최댓값보다 크거나 같다면 return # 재귀 종료 max..
https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV5PpLlKAQ4DFAUq SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com 기존의 BFS와 비슷하나 터널이 연결되어 있는지 연결성을 확인해야 하는 문제이다. 약간의 귀찮은 문제이긴 하나 그렇게 어렵지 않게 해결 할 수 있다. import sys from collections import deque sys.stdin = open('input.txt', 'r') # 각 수마다 방향 처리 def direction(num): if num == 1: return [(-1, 0), ..
https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV5LtJYKDzsDFAXc SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com 전형적인 BFS문제이다. 단, 첫 번째 출발 번호 방을 찾기위해 나는 큐에 시작점을 계속 담아서 보냈다. 또한 0,0 ~ N -1 , N - 1 으로만 검사하면 아래와 오른쪽으로만 커지는 방향을 정확하게 탐색할 수 있기 때문에 N -1 , N -1 ~ 0, 0 으로 역으로 인덱스를 돌면서 위쪽방향과 왼쪽방향도 정확하게 탐색하도록 하였다. from collections import deque T = ..