반응형 알고리즘38 [알고리즘/백준] 2021번 최소 환승 Python 파이썬 이번 문제는 오랜만에 스스로의 힘으로 풀어볼 수 있었던 문제입니다. 노선별로 지나는 역들이 주어졌을 때 출발역과 도착역이 주어지고 최소 환승 회수를 구하는 문제입니다. 보고 탐색해야하는 문제이니 BFS 로 풀어야겠다고 생각하였습니다. 해당 문제를 쉽게 풀기 위해서 먼저 저장할 때 각 역별로 지나는 노선 번호, 노선별로 지날 수 있는 역 번호들로 리스트를 만들어 저장하였습니다. 그 다음 풀이한 로직을 설명하자면, 시작점이 주어졌을 때 1. 해당 역에서 지나는 노선을 확인한다. 2. 이미 탄 노선인지 아닌지 확인한다. 3. 만약 안 탄 노선이라면 해당 노선에서 갈 수 있는 역을 확인한다 4. 갈 수 있는 역에서 도착역이 있는 확인한다. 5. 도착역이 있다면, 이때까지 누적된 환승 회수를 비교해준다. 4. 도.. 2023. 4. 5. [알고리즘/백준] 1922번 네트워크 연결 Python 파이썬 이번 문제는 어려워서 풀이만 하는데도 1시간 넘게 걸린 문제였습니다. 모든 컴퓨터가 연결했을 때 최소 비용을 구하는 문제로 처음 문제를 보고 생각한 풀이 방법은 가중치가 적은 순으로 나열해연결할까 생각했는데 그 경우 어떻게 모든 컴퓨터가 연결되었는지 확인 방법이 생각 안났습니다. 그래서 두번째는 한 점을 잡아서 작은 가중치로 타고 타고 연결할까 했지만 그 경우 최소값을 구할 수 없다는 점이 있었습니다. 결국 머리 싸매다가 다른 분의 풀이를 찾아봤고 새로운 알고리즘에 대해 알게 되었습니다. (대개 문제가 안 풀리면 기존에 알고 있는 알고리즘으로는 안 풀리는 거 같습니다ㅠㅠ) 이번에 알게된 알고리즘은 "최소 스패닝 트리"하는 알고리즘으로 이해하는데는 해당 블로그(https://www.crocus.co.kr/.. 2023. 3. 29. [알고리즘/백준] 1915번 가장 큰 정사각형 Python 파이썬 이번 문제는 시간복잡도를 고려한 문제 DP 알고리즘이 필요한 문제였습니다. 배열이 주어졌을 때 최대 정사각형 넓이 구하는 문제로 단순하게 생각하면 반복문을 통해 검사해서 답을 구할 수 있지만 이 경우 시간초과가 날 수 있습니다. 이를 방지하기 위해서는 DP 알고리즘을 사용하여 시간 복잡도를 줄어야 통과가 될 수 있습니다. 아래와 같은 코드로 통과하였습니다. import sys input = sys.stdin.readline n, m = map(int, input().split()) map_list = [] dp = [[0]*m for _ in range(n)] for i in range(n): map_list.append(list(map(int, input().rstrip()))) answer = 0 f.. 2023. 3. 27. [알고리즘/백준] 1753번 최단경로 Python 파이썬 이번 문제는 처음으로 heap 을 사용해보고 푸는데 애 먹었던 문제였습니다. 문제는 보기에 간단해보입니다. 시작점이 주어졌을때 각 정점의 최소 경로 거리를 구해서 출력하는 문제입니다. 저는 처음에 탐색 문제로 판단하고 BFS를 통해서 풀려고 접근했습니다 풀다가 너무 복잡해진게 틀린 거 같아서 다른 분의 풀이를 찾아보니 다들 heap을 사용하시더라고요 그래서 왜 heap을 사용해서 푸는 가? 의문이 생겼는데 해당 블로그 https://my-coding-notes.tistory.com/200 이해할 수 있었습니다. 간단히 말하면 효율성 때문에 heap을 써주는 것이었습니다. heap의 특징으로는 최소값을 먼저 pop 해주는데 이를 통해서 최소 경로를 구하는데 계산을 단축할 수 있게 됩니다. 아래와 같은 코드.. 2023. 3. 26. 이전 1 2 3 4 5 6 ··· 10 다음 반응형
