본문 바로가기

전체 글229

[백준] 14567번 선수과목(python) https://www.acmicpc.net/problem/14567 14567번: 선수과목 (Prerequisite) 3개의 과목이 있고, 2번 과목을 이수하기 위해서는 1번 과목을 이수해야 하고, 3번 과목을 이수하기 위해서는 2번 과목을 이수해야 한다. www.acmicpc.net 1. 난이도 골드5 (🥇) 위상정렬을 이용해 문제를 풀었다. 위상정렬은 위 문제와 같이, 작업을 차례대로 수행해야 할 때 사용하는 알고리즘이다. 2. 내가 작성한 코드 import sys from collections import deque input = sys.stdin.readline n,m = map(int, input().rstrip().split()) #n = 과목수 m = 선수 조건수 indegree = [0] .. 2023. 3. 3.
[알고리즘] 위상정렬 + 문제풀이 위상 정렬 => O(V+E) 순서가 정해져 있는 작업을 차례대로 수행할 때 사용되는 알고리즘 (방향그래프) 진입차수(indegree) : 노드로 들어오는 간선의 개수 진입차수가 0인 것을 queue에 넣고 그 노드에서 출발하는 간선 삭제 queue가 빌 때까지 반복 코드 from collections import deque v,e = map(int, input().split()) # v 노드 e 간선 indegree = [0] * (v+1) # 진입차수의 정보 graph = [[] for i in range(v+1)] for _ in range(e): a,b = map(int, input().split()) graph[a].append(b) indegree[b] += 1 def topology_sort(.. 2023. 3. 2.
[백준] 1197번 최소 스패닝 트리(python) 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 1. 난이도 골드4 (🥇) import sys input = sys.stdin.readline v,e = map(int, input().rstrip().split()) #v정점 e간선 parent = [i for i in range(v+1)] edges = [] result = 0 def find(x): if parent[x] != x: parent[.. 2023. 3. 2.
[알고리즘] 최소 스패닝 트리 + 문제풀이 신장트리 모든 노드를 포함하면서 사이클이 존재하지 않는 부분 그래프 즉, 사이클 없이 모든 노드가 연결됨 (=트리) 최소 신장 트리 알고리즘 => E(logE) 최소 비용으로 만들 수 있는 신장트리를 찾는 알고리즘 간선 개수 = 노드 개수 - 1 대표적으로 크루스칼 알고리즘이 있음 간선을 가중치에 따라 오름차순 정렬 사이클이 발생하지 않는 경우 MST에 포함 코드 n,m = map(int, input().split()) #n=노드 m=간선 edges = [] parent = [i for i in range(n+1)] #부모를 본인으로 초기화 result = 0 def find(x): if parent[x] != x: parent[x] = find(parent[x]) return parent[x] def .. 2023. 3. 2.
[백준] 1749번 점수따먹기(python)(누적합) https://www.acmicpc.net/problem/1749 1749번: 점수따먹기 동주는 항상 혼자 노느라 심심하다. 하지만 혼자 놀기의 고수가 된 동주는 매일매일 게임을 개발하여 혼자놀기의 진수를 우리에게 보여준다. 어느 날 동주는 새로운 게임을 개발하였다. 바로 점 www.acmicpc.net 1. 난이도 골드4 (🥇) https://www.acmicpc.net/problem/11660 (구간 합 구하기5) 2차원 배열을 이용한다는 점에서 이 문제와 유사하나, (x1,y1)부터 (x2,y2)까지의 경우에 가능한 x1,y1을 모두 확인해봐야 한다는 차이점이 존재한다. 1. 새로운 배열에 구간합을 구한다. sum_num[i][j] = sum_num[i-1][j] + sum_num[i][j-1] -.. 2023. 3. 2.
[백준] 피아노 체조(python)(누적합) https://www.acmicpc.net/problem/21318 21318번: 피아노 체조 피아노를 사랑하는 시은이는 매일 아침 피아노 체조를 한다. 시은이는 N개의 악보를 가지고 있으며, 1번부터 N번까지의 번호로 부른다. 각 악보는 1 이상 109 이하의 정수로 표현되는 난이도를 www.acmicpc.net 1. 난이도 실버1 (🥈) 2. 문제 해결 방법 누적합을 이용해서 문제를 해결하면 된다. 지금 연주가 다음 연주보다 어려울 경우 '총 실수'에서 +1 해준 값으로 list의 value를 바꿔준다. 이후 주어진 구간의 합을 출력하면 된다. //실수한 부분// '마지막 연주는 무조건 실수하지 않는다'를 분리해서 생각해 1. 실수를 한 횟수가 누적된 list 2. 지금 연주가 다음보다 더 어려운 인.. 2023. 3. 2.
[백준] 20438번 출석체크(python)(누적합) https://www.acmicpc.net/problem/20438 20438번: 출석체크 1번째 줄에 학생의 수 N, 졸고 있는 학생의 수 K, 지환이가 출석 코드를 보낼 학생의 수 Q, 주어질 구간의 수 M이 주어진다. (1 ≤ K, Q ≤ N ≤ 5,000, 1 ≤ M ≤ 50,000) 2번째 줄과 3번째 줄에 각각 K명 www.acmicpc.net 1. 난이도 실버2 (🥈) 2. 내가 작성한 풀이 구간합을 이용한 문제다! 나름 잘 풀었다고 생각했는데, 다른 분들이 푼 거랑 시간차이가 무려 4배가 나서 내 코드보단 수정 코드 참조하시길 추천ㅡ,,, n,k,q,m = map(int,input().split()) #n학생수 k졸고 있는 q출석코드 m구간수 dp = [0,0,0] + [0] * (n+1).. 2023. 3. 2.
[백준] 11659 구간 합 구하기 4(python)(누적합) https://www.acmicpc.net/problem/11659 11659번: 구간 합 구하기 4 첫째 줄에 수의 개수 N과 합을 구해야 하는 횟수 M이 주어진다. 둘째 줄에는 N개의 수가 주어진다. 수는 1,000보다 작거나 같은 자연수이다. 셋째 줄부터 M개의 줄에는 합을 구해야 하는 구간 i와 j www.acmicpc.net 1. 내가 작성한 코드 import sys input = sys.stdin.readline n,m = map(int, input().rstrip().split()) a = list(map(int, input().rstrip().split())) + [0] for i in range(n): a[i] += a[i-1] for i in range(m): left,right = m.. 2023. 3. 1.
[백준] 10986번 나머지 합(python)(누적합) https://www.acmicpc.net/problem/10986 10986번: 나머지 합 수 N개 A1, A2, ..., AN이 주어진다. 이때, 연속된 부분 구간의 합이 M으로 나누어 떨어지는 구간의 개수를 구하는 프로그램을 작성하시오. 즉, Ai + ... + Aj (i ≤ j) 의 합이 M으로 나누어 떨어지는 (i, j) www.acmicpc.net 1. 난이도 골드3 (🥇) 2. 문제 해결 방법 1. 누적 합 개념을 이용해야한다. 2. 누적합 % M == 0 인 경우 카운팅해준다. 3. (누적 합1 % M) 값과 (누적 합2 % M) 의 값이 같다는 것은 (누적합1 - 누적합2) % M이 0이라는 뜻과 같다. 예를 들어 10 % 3 => 1 13 % 3 =>1 (13 - 10) % 3 => 0.. 2023. 3. 1.

티스토리툴바