상상쓰

https://www.acmicpc.net/problem/1300 1300번: K번째 수 세준이는 크기가 N×N인 배열 A를 만들었다. 배열에 들어있는 수 A[i][j] = i×j 이다. 이 수를 일차원 배열 B에 넣으면 B의 크기는 N×N이 된다. B를 오름차순 정렬했을 때, B[k]를 구해보자. 배열 A와 B www.acmicpc.net N = 5 로 예를 들면, N * N 배열은 아래와 같다. [1, 2, 3, 4, 5] [2, 4, 6, 8, 10] [3, 6, 9, 12, 15] [4, 8, 12, 16, 20] [5, 10, 15, 20, 25] 이분 탐색으로 나올 수 있는 수 중 최솟값인 1과 최댓값인 5*5(=25)를 시작으로 한 중간값(=mid)이 조건에 맞는지를 확인한다. 배열 안에 중..

https://www.acmicpc.net/problem/1003 1003번: 피보나치 함수 각 테스트 케이스마다 0이 출력되는 횟수와 1이 출력되는 횟수를 공백으로 구분해서 출력한다. www.acmicpc.net 불금! import sys T = int(sys.stdin.readline()) dp = [[1, 0], [0, 1]] for i in range(39): dp.append([dp[-2][0] + dp[-1][0], dp[-2][1] + dp[-1][1]]) for i in range(T): N = int(sys.stdin.readline()) print(dp[N][0], end = ' ') print(dp[N][1])

https://www.acmicpc.net/problem/16500 16500번: 문자열 판별 첫째 줄에 길이가 100이하인 문자열 S가 주어진다. 둘째 줄에는 A에 포함된 문자열의 개수 N(1 ≤ N ≤ 100)이 주어진다. 셋째 줄부터 N개의 줄에는 A에 포함된 단어가 한 줄에 하나씩 주어진다. A에 www.acmicpc.net A에 포함된 문자열을 한 개 이상 붙일 수 있으므로 dp[index] 가 1이면 이미 재귀함수로 A의 문자열로 S를 만들 수 있는지 확인하고 있으므로 무시해도 된다. DFS 알고리즘으로 S = 'softwarecontest' A = ['software', 'contest'] 라면 1) index = 0 (dp[0] = 1) : softwarecontest(= S[0:]) 와 ..

https://www.acmicpc.net/problem/23037 23037번: 5의 수난 키파는 문득 3과 4의 견고한 벽에 가로막혀 스포트라이트를 받지 못하는 5를 떠올렸다. '세상에 얼마나 많은 것들이 5와 관련이 있는데!' 키파는 5가 쓰이는 곳을 떠올리기 시작했다. 사람의 손가 www.acmicpc.net 오 신기방기 import sys n = sys.stdin.readline().strip() answer = sum(list(map(lambda x : int(x) ** 5, n))) print(answer)

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://www.acmicpc.net/problem/11052 11052번: 카드 구매하기 첫째 줄에 민규가 구매하려고 하는 카드의 개수 N이 주어진다. (1 ≤ N ≤ 1,000) 둘째 줄에는 Pi가 P1부터 PN까지 순서대로 주어진다. (1 ≤ Pi ≤ 10,000) www.acmicpc.net P[i] 를 i+1 장 뽑았을 때의 최댓값으로 값을 재설정한다. 예를 들어 카드가 5장 뽑았을 때의 최댓값은 카드를 1장 뽑았을 때의 최댓값 + 카드를 4장 뽑았을 때의 최댓값, 카드를 2장 뽑았을 때의 최댓값 + 카들르 3장 뽑았을 때의 최댓값, 카드를 5장 뽑았을 때의 값 중 최댓값이다. import sys N = int(sys.stdin.readline()) P = list(map(int, sys...