본문 바로가기

🔅코딩테스트 공부🔅213

[알고리즘] 최소 스패닝 트리 + 문제풀이 신장트리 모든 노드를 포함하면서 사이클이 존재하지 않는 부분 그래프 즉, 사이클 없이 모든 노드가 연결됨 (=트리) 최소 신장 트리 알고리즘 => 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.
[백준] 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.
[백준] 11055번 가장 큰 증가 부분 수열(python)(dp) https://www.acmicpc.net/problem/11055 1. 난이도 실버2 (🥈) 2. 문제 해결 방법 가장 긴 증가하는 부분 수열과 비슷한 문제다. 증가하고 있을 경우 max(본인이 가지고 있는 누적합, 그 전 원소의 누적합 + 본인의 값)를 출력하면 되고, 감소하고 있을 경우 max(본인이 가지고 있는 누적합, 본인의 값)을 출력하면 된다. 감소하고 있을 경우를 고려하지 않고 제출해서 2트만에 맞았다. 3. 내가 작성한 코드 n = int(input()) num = list(map(int, input().split())) dp = [0] * n dp[0] = num[0] for i in range(n): for j in range(i): if num[i] > num[j]: dp[i] = .. 2023. 3. 1.

티스토리툴바