개인 공부185 [Python] 백준 2252번 : 줄 세우기 https://www.acmicpc.net/problem/2252 2252번: 줄 세우기 첫째 줄에 N(1 ≤ N ≤ 32,000), M(1 ≤ M ≤ 100,000)이 주어진다. M은 키를 비교한 회수이다. 다음 M개의 줄에는 키를 비교한 두 학생의 번호 A, B가 주어진다. 이는 학생 A가 학생 B의 앞에 서야 한다는 의 www.acmicpc.net 💡 문제 풀이 위상 정렬 문제이다! 위상 정렬을 구현해주면 된다 ㅎㅎ ✔️ 느낀 점 💻 코드 import sys input = sys.stdin.readline N, M = map(int, input().split()) graph = [[] for _ in range(N+1)] indegree = [0] * (N + 1) for _ in range(M):.. 2022. 8. 4. [Python] 백준 1238번 : 파티 https://www.acmicpc.net/problem/1238 1238번: 파티 첫째 줄에 N(1 ≤ N ≤ 1,000), M(1 ≤ M ≤ 10,000), X가 공백으로 구분되어 입력된다. 두 번째 줄부터 M+1번째 줄까지 i번째 도로의 시작점, 끝점, 그리고 이 도로를 지나는데 필요한 소요시간 Ti가 들어 www.acmicpc.net 💡 문제 풀이 그래프 이론 중 다익스트라 알고리즘 문제이다. 기본적인 다익스트라 알고리즘과 형태가 비슷하지만 주의할 점이 있다. 바로, 원하는 값이 특정 노드에서 목적지로의 거리 + 목적지부터로의 거리라는 점이다. 구현한 다익스트라 알고리즘은 출발지로부터 모든 정점에 대해서 최단 거리를 구해준다. 따라서 최단 거리를 저장하는 배열을 2개를 구현해서 최대 거리를 찾아준.. 2022. 8. 2. TIL : 다익스트라 알고리즘 (5) 💻 알고리즘 ✔️ 다익스트라 알고리즘 그래프 이론 알고리즘 중 목적지에서 다른 노드로 이동할 때 최단 경로를 계산하는 알고리즘이다! 이 알고리즘의 특징과 동작 원리는 다음과 같다. 💡 특징 최단 거리를 기록할 추가적인 테이블이 필요하다. 그리디 알고리즘과 비슷한 면이 있다. 💡 동작 원리 출발 노드를 정하고 최단거리 테이블을 초기화한다. 방문하지 않은 노드 중 거리가 가장 짧은 노드를 선택한다. 거리를 계산해서 더 짧은 거리라면 최신화해준다. 2번, 3번 과정을 반복한다. import heapq def dijkstra(graph, start): # 최단거리 계산용 리스트, INF는 무한대를 의미한다. distance = [INF] * (size + 1) distance[start] = 0 queue = .. 2022. 8. 1. [Python] 백준 1753번 : 최단경로 https://www.acmicpc.net/problem/1753 1753번: 최단경로 첫째 줄에 정점의 개수 V와 간선의 개수 E가 주어진다. (1 ≤ V ≤ 20,000, 1 ≤ E ≤ 300,000) 모든 정점에는 1부터 V까지 번호가 매겨져 있다고 가정한다. 둘째 줄에는 시작 정점의 번호 K(1 ≤ K ≤ V)가 www.acmicpc.net 💡 문제 풀이 그래프 이론 중 다익스트라 알고리즘 문제이다. 다익스트라 알고리즘을 알면 바로 풀려 딱히 풀이는 없어도 될 것 같다. ✔️ 느낀 점 처음에는 나만의 코드로 작성하려고 했는데 이상하게 계속 시간 초과가 발생하길래 리스트로 바꾸어주고 언패킹도 모두 해주었다. 확실히 리스트가 시간이 좀 빠르긴 한가보다. 💻 코드 import sys, heapq inp.. 2022. 8. 1. [Python] 백준 10819번 : 차이를 최대로 https://www.acmicpc.net/problem/10819 10819번: 차이를 최대로 첫째 줄에 N (3 ≤ N ≤ 8)이 주어진다. 둘째 줄에는 배열 A에 들어있는 정수가 주어진다. 배열에 들어있는 정수는 -100보다 크거나 같고, 100보다 작거나 같다. www.acmicpc.net 💡 문제 풀이 브루트 포스 문제이다. permutation으로 6자리의 순열을 만들어 셈을 해준 후 최댓값을 최신화해주면 된다. ✔️ 느낀 점 처음에 어떤 공식을 만들려고 생각했지만 굳이 그럴 필요가 없음을 알게되어서 바로 해결했다. 💻 코드 import sys, itertools input = sys.stdin.readline N = int(input()) arr = list(map(int, input().s.. 2022. 8. 1. [Python] 백준 1182번 : 부분수열의 합 https://www.acmicpc.net/problem/1182 1182번: 부분수열의 합 첫째 줄에 정수의 개수를 나타내는 N과 정수 S가 주어진다. (1 ≤ N ≤ 20, |S| ≤ 1,000,000) 둘째 줄에 N개의 정수가 빈 칸을 사이에 두고 주어진다. 주어지는 정수의 절댓값은 100,000을 넘지 않는다. www.acmicpc.net 💡 문제 풀이 브루트 포스 문제이다. 부분 수열을 만들어서 합이 목표값과 같은지만 확인해주면 된다. itertools의 combination을 사용하면 부분 수열을 쉽게 만들 수 있다. ✔️ 느낀 점 그렇게 어려운 문제는 아니었다. 💻 코드 import sys from itertools import combinations input = sys.stdin.read.. 2022. 7. 31. 이전 1 ··· 19 20 21 22 23 24 25 ··· 31 다음