반응형 문제해결(PS)12 백준 BOJ 1976번 여행 가자 골드5 - Python 풀이 https://www.acmicpc.net/problem/1976 문제 동혁이는 친구들과 함께 여행을 가려고 한다. 한국에는 도시가 N개 있고 임의의 두 도시 사이에 길이 있을 수도, 없을 수도 있다. 동혁이의 여행 일정이 주어졌을 때, 이 여행 경로가 가능한 것인지 알아보자. 물론 중간에 다른 도시를 경유해서 여행을 할 수도 있다. 예를 들어 도시가 5개 있고, A-B, B-C, A-D, B-D, E-A의 길이 있고, 동혁이의 여행 계획이 E C B C D 라면 E-A-B-C-B-C-B-D라는 여행경로를 통해 목적을 달성할 수 있다. 도시들의 개수와 도시들 간의 연결 여부가 주어져 있고, 동혁이의 여행 계획에 속한 도시들이 순서대로 주어졌을 때 가능한지 여부를 판별하는 프로그램을 작성하시오. 같은 도시.. 2023. 10. 20. 백준 2589번 보물섬 골드5 - Python 풀이 2589번 보물섬 문제는 그래프 너비 우선 탐색(BFS) 와 부루트 포스(Brute Force)를 이용하여 푸는 문제다. 기본적인 풀이 아이디어는 1. 모든 칸에 대해 순회하는데 2. 해당 칸이 육지라면 너비 우선 탐색을 사용하고 3. 최단 거리로 이동하는데 있어 가장 긴 시간이 걸리는 두 곳 간의 최단 거리를 저장하는데 4. 그 저장한 시간들 중 최대값이 바로 보물이 묻혀있는 두 곳 사이의 최단 거리를 이동하는 시간이다. 라고 정리할 수 있다. 다음 코드는 pypy3로 제출하면 통과할 수 있지만 Python3로는 시간초과가 발생한다. 방문 여부를 저장하는 추가 배열을 생성해서 않기 위해 graph 배열에 "L"과 'l' 문자를 번갈아 저장하면서 육지를 구분함과 동시에 flag로 활용했다. (결과적으로 .. 2023. 10. 18. 백준 2096번 내려가기 골드5 - Python 풀이 다이나믹 프로그래밍을 활용하는 문제이다. 메모리 제한에 대한 생각 없이 단순히 메모이제이션에 대한 아이디어만 가지고 문제를 풀면 다음과 같은 풀이를 생각할 수 있다. import sys, copy input = sys.stdin.readline n = int(input()) dp_max = [list(map(int, input().split())) for _ in range(n)] dp_min = copy.deepcopy(dp_max) for i in range(1, n): # 0 dp_max[i][0] += max(dp_max[i - 1][0], dp_max[i - 1][1]) dp_min[i][0] += min(dp_min[i - 1][0], dp_min[i - 1][1]) # 1 dp_max[i][.. 2023. 10. 18. 백준 11000번 강의실 배정 골드5 - Python 풀이 문제를 보자마자 직관적으로 이런 풀이를 떠올릴 수 있는데, 수업 시간표를 딕셔너리로 생성하고, 각 시간대 중 배정된 강의 수의 최대 값이 필요한 강의실의 개수일 것이다. import collections n = int(input()) arr = [list(map(int, input().split())) for _ in range(n)] time_table = collections.defaultdict(int) for s, t in arr: for i in range(s, t): time_table[i] += 1 print(max(time_table.values())) 그러나 위 풀이는 메모리 초과가 발생한다. 어짜피 겹치는 시간대만 확인하면 되므로, 시간대를 정렬해서 계산하면 한번만 순회하여 구할 수 있.. 2023. 10. 12. [C언어] 버블정렬(Bubble Sort) 버블정렬: 두 인접한 원소를 검사하여 정렬하는 방법. 시간복잡도: O(n^2) 2020. 10. 26. 의사코드(수도코드) 장점 코드 검토, 수정에 용이함 간결하며 좋은 코드가 작성된다. 문법 (사실 의사코드는 정해진 표준은 없다) 제어(control flow) if (exp) … [elseif (exp) …]* [else …] for var 2020. 4. 6. 이전 1 2 다음 반응형