728x90 반응형 파이썬13 최단 경로 알고리즘 - 플로이드 워셜 알고리즘 드디어 최단 경로 알고리즘! DFS/BFS의 벽이 너무 높았지만 내가 해냄 플로이드 워셜 알고리즘 플로이드 워셜 알고리즘은 모든 지점에서 다른 모든 지점까지의 최단경로를 구할때 사용하는 알고리즘이다. 단계마다 거쳐가는 노드를 기준으로 알고리즘을 수행한다. 이 때 점화식을 사용하게 되므로 일종의 다이나믹 프로그래밍이다. 노드의 개수가 n개 일때 n번의 단계를 수행하며 단계마다 n^2의 연산을 통해 모든 경로를 고려하게된다. 총 시간복잡도는 n^3이다. 시간복잡도가 큰 만큼 풀 수 있는 유형이 정해져있다. 풀이 순서 1. 2차원의 리스트를 무한의 값으로 채워 넣는다. 2. 자기자신에서 자기자신으로 가는 경우는 비용을 0으로 처리 3. 각 간선의 정보를 입력받아 초기화 한다. 4. 플로이드 워셜 알고리즘 수행.. 2023. 1. 24. 백준 2512 - 예산 ( Python ) https://www.acmicpc.net/problem/2512 2512번: 예산 첫째 줄에는 지방의 수를 의미하는 정수 N이 주어진다. N은 3 이상 10,000 이하이다. 다음 줄에는 각 지방의 예산요청을 표현하는 N개의 정수가 빈칸을 사이에 두고 주어진다. 이 값들은 모두 1 이상 www.acmicpc.net 이진 탐색으로 풀이가 가능하다 예산의 상한선을 구하는 문제다 예산의 상한선을 구하기 위해서는 총 예산의 최적의 합계가 필요하다. 이진 탐색의 중간값이 예산의 상한선이 되며 해당 상한선보다 예산이 큰 경우에는 상한선을 더하고 예산이 작거나 같은경우에는 해당 예산을 더한다 총 예산의 합이 지정된 예산값보다 작거나 같은 경우 상한선을 높이고 -> start값을 늘려줌 초과된 경우에는 상한선을 줄이.. 2023. 1. 10. 백준 1463 - 1로 만들기( Python ) https://www.acmicpc.net/problem/1463 전형적인 dp유형의 문제로 입력값이 1000000개, 백만개로로 적은편이기때문에 더욱이 dp로 풀어야하는 문제임을 알 수 있다. 점화식을 찾아보자 array[1] = 0 array[2] = min(array[1] + 1, array[2//2] + 1) array[3] = min(array[2] + 1, array[3//3] + 1) array[4] = min(array[3] + 1, array[4//2] + 1) array[5] = array[4] + 1 //2와 3으로 나누어 지지 않는 경우 array[6] = min(array[5] + 1, array[6//3] + array[3]) array[7] = array[6] + 1 array.. 2022. 12. 24. 백준 11727 - 2×n 타일링 2 (Python) https://www.acmicpc.net/problem/11727 11727번: 2×n 타일링 2 2×n 직사각형을 1×2, 2×1과 2×2 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오. 아래 그림은 2×17 직사각형을 채운 한가지 예이다. www.acmicpc.net 전형적인 dp 문제 dp문제의 핵심은 점화식을 빨리찾는 수 밖에 없는거 같다. 해당 문제는 직접 그리는 방식으로 점화식을 쉽게 찾을 수 있는 것 같다. 점화식 연습을 위해서는 가능한 다양한 문제를 풀어봐야할 것 같다. 1. 입력값이 1000이므로 1001개의 배열을 생성 -> 0번 인덱스는 계산하지 않기 때문 2. 입력값 1, 2는 규칙성을 찾을 수 없으므로 값을 바로 대입 3. 점화식 찾기 n = 2 -> 3 n = 3 ->.. 2022. 12. 19. 백준 17478 - 재귀함수가 뭔가요? https://www.acmicpc.net/problem/17478 17478번: 재귀함수가 뭔가요? 평소에 질문을 잘 받아주기로 유명한 중앙대학교의 JH 교수님은 학생들로부터 재귀함수가 무엇인지에 대하여 많은 질문을 받아왔다. 매번 질문을 잘 받아주셨던 JH 교수님이지만 그는 중앙대 www.acmicpc.net 문제는 전혀 어렵지않은데 문자열을 작성하는 점이 조금은 헷갈렸다... 문자열을 연결해야하는 경우 콤마(,) 와 플러스(+)의 경우가 달랐다 콤마는 공백이 자동으로 추가되며 플러스의 경우 공백없이 연결된다 이것 때문에 6번은...제출을 다시함 ㅠㅠㅠ n = int(input()) text1 = "\"재귀함수가 뭔가요?\"" text2 = "\"잘 들어보게. 옛날옛날 한 산 꼭대기에 이세상 모든 지.. 2022. 12. 17. 백준 1439 - 뒤집기 ( Python ) https://www.acmicpc.net/problem/1439 1439번: 뒤집기 다솜이는 0과 1로만 이루어진 문자열 S를 가지고 있다. 다솜이는 이 문자열 S에 있는 모든 숫자를 전부 같게 만들려고 한다. 다솜이가 할 수 있는 행동은 S에서 연속된 하나 이상의 숫자를 잡고 모 www.acmicpc.net 초급 그리디 알고리즘 문제 거스름돈을 거슬러주는 그리디 문제랑 다른경우이다. 문제에서 2가지 경우를 나눠서 구분하므로 알고리즘도 2가지의 경우로 나눠서 짜야한다. 제한 시간 20분 풀이방법 1. 모두 1로 뒤집는 경우 혹은 0으로 뒤집는 경우로 나눠서 계산 후 각각 변수에 저장 2. 1로 뒤집는 경우 -> 첫번째 숫자가 0이면 카운트 + 1 -> 1에서 0으로 바뀔 때 카운트 + 1 3. 0으로 .. 2022. 12. 9. 이전 1 2 3 다음 728x90 반응형
