본문 바로가기

Algorithm144

[백준] 파티 / 1238번 / Python / 파이썬 / 다익스트라(Dijkstra) 알고리즘 💡solutions 💬 heap 최소힙 자료구조를 활용하여 다익스트라 알고리즘으로 해결하였다. 💬 먼저 N명의 학생들마다 X번 마을에 왕복으로 다녀오는데 걸리는 최소 시간을 구한다. -> 이때 편도가 아니기 때문에 최소 시간은 dijkstra(i, x) + dijkstra(x, i)으로 ① i번 학생이 본인의 마을에서 X번 마을로 가는 최소 시간과 ② X번 마을에서 출발하여 본인 마을로 돌아오는 데 걸리는 최소 시간을 더하면 된다. 💬 마지막으로 각 학생들이 X번 마을에 다녀오는데 걸린 최소 시간을 비교하여 가장 많은 시간을 소비한 학생의 소요시간을 출력하면 된다. 👨‍💻code import heapq import sys def dijkstra(start, end): distance = [INF] * (.. 2021. 11. 17.
[백준] 도시 분할 계획 / 파이썬 / Python / 크루스칼 알고리즘 / Kruskal 💡solutions 💬 크루스칼 알고리즘을 사용해서 문제를 해결했다. 💬 하나의 마을을 분리하여 두개의 마을로 분활하면 -> 각 마을 안에 있는 집들은 서로 연결돼 있어야 하며 이때 길의 유지비의 합은 최소가 돼야 한다 💬 크루스칼 알고리즘을 활용하여 N-1개의 집들을 연결하고 마지막 유지비가 최대인 경로는 끊으면 (즉, 연결하지 않으면) 이게 바로 유지비가 최소가 되도록 마을을 두개로 분활하는 방법이다. -> 각 집을 연결할 때마다 edge_cnt를 세서 간선의 개수가 n-2가 되면 break한다. (*참고로 MST에서 모든 간선을 연결할 때 최소 간선의 개수는 n-1이다.) 💬 처음에 파이썬으로 코드를 제출했을 때 시간초과가 났고, sys 모듈을 불러와서 input = sys.stdin.readlin.. 2021. 11. 14.
[백준] 보석 도둑 / 1202번 / 파이썬 / Python / heapq/ 힙큐 💡solutions 💬 heapq모듈을 사용하여 최소힙, 최대힙 자료구조를 사용하였음. 💬 보석들은 무게가 작은 순서대로 뽑힐 수 있도록 최소힙으로 구현 💬 가방은 제한된 무게를 기준으로 가벼운 것부터 무거운 순으로 나오도록 오름차순 정렬 💬 for 반복문을 통해 작은 무게 제한을 가진 가방부터 꺼내와서 제한된 무게보다 가벼운 보석들을 임시 리스트인 tmp에 모두 담아둔다 -> 이때 주의할 점은 추후 tmp에서 가장 비싼 애들부터 순서대로 뽑을 수 있게 가격에 마이너스 부호를 붙여 tmp 리스트에 heappush로 넣어준다. (이게 바로 최대힙 구현하는 방법) 💬 가방에 담을 수 있는 보석 중 가장 제일 비싼 가격의 보석을 뽑아서 answer에서 빼준다 -> 애초에 보석 가격을 음수로 넣어놨기 때문에 a.. 2021. 11. 12.
[프로그래머스] 섬 연결하기 / 파이썬 / Python / 크루스칼(Kruskal) 알고리즘 💡solutions ) 💬 '최소 비용으로 모든 노드(섬) 연결' -> 최소 신장 트리(MST)를 사용하는 크루스칼 알고리즘 활용 문제다. 신장 트리(Spanning Tree)란? 그래프 내의 모든 정점을 연결하는 트리로 간선의 개수가 n-1개로 최소 연결 부분 그래프이다. 최소 신장 트리(Minimum Spanning Tree )란? 신장 트리에서 사용된 간선들의 가중치의 합이 최소인 트리 즉, 최소 비용으로 모든 노드 연결하는 그래프이다. 참고 블로그 💬 먼저 다리 건설 비용 기준으로 costs를 오름차순 정렬한다. -> 적은 비용의 노드부터 꺼내와서 연결한다. 💬 노드의 부모를 찾는 find_parent를 통해 꺼내온 두 노드의 부모를 비교한다. ->사이클이 생기지 않게 하기 위해 부모가 다른 경우.. 2021. 11. 9.
[프로그래머스] 약수의 합 / 자바 / Java 💡solutions ) 💬 for 반복문을 통해 n을 i로 나누었을 때 0이되는 약수들을 모두 찾아서 더해주면 되는 문제이다. 💬 참고 : 약수를 찾는 것이기 때문에 for문에서 주어진 n에 대해서 n / 2까지만 약수인지 확인해주면 돼서 계산을 반으로 줄일 수 있다. => for (int i=1; i 2021. 11. 8.
[프로그래머스] 가운데 글자 가져오기 / 자바 / Java / substring() 💡solutions ) 💬 자바 언어 공부를 시작한지 얼마 안돼서, 문법 공부를 할겸 프로그래머스 기본 문제들을 다시 풀어보고 있다. 💬 파이썬에서는 문자열을 s[:2] 이런식으로 간편하게 슬라이싱할 수 있는데, 자바에서는 해당 인덱스의 문자열을 반환하는 substring() 메소드를 사용한다. substring() 메소드는 인자의 개수에 따른 차이 ✔ substring(int Index) 해당 인덱스부터 끝까지 문자열 반환 ✔ substring(int IndexA, int IndexB) 인덱스 A부터 B 직전까지의 문자열 반환 👨‍💻code ) class Solution { public String solution(String s) { String answer = ""; int a = s.length(.. 2021. 11. 8.

티스토리툴바