또다시 코딩

완전탐색이란?

• 완전탐색은 Brute-force Search라고 부르며 알고리즘 문제를 해결할 때 기본적으로 처음 접할 수 있는 방법입니다.
• 한 상황을 생각해 봅시다. 1000개까지 담길 수 있는 배열에서 두개의 가장 큰 수를 찾아 두 수의 합을 출력해보는 문제가 있다고 한다면, 이 두 수를 어떻게 찾을 수 있을까요?
• 쉽게 생각해서 우리는 for문을 활용해 각 배열의 원소들을 더해보고 가장 큰 값을 구하는 방법을 생각해 볼 수 있습니다.
• 즉 쉽게 말하면 모든 경우의 수를 다 탐색해보며 찾아보는 방식이고 그렇기 때문에 시간복잡도는 최대로 O(n^2) 의 시간이 소요됩니다.

• #include <iostream>
  #include <algorithm>
  #include <climits>
  using namespace std;
  int Number;
  int ret = INT_MIN;
  int main()
  {
    int array[1000];
    cin >> Number; // Array의 크기를 입력받습니다.
    for(int i=0;i<Number;i++) // Number의 크기만큼 순회하며 Array의 요소를 채워넣습니다.
      cin >> array[i];
    //여기서 array담긴 숫자들 중 가장 큰 값을 가지는 숫자 2개를 더한 값을 호출해야하는 경우를 생각해봅시다.
    for(int i=0;i<Number;i++)
        for(int j=0;j<Number;j++)
        if (i!=j) // Array의 두 index가 다를 때, 즉 같은숫자의 경우는 제외합니다.
          ret = max(ret, array[i] + array[j]); //return값을 max함수를 통해 더 큰값으로 갱신합니다.
    cout << ret;
    return (0);
  }

• 위 코드를 살펴보면 Array의 담겨있는 최대 1000개까지 담길 수 있는 배열에서 2개의 큰 수를 찾아 결과를 반환하는 것을 확인할 수 있습니다.
• 모든 가능한 경우를 다 돌아보기 때문에 Number크기(Array의 크기)의 제곱만큼의 시간이 소요될 수 있습니다.
• 정답을 찾아내는 방법 중 가장 확실한 방법이지만 그만큼 시간이 많이 소요되기 때문에 알고리즘문제의 제한시간 을 확인해서 사용해야 합니다.
• c++기준으로 1억번의 시간복잡도를 가질 경우 제한시간이 1초 소요되는 것으로 생각하여 문제를 해결합시다.
• 완전탐색 알고리즘을 활용한 문제는 다음 게시글에서 확인할 수 있습니다.
  • https://ukjinlee.tistory.com/21

https://programmers.co.kr/learn/courses/30/lessons/42584

문제를 처음 확인할 때 생각해볼 수 있는 가장 쉬운 방법으로는 O(n^2) 시간 복잡도를 가지고 있는 완전 탐색이다.

그러나 문제를 읽어보면 다음 인덱스 시점의 시간에서 가격이 떨어지느냐 안 떨어지느냐에 따라 return값이 결정된다는 것을 확인할 수 있다.

한 가지 주의해야 할 점은 다음 인덱스가 이전 인덱스보다 작다는 것을 알기 전 시간은 이미 1초가 흘렀다고 생각하는 것이고

전부 다 돌아보는 것이 아닌 두 번째 for문부터는 바로 앞 인덱스부터 탐색을 시작하면 해결할 수 있다.

문제의 분류로는 스택과 큐 카테고리에 존재하지만 오히려 스택과 큐를 활용하여 해결방법을 생각해보더라도 오히려 코드가 더 길어질 것 같으며 큰 차이가 없을 것 같아 다음과 같이 완전 탐색과 같은 방법으로 해결하였다.

3 언어의 코드 방식도 전부 동일하며 문제 예시에 대한 이해를 빠르게 한다면 빠른 시간 내에 해결할 수 있을 것 같다.

C++

#include <string>
#include <vector>

using namespace std;

vector<int> solution(vector<int> prices) 
{
    vector<int> answer;
    for(int i=0;i<prices.size();i++)
    {
        int cnt=0;
        for(int j=i+1;j<prices.size();j++)
        {
            cnt++;
            if (prices[i] > prices[j])
                break;
        }
        answer.push_back(cnt);
    }
    return answer;
}

Java

class Solution 
{
    public int[] solution(int[] prices) 
    {
        int[] answer = new int[prices.length];
        for(int i=0;i<prices.length;i++)
        {
            for (int j=i + 1;j<prices.length;j++)
            {
                answer[i]++;
                if (prices[i]>prices[j])
                    break;
            }
        }
        return answer;
    }
}

Python3

def solution(prices):
    answer = [0] * len(prices)
    # prices 크기만큼 빈 리스트를 할당.
    for i in range(0,len(prices)):
        for j in range(i + 1, len(prices)):
            answer[i] += 1
            if prices[i]>prices[j]:
                break;
    return answer

도형의 종류별로 회전과 대칭의 index를 확인해보며 넣었을 경우 얻는 값을 최대로 경신해주기만 하면 풀리는 막일 문제였다. 꼼꼼하게 체크할게 거의 없었고 가능하면 정리해서 코드를 짜야 하지만 역량테스트를 치른다는 가정하에 가장 빠르게 해결하기 위하여 너저분하게 코드가 짜였다.

https://github.com/ukjinlee66/BOJ/blob/master/14500.cpp

https://www.acmicpc.net/problem/14500