Algorithm 구현의 기초
- 알고리즘 문제 풀기 = 내가 생각한 문제 해결 과정을 컴퓨팅 사고로 변환하여 코드로 구현하는 것
- 문제 해결을 코드로 풀어낼 때, 정확하고 빠를 수록 구현 능력이 좋다
- 본인이 선택한 프로그래밍 언어의 문법을 정확히 알고 있어야 하며, 문제의 조건에 전부 부합하는 코드를 실수 없이 빠르게 작성하는 것을 목표로 두는 것을 구현 문제, 구현 유형이라고 통칭할 수 있다.
- 구현 능력을 보는 대표적 사례 : 완전 탐색, 시뮬레이션
- 완전 탐색 : 가능한 모든 경우의 수를 전부 확인하여 문제를 푸는 방식
- 시뮬레이션 : 문제에서 요구하는 복잡한 구현 요구 사항을 하나도 빠트리지 않고 코드로 옮겨 마치 시뮬레이션 하는 것과 동일한 모습을 그림
완전 탐색(brute force)
브루트(Brute): 무식한 ✚ 포스(Force): 힘
컴퓨터의 빠른 계산 능력을 이용하여 가능한 경우의 수를 일일이 나열하면서 답을 찾는 방법
- 장점 : 알고리즘을 설계하고 구현하기 쉽다.
- 단점 : 알고리즘 실행 시간이 오래 걸리고, 메모리 효율면에서 비효율적
"양의 정수 1부터 100까지의 임의의 요소가 오름차순으로 하나씩 담긴 배열 중, 원하는 값 N을 찾기"
→ 배열의 첫 요소부터 마지막 요소까지 전부 확인해 최대 100 번의 탐색을 하는 것. 단순히 모든 경우의 수를 탐색하는 모든 경우
완전 탐색 기법
- 단순 Brute Force(조건/반복을 사용하여 해결)
- 비트마스크(Bitmask)
- 재귀함수
- 순열
- DFS/BFS
1. 단순 Brute Force
단순 for, if문 등으로 모든 경우를 만들어 답을 구하는 방법.
2. 비트마스크(Bitmask)
2진수를 이용하는 컴퓨터 연산을 이용한 방식.
나올 수 있는 모든 경우의 수가 각각의 원소가 포함되거나, 포함되지 않는 두 가지 선택으로 구성되는 경우에 사용한다.
5자리 이진수(0~31)을 이용해 각 원소의 포함 여부를 체크할 수 있다.
3. 재귀 함수
만들고자 하는 부분집합을 S'라고 할 때, S'={}부터 시작해서 각 원소에 대해 해당 원소가 포함되면 S'에 넣고 재귀함수를 돌리고, 포함되지 않으면 S'를 그대로 재귀 함수에 넣어주는 방식.
비트마스크와 마찬가지로 각 원소가 포함되거나, 포함되지 않는 두 가지 선택으로 구성되는 경우에 사용한다.
4. 순열
완전 탐색의 대표적 유형.
서로 다른 N개를 일렬로 나열하는 순열의 경우의 수는 N! 이므로 완전 탐색을 이용하기 위해선 N이 한자리 수 정도는 되어야한다.
순열에 원소를 하나씩 채워가는 방식이다.
5. DFS/BFS
주로 완전탐색 + DFS/BFS 문제가 자주 출제됨.
- 대표적 유형 : 길 찾기 문제
- 길에 장애물 설치 & 목적지 추가된 경우 : 완전 탐색으로 해결한 후 DFS/BFS를 이용하는 방식
완전 탐색 예시 문제
💡 정리
- 브루트 포스 = 완전 탐색 알고리즘
- 모든 경우의 수를 대입해 결과를 찾는 알고리즘
- 경우의 수에 따라 실행 시간이 증가하므로 시간적인 측면에선 비효율적
- 그러나 단순 반복하기 때문에 알고리즘 설계적인 측면에선 만들기 쉬움
블로그 이사했습니다 🧳