알고리즘 스터디
[백준] 2252 줄 세우기 - 위상 정렬 파이썬
문제 https://www.acmicpc.net/problem/2252 2252번: 줄 세우기 첫째 줄에 N(1 ≤ N ≤ 32,000), M(1 ≤ M ≤ 100,000)이 주어진다. M은 키를 비교한 회수이다. 다음 M개의 줄에는 키를 비교한 두 학생의 번호 A, B가 주어진다. 이는 학생 A가 학생 B의 앞에 서야 한다는 의 www.acmicpc.net 풀이 https://freedeveloper.tistory.com/390 [이것이 코딩 테스트다 with Python] 36강 위상 정렬 4https://www.youtube.com/watch?v=xeSz3pROPS8&list=PLVsNizTWUw7H9_of5YCB0FmsSc-K44y81&index=36 위상 정렬 사이클이 없는 방향 그래프의 모든 ..
[백준] 16916 부분 문자열 - KMP 파이썬
문제 https://www.acmicpc.net/problem/16916 16916번: 부분 문자열 첫째 줄에 문자열 S, 둘째 줄에 문자열 P가 주어진다. 두 문자열은 빈 문자열이 아니며, 길이는 100만을 넘지 않는다. 또, 알파벳 소문자로만 이루어져 있다. www.acmicpc.net 부분 문자열 시간제한 메모리 제한 제출 정답 맞힌사람 정답비율 1 초 512 MB 6354 1927 1410 36.191% 문제 문자열 S의 부분 문자열이란, 문자열의 연속된 일부를 의미한다. 예를 들어, "aek", "joo", "ekj"는 "baekjoon"의 부분 문자열이고, "bak", "p", "oone"는 부분 문자열이 아니다. 문자열 S와 P가 주어졌을 때, P가 S의 부분 문자열인지 아닌지 알아보자. 입..
[백준] 1197 최소 스패닝 트리 파이썬
문제 https://www.acmicpc.net/problem/1197 1197번: 최소 스패닝 트리 첫째 줄에 정점의 개수 V(1 ≤ V ≤ 10,000)와 간선의 개수 E(1 ≤ E ≤ 100,000)가 주어진다. 다음 E개의 줄에는 각 간선에 대한 정보를 나타내는 세 정수 A, B, C가 주어진다. 이는 A번 정점과 B번 정점이 www.acmicpc.net 문제 그래프가 주어졌을 때, 그 그래프의 최소 스패닝 트리를 구하는 프로그램을 작성하시오. 최소 스패닝 트리는, 주어진 그래프의 모든 정점들을 연결하는 부분 그래프 중에서 그 가중치의 합이 최소인 트리를 말한다. 입력 첫째 줄에 정점의 개수 V(1 ≤ V ≤ 10,000)와 간선의 개수 E(1 ≤ E ≤ 100,000)가 주어진다. 다음 E개의 ..
[백준] 1916 최소비용 구하기 파이썬
문제 https://www.acmicpc.net/problem/1916 1916번: 최소비용 구하기 첫째 줄에 도시의 개수 N(1 ≤ N ≤ 1,000)이 주어지고 둘째 줄에는 버스의 개수 M(1 ≤ M ≤ 100,000)이 주어진다. 그리고 셋째 줄부터 M+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 www.acmicpc.net 문제 N개의 도시가 있다. 그리고 한 도시에서 출발하여 다른 도시에 도착하는 M개의 버스가 있다. 우리는 A번째 도시에서 B번째 도시까지 가는데 드는 버스 비용을 최소화 시키려고 한다. A번째 도시에서 B번째 도시까지 가는데 드는 최소비용을 출력하여라. 도시의 번호는 1부터 N까지이다. 입력 첫째 줄에 도시의 개수 N(1 ≤ N ≤ 1,000)이 주어지고 둘..
[백준] 1700 멀티탭 스케줄링 파이썬
문제 https://www.acmicpc.net/problem/1700 1700번: 멀티탭 스케줄링 기숙사에서 살고 있는 준규는 한 개의 멀티탭을 이용하고 있다. 준규는 키보드, 헤어드라이기, 핸드폰 충전기, 디지털 카메라 충전기 등 여러 개의 전기용품을 사용하면서 어쩔 수 없이 각종 전 www.acmicpc.net 풀이 현재 탭에 꽂혀있는 제품 중 가장 나중에 사용되는 제품을 뽑는 그리디 문제였다. next에 현재 스케줄 뒤로 제품별로 가장 빨리 사용되는 순번을 저장해놓는다. 멀티텝에 꽂힌 제품 중 next에서 가장 번호가 큰 것을 제거한다. n, k = map(int, input().split()) order = list(map(int, input().split())) next = {} for i i..
[백준] 1806 부분합 파이썬
문제 https://www.acmicpc.net/problem/1806 1806번: 부분합 첫째 줄에 N (10 ≤ N < 100,000)과 S (0 < S ≤ 100,000,000)가 주어진다. 둘째 줄에는 수열이 주어진다. 수열의 각 원소는 공백으로 구분되어져 있으며, 10,000이하의 자연수이다. www.acmicpc.net 풀이 그냥 투포인터로 풀면 되는 문제였다. st 부터 ed까지의 합이 s 미만이면 ed를 한 칸 뒤로 옮기고 s 이상이면 st를 한 칸 뒤로 옮겨 sum 에서 st에 해당하는 값을 뺐다. 불가능할 경우 0을 출력하라는 문구를 못 봐서 틀렸었다. n, s = map(int, input().split()) arr = list(map(int, input().split())) st =..
[백준] 1062 가르침 파이썬
문제 https://www.acmicpc.net/problem/1062 1062번: 가르침 첫째 줄에 단어의 개수 N과 K가 주어진다. N은 50보다 작거나 같은 자연수이고, K는 26보다 작거나 같은 자연수 또는 0이다. 둘째 줄부터 N개의 줄에 남극 언어의 단어가 주어진다. 단어는 영어 소문 www.acmicpc.net 풀이 공통으로 포함되는 알파벳 a c n t i를 제외하고 중복을 없애기 위해 set으로 각 단어를 읽기 위해 추가로 필요한 알파벳들을 구한다. 그 다음 전체 알파벳에서 a c n t i 를 제외한 k-5개의 조합을 만들어 각 조합별로 몇 개의 단어를 읽을 수 있는지 세려고 했다. 그런데 조합 만들어서 테스트하는 부분에서 연산이 엄청 많이 시행될 것 같았다. 뭔가 시간초과의 느낌이 나..
[백준] 14719 빗물 파이썬
문제 https://www.acmicpc.net/problem/14719 14719번: 빗물 첫 번째 줄에는 2차원 세계의 세로 길이 H과 2차원 세계의 가로 길이 W가 주어진다. (1 ≤ H, W ≤ 500) 두 번째 줄에는 블록이 쌓인 높이를 의미하는 0이상 H이하의 정수가 2차원 세계의 맨 왼쪽 위치 www.acmicpc.net 풀이 가장 아래쪽부터 반복문을 돌며 왼쪽이 뚫려 있을 때는 -1 막혀있으면 0으로 바꿔주고 그 다음 블록부터 카운트를 시작해서 비어있는 칸이 있을 때마다 1씩 더해줬다. O(n^2)이라 이게 될까? 싶었는데 통과했다. h, w = map(int, input().split()) heights = list(map(int, input().split())) answer = [0]*..