군대에서_코딩하기_알고리즘_12

오늘의 문제는.. 정말 이마가 탁 쳐졌던 그런 문제였다.. 아니 문제가 너무 간단해보이길래 '엥 너무 쉬운데..?'라고 생각했지만, 절대 쉽게 풀지 못했다..그래서 결국 강의를 보고 풀기는 했는데.. '브루트포스' 문제라고 한다.

우선 브루트포스(Brute force)란

조합 가능한 모든 문자열을 하나씩 대입해 보는 방식으로 암호를 해독하는 방법.
브루트 포스 공격(brute force attack) 또는 키 전수조사(exhaustive key search), 무차별 대입 공격(無差別代入攻擊) 등으로도 부른다. 흔히 수학 문제를 원시적으로 푸는 방법인 '수 대입 노가다'의 학술적 버전이다. 주로 암호학에서 연구되는 방법이나, 다른 알고리즘 분야에서도 사용되고 있다.
[출처] https://namu.wiki/w/%EB%B8%8C%EB%A3%A8%ED%8A%B8%20%ED%8F%AC%EC%8A%A4

쉽게 말하자면, 노가다..? ㅋㅋㅋㅋㅋㅋ 일전까지는 이런 노가다방식은 지양하고 있었다. 왜냐면 시간복잡도가 조금만 높아지는 노가다 방식을 택하면 바로 time_limit이 떠서 점수를 받지 못했기 때문이다.

하지만 요놈은 조금 다르다.
우선 오늘의 문제는 N명의 학생 점수가 입력되면, 각 학생의 석차를 입력된 순서대로 출력하는 프로그램을 작성해야한다. 예를 들어 N으로 5가 주어지고, 학생들의 점수가 100 80 98 70 97 이라고 입력되면 1 5 2 4 3 이라고 출력해야한다.

처음에는 그냥 Max값을 뽑아내는 형식으로 문제를 풀려고했는데, 그렇게 접근하니까 도저히 답이 안나왔다..그렇다고 정렬을 하기엔, 처음에 출력된 점수 순서대로 석차를 뽑아야했다.. 그래서 이것저것 고민하다가 결국 강의를 봤는데, 정말 이마를 탁 치는..그런 코드였다. 강의를 참고해 짜본 코드는 다음과 같다.

#include<iostream>
#include<vector>
#include<algorithm>

using namespace std;

int main(){
    
    int N, i, j;
    cin>>N;
    
    vector <int> score(N);
    vector <int> fin(N,1);
    
    for(i=0; i<N; i++){
        cin>>score[i];
    }
    
    for(i=0; i<N; i++){
        for(j = 0; j<N; j++){
            if(score[i]<score[j]){
                fin[i]++;
            }
        }
    }
    
    for(i=0; i<N; i++){
        cout<<fin[i]<<" ";
    }
}

도대체 이런 생각을 어떻게 하는지는 모르겠지만.. 노가다 형식으로 배열을 하나씩 다 비교해주면서, 1로 초기화된 fin이라는 배열의 인덱스를 하나씩 올려주는 방식이다. 진짜 상상도 못했던 방식이라, 뒷통수를 한대 맞은 기분이었다..

효율적인 프로그래밍에서는 노가다를 매우 지양하지만, 때로는 필요하다는것을 느꼈다..