본문 바로가기

알고리즘135

[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.
[Python] 백준 14698번 : 전생했더니 슬라임 연구자였던 건에 대하여 (Hard) https://www.acmicpc.net/problem/14698 14698번: 전생했더니 슬라임 연구자였던 건에 대하여 (Hard) 각 테스트 케이스마다 슬라임을 끝까지 합성했을 때 청구될 비용의 최솟값을 1, 000, 000, 007로 나눈 나머지를 출력한다. 전기 에너지가 전혀 필요하지 않은 경우엔 1 을 출력한다. www.acmicpc.net 💡 문제 풀이 그리디 알고리즘 문제이다. 간단하게 작은 것부터 계산해주면 된다. 매번 정렬하면서 사용할 수 없으니까 우선순위 큐를 사용해주면 된다. ✔️ 느낀 점 heapq.heappop이 힙 구조로 되어있다는 가정 하에 0번 인덱스를 리턴하는 것인 것을 몰라서 heapify를 안 써서 계속 틀렸다. 이번 기회에 확실하게 잡고 가게 되었다. 💻 코드 imp.. 2022. 8. 24.
[Python] 백준 1647번 : 도시 분할 계획 https://www.acmicpc.net/problem/1647 1647번: 도시 분할 계획 첫째 줄에 집의 개수 N, 길의 개수 M이 주어진다. N은 2이상 100,000이하인 정수이고, M은 1이상 1,000,000이하인 정수이다. 그 다음 줄부터 M줄에 걸쳐 길의 정보가 A B C 세 개의 정수로 주어지는데 A번 www.acmicpc.net 💡 문제 풀이 최소 신장 트리(MST) 문제이다. 크루스칼 알고리즘을 통해서 해결했다. 문제 자체는 알고리즘을 이해하고 있으면 어렵지 않으나, 도시를 분리해야 해야 하므로 마지막에 추가된 비용을 빼줘야 한다. ✔️ 느낀 점 솔직히 마지막에 왜 빼줘야 하는지 이해를 할 수 없다. 크루스칼 알고리즘 자체를 이해하는 것이 목표라서 그냥 이해하지 않고 넘어갔다. 💻 .. 2022. 8. 21.
TIL : Kruskal(크루스칼) 알고리즘 (9) 💻 알고리즘 📌 크루스칼 알고리즘 프림 알고리즘과 같이 대표적인 최소 신장 트리(MST)를 찾는 알고리즘이다. 이 알고리즘의 특징과 동작 원리는 다음과 같다. ✔️ 특징 확인하는 그래프가 무방향 그래프이고 가중치가 존재한다. 가장 비용이 작은 것부터 확인하기 때문에 그리디 알고리즘의 일종이다. 순환(Cycle)이 있는지 확인하기 위해서 Union-Find 알고리즘을 사용한다. ✔️ 동작 원리 입력받은 간선들을 cost을 기준으로 정렬한다. 가장 작은 비용을 가진 간선을 확인한다. 사이클이 안 만들어지면 추가하고 만들어지면 다음 간선을 확인한다. 간선의 개수가 정점 - 1 개가 될 때까지 반복한다. # find function def find(x): if x != parent[x]: parent[x] = .. 2022. 8. 21.

티스토리툴바