[코드트리 조별과제] 알고리즘 : 완전탐색(1)

코드트리에서 진행하는 방학조별과제 이벤트에 참여하게 되었습니다.

코드트리 | 코딩테스트 준비를 위한 알고리즘 정석

✍🏻 이번주 목표

코드트리 조별과제로 가장 먼저 공부해 볼 알고리즘으로 완전탐색을 선택해보았습니다. 

가장 많이 만나는 알고리즘이기도 하고 제가 부족하기도 해서 기본부터 탄탄히 공부해 보기 위해서 선택하였습니다. 😊

---

격자 안에서의 완전탐색

완전탐색이란, 문제를 해결할 수 있는 가장 naive한 방법이다.

이는 모둔 가능한 경우를 다 따져보는 것으로, 코드를 작성하기가 쉽다는 장점이 있지만 모든 가능한 경우를 전부 계산해봐야 하므로 올바른 정답을 찾기까지 걸리는 시간(프로그램 수행시간)이 비교적 오래 걸린다.

즉, 완전탐색은 시간복잡도를 계산해 보고, 시간초과가 나지 않을 것 같다면 항상 적용해야 하는 방법이다.

완전탐색을 구현할 수 있는 방법

1. For문 기반으로 구현
2. 재귀함수 기반의 Backtracking(BruteForce) 기법을 이용

👆🏻먼저 For문을 기반으로 한 완전탐색 문제를 풀어보자

---

문제 : 최고의 33위치

→ 코드트리에서 제공하는 문제입니다. (바로가기)

 

✏️ 풀이

• n의 값이 최대 20이기 때문에 완전탐색으로 구현하여도 무리 없이 가능하다!
• 3 * 3 크기의 격자 내에 들어올 수 있는 최대 동전의 수를 구하는 문제이므로, 범위를 0부터 n - 3까지로 지정하여 모든 경우를 탐색하였다.
• 예를 들어, 현재 탐색위치가 (0, 0)인 경우 (0, 0)부터 (2, 2)까지의 인덱스에서 1의 개수를 카운팅 한다.
• 가장 큰 값은 max_cnt에 저장하고, 각 반복문마다 비교하여 더 큰 값으로 갱신하였다.

💡 정답

#include <iostream>
using namespace std;

int main() {
    int n;
    int arr[20][20];
		
		// 배열 크기 n 입력
    cin >> n;
    
    // 배열 요소 입력
    for(int i = 0; i<n;i++){
        for(int j = 0; j<n;j++){
            cin>>arr[i][j];
        }
    }
		
		// 최대 1의 개수를 저장할 변수
    int max_cnt = 0;
    
    // 3 x 3 격자의 시작 위치를 탐색
    for(int i = 0; i < n - 2;i++){
        for(int j = 0; j<n-2;j++){
            
            // 현재 3 x 3 격자 내의 1의 개수를 세기 위한 변수
            int cnt = 0;
            
            // 3x3 격자 내의 요소를 탐색
            for(int x = 0; x<3;x++){
                for(int y = 0; y<3;y++){
                    int idx_x = i + x;
                    int idx_y = j + y;
                    
                    // 1인 경우 개수 증가
                    if(arr[idx_x][idx_y] == 1){
                        cnt++;
                    }
                }
            }
            
            // 최대 개수 갱신
            max_cnt = max(max_cnt, cnt);
        }
    }
    cout<<max_cnt<<endl;
    return 0;
}

 

문제 : 행복한 수열의 개수

→ 코드트리에서 제공하는 문제입니다. (바로가기)

 

💡정답

#include <iostream>
using namespace std;

int n, m;

// 해당 행이 행복한 수열인지 판단하는 함수
bool check_arr(int *arr){

    for(int i = 0; i<=n - m;i++){

        int cnt = 1;
        for(int j = 1; j< m;j++){
            if(arr[i] == arr[i + j]) cnt++;
        }

        if(cnt == m){
            return true;
        }
    }
    return false;
}

int main() {

    int arr[100][100];
    int cnt = 0;
    cin >> n >> m;

    for(int i = 0; i<n;i++){
        for(int j = 0; j<n;j++){
            cin >> arr[i][j];
        }
    }

    // 가로행 탐색
    for(int i = 0; i<n;i++){
        if(check_arr(arr[i]))cnt++;
    }
    
    // 세로행 탐색
    for(int j = 0; j<n;j++){
        
        // 임시배열
        int tmp_arr[100];
        for(int i = 0; i<n;i++){
            tmp_arr[i] = arr[i][j];
        }

        if(check_arr(tmp_arr)) cnt++;
    }

    cout<<cnt<<endl;
    return 0;
}

 

🗨️ 회고

이번주에는 생각보다 시간이 나지 않아 많이 하지는 못하였다.

완전탐색 부분에서도 아주 기본적인 for문을 사용하여 탐색하는 문제를 풀어봤으며 완전탐색의 개념과 시간 복잡도에 대해서 공부해 보았다.

코드트리에서는 문제를 풀기 전 기본 개념을 학습할 수 있도록 제공해 주며, 각 문제마다 원하는 언어의 풀이를 제공해 준다. 알고리즘 공부하기에 도움이 많이 될 것 같다. 다음 주에는 더 많은 내용을 리뷰해 보아야겠다!