Brute Force / 완전탐색 / 백트래킹 정복

[wooyn730]

Brute Force 정복

정의

브루트 포스(brute force) brute: 무식한, force: 힘 무식한 힘으로 해석할 수 있다. 완전탐색 알고리즘. 즉, 가능한 모든 경우의 수를 모두 탐색하면서 요구조건에 충족되는 결과만을 가져온다. 이 알고리즘의 강력한 점은 예외 없이 100%의 확률로 정답만을 출력한다.

브루트 포스(brute force)란 조합 가능한 모든 경우의 수를 다 대입하는 것이다. 쉽게 말하면 비밀번호가 4자리인 잠금을 풀기 위해 0000부터 9999까지 전부 다 시도해서 때려 맞추는 것과 같다. 이런 걸 언제 다 하나 싶겠지만 컴퓨터는 1초에 엄청나게 많은 연산을 하기 때문에 이런 노가다도 잘 한다. 그래서 실제 보안 공격에도 쓰이는 수법(brute force attack)이기도 하다.

장점 모든 경우를 다 고려하기 때문에 확실한 정답을 찾을 수 있다. 복잡한 알고리즘 없이 빠르게 구현이 가능하다.

단점 모든 경우를 다 고려하기 때문에 효율적이지 못하다. 알고리즘 실행시간이 오래 걸린다.

Brute : 무식한

Force : 힘

직역하면, 무식한 힘을 갖는 알고리즘이란 뜻으로, 완전 탐색 알고리즘의 한 종류이지만 완전 탐색의 또 다른 이름으로 쓰이기도 한다. 브루트 포스 알고리즘은 완전탐색으로 답을 도출하는 알고리즘이며, 대부분은 반복문과 조건문을 통하여 답을 도출한다.

모든 경우의 수를 전부 탐색하기 때문에, 100%의 정확성을 보장하지만,

모든 경우의 수를 전부 탐색하기 때문에, 높은 시간 복잡도를 갖는다.

완전 탐색과 브루트 포스의 이름에서 유추할 수 있듯이 이 알고리즘의 방법은 발생 가능한 모든 경우의 수를 전부 탐색하면서 조건에 맞는 답을 찾아내는 방법입니다. 이 알고리즘의 대표적인 장점은 모두 확인하기 때문에 100%의 확률로 정답만을 출력한다는 것입니다. 하지만 확실하게 확인하는 만큼 시간이 오래 걸리는 탐색기법입니다.

💡 Brute: 무식한, 짐승 같은 + Force: 힘 - 무식하게 풀기

구현 방법

대부분은 반복문과 조건문 / 재귀 / DFS BFS

문제 유형

1. 입력으로 주어지는 데이터(N)의 크기가 매우 작다. 

2. 답의 범위가 작고, 임의의 답을 하나 선택했을 때 문제 조건을 만족하는지 역추적할 수 있다. 

3. 여러 문제 조건 중 한 조건을 고정시키면 문제 풀이가 간단해진다. 

4. 문제에서 달성하고자 하는 솔루션이 잘 정의 되어 있어야한다.

5. 문제를 해결할 수 있는 풀이의 수가 제한되어 있어야 한다.

참고 링크 참고 링크2

다음엔 비트 마스킹, 다이나믹 프로그래밍?

---

브루트포스, 백트래킹, DFS 차이

브루트 포스 알고리즘 = 모든 가능한 경우를 전부 해보는 방식의 알고리즘 백트래킹 = 탐색을 진행하고 조건에 맞지 않는 부분을 제외하면서 진행하는 방식의 알고리즘 DFS = 트리를 완전 탐색하는 한가지 방법

---

[백준] 브루트포스 실~골 맞은사람순

[프로그래머스] 완전탐색

[wooyn730]

부분수열의 합

번호: 1182 사이트: 백준 난이도: 실버2

풀이

• 링크 (02/12)

[wooyn730]

차이를 최대로

번호: 10819 사이트: 백준 난이도: 실버2

풀이

• 링크 (02/12)

---

풀이를 참고했다..

내 머리로는 안풀려서 너무너무너무너무 스트레스 받았다.

하지만 재귀를 통해 조합과 순열 구현하는 방법만 익히면 금방 다른 문제에도 잘 써먹을 수 있지 않을까?????

[wooyn730]

연산자 끼워넣기

번호: 14888 사이트: 백준 난이도: 실버1

풀이

• 링크 (02/15)

---

백트래킹 기법을 저번 문제풀이 때 알아두니 어렵지 않게 풀 수 있었다!!!! 굿

[wooyn730]

부등호

번호: 2529 사이트: 백준 난이도: 실버1

풀이

• 링크 (02/18)

---

