열코의 프로그래밍 일기

문제의 조건은 3가지로 단순합니다. 

1. 금메달 수가 더 많은 나라  
2. 금메달 수가 같으면, 은메달 수가 더 많은 나라 
3. 금, 은메달 수가 모두 같으면, 동메달 수가 더 많은 나라  

얼핏보면 if문을 사용하여 조건을 걸어 풀 수 있지만  

'전체 메달 수의 총합은 1,000,000 이하이다.' 라는 입력 전제조건을  활용하여 
금,은,동 메달에 각각 점수를 부여하여 각각의 메달의 최대치(1,000,000)를 획득해도 
그보다 높은 메달 1개 보다 낮은 점수를 부여하여 풀 수있는 알고리즘입니다. 

다음은 score배열에 각각의 메달에 가중치를 부여하여 계산하여 저장하는 구문입니다. 

for (int i = 0; i < country_num; i++)  { 
     score[i][0] = arr[i][0]; // 1) 
     score[i][1] = (arr[i][1] * 1000000000000) + (arr[i][2] * 1000000)+ (arr[i][3] * 1); // 2) 
} 

country_num은 입력받은 국가 개수입니다. 
score 배열은 국가 넘버, 국가 별 점수를 저장한 배열입니다. 
arr는 입력받은 배열입니다. 
1. 첫번째 열이 모두 국가 넘버이기 때문에 score배열 첫번째 행에 모두 저장합니다. 
2. arr배열의 두번째, 세번째, 네번째 열이 금,은,동메달 순이므로 각각에 가중치를 곱한 후 score배열에 저장합니다. 


두번째로 동일 점수에 대한 등수 계산법입니다. 
간단하게 구현 가능합니다. 

int count = 1; 
for (int i = 0; i < country_num; i++){ 
     if (score[i][0] == country){ 
          for (int j = 0; j < country_num; j++){ 
               if (score[i][1] < score[j][1]) count++; 
          } 
          break; 
     } 
} 
cout << count; 

두번째로 들어온 입력 (등수를 알고싶은 국가K)을 country변수에 저장한 후 
반복문을 사용하여 배열의 인덱스를 알아냅니다(각 국가가 순서대로 입력되지 않기 때문에) 
인덱스를 알아낸 상태에서 다시 반복문을 사용하여 자신의 점수보다 큰 점수를 count하면 됩니다. 
break 사용 이유는 인덱스를 이미 찾은 상태이므로 더이상 반복문을 실행하지 않아도 되기 때문입니다. 

다음 실행 코드 전체입니다. 

 * score 배열의 자료형을 unsigned long long으로 한 이유는 가중치의 총 합이 10^19이 넘어가는 숫자이기 때문에 long long을 사용해도 범위(-9x10^19~9x10^19)안에 속하지만 가중치에 음수가 없기 때문에 편의상 unsigned long long으로 표현했습니다.

*전체 소스코드 

#include <iostream> 

using namespace std; 

int main() 
{ 
     int country_num = 0; 
     int country = 0; 
     int **arr = NULL; 
     unsigned long long **score = NULL; 

     cin >> country_num >> country; 

     arr = new int*[country_num]; 
     score = new unsigned long long*[country_num]; 

     for (int i = 0; i < country_num; i++) { 
          arr[i] = new int[4]; 
          score[i] = new unsigned long long[2]; 
     } 

     for (int i = 0; i < country_num; i++) 
          for (int j = 0; j < 4; j++) 
               cin >> arr[i][j]; 

     for (int i = 0; i < country_num; i++) { 
          score[i][0] = arr[i][0]; 
          score[i][1] = (arr[i][1] * 1000000000000) + (arr[i][2] * 1000000) + (arr[i][3] * 1); 
     } 

     int count = 1; 
     for (int i = 0; i < country_num; i++) { 
          if (score[i][0] == country) { 
               for (int j = 0; j < country_num; j++) { 
                    if (score[i][1] < score[j][1]) 
                         count++; 
                    } 
               break; 
          } 
     } 
     cout << count; 

     for (int i = 0; i < country_num; i++) 
          delete[] arr[i]; 
     delete[] arr; 

     return 0; 
} 

1. 선형 검색 (Linear Search)

- 배열의 가장 좌측부터 시작하여 찾으려는 값과 하나씩 배열의 각 요소와 비교합니다.

- 찾으려는 값을 발견한다면 배열의 해당 인덱스를 반환(return)합니다.

- 찾으려는 값이 없다면 -1을 반환합니다.

- 시간복잡도 O(n)

- 이진 검색 및 해시 테이블과 같은 다른 검색 알고리즘이 훨씬 빠르기 때문에 실제로 거의 사용하지 않습니다.

- 소스코드

2. 이진 검색 (Binary Search)

- 검색 반경을 반으로 나눠어 반복하는 검색 방법입니다.

- 정렬 된 배열에서 사용 가능합니다.

- 찾으려는 값을 배열의 중간값과 비교하여 그 값이 더 작다면 우측 배열, 크다면 좌측 배열로 이동하여 반복

- 시간 복잡도 O(log n)

- 소스코드

- C++ STL에서는 이진 검색을 라이브러리로 제공합니다.

- binary_search(시작위치, 끝위치, 찾으려는값) 식으로 사용합니다.

- lower_bound는 찾으려는 값이 여러개 존재할 때 사용합니다. (upper_bound는 큰 인덱스를 반환)

- 배열(또는 리스트) 안에 찾으려는 값이 1개(단일) 존재한다면 해당 값의 인덱스를 반환합니다.

- 배열 안에 찾으려는 값이 2개 이상 존재한다면 해당 값 중 가장 앞쪽(낮은) 인덱스(num of first position)를 반환합니다.

- 배열 안에 찾으려는 값이 없을 경우 찾으려는 값 다음 위치의 인덱스를 반환합니다.

- 자바에서 Array.binarySearch() 또는 Collections.binarySearch()을 라이브러리로 사용할 수 있습니다.

- 만약 자바에서 이진 탐색을 사용하려면 전에 Array.sort() 메소드를 호출하여 배열을 정렬할 필요가 있습니다.

※ 배열 또는 리스트에서 최소값, 최대값 검색

- 정렬된 배열 또는 리스트에서는 양쪽 끝 값이 최소값 또는 최대값입니다.

- Divide and Conquer를 사용하여 O(log n) 시간에서 최소값 또는 최대값을 구할 수 있습니다.

- 소스코드

이상 ''에 대해 알아보았습니다.

질문 또는 오타나 잘못된 정보가 있는 경우 댓글로 달아주세요!