본문 바로가기

알고리즘 & PS69

[Python] 최단 경로 알고리즘, Dijkstra 알고리즘 참고자료 [1] https://m.blog.naver.com/ndb796/221234424646 23. 다익스트라(Dijkstra) 알고리즘 다익스트라(Dijkstra) 알고리즘은 다이나믹 프로그래밍을 활용한 대표적인 최단 경로(Shortest Path) 탐... blog.naver.com [2] 이것이 코딩테스트다 with 파이썬 다익스트라 알고리즘이란? 다익스트라 알고리즘은 최단 경로 문제를 푸는데, 다이나믹 프로그래밍을 활용하는 알고리즘이다. 이는, 하나의 최단 거리를 구하기 위해 그 이전까지 구한 최단 거리 정보를 그대로 사용한다는 것이다. 다익스트라 알고리즘의 개요 1. 출발 노드를 설정한다. 2. 최단 거리 테이블을 초기화한다. 3. 방문하지 않은 노드 중 최단거리가 가장 짧은 노드를 선택한다.. 2021. 5. 30.
[Python] 백준 13413번 : 오셀로 재배치 출처 : www.acmicpc.net/problem/13413 13413번: 오셀로 재배치 로봇을 좋아하는 세희는 로봇동아리에서 카메라와 센서, 라즈베리 파이, 집게발을 이용해 로봇을 완성하였다. 이 로봇을 통해서 오셀로 재배치라는 작업을 하려고 한다. 오셀로 말은 앞면이 검 www.acmicpc.net 알고리즘 그리디 문제이다. 시작문자열과, 끝 문자열일 비교하여 틀린 부분만 집어넣고 정렬하여, 비교하자. 색이 일치했으면 나중에 위치를 바꿀 놈이 나온다는 의미이므로 +0.5 색이 일치하지 않는다면 뒤집었어야 하는 놈이므로 1을 더하자. 이 풀이방식을 떠올리기 쉽지 않은 문제이다. 코드 def main(): cases = int(input()) for _ in range(cases): length = i.. 2021. 5. 10.
[Python] 백준 7562 - 나이트의 여행 문제출처 : www.acmicpc.net/problem/7562 7562번: 나이트의 이동 체스판 위에 한 나이트가 놓여져 있다. 나이트가 한 번에 이동할 수 있는 칸은 아래 그림에 나와있다. 나이트가 이동하려고 하는 칸이 주어진다. 나이트는 몇 번 움직이면 이 칸으로 이동할 수 www.acmicpc.net 알고리즘 일반적인 bfs문제이다. 다만, 최소값을 항상 유지시켜야함에 주의하자. 이미 최소 스텝이 아니었으면 최소가 아니니까. deque를 쓸 경우 왼쪽부터 빼야, 최소에서 최소를 시도할수가 있다. popleft를 해줘야 한다. 따라서, visited를 만드는 것이 아니라 보드판 자체를 visited로 사용하는 것이 중요 포인트. 시작점이 0으로 시작하므로 -1을 default값으로 설정하여 풀었다... 2021. 5. 4.
[Python] 프로그래머스 Lv 3 - 가장 먼 노드 개고생했던 문제 중 하나. 출처 알고리즘 그저, 1번노드부터 시작해서 최단거리를 구하면 되는 문제다. BFS로 depth를 돌려줘도 되고, 다익스트라를 쓰되, 모든 거리를 1이라고 가정해도 되는 문제다. 주의할 점은, edge의 집합이 주어져 있는데, 모든 vertex에 대해 edge의 유무를 따질 경우 시간초과가 난다. 따라서, dict를 만들어야 하는데, 각 꼭지점으로 연결된 상태 파악을 위해서는 defaultdict를 활용하여, 각 꼭지점마다 연결된 다른 점들의 list를 만들어줘야 한다. 코드(1트, 실패) 그저 bfs로 푼 코드이다. 시간 초과가 걸려 실패했으며, 빼는 방향과 넣는 방향이 반대로 해야 성공하는데, 아직까지도 정확한 이유를 판단하지 못했다. 따라서, 더 확실한 방향인 다익스트라로의.. 2021. 4. 29.
[Python] 프로그래머스 Lv 3 - 거스름돈 프로그래머스 Lv 3 거스름돈 문제 풀이 출처 알고리즘 단순히, 큰 거부터 고르면 큰일난다. 왜냐면, 돈의 종류에 대해서 제한이 없기에, 작은 돈의 배수가 money중에 있을 수 있 으며, 이의 경우 경우의 수가 달라진다! 따라서, 그리디로 푸는 것은 불가능. 이 문제는 다른 방법으로 풀어야 할 것이다. 그 방법은 바로 DP. 동전이 1개인 경우, 2개인 경우, 3개인 경우로 늘려야 한다. 간단한 방식인데, 동전이 2개로 해결되는 경우와 그 동전이 꼭 필요한 경우를 나눠서 합치면 된다. 예시) 1,2,5원에서 13원 의 경우의 수를 구할려면 (1, 2원으로만 13원을 만드는 경우의 수) + (5원을 끼고 1,2,5원으로 13원을 만드는 수) = (1, 2원으로만 13원을 만드는 경우의 수) + (5원 1.. 2021. 4. 29.
[Python] 프로그래머스 Lv 3 - 입국심사 이진탐색을 어떻게 써먹는지 알 수 있는 문제 출처 : https://programmers.co.kr/learn/courses/30/lessons/43238 알고리즘 그냥 배수를 저장한다던가, 하는 방식으로는 도저히 무리거니와, 입국심사대가 늘어날수록 2개의 쌍만 최소공배수인 경우도 발생하고... 너무 복잡하다. 되도 않는 소리다. 따라서, 방법을 바꿔야 한다. 시간을 많이 줄수록 입국심사대에서 처리할 수 있는 사람은 많을거니까, 아예 시간을 기준으로 입국심사대가 제한된 인원보다 많거나 같게 처리하면 시간을 줄이고, 덜 통과시키면 늘려버리면 된다. 최소의 지점이 바로 최소시간이 될 것이고 이는 이진탐색으로 구현 가능하다. right의 지정이 문제인데, 최소 개수의 * n만큼만 하면 충분하다. 그거보다 다른.. 2021. 4. 29.

티스토리툴바