본문 바로가기

PS75

[Python] 백준 11404번 : 플로이드 https://www.acmicpc.net/problem/11404 11404번: 플로이드 첫째 줄에 도시의 개수 n이 주어지고 둘째 줄에는 버스의 개수 m이 주어진다. 그리고 셋째 줄부터 m+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 버스의 출발 도시의 번호가 www.acmicpc.net 💡 문제 풀이 그래프 문제 중 플로이드-워샬 알고리즘 문제이다. 플로이드-워샬 알고리즘을 구현하면 된다. 입력값 중에 목적지가 같은 버스가 있어서 edge들을 입력받을 때 더 작은 값으로 최신화해야 한다. ✔️ 느낀 점 플로이드-워샬 알고리즘 자체는 어렵지 않지만 문제 조건인 "갈 수 없을 때 0으로 출력하라."와 "같은 목적지의 버스가 있음."을 놓쳐서 계속 틀려서 화가 났다 ^^. 문제를 잘 .. 2022. 8. 17.
[Python] 백준 18352번 : 특정 거리의 도시 찾기 https://www.acmicpc.net/problem/18352 18352번: 특정 거리의 도시 찾기 첫째 줄에 도시의 개수 N, 도로의 개수 M, 거리 정보 K, 출발 도시의 번호 X가 주어진다. (2 ≤ N ≤ 300,000, 1 ≤ M ≤ 1,000,000, 1 ≤ K ≤ 300,000, 1 ≤ X ≤ N) 둘째 줄부터 M개의 줄에 걸쳐서 두 개 www.acmicpc.net 💡 문제 풀이 그래프 탐색 문제이다. BFS와 다익스트라 알고리즘 2가지로 해결할 수 있다. 출발지점부터 큐에 넣고 가중치를 계산해주면 된다. ✔️ 느낀 점 코드를 짜다보니 어쩌다 보니 BFS로 구현했다. 💻 코드 import sys from collections import deque input = sys.stdin.rea.. 2022. 8. 16.
[Python] 백준 1744번 : 수 묶기 https://www.acmicpc.net/problem/1744 1744번: 수 묶기 길이가 N인 수열이 주어졌을 때, 그 수열의 합을 구하려고 한다. 하지만, 그냥 그 수열의 합을 모두 더해서 구하는 것이 아니라, 수열의 두 수를 묶으려고 한다. 어떤 수를 묶으려고 할 때, 위치에 www.acmicpc.net 💡 문제 풀이 그리디 알고리즘 문제이다. 수를 묶는 기준을 가장 큰 값이 되는 기준을 찾아내면 된다. 같은 부호끼리는 곱해도 되지만 부호가 다르면 그냥 더하는게 곱하는 것보다 큰 값이 나온다. 0은 양수는 더하는게 크지만 음수는 곱하는게 더 큰 값이 나온다. 1은 양수, 음수 모두 더하는게 더 큰 값이 나온다. 이런 이유로 입력받는 값들을 나누어줘야하는데 음수(+ 0), 양수, 1로 나눠서 입력.. 2022. 8. 15.
[Python] 백준 1644번 : 소수의 연속합 https://www.acmicpc.net/problem/1644 1644번: 소수의 연속합 첫째 줄에 자연수 N이 주어진다. (1 ≤ N ≤ 4,000,000) www.acmicpc.net 💡 문제 풀이 투 포인터 문제이다. 소수랑 섞은 문제인데 범위가 4백만까지 이므로 에라토스테네스의 체를 사용해서 소수를 찾아준다. 찾은 소수를 대상으로 투 포인터 알고리즘 중 특정 값과 일치하는 부분 배열을 찾는 알고리즘으로 카운트하면 된다. ✔️ 느낀 점 그렇게 어렵지 않았는데 시간이 생각보다 오래 걸리는 풀이여서 더 나은 코드로 바꾸고 싶었으나 굳이 그러기엔 너무 귀찮아서 넘어가야겠다. 💻 코드 N = int(input()) prime_nums = [True] * (N+1) for i in range(2, int.. 2022. 8. 10.
[Python] 백준 1806번 : 부분합 https://www.acmicpc.net/problem/1806 1806번: 부분합 첫째 줄에 N (10 ≤ N < 100,000)과 S (0 < S ≤ 100,000,000)가 주어진다. 둘째 줄에는 수열이 주어진다. 수열의 각 원소는 공백으로 구분되어져 있으며, 10,000이하의 자연수이다. www.acmicpc.net 💡문제 풀이 투 포인터 문제이다. 투 포인터의 2가지 유형 중 특정 값을 넘는 배열에 대해서 구하면 된다. 누적 값이 S보다 크다면 개수를 따져주고 왼쪽 포인터를 1 늘린다. S보다 작다면 오른쪽 포인터를 1 늘린다. ✔️ 느낀 점 쉬운 문제였는데 문제를 제대로 안 읽어서 오래 걸렸다. '이상인 값 모두' 💻 코드 N, S = map(int, input().split()) arr =.. 2022. 8. 10.
[Python] 백준 3273번 : 두 수의 합 https://www.acmicpc.net/problem/3273 3273번: 두 수의 합 n개의 서로 다른 양의 정수 a1, a2, ..., an으로 이루어진 수열이 있다. ai의 값은 1보다 크거나 같고, 1000000보다 작거나 같은 자연수이다. 자연수 x가 주어졌을 때, ai + aj = x (1 ≤ i < j ≤ n)을 만족하는 www.acmicpc.net 💡 문제 풀이 두 포인터 문제이다. 정렬을 한 다음에 시작 값과 끝 값을 계산해서 같다면 정답의 개수를 늘리고, 계산값이 찾는 값 보다 크면 end를 줄이고, 반대라면 start를 늘리면 된다. ✔️ 느낀 점 두 포인터의 개념을 처음 공부하는 기회였다. 이번에 잘 정리해놔야겠다. 💻 코드 N = int(input()) arr = list(ma.. 2022. 8. 8.

티스토리툴바