상상쓰

https://programmers.co.kr/learn/courses/30/lessons/86971 코딩테스트 연습 - 9주차 9 [[1,3],[2,3],[3,4],[4,5],[4,6],[4,7],[7,8],[7,9]] 3 7 [[1,2],[2,7],[3,7],[3,4],[4,5],[6,7]] 1 programmers.co.kr DFS 알고리즘으로 풀었고 리프 노드를 시작으로 하여 해당 노드의 전선 연결을 끊었을 때 남아 있는 송전탑의 개수(하위 노드의 개수 + 1)를 부모 노드의 result[] 에 더했다. (리프 노드는 result[] = 1) 만들어진 result[] 와 n - result[] 의 차이의 절대값과 result[0] 중 최솟값을 result[0] 으로 잡고 최종적으로 result[0..

https://www.acmicpc.net/problem/11053 11053번: 가장 긴 증가하는 부분 수열 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이 www.acmicpc.net dp[i] = i 를 마지막 원소로 가지는 증가하는 부분 수열의 길이 A[i] > A[j] (단, j = 0,1,2, ..., i-1) 일 경우 dp[j] + 1 중 가장 큰 값을 dp[i] 로 설정한다. dp 의 최댓값을 반환하면 된다. import sys N = int(sys.stdin.readline()) A = ..

https://www.acmicpc.net/problem/18185 18185번: 라면 사기 (Small) 라면매니아 교준이네 집 주변에는 N개의 라면 공장이 있다. 각 공장은 1번부터 N번까지 차례대로 번호가 부여되어 있다. 교준이는 i번 공장에서 정확하게 Ai개의 라면을 구매하고자 한다(1 ≤ i www.acmicpc.net i, i+1, i+2 공장에 라면이 있는 경우 7원으로 세 개의 라면을 사는 것이 가장 합리적이지만, [1, 2, 1, 1] 의 경우 7원으로 사는 것을 우선적으로 사버리면 [0, 1, 0, 1] 로 다음 번에 무조건 하나씩 사게 되어 최소한의 가격으로 사지 못하는 경우가 발생한다. [1, 2, 1, 1] 의 경우는 먼저 두 개의 공장에서 5원으로 라면을 산 뒤([0, 1, 1,..

https://programmers.co.kr/learn/courses/30/lessons/49190 코딩테스트 연습 - 방의 개수 [6, 6, 6, 4, 4, 4, 2, 2, 2, 0, 0, 0, 1, 6, 5, 5, 3, 6, 0] 3 programmers.co.kr 오일러 공식이 생각나서 활용하니 맞았다. v(꼭짓점의 개수) - e(변의 개수) + f(면의 개수) = 2 문제로 주어진 조건으로 봤을 때, 대각선으로 변이 교차하는 경우 오일러 공식의 전제 조건인 평면 그래프가 아닐 수 있으므로 1칸이 아니라 2칸으로 그래프를 늘려 1칸마다 꼭짓점으로 생각한다. set 을 이용하여 중복된 꼭짓점 또는 변을 무시하여 정확한 개수를 구한다. 변은 점과 점이 이어진 선으로 중복을 막기 위해서 값을 (x[0]..

https://www.acmicpc.net/problem/1092 1092번: 배 첫째 줄에 N이 주어진다. N은 50보다 작거나 같은 자연수이다. 둘째 줄에는 각 크레인의 무게 제한이 주어진다. 이 값은 1,000,000보다 작거나 같다. 셋째 줄에는 박스의 수 M이 주어진다. M은 10,000보 www.acmicpc.net 시간초과를 방지하기 위해서 크레인을 두 번째 이상 돌릴 때는 정렬된 박스들의 위치를 기억해서 무게 제한보다 무거운 박스인지는 비교하지 않도록 하였다. cranes = [9, 8, 6], boxes = [2, 2, 4, 5, 7] 이라고 가정했을 때, bisect_right 를 이용하여 positions = {9 : 5, 8 : 5, 6 : 4} 즉, 크레인 9번은 1 ~ 5번, 6..

