알고리즘

코딩테스트 공부하는 절차에서 보통 기본적인 구현 문제들을 풀이한 뒤에 그리디 알고리즘 문제부터 풀이해본다고 한다.  그리디 알고리즘이란 뭘까..?  지금부터 그리디 알고리즘에 대해 알아보려고 한다.   👽 그리디 알고리즘 그리디 알고리즘 (탐욕법)은 현재 상황에서 지금 당장 좋은 것만 고르는 방법을 의미한다. 그리디 알고리즘을 이용하면 빠르게 최적해로 가는 근사치를 구할 수 있다. 일반적인 상황에서 그리디 알고리즘은 최적의 해를 보장할 수 없을 때도 많다. 하지만, 코딩테스트에서의 대부분의 그리디 문제는 탐욕법으로 얻은 해가 최적의 해가 되는 상황에서, 이를 추론할 수 있어야 풀리도록 출제 된다.    👽 그리디 알고리즘 문제 #1 거스름 돈 : 문제 설명 당신은 음식점의 계산을 도와주는 점원입니다...

큰 수의 법칙 입력 조건 첫째 줄에 N(2 ≤ N ≤ 1,000), M(1 ≤ M ≤ 10,000), K(1 ≤ K ≤ 10,000)의 자연수가 주어지며, 각 자연수는 공백으로 구분된다. 둘째 줄에 N개의 자연수가 주어진다. 각 자연수는 공백으로 구분된다. 단, 각각의 자연수는 1 이상 10,000 이하의 수로 주어진다. 입력으로 주어지는 K는 항상 M보다 작거나 같다. 출력 조건 첫째 줄에 동빈이의 큰 수의 법칙에 따라 더해진 답을 출력한다. 입력 예시 5 8 3 2 4 5 4 6 출력 예시 46 코드 (단순하게 푸는 답안 예시) n,m,k = map(int,input().split()) data = list(map(int, input().split())) data.sort() first = data[..

힙 정렬 힙 트리 구조 (Heap Tree Structure)를 이용하는 정렬 방법이다. 힙이 무엇인지 알기 전에 이진 트리(Binary Tree)에 대해 알고 있을 필요가 있다. 이진 트리란 컴퓨터 안에서 데이터를 표현할 때 데이터를 각 노드(node)에 담은 뒤에 노드를 두개 씩 이어 붙이는 구조를 말한다. 이 때 트리 구조에 맞게 부모 노드에서 자식 노드로 가지가 뻗힌다. 이진 트리는 모든 노드의 자식 노드가 2개 이하인 구조이다. 위와 같은 구조를 이진트리라 한다. 여기서 트리(Tree)라는 것은 말 그대로 가지를 뻗어나가는 것처럼 데이터가 서로 연결되어있다는 것이다. 완전이진트리(Complete Binarat Tree) 에 대해서도 알아보자. 완전 이진트리는 데이터가 루트(Root) 노드 부터 ..

문제 2022 연세대학교 미래캠퍼스 슬기로운 코딩생활에 N명의 학생들이 응시했다. 이들 중 점수가 가장 높은 k명은 상을 받을 것이다. 이 때, 상을 받는 커트라인이 몇 점인지 구하라. 커트라인이란 상을 받는 사람들 중 점수가 가장 가장 낮은 사람의 점수를 말한다. 입력 첫째 줄에는 응시자의 수 N과 상을 받는 사람의 수 k가 공백을 사이에 두고 주어진다. 둘째 줄에는 각 학생의 점수 x가 공백을 사이에 두고 주어진다. 출력 상을 받는 커트라인을 출력하라. 제한 1 ≤ N ≤1000 1 ≤ k ≤ N 0 ≤ x ≤ 10000 예제 입력 1 5 2 100 76 85 93 98 예제 출력 1 98 시험 응시자들 가운데 1등은 100점, 2등은 98점, 3등은 93점이다. 2등까지 상을..

지난 시간에는 클래스(Class)를 정의해서 여러 개의 변수가 존재하는 상황에서 '특정한 변수'를 기준으로 정렬하는 방법에 대해 알아봤다. 다만 클래스를 정의하는 방식은 프로그래밍 속도 측면에서 별로 유리하지 않다. 실제 프로그래밍 대회에서 문제 하나를 풀기 위해 클래스를 정의하고 있는 것은 적절치 못하다. 따라서, 일반적으로 프로그래밍 대회와 같이 빠른 개발이 필요할 때는 페어(Pair)라이브러리를 사용하는 것이 효율적이다. #include #include #include using namespace std; int main (void) { vectorv; v.push_back(pair(90, "민지")); v.push_back(pair(85, "해린")); v.push_back(pair(82, "다니..

문제 어떤 수들이 있을 때, 그 수들을 대표하는 값으로 가장 흔하게 쓰이는 것은 평균이다. 평균은 주어진 모든 수의 합을 수의 개수로 나눈 것이다. 예를 들어 10, 40, 30, 60, 30의 평균은 (10 + 40 + 30 + 60 + 30) / 5 = 170 / 5 = 34가 된다. 평균 이외의 또 다른 대표값으로 중앙값이라는 것이 있다. 중앙값은 주어진 수를 크기 순서대로 늘어 놓았을 때 가장 중앙에 놓인 값이다. 예를 들어 10, 40, 30, 60, 30의 경우, 크기 순서대로 늘어 놓으면 10 30 30 40 60 이 되고 따라서 중앙값은 30이 된다. 다섯 개의 자연수가 주어질 때 이들의 평균과 중앙값을 구하는 프로그램을 작성하시오. 입력 첫째 줄부터 다섯 번째 줄까지 한 줄에 하나씩 자연..

다음의 숫자들을 오름차순으로 정렬하는 프로그램을 작성하시오. 7 6 5 8 3 5 9 1 병합 정렬 하나의 큰 문제를 두 개의 작은 문제로 분할한 뒤에 각자 계산하고 나중에 합치는 방법을 채택한다. 즉, 기본 아이디어는 일단 정확히 반으로 나누고 나중에 정렬하는 것이다. 병합 정렬은 퀵 정렬과 다르게 피벗 값이 없고, 항상 반으로 나눈다는 특징이 있다. 바로, 이 특징이 단계의 크기가 logN이 되도록 만들어준다. 7 6 5 8 3 5 9 1 인 모두 크기가 개별 배열로 즉, 크기가 1인 배열 상태로 시작한다. 1단계에서는 각 배열의 크기가 2이고, 크기가 1개 였던 것들을 두 개씩 묶어서 합친 것이다. 1단계에서는 6 7 / 5 8/ 3 5/ 9 1로 나눠진 것을 확인할 수 있다. 2단계에서는 크기가 ..

다음의 숫자들을 오름차순으로 정렬하는 프로그램을 작성하시오. 1 10 5 8 7 6 4 3 2 9 퀵 정렬 하나의 큰 문제를 두 개의 작은 문제로 분할하는 식으로 빠르게 정렬한다. 특정한 값을 기준으로 큰 숫자와 작은 숫자를 서로 교환한 뒤에 배열을 반으로 나눈다. 퀵정렬에서는 기준값 (=피벗(Pivot))이 있는데, 보통 첫 번째 원소를 피벗 값으로 설정하고 사용한다. 다음과 같이 1이라는 값이 먼저 피벗 값으로 설정되었다고 생각해보자. (1) 10 5 8 7 6 4 3 2 9 이 경우 1보다 큰 숫자를 왼쪽부터 찾고, 1보다 작은 숫자를 오른쪽부터 찾는다. 이 때 1보다 큰 숫자로는 바로 10을 찾을 수 있고, 1보다 작은 숫자는 찾지 못해서 결국 1까지 도달한다. 이 때 작은 값의 인덱스가 큰 값의..

다음의 숫자들을 오름차순으로 정렬하는 프로그램을 작성하세요. 1 10 5 8 7 6 4 3 2 9 버블정렬 가까이에 있는 두 숫자끼리 비교해서 당장 더 작은 숫자를 앞으로 보내주는 것을 반복하는 것이다. 코드 및 풀이 (with c언어) #include int main(void) { int i, j, temp; int array[10] = {1, 10, 5, 8, 7, 6, 4, 3, 2, 9}; for (i = 0; i array[j + 1]) { temp = array[j]; array[j] = array[j + 1]; array[j + 1] = temp; } } } for (i = 0; i < 10;..

다음의 숫자들을 오름차순으로 정렬하는 프로그램을 작성하세요. 1 10 5 8 7 6 4 3 2 9 선택정렬 가장 작은 것을 선택해 제일 앞으로 보내는 알고리즘 코드 및 풀이 (with. c언어) #include int main (void) { int i, j, min, index, temp; int array[10] = {1, 10, 5, 8, 7, 6, 4, 3, 2, 9}; for (i = 0; i array[j]) { min = array[j]; index = j; } } temp = array[i]; array[i] = array[index]; array[index] = temp; } for..