취준생의 코딩테스트 연습기

# 문제 링크 https://www.acmicpc.net/problem/1932 1932번: 정수 삼각형 첫째 줄에 삼각형의 크기 n(1 ≤ n ≤ 500)이 주어지고, 둘째 줄부터 n+1번째 줄까지 정수 삼각형이 주어진다. www.acmicpc.net # Soultion 자신 위의 두 숫자중 큰 숫자를 더해주는 방식으로 문제해결 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 n = int(input()) li = [] for _ in range(n): li.append(list(map(int,input().split()))) for i in range(1,n): for j in range(len(li[i])): if j==0: li[i][j] += li[i-1][0] elif j==l..

# 문제 링크 https://www.acmicpc.net/problem/1912 1912번: 연속합 첫째 줄에 정수 n(1 ≤ n ≤ 100,000)이 주어지고 둘째 줄에는 n개의 정수로 이루어진 수열이 주어진다. 수는 -1,000보다 크거나 같고, 1,000보다 작거나 같은 정수이다. www.acmicpc.net # Soultion i번째에서 최대값은 max(i-1까지의 누적값+i값, i값) 1 2 3 4 5 6 7 8 n = int(input()) li = list(map(int,input().split())) s = [li[0]] for i in range(1,len(li)): s.append(max(s[i-1]+li[i], li[i])) print(max(s)) cs 4. 누적값을 저장하기위한 리..

# 문제 링크 https://www.acmicpc.net/problem/1699 1699번: 제곱수의 합 어떤 자연수 N은 그보다 작거나 같은 제곱수들의 합으로 나타낼 수 있다. 예를 들어 11=32+12+12(3개 항)이다. 이런 표현방법은 여러 가지가 될 수 있는데, 11의 경우 11=22+22+12+12+12(5개 항)도 가능하다 www.acmicpc.net # Soultion 처음에는 단순히 제곱근이 큰거부터 한개씩 제거했더니 문제가 발생하였다.12같은 경우는 9+1+1+1이므로 4개가 되는데, 실제로 최소값은 4+4+4이므로 모든 경우의 수를 확인해야하는 문제이다. 1 2 3 4 5 6 7 8 9 10 11 12 n = int(input()) dp = [i for i in range(n+1)] ..

# 문제 링크 https://www.acmicpc.net/problem/11724 11724번: 연결 요소의 개수 첫째 줄에 정점의 개수 N과 간선의 개수 M이 주어진다. (1 ≤ N ≤ 1,000, 0 ≤ M ≤ N×(N-1)/2) 둘째 줄부터 M개의 줄에 간선의 양 끝점 u와 v가 주어진다. (1 ≤ u, v ≤ N, u ≠ v) 같은 간선은 한 번만 주 www.acmicpc.net # Soultion 처음에 dfs를 이용하여 문제를 풀었더니 recursion 에러가 발생하여 재귀깊이를 설정해주었다. 그래도 동일하게 문제가 발생하여 bfs로 풀었더니 동일한 에러가 발생하였다. 알고보니 input()을 받는과정에서 시간초과가 발생하였다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 ..

# 문제 링크 https://www.acmicpc.net/problem/1654 1654번: 랜선 자르기 첫째 줄에는 오영식이 이미 가지고 있는 랜선의 개수 K, 그리고 필요한 랜선의 개수 N이 입력된다. K는 1이상 10,000이하의 정수이고, N은 1이상 1,000,000이하의 정수이다. 그리고 항상 K ≦ N 이다. 그 www.acmicpc.net # Soultion 이진탐색을 이용하여 문제해결 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 k,n= map(int, input().split()) line = [] for _ in range(k): line.append(int(input())) start = 1 end = max(line) while(start=n: #자른..

# 문제 링크 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 # Soultion 1 2 3 4 5 6 7 8 9 10 11 n = int(input()) arr = list(map(int,input().split())) length = [1]*n for i in range(1,n): for j in range(i-1,-1,-1): if arr[j]

# 문제 링크 https://www.acmicpc.net/problem/1463 1463번: 1로 만들기 첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다. www.acmicpc.net # Soultion 1 2 3 4 5 6 7 8 9 10 11 12 13 14 n = int(input()) count = [n+1]*(n+1) count[1]=0 for i in range(2,n+1): tmp = [count[i-1]] if i%2==0: tmp.append(count[i//2]) if i%3==0: tmp.append(count[i//3]) count[i] = min(tmp)+1 print(count[n]) cs 3. 최소계산수를 저장하기 위해 n+1개의 배열을 선언 4. 숫..

# 문제 링크 https://www.acmicpc.net/problem/1149 1149번: RGB거리 첫째 줄에 집의 수 N(2 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 각 집을 빨강, 초록, 파랑으로 칠하는 비용이 1번 집부터 한 줄에 하나씩 주어진다. 집을 칠하는 비용은 1,000보다 작거나 www.acmicpc.net # Soultion 점화식을 찾아 DP방법으로 해결함 현재위치(빨) = 이전위치(파)+이전위치(초) 이런 식으로 진행된다. 1 2 3 4 5 6 7 8 9 10 11 n = int(input()) li = [] for _ in range(n): li.append(list(map(int,input().split()))) for i in range(1,n): li[..

# 문제 링크 https://www.acmicpc.net/problem/10816 10816번: 숫자 카드 2 첫째 줄에 상근이가 가지고 있는 숫자 카드의 개수 N(1 ≤ N ≤ 500,000)이 주어진다. 둘째 줄에는 숫자 카드에 적혀있는 정수가 주어진다. 숫자 카드에 적혀있는 수는 -10,000,000보다 크거나 같고, 10, www.acmicpc.net # Soultion 간단하게 bisect함수를 이용하여 문제를 풀었다. 1 2 3 4 5 6 7 8 9 from bisect import bisect_right, bisect_left n = int(input()) li_n = sorted(list(map(int,input().split()))) m = int(input()) li_m = list(m..

# 문제 링크 https://www.acmicpc.net/problem/1920 1920번: 수 찾기 첫째 줄에 자연수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 줄에는 N개의 정수 A[1], A[2], …, A[N]이 주어진다. 다음 줄에는 M(1 ≤ M ≤ 100,000)이 주어진다. 다음 줄에는 M개의 수들이 주어지는데, 이 수들 www.acmicpc.net # Soultion 처음에 단순하게 in을 사용하여 문제를 풀었더니 시간초과가 발생했다. 따라서 이진탐색을 이용하여 문제 해결. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 # 시간초과 -> 이진탐색 n = int(input()) li_n = sorted(list(map(int,inp..