ao

https://programmers.co.kr/learn/courses/30/lessons/43165 코딩테스트 연습 - 타겟 넘버 n개의 음이 아닌 정수들이 있습니다. 이 정수들을 순서를 바꾸지 않고 적절히 더하거나 빼서 타겟 넘버를 만들려고 합니다. 예를 들어 [1, 1, 1, 1, 1]로 숫자 3을 만들려면 다음 다섯 방법을 쓸 수 programmers.co.kr def solution(numbers, target): n = len(numbers) answer = 0 def dfs(idx, result): if idx == n: if result == target: nonlocal answer answer += 1 return else: dfs(idx+1, result+numbers[idx]) df..

문제에 앞서 Greedy(탐욕법)가 무엇인지 알아보겠습니다. 각 단계마다 지금 당장 가장 좋은 방법만을 선택하는 해결 방법입니다. 많은 경우 최적해를 찾지 못하고 적용될 수 있는 경우가 두 가지로 제한됩니다 탐욕법을 사용해도 항상 최적해를 구할 수 있는 경우 시간이나 공간적 제약으로 최적해 대신 근사해를 찾아서 해결하는 경우 접근 방법 문제의 답을 만드는 과정을 여러 조각으로 나눈다. 각 조각마다 어떤 우선순위로 선택을 내려야 할지 결정한다. 작은 입력을 손으로 풀어본다. 다음 두 속성이 적용되는지 확인해본다. 탐욕적 성택 속성 : 항상 각 단계에서 우리가 선택한 답을 포함하는 최적해가 존재하는가 최적 부분 구조 : 각 단계에서 항상 최적의 선택만을 했을 때, 전체 최적해를 구할 수 있는가 한 개의 회의..

지니레코드에서는 불세출의 가수 조영필의 라이브 동영상을 DVD로 만들어 판매하려 한다. DVD에는 총 N개의 곡이 들어가는데, DVD에 녹화할 때에는 라이브에서의 순서가 그대로 유지 되어야 한다. 순서가 바뀌는 것을 우리의 가수 조영필씨가 매우 싫어한다. 즉, 1번 노래와 5번 노래를 같은 DVD에 녹화하기 위해서는 1번과 5번 사이의 모든 노래도 같은 DVD에 녹화해야 한다. 또한 한 노래를 쪼개서 두 개의 DVD에 녹화하면 안된다. 지니레코드 입장에서는 이 DVD가 팔릴 것인지 확신할 수 없기 때문에 이 사업에 낭비되는 DVD를 가급적 줄이려고 한다. 고민 끝에 지니레코드는 M개의 DVD에 모든 동영상을 녹화하기 로 하였다. 이 때 DVD의 크기(녹화 가능한 길이)를 최소로 하려고 한다. 그리고 M개..

엘리트 학원은 자체적으로 K개의 랜선을 가지고 있다. 그러나 K개의 랜선은 길이가 제각각이 다. 선생님은 랜선을 모두 N개의 같은 길이의 랜선으로 만들고 싶었기 때문에 K개의 랜선을 잘라서 만들어야 한다. 예를 들어 300cm 짜리 랜선에서 140cm 짜리 랜선을 두 개 잘라내면 20cm 은 버려야 한다. (이미 자른 랜선은 붙일 수 없다.) 편의를 위해 랜선을 자를때 손실되는 길이는 없다고 가정하며, 기존의 K개의 랜선으로 N개의 랜선을 만들 수 없는 경우는 없다고 가정하자. 그리고 자를 때는 항상 센티미터 단위로 정수 길이만큼 자른다고 가정하자. N개보다 많이 만드는 것도 N개를 만드는 것에 포함된다. 이때 만들 수 있는 최대 랜선의 길이를 구하는 프로그램을 작성하시오. ▣ 입력설명 첫째 줄에는 엘리..

