알고리즘 헤더파일에는 배열의 정렬을 쉽게 처리해주기 위한 sort가 내장되어 있습니다. 오름차순 정렬, 내림차순 정렬과 Pair가 있을 때 내맘대로 정렬하는 법을 살펴보겠습니다. 1. 오름차순 정렬 정렬할 배열과 범위를 정해주면, 기본적으로 오름차순으로 정렬해줍니다. c++의 sort함수는 quick sort로 구현되어 있습니다. sort(a, a + 10, less()); 오름차순이 기본이므로, 세번째 인자를 제외해도 오름차순 정렬이 됩니다. sort(a, a + 10); #include #include #include #include using namespace std; int main() { int a[10] = { 1,5,4,6,7,10,9,2,3,8 }; sort(a, a + 10);..
분류 전체보기
youtu.be/neR0Dmct6E8 youtu.be/D9Vf4L-a76k
문제 링크 codeforces.com/contest/1473 Dashboard - Educational Codeforces Round 102 (Rated for Div. 2) - Codeforces codeforces.com A. Replacing Elements 문제 양의 정수로 이루어진 수열 a가 주어질 때, 다음과 같은 작업을 할 수 있다. 서로 다른 인덱스 i, j, k를 고른 후, ai = aj + ak 로 바꿀 수 있다. 이 작업을 무한정 할 수 있다고 할 때, 수열 a의 모든 수를 d보다 작거나 같게 만들 수 있는가? 풀이 1 더보기 이 문제의 경우 두 가지 case일 때, 문제 조건을 만족시킬 수 있습니다. 1. 모든 수가 d보다 작거나 같을 때, 작업을 하지 않고 그대로 정답이 됩니다. ..
www.acmicpc.net/problem/2992 2992번: 크면서 작은 수 정수 X가 주어졌을 때, X와 구성이 같으면서 X보다 큰 수 중 가장 작은 수를 출력한다. 수의 구성이 같다는 말은, 수를 이루고 있는 각 자리수가 같다는 뜻이다. 예를 들어, 123과 321은 수의 구성이 www.acmicpc.net 두가지 풀이를 가지고 왔습니다. 1. 첫번째는 풀이는 강의에서 소개해주신 next_permutation 함수를 이용하는 방식입니다. 코드가 매우 직관적이고 간결합니다. string변수로 입력을 받고난뒤 next_permutation 함수를 1번 실행시키면 문제에서 요구하는 "크면서 작은 수"를 얻을 수 있습니다. if 조건문 내부에서 next_permutation 함수를 실행시킴으로서 정답이 ..
https://www.acmicpc.net/problem/1182 1182번: 부분수열의 합 첫째 줄에 정수의 개수를 나타내는 N과 정수 S가 주어진다. (1 ≤ N ≤ 20, |S| ≤ 1,000,000) 둘째 줄에 N개의 정수가 빈 칸을 사이에 두고 주어진다. 주어지는 정수의 절댓값은 100,000을 넘지 않는다. www.acmicpc.net 주어진 N개의 숫자 중 부분수열의 합이 S를 만족시키는 수열의 개수를 찾는 문제이다. 백트래킹을 이용해 모든 경우의 수의 수열을 뽑아낸뒤 그 수열의 합이 S를 만족시킨다면 카운트를 하는 방식으로 접근하였다. #define _CRT_SECURE_NO_WARNINGS #include #include #include #include #include #include #..
www.acmicpc.net/problem/1969 1969번: DNA DNA란 어떤 유전물질을 구성하는 분자이다. 이 DNA는 서로 다른 4가지의 뉴클레오티드로 이루어져 있다(Adenine, Thymine, Guanine, Cytosine). 우리는 어떤 DNA의 물질을 표현할 때, 이 DNA를 이루는 뉴클레오 www.acmicpc.net 이 문제는 주어진 DNA들에대해 Hamming Distance의 합이 가장 작은 DNA하나를 찾고, 그, Hamming Distance의 합을 구하는 문제입니다. *Hamming Distance : 두 DNA가 있을 때 각 위치의 뉴클오티드 문자가 다른 것의 개수 입력받은 DNA들과의 Hamming Distance 합이 최소가 되기 위해서는 각 열 별로 빈도가 가장 ..
www.acmicpc.net/problem/1969 1969번: DNA DNA란 어떤 유전물질을 구성하는 분자이다. 이 DNA는 서로 다른 4가지의 뉴클레오티드로 이루어져 있다(Adenine, Thymine, Guanine, Cytosine). 우리는 어떤 DNA의 물질을 표현할 때, 이 DNA를 이루는 뉴클레오 www.acmicpc.net 더보기 #include #include #include using namespace std; int N, M; vector DNA; int main() { cin >> N >> M; char dna; vector result; char AGCT[4] = { 'A', 'C', 'G', 'T' }; for (int i = 0; i < N; i++) { for (int j..
www.acmicpc.net/problem/1969 1969번: DNA DNA란 어떤 유전물질을 구성하는 분자이다. 이 DNA는 서로 다른 4가지의 뉴클레오티드로 이루어져 있다(Adenine, Thymine, Guanine, Cytosine). 우리는 어떤 DNA의 물질을 표현할 때, 이 DNA를 이루는 뉴클레오 www.acmicpc.net 풀이 더보기 문제의 예제 2로 살펴보겠습니다. [입력] 4 10 ACGTACGTAC CCGTACGTAG GCGTACGTAT TCGTACGTAA 주어진 입력을 배열로 저장한 후 각 행의 같은 열에 있는 문자의 개수를 비교하고 개수를 저장합니다. 1열: A C G T -> A: 1개 / C: 1개 / G: 1개 / T: 1개 2열: C C C C -> A: 0개 / C:..
문제 N부터 M까지의 수들을 종이에 적었을 때 종이에 적힌 0들을 세는 프로그램을 작성하라. 예를 들어, N, M이 각각 0, 10일 때 0을 세면 0에 하나, 10에 하나가 있으므로 답은 2이다. 풀이 더보기 N,M 을 입력받아 N 부터 M까지 하나하나씩 0의 개수를 센다 . cnt =0 find_zero 함수를 만들어 num을 10으로 나눈 나머지가 0이면 0의 개수를 하나 추가한다. num 을 10으로 나누는 과정을 반복하여 위와 같은 방식으로 십의 자리, 백의자리 ... 를 확인한다. 코드 더보기 # include int find_zero(int num, int* cnt); int main() { int T, N, M; scanf("%d", &T); for (int i = 0; i < T; i++..
문제 우리는 사람의 덩치를 키와 몸무게, 이 두 개의 값으로 표현하여 그 등수를 매겨보려고 한다. 어떤 사람의 몸무게가 x kg이고 키가 y cm라면 이 사람의 덩치는 (x, y)로 표시된다. 두 사람 A 와 B의 덩치가 각각 (x, y), (p, q)라고 할 때 x > p 그리고 y > q 이라면 우리는 A의 덩치가 B의 덩치보다 "더 크다"고 말한다. 예를 들어 어떤 A, B 두 사람의 덩치가 각각 (56, 177), (45, 165) 라고 한다면 A의 덩치가 B보다 큰 셈이 된다. 그런데 서로 다른 덩치끼리 크기를 정할 수 없는 경우도 있다. 예를 들어 두 사람 C와 D의 덩치가 각각 (45, 181), (55, 173)이라면 몸무게는 D가 C보다 더 무겁고, 키는 C가 더 크므로, "덩치"로만 볼..
www.acmicpc.net/problem/14620 14620번: 꽃길 2017년 4월 5일 식목일을 맞이한 진아는 나무를 심는 대신 하이테크관 앞 화단에 꽃을 심어 등교할 때 마다 꽃길을 걷고 싶었다. 진아가 가진 꽃의 씨앗은 꽃을 심고나면 정확히 1년후에 꽃이 피므 www.acmicpc.net 이 문제는 가능한 씨앗의 배치를 모두 검색한 뒤, 씨앗을 중심으로 4방향이 화단에 들어오면서, 겹치지 않는 경우에 따라 세 개의 꽃을 배치하고 해당 위치의 가격을 모두 더한 값 중 최소값을 찾는 문제입니다. 이 문제를 나눠보면 첫 번째로 씨앗을 배치하는 것, 두 번째로 씨앗이 꽃이 피었을 때 겹치지 않는지 판단하는 것, 겹치지 않는 경우에서 화단의 최소값을 찾는 것으로 나눌 수 있습니다. 가장 먼저 씨앗을 배..
문제링크 atcoder.jp/contests/abc188 AtCoder Beginner Contest 188 - AtCoder AtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online. atcoder.jp A - Three-Point shot 문제 : 농구 양팀의 점수가 주어지고(x,y x!=y), 지고있는 팀이 3점슛을 성공해 역전할 수 있는지 파악하는 문제 풀이 더보기 작은수에서 +3한수가 큰수보다 크면 되는 간단한 문제 코드 더보기 #define _USE_MATH_DEFINES #include using namespace std; using ll..
