코딩테스트/Python43 [python 구름] 구름이의 여행 📜 접근 방법 인접 리스트로 그래프를 표현한다. BFS 방식을 사용한다. ❌ 실패 코드 ✅ 정답 코드 from collections import deque import sys input = sys.stdin.readline n, m, k = map(int, input().split()) graph = [[] for _ in range(n + 1)] for _ in range(m): u, v = map(int, input().split()) graph[u].append(v) graph[v].append(u) distance = [ 9**9 for _ in range(n + 1)] distance[1] = 0 que = deque() que.append(1) while que: cur = que.poplef.. 2023. 5. 23. [python 구름] 보드 게임 다이나믹 프로그래밍(DP) 📜 접근 방법 처음부터 접근하되 1칸과 3칸 기준으로 확인을 하기 때문에 3미만의 숫자들은 1로 둔다(0부터 시작이고 0, 1, 2는 한칸으로 밖에 갈 수 없음) 3번째부터 확인을 하는데 3번째에서 한칸 뒤, 3번째에서 3칸 뒤의 값들을 더해서 저장한다. (1칸으로 가는 방법과 3칸으로 가는 방법 두가지 중 가능한 갯수) 주어진 n까지 반복한다. ❌ 실패 코드 ✅ 정답 코드 import sys input = sys.stdin.readline # 문제에서 주어진 것 MOD = 10 ** 9 + 7 n = int(input()) dp = [0 for i in range(n + 1)] # 0부터 2번째 위치는 무조건 한칸만 가능하기 때문에 초기값을 1로 둠 dp[0] = dp[1] .. 2023. 5. 22. [python 구름] 피보나치 수 F(K)를 1000000007로 나눈 나머지 출력 📜 접근 방법 ❌ 실패 코드 런타임 에러 import sys input = sys.stdin.readline def fibo(n): if n 2023. 5. 21. [python 구름] 구름 스퀘어 📜 접근 방법 회의실 배정과 같은 문제는 그리디 알고리즘으로 푼다 종료시간이 빠른 기준으로 우선순위를 잡는다. 시작 시간과 종료 시간을 받아 리스트에 넣는다. 우선순위는 첫번째로 종료시간이 빠르고, 두번째론 시작시간이 빠른 순으로 정렬한다. events를 돌면서 시작 시간 보다 종료 시간이 적을 경우 cnt + 1 해주고 종료 시간을 변경해준다. ❌ 실패 코드 ✅ 정답 코드 import sys input = sys.stdin.readline n = int(input()) events = [] for _ in range(n): s, e = map(int, input().split()) events.append([s, e]) events.sort(key = lambda x : (x[1], x[0])) cnt.. 2023. 5. 20. 이전 1 2 3 4 ··· 11 다음