순열 백트래킹을 확실히 기억해두었다. 하지만 테스트로 출력하게 해둔 걸 그냥 제출하는 등 사소한 실수가 있었다 ㅎㅎ..

[wooyn730]

스타트와 링크

번호: 14889 사이트: 백준 난이도: 실버1

풀이

• 링크 (02/19)

---

실버라 어렵지는 않았다. 하지만 조합 문제는 처음이라 참고가 필요했다.

앞에서부터 숫자를 뽑기 때문에 어디까지 뽑았는지 체크가 필요하다.

체크 안해서 시간 초과가 났었다.

컴파일 에러는 select(예약어), INT_MAX 키워드 때문이었다.

[wooyn730]

외판원 순회 2

번호: 10971 사이트: 백준 난이도: 실버2

풀이

• 링크 (02/21)

---

문제를 자세히 안 읽어서 헷갈릴 뻔 했지만 무난히 1트 통과~

[wooyn730]

마인크래프트

번호: 18111 사이트: 백준 난이도: 실버2

풀이

• 링크 (02/22)

---

백트래킹 아닌 그저 완탐 문제! (별 생각 없이 함수 이름은 DFS로 했지만..)

깊은 생각 없이 짠 코드가 시간초과가 나와서 (그럴줄은 알았지만) 리팩터링 후 통과했다.

문제 레벨이 높거나 정답률이 낮다고 지레 겁 먹지 않았으면 좋겠음!

[wooyn730]

치킨 배달

번호: 15686 사이트: 백준 난이도: 골드5

풀이

• 링크 (02/23)

---

조합 백트래킹 사용!

저번에 시간초과 걸렸어서 반복문 추가하지 않고 입력 받을 때 미리 체크해뒀다.

TC 2번 통과 못해서 잠깐 헷갈렸지만 인덱스를 0이 아닌 -1로 해줬어서 생긴 사소한 일..^_^

[wooyn730]

사탕 게임

번호: 3085 사이트: 백준 난이도: 실버2

풀이

• 링크 (02/24)

---

백트래킹 X 그냥 완탐

1트는 가로 세로 헷갈려서 틀렸고 2트는 j를 i로 쓰는 오타 때문에 틀렸다 (근데 TC를 통과한..ㅠ)

[wooyn730]

링크

브론즈도 2 문제 있음

[wooyn730]

N-Queen

번호: 9663 사이트: 백준 난이도: 골드4

풀이

• 링크 (02/25)

---

어쪈지 풀기 싫게 생겼더라.... 다른 풀이 참고해서 풂 ㅠㅠ

완전탐색이 아니라 규칙을 먼저 생각해내는게 포인트였다. 나는 퀸을 조합으로 배치한 후 조건을 체크했는데 퀸을 배치할 때부터 조건을 체크해야 했다 (그냥 ㄴㄴ 효율적으로 ㅇㅇ)

따라서 한 열씩 퀸을 배치해보되, 같은 행에는 퀸을 배치할 수 없으며, 대각선에도 퀸을 배치할 수 없는 사실을 알았어야 하고

퀸의 좌표를 2차원이 아닌 1차원 배열에 저장할 줄 알며, x좌표 차와 y좌표 차가 같을 때 대각선에 위치함 (대각선 배치를 효율적으로 구분할 수 있어야 함)을 알았어야 한다.

알고리즘을 하나씩 정복한다고 했어도 배운 것에 대해, 틀에 갖혀있지 않고 효율적인 방법, 그 안에 있는 규칙을 먼저 떠올리는 연습을 해야한다...

[wooyn730]

암호 만들기

번호: 1759 사이트: 백준 난이도: 골드5

풀이

• 링크 (02/29)

---

처음엔 조건에 맞게 모음1 자음2를 먼저 선택하고 나머지를 뽑아야하나? 싶었지만 꼬아서 생각하지 않고 완탐 후 조건에 맞으면 출력하게 했더니 무난하게 1트 성공했다.

[wooyn730]

좋은수열

번호: 2661 사이트: 백준 난이도: 골드4

풀이

• 링크

---

이 꼴이 난 이유

1. 백트래킹 안쓰고도 풀 수 있을 줄 (바보)
2. vector에 넣었다 뺐다가, 매번 string을 만드는 비용을 생각 안함

[wooyn730]

리모컨

번호: 1107 사이트: 백준 난이도: 골드5

풀이

• 링크

---

솔직히 어려운 문제는 아니었음 예외처리를 잘 못해줘서 많이 틀림..

1) 답이 3자릿수면 2자릿수, 4자릿수와도 비교해줘야함 2) 0을 무한으로 선택해서 return 안되는 것 주의 <= 0 때문에 오래 걸림