python125 [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. [Python] 백준 12904번 : A와 B https://www.acmicpc.net/problem/12904 12904번: A와 B 수빈이는 A와 B로만 이루어진 영어 단어가 존재한다는 사실에 놀랐다. 대표적인 예로 AB (Abdominal의 약자), BAA (양의 울음 소리), AA (용암의 종류), ABBA (스웨덴 팝 그룹)이 있다. 이런 사실에 놀란 수 www.acmicpc.net 💡 문제 풀이 그리디..? 알고리즘 문제이다. 두 가지 연산만 할 수 있다. 끝에 A 붙이기 뒤집고 B 붙이기 따라서 마지막에 어떤 값이 오는지만 확인해서 문자열의 길이가 같을 때까지 역순으로 따져주면 된다. 즉, 끝에 A가 온다면 A를 빼주고 B가 온다면 B를 빼주고 뒤집으면 된다. ✔️ 느낀 점 그리디 알고리즘..? 문제 항목에서 찾았는데 그냥 문자열에 대.. 2022. 8. 26. [Python] 백준 2931번 : 가스관 https://www.acmicpc.net/problem/2931 2931번: 가스관 www.acmicpc.net 💡 문제 풀이 구현 문제이다. 문제의 조건만 맞춰서 풀어주면 된다. 중요한 조건은 다음과 같다. 무조건 답이 존재한다. 가스의 흐름이 유일하다. M과 Z에는 단 하나의 파이프와 연결되어있다. 무조건 하나의 파이프만 문제가 있다. 위 조건들에 따라서 우리는 파이프만 확인해주면 된다. 내 풀이의 사고 과정은 다음과 같다. 2차원 배열을 돌면서 파이프만 확인한다. 확인하는 파이프 모양에 맞게 파이프들이 연결되어있는지 체크한다. 단 하나의 파이프만 문제가 있으므로 연결되어있지 않는 파이프를 확인하면 바로 반복을 종료해준다. 길이 4의 배열에 문제가 있는 파이프 근처 상, 좌, 우, 하 순서로 파이프.. 2022. 8. 25. 이전 1 ··· 4 5 6 7 8 9 10 ··· 21 다음