알고리즘

소스 코드#include #pragma warning(disable:4996)int main() { int n; scanf("%d", &n); int knee[50][50]; for (int i = 0; i maxRow) ? i : maxRow; minCol = (j maxCol) ? j : maxCol; } } } //상처를 모두 포함하는 직사각형의 넓이를 계산 int width = maxCol - minCol + 1; // 가장 오른쪽 열 - 가장 왼쪽 열 + 1 int height = maxRow - minRow + 1; // 가장 위의 행 - 가장 아래 행 + 1 int area = wi..

문제 정리구름이가 가진 모든 와인 용량은 N-1로 통일7잔 이라면 와인의 용량은 6임한 병의 와인을 따를 시 N-1개 잔을 각 잔에 정확히 1만큼씩 따라야함7잔 이라면 7잔 중 6잔에 1만큼 씩 따라야함문제 접근 방법 1qsort 후 첫 번째 인덱스 제외한 나머지 인덱스 증가내림차순으로 정렬모든 인덱스가 같은지 검사하는 check 함수 작성해서 모든 인덱스가 같다면 종료1차 시도#include #include #pragma warning(disable:4996)int compare(const void*a, const void*b) { return(*(int*)b - *(int*)a); //내림차순 }int check(int *arr,int n,int a){ for(int i = 0 ; i 문제에서 주어졌..

더보기 input output 3 7 6 해당 문제는 단순히 이중 배열을 선언하여 정렬하려고 한다면 시간 초과가 발생할 것이다. 따라서 빠르게 해결할 수 있는 알고리즘인 이진 탐색(이분 탐색)을 사용하였다. 기본적인 알고리즘은 아래와 같다. 더보기 low=1, high=n*n으로 설정 low cnt cnt값이 목표 인덱스 보다 크거나 같을 경우 mid를 왼쪽으로 옮기기 cnt값이 목표 인덱스 보다 작을 경우 mid를 오른쪽으로 옮기기 루프 탈출 후 low값 출력 [n = 3 , k = 5 인 경우] array[3][3] 1 2 3 1 1 2 3 2 2 4 6 3 3 6 9 *mid 값보다 작은 값들의 갯수를 구하는 함수 먼저 구현 ll func(ll x) { // mid보다 작은 수들의 개수를 시간 초과..

input output 6 10 20 10 30 20 50 4 해당 문제는 동적 계획법을 사용하여 문제를 해결 하였다. 입력된 배열을 탐색하는 과정에서 자기 자신보다 작은 값을 찾는 경우에 해당 인덱스를 저장하고 dp 배열에 저장하였다. 수열의 길이는 dp 배열에서 가장 최댓값을 가지는 수의 인덱스이므로 가장 큰 값을 업데이트 해주면 문제 해결이 가능하다. 전체 소스 코드는 아래와 같다. #include #pragma warning(disable:4996) int main() { int arr[1001]; int dp[1001] = {0,}; // Dynamic Programming Array int max = 0; int n; scanf("%d", &n); for (int i = 0; i < n; i+..

input output 3 3 2 1 3 해당 문제는 버블 정렬에 대한 개념을 설명하고 SWAP이 일어나는 횟수를 구하는 문제여서 단순히 버블정렬을 사용한다면 시간초과가 발생한다. 시간 제한이 1초이므로 시간복잡도가 O(N^2)인 버블정렬로는 절대 구현할 수 없다. 보다 빠른 알고리즘인 합병정렬을 사용하거나 세그먼트 트리를 이용하면 O(NlogN)의 시간 복잡도를 가지므로 문제 해결이 가능하다. 필자는 합병 정렬을 사용하였다. 우선, 버블 정렬에서 SWAP이 일어나는 구간은 어떤 원소 i가 존재할 때, i보다 앞에 있으면서 작은 수들을 뒤로 보낼때 작은 수들의 갯수만큼 SWAP이 일어난다. 따라서 합병 정렬에서는 정복 단계에서 SWAP이 일어나고 정렬은 합병 단계에서 일어난다. 버블 정렬에서 SWAP의 ..

input output 5 2 2 1 2 3 4 5 1 3 6 2 2 5 1 5 2 2 3 5 17 12 해당 문제는 배열의 인덱스 요소에서 설정한 범위내에 구간의 합을 구하는 문제이다. 일반적인 배열의 구간 합은 O(n)의 시간 복잡도를 가지만 해당 문제에서 입력으로 주어지는 모든 수는 -2^63 보다 크거나 같고 2^63 - 1보다 작거나 같은 정수이므로 시간 제한이 2초이므로 보다 빠른 알고리즘을 사용해야 한다. 필자는 세그먼트 트리를 통해 해결하였는데, 세그먼트 트리는 O(logn)의 상당히 빠른 알고리즘이다. 세그먼트 트리는 몰랐던 자료구조 이기 때문에 세그먼트 트리가 무엇인지 알아보면서 풀이를 진행하겠다. 세그먼트 트리는 이진 트리 구조이다. 따라서 각 노드에 대한 정보를 알 수 있다. 부모노..

input1 output1 input1 output1 A*(B+C) ABC+* A+B*C-D/E ABC*+DE/- 해당 문제는 자료구조 중에서 스택을 이용하여 해결가능 한 문제이다. 문제 해결 과정은 아래와 같다. 피연산자를 만나면 바로 출력한다. 연산자가 들어오면 자신보다 우선순위가 높거나 같은것들을 제외하고 스택에 넣는다. 여는 괄호 '('를 만나면 스택에 넣는다. 닫힘 괄호 ')'를 만나면 여는 괄호 '('를 만날때 까지 스택에서 꺼내 출력한다. 우선순위 처리는 다음과 같다. 현재 처리 중인 연산자의 우선순위가 스택에 있는 우선순위보다 낮은 경우 스택에 있는 연산자를 꺼내 출력하고 처리 중인 연산자는 스택에 넣는다. 현재 처리 중인 연산자의 우선순위가 스택에 있는 우선순위보다 큰 경우 처리 중인 연..

input output 4 14 9 12 10 1 11 5 4 7 15 2 13 6 3 16 8 4 해당 문제를 먼저 해석하면, n x n 크기의 대나무 숲은 2차원 배열로 정의한다. 판다는 대나무가 많은 곳으로 이동하기 때문에 판다가 이동하는 만큼 생존한다고 볼 수 있다. 판다가 생존 가능한 최대 일 수는 아래 표로 정리하였다. 해당 문제는 DFS와 동적 계획법을 사용한다면 해결가능한 문제이다. 만약, DFS만을 진행한다면 이미 탐색한 곳에 대해서 다시 탐색하는 의미없는 탐색을 진행하기 때문에 최대 깊이까지 탐색한 후 백트래킹을 통해 동적계획법의 값을 저장한다. 백트래킹시에 현재 값에 1을 더해준 값을 반환한다. 전체 소스 코드는 아래와 같다. #include #define max(X,Y) ((X) >..