문제 풀이41 [G4] 백준 1253 - 좋다 (python3) https://www.acmicpc.net/problem/1253 1253번: 좋다 첫째 줄에는 수의 개수 N(1 ≤ N ≤ 2,000), 두 번째 줄에는 i번째 수를 나타내는 Ai가 N개 주어진다. (|Ai| ≤ 1,000,000,000, Ai는 정수) www.acmicpc.net 해결방법 투 포인터를 이용해서 문제를 해결할 수 있다. 풀이👀 이번 문제에서 투 포인터를 활용하기 위해선, 반드시 입력되는 배열이 정렬되어야 한다. 왜냐하면 투 포인터의 head와 tail 인덱스로 어떤 값이 나올지 예측해야 하기 때문이다. 만약 target과 비교했을 때, 값이 작으면 head를 +1 해주고, 반대로 작으면 tail을 -1 해주는 식으로 말이다. 곰곰이 생각해보면 이 로직은 이분탐색의 로직과 같다. (이분탐.. 2023. 7. 14. [G4] 백준 1753 - 최단경로 (Python3) https://www.acmicpc.net/problem/1753 1753번: 최단경로 첫째 줄에 정점의 개수 V와 간선의 개수 E가 주어진다. (1 ≤ V ≤ 20,000, 1 ≤ E ≤ 300,000) 모든 정점에는 1부터 V까지 번호가 매겨져 있다고 가정한다. 둘째 줄에는 시작 정점의 번호 K(1 ≤ K ≤ V)가 www.acmicpc.net 해결방법 다익스트라 알고리즘을 활용하여 풀었다. 풀이👀 나는 그래프를 python의 dictionary로 표현했다. 그래서 입력받은 간선의 정보들을 모두 graph에 담았다. * 하지만 이렇게 되면 쓸모없는 데이터까지 받아오게 된다. "서로 다른 두 정점 사이에 여러 개의 간선이 존재할 수도 있음에 유의한다." 라는 문제 조건이 있기 때문이다. 모든 정보를 담.. 2023. 2. 20. [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. 이전 1 2 3 4 5 6 다음
