Algorithm 56

영지 선택(2차원 배열 구간합, DP)

▣ 문제 세종대왕은 현수에게 현수가 다스릴 수 있는 영지를 하사하기로 했다. 전체 땅은 사각형으로 표 시된다. 그 사각형의 땅 중에서 세종대왕이 현수가 다스릴 수 있는 땅의 크기(세로의 길이와 가 로의 길이)를 정해주면 전체 땅 중에서 그 크기의 땅의 위치를 현수가 정하면 되는 것이다. 전체 땅은 사각형의 모양의 격자로 되어 있으며, 그 사각형 땅 안에는 많은 오렌지 나무가 심겨져 있다. 현수는 오렌지를 무척 좋아하여 오렌지 나무가 가장 많이 포함되는 지역을 선택하고 싶어 한다. 현수가 얻을 수 있는 영지의 오렌지 나무 최대 개수를 출력하는 프로그램을 작성하세요. 다음과 같은 땅의 정보가 주어지고, 현수가 하사받을 크기가, 가로 2, 세로 3의 크기이면 가장 많은 오렌지 나무가 있는 영지는 총 오렌지 나..

Algorithm 2021.02.03

이분검색

▣ 입력설명 임의의 N개의 숫자가 입력으로 주어집니다. N개의 수를 오름차순으로 정렬한 다음 N개의 수 중 한 개의 수인 M이 주어지면 이분검색으로 M이 정렬된 상태에서 몇 번째에 있는지 구하는 프로그램을 작성하세요. ▣ 입력설명 - 첫 줄에 한 줄에 자연수 N(3 M) inx = inx / 2; else inx = inx + inx / 2; } printf("%d", answer); return 0; } #pragma warning(disable:4996) #include #include int compare(const void* n1, const void* n2) { if (*(int*)n1 > * (int*)n2) return 1; else if (*(int*)n1 < *(int*)n2) retur..

Algorithm 2021.01.29

[개념] 정렬 알고리즘

선택 정렬(Selection Sort) 첫 번째 자리에 가장 작은 요소를 넣고, 두 번째 자리에 그 다음 가장 작은 요소를 넣고.... 가장 작은 요소를 찾으면 첫 번째 자리에 있는 요소와 교환 void selectionsort(int arr[], int size){ int minIndex; for(int i = 0; i < size - 1; i++){ minIndex = i; for(int j = i + 1; j < size; j++){ if(arr[j] < arr[minIndex]) minIndex = j; } swap(&arr[i], &arr[minIndex]); } } 삽입 정렬(Insertion Sort) key 원소 값의 알맞은 자리를 찾아 삽입 key보다 큰 값들은 하나씩 밀어버리고 작은 값..

Algorithm 2021.01.25

[개념] 탐색(검색) 알고리즘

선형 탐색/순차 탐색(Linear Search/Sequential Search) 순서대로 하나하나씩 찾기 왼쪽에서부터 순서대로 하나씩 확인해 나가는 것... 찾는 대상이 앞쪽에 있으면 짧은 시간에 탐색할 수 있지만, 뒤쪽에 있거나 결과가 없거나 탐색 대상이 많으면 많은 시간이 걸리고 비효율적일 수 있다 시작 복잡도: O(n) 이진 탐색/이분 검색(Binary Search) 반씩 제외시키면서 찾기 미리 오름차순이나 내림차순으로 정렬되어 있는 경우 사용할 수 있다. 가운데 있는 요소보다 큰지 작은지 보고 범위를 좁힌다. 예) 술자리에서 했던 소주 뚜껑 숫자 업다운으로 맞추기 평균적으로 이진 탐색법이 선형 탐색보다 빠르다. 시작 복잡도: O(logN) 해시법 (Hash)

Algorithm 2021.01.25

N!의 표현법

문제 코드 - C /C++언어 -접근한 방식 5 = 5 * 4 * 3 * 2 * 1 = 120 120의 소수들의 곱을 찾는게 아니라 5부터 하나씩 소수들의 곱으로 만들어서 구해본다. 1. N을 입력받고 2. 2부터 N까지 반복문을 돌려서 해당 값을 소수들의 곱으로 만들어 구한다. 3. prime이라는 배열에 구해진 소수들을 index로 가지는 값을 +1 4. 출력할때 index가 소수인지 확인 후, 그 값을 출력 -내가 작성한 코드 #include void findprime(int *arr, int a){ int index = 0; int now = a; for(int i = 2; i

Algorithm 2021.01.18
728x90