PS75 [Python] 백준 14572번 : 스터디 그룹 https://www.acmicpc.net/problem/14572 14572번: 스터디 그룹 첫 줄에 학생의 수 N, 알고리즘의 수 K, 문제에 설명한 D가 주어진다. (1 ≤ N ≤ 105, 1 ≤ K ≤ 30, 0 ≤ D ≤ 109) 이어 N명의 학생에 대한 정보가 아래와 같이 주어진다. M d (0 ≤ M ≤ K, 0 ≤ d ≤ 109): 해 www.acmicpc.net 💡 문제 풀이 투 포인터 알고리즘 문제이다. 투 포인터 알고리즘 중 누적합과 비슷한 알고리즘을 한 단계 더 올려서 해결하면 되는 문제이다. E를 계산하는 식을 보면 다음과 같다. E = (아는 모든 알고리즘(anyknows) - 모두 아는 알고리즘(allknows)) × 그룹원 수 결정적으로 값을 크게 만드는 것은 그룹원의 수이기.. 2022. 9. 7. [Python] 백준 1774번 : 우주신과의 교감 https://www.acmicpc.net/problem/1774 1774번: 우주신과의 교감 (1,1) (3,1) (2,3) (4,3) 이렇게 우주신들과 황선자씨의 좌표가 주어졌고 1번하고 4번이 연결되어 있다. 그렇다면 1번하고 2번을 잇는 통로를 만들고 3번하고 4번을 잇는 통로를 만들면 신들과 선자씨끼 www.acmicpc.net 💡 문제 풀이 최소 신장 트리 문제이다. 크루스칼 알고리즘으로 해결했다. 이 문제는 특이하게 각 정점에 대한 좌표가 주어지고 이미 연결된 간선의 정보를 준다. 우선 입력받는 순서가 정점의 순서이기 때문에 각 좌표를 저장한 이후에 간선의 정보를 만들어준다. 크루스칼 알고리즘이 (정점 개수 - 1)개 일 때 종료되니 이미 연결된 edge의 정보를 받을 때 세준다. ✔️ 느낀.. 2022. 9. 4. [Python] 백준 1197번 : 최소 스패닝 트리 https://www.acmicpc.net/problem/1197 1197번: 최소 스패닝 트리 첫째 줄에 정점의 개수 V(1 ≤ V ≤ 10,000)와 간선의 개수 E(1 ≤ E ≤ 100,000)가 주어진다. 다음 E개의 줄에는 각 간선에 대한 정보를 나타내는 세 정수 A, B, C가 주어진다. 이는 A번 정점과 B번 정점이 www.acmicpc.net 💡 문제 풀이 최소 신장 트리 문제이다. 크루스칼로 해결했다. 가장 기본적인 문제로 알고리즘의 개념만 잘 숙지하고 있다면 해결할 수 있다. ✔️ 느낀 점 다음에는 크루스칼 외에 프림 알고리즘으로도 풀어봐야겠다. 💻 코드 import sys input = sys.stdin.readline V, E = map(int, input().split()) edg.. 2022. 9. 4. [Python] 백준 2458번 : 키 순서 https://www.acmicpc.net/problem/2458 2458번: 키 순서 1번부터 N번까지 번호가 붙여져 있는 학생들에 대하여 두 학생끼리 키를 비교한 결과의 일부가 주어져 있다. 단, N명의 학생들의 키는 모두 다르다고 가정한다. 예를 들어, 6명의 학생들에 대하여 www.acmicpc.net 💡 문제 풀이 플로이드-워샬 알고리즘 문제이다. 특정 경로로 이동할 수 있는지 여부를 플로이드-워샬로 처리하고 값을 따진다. 여기서 자기 키 순서는 (자기보다 작은 사람 수 + 자기보다 큰 사람 수) == N-1 이면 알 수 있다. 예를 들어서, 6명이 있다면 작은 사람이 3명, 큰 사람이 2명 있다면 자기 키 순서는 3등이라는 것을 알 수 있다. ✔️ 느낀 점 안 좋아하는 유형의 문제라서 30분을.. 2022. 9. 2. [Python] 백준 1043번 : 거짓말 (빅뱅 거짓말 아님ㅋ) https://www.acmicpc.net/problem/1043 1043번: 거짓말 지민이는 파티에 가서 이야기 하는 것을 좋아한다. 파티에 갈 때마다, 지민이는 지민이가 가장 좋아하는 이야기를 한다. 지민이는 그 이야기를 말할 때, 있는 그대로 진실로 말하거나 엄청나게 www.acmicpc.net 💡 문제 풀이 분리 집합 문제이다. 사실 유니온&파인드 알고리즘으로 해결하고 싶었는데 자료구조로 푸는 게 더 적절해 보였다. 진실을 알고 있는 사람들과 각 파티에 참석하는 사람들을 입력받은 다음에 처리를 해줘야 한다. 이 문제에서 가장 중요한 것은 이미 거짓말을 들은 사람이 다른 파티에서 진실을 알고 있는 사람과 만날 경우이다. 따라서 진실을 알고있는 사람과 같이 있는 모든 사람들을 진실을 알고있는 그룹에 .. 2022. 9. 1. [Python] 백준 18223번 : 민준이와 마산 그리고 건우 https://www.acmicpc.net/problem/18223 18223번: 민준이와 마산 그리고 건우 입력의 첫 번째 줄에 정점의 개수 V와 간선의 개수 E, 그리고 건우가 위치한 정점 P가 주어진다. (2 ≤ V ≤ 5,000, 1 ≤ E ≤ 10,000, 1 ≤ P ≤ V) 두 번째 줄부터 E개의 줄에 걸쳐 각 간선의 정보 www.acmicpc.net 💡 문제 풀이 다익스트라 알고리즘 문제이다. 문제를 처음 읽으면 최단 경로에 건우가 있는지 따져야 할 것만 같지만 이 문제는 단순히 최소 비용만 따지면 된다. 마산까지의 최소 비용과 (시작 지점부터 건우가 있는 곳까지의 비용 + 건우가 있는 곳부터 마산까지의 비용)이 같다면 최단 경로의 길이보다 길어지지 않는 것이므로 건우를 구해서 마산으로 가도.. 2022. 8. 29. 이전 1 2 3 4 ··· 13 다음