💻

탐욕적 알고리즘이란? 어떤 선택을 해야할 때 그 당시에 가장 최선의 선택을 하여 문제를 해결하는 알고리즘을 말한다. - 순간의 선택은 그 당시의 최적의 선택이다. 이런 선택들이 모여 최종적인 해답을 얻는다고 하여 최종 해답이 최적이라는 보장은 없다. 따라서, 탐욕적 알고리즘은 해답을 얻은 후에 이 해답이 최적인지 검사해야 한다. - 알고리즘 설계 절차 1단계) 선정과정(selection procedure) : 현재 상태에서 가장 좋은 선택이라고 생각되는 해답을 찾아서 해답모음(solution set)에 포함시킨다. 2단계) 적정성검사(feasibility test) : 새로 얻은 해답모음이 적절한지를 결정한다. 3단계) 해답 검사(solution check) : 새로 얻은 해답모음이 최적의 해인지 결정한..

이분 탐색(이진탐색) 알고리즘 은 찾을 범위를 반으로 나눠서 탐색하는 알고리즘이다. 처음 중간의 값을 임의의 값으로 선택하여, 그 값과 키값의 크고 작음을 비교하는 방식이다. 처음 선택한 중간값이 만약 찾는 값보다 크면 최댓값이 되고, 작으면 최솟값이 된다. - 분할 정복 알고리즘에 속하는 알고리즘이다. - 단, 이미 정렬된 경우에만 적용할 수 있다. - 최악의 경우는 찾으려는 키값이 배열에 존재하지 않을 때이다. - 시간복잡도는 O(logN) 이다. 반복문을 사용하는 경우 int BinarySearch(int arr[], int length, int key){ int first = 0; int last = length - 1; int mid = 0; while(first key){ // 중간값이 찾으려..

분할 정복법이란? 문제의 사례를 2개 이상의 더 작은 사례로 나누어(divide) 각 작은 사례에 대한 해답(conquer)을 쉽게 얻을 수 있으면 이들의 해답을 결합(combine)하여 원문제의 해답을 얻는 방식. - 문제를 나누는 과정은 해답을 쉽게 얻을 때까지 반복적으로 적용한다. - 하향식(top-down) 접근 방법이다. 분할(Divide) : 해결하기 쉽도록 문제를 여러 개의 작은 부분으로 나눈다. 정복(Conquer): 나눈 작은 문제를 각각 해결한다. 통합(Combine): (필요하다면) 해결된 해답을 모은다. - 보통 재귀 프로시저로 먼저 해결한 다음에 보다 효율적인 반복 프로시저가 없는지 검토한다. - 대표적인 알고리즘 이진 검색(BinarySearch) 합병 정렬(MergeSort) ..

문제 N개의 정수 A[1], A[2], …, A[N]이 주어져 있을 때, 이 안에 X라는 정수가 존재하는지 알아내는 프로그램을 작성하시오. 입력 첫째 줄에 자연수 N(1≤N≤100,000)이 주어진다. 다음 줄에는 N개의 정수 A[1], A[2], …, A[N]이 주어진다. 다음 줄에는 M(1≤M≤100,000)이 주어진다. 다음 줄에는 M개의 수들이 주어지는데, 이 수들이 A안에 존재하는지 알아내면 된다. 모든 정수들의 범위는 int 로 한다. 출력 M개의 줄에 답을 출력한다. 존재하면 1을, 존재하지 않으면 0을 출력한다. 예제 입력1 5 4 1 5 2 3 5 1 3 7 9 5 예제 출력1 1 1 0 0 1 생각 처음에는 단순하게 하나씩 입력받은 수를 배열에서 있는지 체크해서 있으면 true를 리턴하..

문제 독일 로또는 {1, 2, ..., 49}에서 수 6개를 고른다. 로또 번호를 선택하는데 사용되는 가장 유명한 전략은 49가지 수 중 k(k>6)개의 수를 골라 집합 S를 만든 다음 그 수만 가지고 번호를 선택하는 것이다. 예를 들어, k=8, S={1,2,3,5,8,13,21,34}인 경우 이 집합 S에서 수를 고를 수 있는 경우의 수는 총 28가지이다. ([1,2,3,5,8,13], [1,2,3,5,8,21], [1,2,3,5,8,34], [1,2,3,5,13,21], ..., [3,5,8,13,21,34]) 집합 S와 k가 주어졌을 때, 수를 고르는 모든 방법을 구하는 프로그램을 작성하시오. 입력 입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스는 한 줄로 이루어져 있다. 첫 ..

문제 예제를 보고 규칙을 유추한 뒤에 별을 찍어 보세요. 입력 첫째 줄에 N이 주어진다. N은 항상 3의 제곱꼴인 수이다. (3, 9, 27, ...) (N=3k, 1 ≤ k [0][1] = ' * ' Star(0,2,1) -> [0][2] = ' * ' -------------------------------- 첫째줄 ***완성 Star(1,0,1) -> [1][0] = ' * ' Star(1,1,1) -> Star(1,2,1) -> [1..

문제 어떤 자연수 N이 있을 때, 그 자연수 N의 분해합은 N과 N을 이루는 각 자리수의 합을 의미한다. 어떤 자연수 M의 분해합이 N인 경우, M을 N의 생성자라 한다. 예를 들어, 245의 분해합은 256(=245+2+4+5)이 된다. 따라서 245는 256의 생성자가 된다. 물론, 어떤 자연수의 경우에는 생성자가 없을 수도 있다. 반대로, 생성자가 여러 개인 자연수도 있을 수 있다. 자연수 N이 주어졌을 때, N의 가장 작은 생성자를 구해내는 프로그램을 작성하시오. 입력 첫째 줄에 자연수 N(1 ≤ N ≤ 1,000,000)이 주어진다. 출력 첫째 줄에 답을 출력한다. 생성자가 없는 경우에는 0을 출력한다. 예제 입력1 216 예제 출력1 198 생각 처음에 문제를 봤을때 나눗셈으로 풀릴 거 같았다..

문제 이 문제는 여러분이 사용하는 큐 자료구조가 시간 복잡도 상으로 충분히 빠른지 테스트하는 문제이다. 입력의 범위를 제외하면 10845 (큐) 문제와 같다. 정수를 저장하는 큐를 구현한 다음, 입력으로 주어지는 명령을 처리하는 프로그램을 작성하시오. 명령은 총 여섯 가지이다. push X: 정수 X를 큐에 넣는 연산이다. pop: 큐에서 가장 앞에 있는 정수를 빼고, 그 수를 출력한다. 만약 큐에 들어있는 정수가 없는 경우에는 -1을 출력한다. size: 큐에 들어있는 정수의 개수를 출력한다. empty: 큐가 비어있으면 1, 아니면 0을 출력한다. front: 큐의 가장 앞에 있는 정수를 출력한다. 만약 큐에 들어있는 정수가 없는 경우에는 -1을 출력한다. back: 큐의 가장 뒤에 있는 정수를 출력..