문제에 앞서 이분 탐색(Binary Search)이 무엇인지, 언제 사용하는 것인지에대해 알아보겠습니다. 이분 탐색이 가능한 주요 조건은 정렬되어 있어야 한다는 것입니다. 정렬되어 있는 배열에서 데이터를 찾으려고 시도할 때, 순차탐색처럼 처음부터 끝까지 하나씩 모든 데이터를 체크하면서 값을 찾는 것이 아니라 탐색 범위를 절반 씩 줄여가며 찾아가는 탐색법입니다. 아래 문제를 이분탐색법을 이용하여 풀어보겠습니다. 임의의 N개의 숫자가 입력으로 주어집니다. N개의 수를 오름차순으로 정렬한 다음 N개의 수 중 한 개의 수인 M이 주어지면 이분검색으로 M이 정렬된 상태에서 몇 번째에 있는지 구하는 프로그램을 작성하세요. 단 중복값은 존재하지 않습니다. ▣ 입력설명 첫 줄에 한 줄에 자연수 N(3

현수의 농장은 N*N 격자판으로 이루어져 있으며, 각 격자안에는 한 그루의 사과나무가 심어저 있다. N의 크기는 항상 홀수이다. 가을이 되어 사과를 수확해야 하는데 현수는 격자판안의 사 과를 수확할 때 다이아몬드 모양의 격자판만 수확하고 나머지 격자안의 사과는 새들을 위해서 남겨놓는다. 만약 N이 5이면 아래 그림과 같이 진한 부분의 사과를 수확한다. 10 13 10 12 15 12 39 30 23 11 11 25 50 53 15 19 27 29 37 27 19 13 30 13 19 현수과 수확하는 사과의 총 개수를 출력하세요. ▣ 입력설명 첫 줄에 자연수 N(홀수)이 주어진다.(3

격자판 최대합 5*5 격자판에 아래롸 같이 숫자가 적혀있습니다. 10 13 10 12 15 12 30 30 28 11 11 25 50 53 15 19 27 29 37 27 19 13 30 13 19 N*N의 격자판이 주어지면 각 행의 합, 각 열의 합, 두 대각선의 합 중 가 장 큰 합을 출력합 니다. ▣ 입력설명 첫 줄에 자연수 N이 주어진다.(1largest: largest=sum2 sum1=sum2=0 for i in range(n): sum1+=a[i][i] sum2+=a[i][n-i-1] if sum1>largest: largest=sum1 if sum2>largest: largest=sum2 print(largest) a에 list문 안에서 변수없이(_) for문을 돌려줍니다. 그 후, a를 ..

import sys sys.stdin=open("input.txt", "rt") a = list(range(21)) for _ in range(10): s, e=map(int, input().split()) for i in range((e-s+1)//2): a[s+i], a[e-i]=a[e-i], a[s+i] a.pop(0) for x in a: print(x, end=' ') 먼저 맨 위의 리스트와 같이 출력하기 위해 a라는 list를 만들어줍니다. range(21)로 하게되면 20 index까지 만들어지게 됩니다. 그리고 카드의 배치를 바꿀 첫 구간(s)과 끝(e) 구간을 정해준 뒤, 반복문을 실행합니다. 반복하고자 하는 구간에 대한 반복문을 만들어야 하는데, 끝과 첫구간을 뺀 값에서 1을 더한 뒤,..

문자와 숫자가 섞여있는 문자열이 주어지면 그 중 숫자만 추출하여 그 순서대로 자연수를 만 듭니다. 만들어진 자연수와 그 자연수의 약수 개수를 출력합니다. 만약 “t0e0a1c2h0er”에서 숫자만 추출하면 0, 0, 1, 2, 0이고 이것을 자연수를 만들면 120이 됩니다. 즉 첫 자리 0은 자연수화 할 때 무시합니다. 출력은 120를 출력하고, 다음 줄에 120 의 약수의 개수를 출력하면 됩니다. 추출하여 만들어지는 자연수는 100,000,000을 넘지 않습니다. ▣ 입력설명 첫 줄에 숫자가 썩인 문자열이 주어집니다. 문자열의 길이는 50을 넘지 않습니다. ▣ 출력설명 첫 줄에 자연수를 출력하고, 두 번째 줄에 약수의 개수를 출력합니다. ▣ 입력예제 1 g0en2Ts8eSoft ▣ 출력예제 1 28 6..

N개의 문자열 데이터를 입력받아 앞에서 읽을 때나 뒤에서 읽을 때나 같은 경우(회문 문자열) 이면 YES를 출력하고 회문 문자열이 아니면 NO를 출력하는 프로그램을 작성한다. 단 회문을 검사할 때 대소문자를 구분하지 않습니다. ▣ 입력설명 첫 줄에 정수 N(1