https://www.acmicpc.net/problem/1654 1654번: 랜선 자르기 첫째 줄에는 오영식이 이미 가지고 있는 랜선의 개수 K, 그리고 필요한 랜선의 개수 N이 입력된다. K는 1이상 10,000이하의 정수이고, N은 1이상 1,000,000이하의 정수이다. 그리고 항상 K ≦ N 이다. 그 www.acmicpc.net 문제요약 K개의 랜선의 길이가 주어진다. 이를 가지고 같은크기로 잘라서 N개의 작은 랜선을 만든다. 이때 만들 수 있는 최대의 길이를 출력한다. 문제 해결 유의해야할 점 랜선의 길이가 2^32-1까지 가능하다. int는 4byte이므로 양수는 2^16-1까지 가능하므로 더 큰 자료형을 써야했다. unsigned int를 사용했다. 1~(입력받은 랜선중 최대길이) 중에 ..
분류 전체보기
문제 n진수는 base가 n인 수를 말한다. 예를 들어 십진수는 base가 10인 수이다. n진수의 수 AmAm-1Am-2…A1A0를 n진수로 표현해보면 AmAm-1Am-2…A1A0 = Am × nm + Am-1 × nm–1 + Am-2 × nm–2 + … + A1 × n1 + A0 × n0이다. 예를 들면, 12468은 12468 = 1 × 104 + 2 × 103 + 4 × 102 + 6 × 101 + 8 × 100로 표현할 수 있다. 회문(Palindrome)이란 앞으로 읽으나 뒤로 읽으나 같은 글을 말한다. 예를 들면, madam, level, 12321은 회문이다. 반면에, Chung-ang이나 university, 54899는 회문이 아니다. 어떤 십진수의 수 A가 주어졌을 때, 이를 n진수로..
문제 왕비를 피해 일곱 난쟁이들과 함께 평화롭게 생활하고 있던 백설공주에게 위기가 찾아왔다. 일과를 마치고 돌아온 난쟁이가 일곱 명이 아닌 아홉 명이었던 것이다. 아홉 명의 난쟁이는 모두 자신이 "백설 공주와 일곱 난쟁이"의 주인공이라고 주장했다. 뛰어난 수학적 직관력을 가지고 있던 백설공주는, 다행스럽게도 일곱 난쟁이의 키의 합이 100이 됨을 기억해 냈다. 아홉 난쟁이의 키가 주어졌을 때, 백설공주를 도와 일곱 난쟁이를 찾는 프로그램을 작성하시오. 입력 아홉 개의 줄에 걸쳐 난쟁이들의 키가 주어진다. 주어지는 키는 100을 넘지 않는 자연수이며, 아홉 난쟁이의 키는 모두 다르며, 가능한 정답이 여러 가지인 경우에는 아무거나 출력한다. 출력 일곱 난쟁이의 키를 오름차순으로 출력한다. 일곱 난쟁이를 찾을..
https://www.acmicpc.net/problem/15565 15565번: 귀여운 라이언 꿀귀 라이언 인형과, 마찬가지로 꿀귀인 어피치 인형이 N개 일렬로 놓여 있다. 라이언 인형은 1, 어피치 인형은 2로 표현하자. 라이언 인형이 K개 이상 있는 가장 작은 연속된 인형들의 집합의 www.acmicpc.net 코드 #include #include #include #include #include #include #include #include #include #include #include #define LL long long using namespace std; int main() { vector arr; int n; int k; cin >> n >> k; int num; for (int i = ..
문제 https://www.acmicpc.net/problem/17390 17390번: 이건 꼭 풀어야 해! [2, 5, 1, 2, 3]을 비내림차순으로 정렬하면 [1, 2, 2, 3, 5]이다. www.acmicpc.net Algorithm 수열을 비내림차순으로 정렬 후에 문제에서 주어지는 구간의 합을 출력하면 되는 문제이다. 구간의 합을 출력하면 되므로 누적합을 사용하였고, 비내림차순으로 정렬하기위해 .sort()함수를 사용하였다. 누적합을 사용할 수 있으면 쉽게 풀리는 문제였던것 같다. Code input = __import__('sys').stdin.readline n,q = map(int,input().split()) arr = list(map(int,input().split())) arr.so..
1806번: 부분합 (acmicpc.net) 1806번: 부분합 첫째 줄에 N (10 ≤ N < 100,000)과 S (0 < S ≤ 100,000,000)가 주어진다. 둘째 줄에는 수열이 주어진다. 수열의 각 원소는 공백으로 구분되어져 있으며, 10,000이하의 자연수이다. www.acmicpc.net 문제유형 *누적 합 문제 10,000 이하의 자연수로 이루어진 길이 N짜리 수열이 주어진다. 이 수열에서 연속된 수들의 부분합 중에 그 합이 S 이상이 되는 것 중, 가장 짧은 것의 길이를 구하는 프로그램을 작성하시오. 입출력 예제 (입력 1) 10 15 5 1 3 5 10 7 4 9 2 8 (출력 1) 2 풀이 1. N짜리 수열을 저장하는 arr배열과, 누적합을 저장하는 total배열을 만들어 준다. ..
문제 https://www.acmicpc.net/problem/13900 풀이 해당 문제는 누적합을 활용해서 풀 수 있다. 모든 경우의 수는 조합으로, nC2이다. 따라서, 시간이 부족하다. 단순 곱을 더하기만 하면 되는 경우이기에 분배 법칙과 누적 합을 활용하면 된다. 예를 들어, [1,2,3,4]인 경우 1*(2+3+4) + 2*(3+4) + 3*(4) 로 계산할 수 있는 것이다. 따라서, 괄호 안의 합은 누적합을 활용하면 된다. 아래 코드는 앞에서부터 계산한 누적합을 활용하기 위해, 분배법칙을 뒤에서부터 시행했다. 코드 N = int(input()) nums = list(map(int, input().split())) dp = [0]*(N+1) for i in range(N-1): dp[i+1] =..
문제 KOI 부설 과학연구소에서는 많은 종류의 산성 용액과 알칼리성 용액을 보유하고 있다. 각 용액에는 그 용액의 특성을 나타내는 하나의 정수가 주어져있다. 산성 용액의 특성값은 1부터 1,000,000,000까지의 양의 정수로 나타내고, 알칼리성 용액의 특성값은 -1부터 -1,000,000,000까지의 음의 정수로 나타낸다. 같은 양의 두 용액을 혼합한 용액의 특성값은 혼합에 사용된 각 용액의 특성값의 합으로 정의한다. 이 연구소에서는 같은 양의 두 용액을 혼합하여 특성값이 0에 가장 가까운 용액을 만들려고 한다. 예를 들어, 주어진 용액들의 특성값이 [-2, 4, -99, -1, 98]인 경우에는 특성값이 -99인 용액과 특성값이 98인 용액을 혼합하면 특성값이 -1인 용액을 만들 수 있고, 이 용액..
문제 설명 회의실 배정에서 좀 더 어려워진 유형의 욕심쟁이 기법 문제이다. 출력으로 모든 강의를 진행하는데 필요한 강의실의 개수와, 각 강의에 배정되는 강의실 번호를 출력하면 된다. 우선 모든 강의를 시작하는 시간 순서대로 오름차순으로 정렬한다. 그리고 강의가 끝나는 시간을 기준으로 최소 힙을 만들어 강의를 하나씩 집어 넣는데 아래 규칙을 따른다. 1. 최소 힙 루트 원소의 끝나는 시간이 현재 넣어야 하는 강의의 시작 시간보다 작거나 같다면 루트를 제거하고 현재 강의를 넣는다. (진행 중인 강의가 끝나고 같은 강의실에서 진행할 수 있음) 2. 최소 힙 루트 원소의 끝나는 시간이 현재 넣어야 하는 강의의 시작 시간보다 크다면 그냥 넣는다. (강의가 끝나지 않아 새로운 강의실을 만들어야 한다.) 모든 강의를..
[문제] https://www.acmicpc.net/problem/2789 2789번: 유학 금지 아주 멀리 떨어져 있는 작은 나라가 있다. 이 나라에서 가장 공부를 잘하는 학생들은 모두 다른 나라로 유학을 간다. 정부는 최고의 학생들이 자꾸 유학을 가는 이유를 찾으려고 했다. 하지만, www.acmicpc.net [소스코드] word = input().strip() censor_word = "CAMBRIDGE" result = ''.join(char for char in word if char not in censor_word) print(result) [문제풀이] 1. 대문자로 단어를 입력받는다. 2. 검열할 단어로 "CAMBRIDGE"를 사용한다. 3. "CAMBRIDGE"에 포함된 알파벳을 제외한..
https://school.programmers.co.kr/learn/courses/30/lessons/43238 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 알고리즘 분류 이진 탐색(이분 탐색) 문제 n명이 입국심사를 위해 줄을 서서 기다리고 있습니다. 각 입국심사대에 있는 심사관마다 심사하는데 걸리는 시간은 다릅니다. 처음에 모든 심사대는 비어있습니다. 한 심사대에서는 동시에 한 명만 심사를 할 수 있습니다. 가장 앞에 서 있는 사람은 비어 있는 심사대로 가서 심사를 받을 수 있습니다. 하지만 더 빨리 끝나는 심사대가 있으면 기다렸다가 그곳으로 가서..
