본문 바로가기

🔅코딩테스트 공부🔅/❗백준138

[백준] 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.
[백준] 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.
[백준] 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.
[백준] 2670번 연속부분최대곱(python)(dp) https://www.acmicpc.net/problem/2670 2670번: 연속부분최대곱 첫째 줄은 나열된 양의 실수들의 개수 N이 주어지고, 그 다음 줄부터 N개의 수가 한 줄에 하나씩 들어 있다. N은 10,000 이하의 자연수이다. 실수는 소수점 첫째자리까지 주어지며, 0.0보다 크거나 www.acmicpc.net 1. 난이도 실버4 (🥈) 2. 문제 해결 방법 DP를 이용해서 문제를 해결했다. (현재의 값)과 (전까지의 최대곱 * 현재의 값) 중 더 큰 값을 dp에 넣으면 된다. round(num, 3) => 소수점 셋째자리까지 출력이지만 1.0 이었을 경우 1.0 으로 출력되어 오답처리된다. 따라서 ('%.3f' %max(dp))로 해야한다. 3. 내가 작성한 코드 n = int(input(.. 2023. 3. 1.
[백준] 2407번 조합(python)(dp) https://www.acmicpc.net/problem/2407 2407번: 조합 n과 m이 주어진다. (5 ≤ n ≤ 100, 5 ≤ m ≤ 100, m ≤ n) www.acmicpc.net 1. 난이도 실버3 (🥈) 2. 내가 작성한 코드 dp 공부중이라 dp로 해결하고 싶었는데, 파스칼의 삼각형 공식을 제대로 몰라서 지저분하게 풀었다. 머쓱,, n,m = map(int, input().split()) dp = [0] * (n+1) dp[1] = 1 dp[n] = n for i in range(2,m+1): if n-i m인 경우 dp[i] = dp[n-i] #nCn-m값 넣어줌 else: #nCm 직접 계산해줌 r = n d = i for j in range(1,i): r.. 2023. 3. 1.

티스토리툴바