![]()
11055번: 가장 큰 증가 부분 수열 (acmicpc.net) 11055번: 가장 큰 증가 부분 수열 수열 A가 주어졌을 때, 그 수열의 증가 부분 수열 중에서 합이 가장 큰 것을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {1, 100, 2, 50, 60, 3, 5, 6, 7, 8} 인 경우에 합이 가장 큰 증가 부분 수 www.acmicpc.net 문제 해석 수열 A의 부분수열 중 제일 합이 큰 부분수열의 합을 구한다. 코드 문제 풀이 예제로 나온 "가장 긴 증가하는 부분 수열"과 비슷한 문제이다. n과 a에 input 값들을 넣어주고 누적합을 구하기 위한 list b를 선언해주었다. 그리고 b는 최소 자기자신을 더한 값이 나오므로 a의 값을 그대로 b로 옮겨주었다. n이 최대 1000..
![]()
코드 t = int(input()) for i in range(t): a = input() print('{0}{1}'.format(a[0],a[-1])) 문제풀이 문제풀이 자체에는 어려움이 없었지만 한가지 문제점이 있었다. 아래는 내가 처음 작성했던 코드이다. import sys input = sys.stdin.readline t = int(input()) for i in range(t): a = input() print('{0}{1}'.format(a[0],a[-2])) sys.stdin.readline을 이용한 입력에서는 \n까지 포함되어 입력되므로 인덱스에서 -1이 아닌 -2를 찾는 방식으로 맞춰주었다. 하지만 이 정답은 결과가 맞게 나왔음에도 오답처리되었고 결국 모듈을 빼고 작성한 코드(상단의 정..
![]()
https://www.acmicpc.net/problem/9012 9012번: 괄호 괄호 문자열(Parenthesis String, PS)은 두 개의 괄호 기호인 ‘(’ 와 ‘)’ 만으로 구성되어 있는 문자열이다. 그 중에서 괄호의 모양이 바르게 구성된 문자열을 올바른 괄호 문자열(Valid PS, VPS)이라고 www.acmicpc.net 문제 풀이 맨처음에는 각 짝을 찾는 탐색형식으로 문제를 풀려고 했는데, 그렇게 하면 너무 번거롭게 됨을 깨닫고 방법을 찾다가 간편한 방식을 찾았다. 바로 '()'를 찾아 이를 문자열에서 제거하는 것이다. 그렇게 계속해서 제거하다보면 결국 짝이 맞는 문자열만이 공백이 되고, 안맞는 문자열은 한쪽 괄호만이 남게 된다. C++로 풀어보려 했지만, 파이썬에 구현되어 있는 아..
![]()
https://www.acmicpc.net/problem/14910 14910번: 오르막 첫째 줄에 공백으로 구분된 N(1 ≤ N ≤ 1,000,000)개의 정수가 주어진다. 입력으로 주어지는 정수는 -1,000,000보다 크거나 같고, 1,000,000보다 작거나 같은 정수이다. www.acmicpc.net 소스 코드 문제 풀이 입력된 정수들의 나열과 그것을 copy()를 통해 복사한 후, sorted()로 인해 오름차순으로 정렬된 정수들의 나열을 비교하여 같으면 "Good" , 다르면 "Bad" 를 출력하게 하였다.
![]()
https://www.acmicpc.net/problem/16395 16395번: 파스칼의 삼각형 파스칼의 삼각형은 이항계수를 삼각형 형태로 배열한 것인데, 블레즈 파스칼(1623-1662)을 따라 이름 붙여졌다. 단순한 형태로, 파스칼의 삼각형은 다음과 같은 방법으로 만들 수 있다. N번째 행 www.acmicpc.net 문제분석 분류 수학, 다이나믹 프로그래밍, 조합론 문제설명 N번째 행에는 N개의 수가 있다. 첫 번째 행은 1이다. 두 번째 행부터 각 행의 양 끝의 값은 1이고, 나머지 수의 값은 바로 위 행의 인접한 두 수의 합이다. 정수 n과 k가 주어졌을 때, 파스칼의 삼각형에 있는 n번째 행에서 k번째 수를 출력한다. (1 ≤ k ≤ n ≤ 30) 코드 1 n, k = map(int, inp..
![]()
https://www.acmicpc.net/problem/7785 7785번: 회사에 있는 사람 첫째 줄에 로그에 기록된 출입 기록의 수 n이 주어진다. (2 ≤ n ≤ 106) 다음 n개의 줄에는 출입 기록이 순서대로 주어지며, 각 사람의 이름이 주어지고 "enter"나 "leave"가 주어진다. "enter"인 경우는 www.acmicpc.net 문제 설명 출입 카드 시스템에 들어온 사람과 나간 사람의 로그가 저장된다. 출입한 사람의 이름과 출입 여부가 주어질 때, 아직 나가지 않은 사람을 출력하면 되는 문제다. 코드 설명 우선, n으로 총 로그의 수를 입력받는다. n만큼 도는 for문 안에서, 2개의 요소로 이루어진 입력값을 리스트로 변환하여 입력받는다. 사람 이름을 key값으로, 회사 출입 여부를..
https://www.acmicpc.net/problem/3449 3449번: 해밍 거리 입력을 여러 개의 테스트 케이스로 이루어져 있다. 첫째 줄에는 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스는 두 줄로 이루어져 있다. 각 줄에는 이진수가 하나씩 주어진다. 두 이진 www.acmicpc.net 문제해석 두 이진수가 다를 때 거리를 1씩 증가시킨다. t = int(input()) for i in range(t): cnt = 0 a = input() b = input() for j in range(len(a)): if a[j] != b[j]: cnt += 1 print('Hamming distance is {}.'.format(cnt)) 문제풀이 반복문을 이용해 입력받은 t번의 횟수만큼 반복한..
![]()
https://www.acmicpc.net/problem/11726 11726번: 2×n 타일링 2×n 크기의 직사각형을 1×2, 2×1 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오. 아래 그림은 2×5 크기의 직사각형을 채운 한 가지 방법의 예이다. www.acmicpc.net 문제분석 코드 n = int(input()) a_1 = 1 a_2 = 1 for _ in range(2, n+1): temp = (a_1 + a_2) % 10007 a_1 = a_2 a_2 = temp print(a_2) 문제분석 1. n = 1일 때 1, 2일 때 1가지 방법으로 배치 가능하다. 2. n = 3일 때는 위의 n=1일때 가로길이 2짜리 블록을 배치하는 방법 + n=1일 때 가로 1짜리 블록을 배치하는 ..
https://www.acmicpc.net/problem/1895 1895번: 필터 숫자 9개가 오름차순이나 내림차순으로 정렬되어 있을 때, 중앙값은 다섯 번째 숫자이다. 예를 들어, 1, 3, 4, 1, 2, 6, 8, 4, 10의 중앙값은 4이다. (1 ≤ 1 ≤ 2 ≤ 3 ≤ 4 ≤ 4 ≤ 6 ≤ 8 ≤ 10) 이미지 I는 www.acmicpc.net 문제 분석 RxC 크기인 이미지 배열(=I)를 입력 받고, 3x3 배열의 필터를 씌여서 중앙값을 찾는 문제이다. 필 터를 씌어서 찾은 중앙값들을 정렬한 뒤, T 값 보다 큰 숫자들의 개수를 새는 문제이다. 코드 ㅋ 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29..
https://www.acmicpc.net/problem/17626 17626번: Four Squares 라그랑주는 1770년에 모든 자연수는 넷 혹은 그 이하의 제곱수의 합으로 표현할 수 있다고 증명하였다. 어떤 자연수는 복수의 방법으로 표현된다. 예를 들면, 26은 52과 12의 합이다; 또한 42 + 32 + 1 www.acmicpc.net 문제 분석 모든 자연수는 넷 혹은 그 이하의 제곱수의 합으로 표현할 수 있다고 증명하였다. 자연수 n이 주어질 때, n을 최소 개수의 제곱수 합으로 표현하는 문제이다. 조건. 입력은 자연수 n을 포함하는 한 줄로 구성된다. 1 ≤ n ≤ 50,000이다. 코드 다이나믹 프로그래밍 import math n = int(input()) dp = [0,1] for i ..
![]()
https://www.acmicpc.net/problem/1463 [문제해석] N을 입력하여 그 수가 위의 조건에 따라 1로 만드는 최소한의 횟수를 찾는 문제이다. [코드] n = int(input()) d = [0] * (n+1) for i in range(2, n+1) : d[i] = d[i-1] + 1 if i % 3 == 0 : d[i] = min(d[i], d[i//3]+1) if i % 2 == 0 : d[i] = min(d[i], d[i//2]+1) print(d[n]) [문제 풀이] n을 입력받는다. n+1 개수만큼의 0으로 된 리스트를 생성하고, 리스트 시작을 0번째가 아닌 첫번째로 시작하기 위해 n+1개로 설정한다. 입력된 값이 1이라면 어차피 계산횟수가 0이고, 그대로 출력하면 되..
문제 나코더 기장 재민이는 동아리 회식을 준비하기 위해서 장부를 관리하는 중이다. 재현이는 재민이를 도와서 돈을 관리하는 중인데, 애석하게도 항상 정신없는 재현이는 돈을 실수로 잘못 부르는 사고를 치기 일쑤였다. 재현이는 잘못된 수를 부를 때마다 0을 외쳐서, 가장 최근에 재민이가 쓴 수를 지우게 시킨다. 재민이는 이렇게 모든 수를 받아 적은 후 그 수의 합을 알고 싶어 한다. 재민이를 도와주자! 입력 첫 번째 줄에 정수 K가 주어진다. (1 ≤ K ≤ 100,000) 이후 K개의 줄에 정수가 1개씩 주어진다. 정수는 0에서 1,000,000 사이의 값을 가지며, 정수가 "0" 일 경우에는 가장 최근에 쓴 수를 지우고, 아닐 경우 해당 수를 쓴다. 정수가 "0"일 경우에 지울 수 있는 수가 있음을 보장할..