https://programmers.co.kr/learn/courses/30/lessons/86491 코딩테스트 연습 - 8주차 [[10, 7], [12, 3], [8, 15], [14, 7], [5, 15]] 120 [[14, 4], [19, 6], [6, 16], [18, 7], [7, 11]] 133 programmers.co.kr 가로를 기준으로 하면 가로는 큰 것 중에서 가장 큰 것, 세로는 작은 것 중에서 가장 큰 것으로 크기를 설정하고 넓이를 구하면 된다. def solution(sizes): answer = 0 weight, length = 0, 0 for w, l in sizes: weight = max(weight, max(w, l)) length = max(length, min(w, ..

https://cafe.naver.com/codeuniv/44826 [추석맞이 코딩챌린지①] 피보나치수 첫 번째 문제에 도전하러 오신 모든 분들 환영합니다🙌 추석에도 코딩하는 열정맨...🥺 코뮤가 항상 응원합니다! 첫 번째 문제는 바로바로 "피보나치수"입니다~! 수학공... cafe.naver.com fn = dp[n] fn := { 0: if n = 0, 1: if n = 1, fn-1 + fn-2: if n >= 2 } import sys n = int(sys.stdin.readline()) dp = [0] * (n + 1) dp[1] = 1 for i in range(2, n+1): dp[i] = dp[i-1] + dp[i-2] print(dp[n])

https://programmers.co.kr/learn/courses/30/lessons/86053?language=python3 코딩테스트 연습 - 금과 은 운반하기 어느 왕국에 하나 이상의 도시들이 있습니다. 왕국의 왕은 새 도시를 짓기로 결정하였습니다. 해당 도시를 짓기 위해서는 도시를 짓는 장소에 금 a kg과 은 b kg이 전달되어야 합니다. 각 도시에는 programmers.co.kr 월간 코드 챌린지 시즌3 문제로 프로그래머스 Level 3에 올라와 있다. https://prgms.tistory.com/101 월간 코드 챌린지 시즌3 9월 해설 코딩이 재미있는 사람들을 위한 챌린지! 프로그래머스에서 2021년 9월 9일, 10월 7일 두 번에 걸쳐 월간 코드 챌린지 시즌3가 진행 중 입니다..

https://www.acmicpc.net/problem/1004 1004번: 어린 왕자 입력의 첫 줄에는 테스트 케이스의 개수 T가 주어진다. 그 다음 줄부터 각각의 테스트케이스에 대해 첫째 줄에 출발점 (x1, y1)과 도착점 (x2, y2)이 주어진다. 두 번째 줄에는 행성계의 개수 n이 주 www.acmicpc.net 하나의 원(행성계의 경계)이 있을 때, 출발점과 도착점이 원의 안 또는 바깥에 있는 경우 진입 또는 이탈이 필요가 없다. 즉, 출발점과 도착점 중 하나의 점이 원 안에 있는 경우만 answer 을 1씩 더해서 반환하면 된다. import sys T = int(sys.stdin.readline()) for i in range(T): x1, y1, x2, y2 = map(int, sys..

https://www.acmicpc.net/problem/1934 1934번: 최소공배수 두 자연수 A와 B에 대해서, A의 배수이면서 B의 배수인 자연수를 A와 B의 공배수라고 한다. 이런 공배수 중에서 가장 작은 수를 최소공배수라고 한다. 예를 들어, 6과 15의 공배수는 30, 60, 90등이 있 www.acmicpc.net 유클리드 호제법을 이용하여 최대공약수(gcd)를 구한 후, 최소공배수(lcd) = a * b // gcd 를 구한다. import sys def gcd(a, b): if a % b == 0: return b else: return gcd(b, a%b) T = int(sys.stdin.readline()) for i in range(T): a, b = map(int, sys.st..