문제 풀이/백준47 [G4] 백준 11404 - 플로이드 (Python3) https://www.acmicpc.net/problem/11404 11404번: 플로이드 첫째 줄에 도시의 개수 n이 주어지고 둘째 줄에는 버스의 개수 m이 주어진다. 그리고 셋째 줄부터 m+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 버스의 출발 도시의 번호가 www.acmicpc.net 해결방법 플로이드-워셜 알고리즘을 이용해 풀이했다. 풀이👀 이번 입력은 [출발-도착-비용]이 들어오는데, 출발과 도착 정보가 동일한 입력도 포함된다. 그래서 이런 경우를 대비해주어야 한다. 이 문제는 모든 경로로 이동하는 최소비용 정보를 (출력하라고)요구하고 있다. 그러므로 출발과 도착 정보가 동일하게 주어질 땐 기존 입력값과 비교해서 더 작은 값을 반영해서 이 문제를 풀면 된다. 코드🐱👓 IN.. 2023. 1. 31. [G5] 백준 1916 - 최소비용 구하기 (Python3) https://www.acmicpc.net/problem/1916 1916번: 최소비용 구하기 첫째 줄에 도시의 개수 N(1 ≤ N ≤ 1,000)이 주어지고 둘째 줄에는 버스의 개수 M(1 ≤ M ≤ 100,000)이 주어진다. 그리고 셋째 줄부터 M+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 www.acmicpc.net 해결방법 다익스트라 알고리즘을 이용한다. 풀이👀 입력에서 버스 이동에 대한 정보를 제공해주고 있다. 순서대로 [출발점, 도착점, (출발->도착)비용] 이다. 각 지점에서는 연결 된 다른 점들로 이동할 수 있다. 이 이동에서 비용이 발생한다. 그런데 이동을 하면서 출발점과 도착점이 같지만 중간에 우회하는 경로를 달리하여 그 비용(결과)를 저렴하게 할 수 있다. 하지.. 2023. 1. 30. [S4] 백준 2417 - 정수 제곱근 (python3) https://www.acmicpc.net/problem/2417 2417번: 정수 제곱근 정수가 주어지면, 그 수의 정수 제곱근을 구하는 프로그램을 작성하시오. www.acmicpc.net 해결방법 0과 n(n>=0) 의 중앙값의 제곱이 n과 같은지, 큰지, 작은지를 따져보며 q를 구해내는 해결 방법이다. n과 m의 중앙값의 제곱은 앞으로 'n과 m의 중앙제곱'이라고 부르겠다. 만약 0과 n의 중앙제곱이 n과 같다면 그 값이 정답이다. ( 0과 4의 중앙제곱 = 2, 2^2 = 4) 만약 0과 n의 중앙제곱이 n보다 크다면 mid와 n의 중앙제곱을 비교한다. 만약 0과 n의 중앙제곱이 n보다 작다면 0과 mid의 중앙제곱을 비교한다. 위 조건문 안에서는 low와 high를 업데이트 해주는 작업도 반드시.. 2023. 1. 19. [S3] 백준 2512 - 예산 (Python3) https://www.acmicpc.net/problem/2512 2512번: 예산 첫째 줄에는 지방의 수를 의미하는 정수 N이 주어진다. N은 3 이상 10,000 이하이다. 다음 줄에는 각 지방의 예산요청을 표현하는 N개의 정수가 빈칸을 사이에 두고 주어진다. 이 값들은 모두 1 이상 www.acmicpc.net 해결방법 이분 탐색으로 풀이한다. 풀이👀 최소값과 최대값을 lo와 hi라고 하고, 그 안에서 binary search를 한다. 동작 과정은 아래와 같다. mid = (lo + hi) // 2 라 한다. ① mid를 상한액으로 지정한 뒤, 지방의 예산요청을 계산하여본다. 만약 합산한 게 국가예산을 넘어서면 hi = mid로 하여 다시 계산하고, 반대로 국가예산보다 적다면 lo = mid로 하여.. 2023. 1. 18. [S2] 백준 1012 - 유기농 배추 (Python3) https://www.acmicpc.net/problem/1012 1012번: 유기농 배추 차세대 영농인 한나는 강원도 고랭지에서 유기농 배추를 재배하기로 하였다. 농약을 쓰지 않고 배추를 재배하려면 배추를 해충으로부터 보호하는 것이 중요하기 때문에, 한나는 해충 방지에 www.acmicpc.net 해결방법 배추가 상하좌우로 모여 있는 곳 하나당 필요한 배추흰지렁이 수가 된다. 그러므로 이렇게 모여있는 군집이 몇 개 인지만 파악하여 출력하는 것이 목표이다. 파악하는 방법은 DFS, BFS 등이 있는데 이 글에선 BFS를 다루고 있다. grid를 일일이 탐색하다가 배추가 있는 자리라고 표시해둔 곳을 마주치게 되면, BFS를 통해서 상하좌우에 위치한 배추들을 0으로 바꾸어준다. 0으로 바꾸는 이유는 '탐색을.. 2023. 1. 15. [S2] 백준 11568 - 민균이의 계략 (Python3) https://www.acmicpc.net/problem/11568 해결방법 최장 증가 부분 수열(LIS, Longest Increasing Subsequence)의 기초 문제이다. 이전에 이 시리즈를 풀어본 경험이 있어서 풀이의 틀은 쉽게 잡았다. 나는 시간복잡도가 O(n^2) 인 알고리즘으로 문제를 풀었다. arr의 길이가 최대 1,000 이므로 O(n^2)은 1,000,000이라 제한시간(1초) 안에 충분히 통과가 가능하다. 더 빠른 방법은 O(n log n) 있다. n=1000 일때, n log n = 3000 이므로 더 빠르게 통과할 것이다. 풀이 이 문제의 풀이는 arr에 있는 각 원소를 주목해야 한다. arr에 있는 원소들을 반복문으로 앞에서부터 차례차례 접근할 것이다. 이때 그 원소가 이 .. 2023. 1. 15. [S3] 백준 21921 - 블로그 (Python3) https://www.acmicpc.net/problem/21921 21921번: 블로그 첫째 줄에 $X$일 동안 가장 많이 들어온 방문자 수를 출력한다. 만약 최대 방문자 수가 0명이라면 SAD를 출력한다. 만약 최대 방문자 수가 0명이 아닌 경우 둘째 줄에 기간이 몇 개 있는지 출력한다 www.acmicpc.net 해결방법 구간 합 중 가장 큰 값이 무엇이며, 그 값이 몇 번 나오는지 파악해야 하는 문제로 누적합과 슬라이딩 윈도우를 이용할 줄 알아야 한다. 코드 N, X = map(int, input().split()) arr = list(map(int, input().split())) prefix = [0] for i in range(N): prefix.append(prefix[i] + arr[i].. 2023. 1. 14. [S4] 백준 4949 - 균형잡힌 세상 (Python3) https://www.acmicpc.net/problem/4949 4949번: 균형잡힌 세상 하나 또는 여러줄에 걸쳐서 문자열이 주어진다. 각 문자열은 영문 알파벳, 공백, 소괄호("( )") 대괄호("[ ]")등으로 이루어져 있으며, 길이는 100글자보다 작거나 같다. 각 줄은 마침표(".")로 끝난다 www.acmicpc.net 이 문제보다 한 단계 쉬운 문제는 백준 9012번: 괄호라고 생각한다. 이 문제를 풀고나서 이 문제를 푸는 것을 추천한다. 해결방법 스택을 활용하는 문제이다. bracket 이라는 리스트 변수에 여는 괄호("(", "[")를 담고, 닫는 괄호(")", "]")가 나올 때마다 bracket의 원소를 pop 해주는 방식으로 문제를 풀었다. 코드 while (string:=inpu.. 2023. 1. 14. 이전 1 2 3 4 5 6 다음
