완전 탐색(브루트 포스)
- 모든 경우의 수를 시도하는 방법
- 경우의 수가 매우 많아지는 문제에 대해서는 제한 시간 내에 해결이 힘들 수 있다.
완전 탐색을 사용하는 경우
- 입력으로 주어지는 데이터의 크기가 작은 경우
- 답의 범위가 작고, 임의의 답을 하나 선택했을 때 문제 조건을 만족하는지 역추적할 수 있는 경우
사용되는 알고리즘 기법
- 단순 브루트 포스
- 단순히 반복문과 조건문을 사용하는 방법이다.
- 난이도가 높은 문제에서 단독으로 사용되는 경우는 거의 없다.
- 비트마스크(Bitmask)
- 2진수를 이용하는 컴퓨터의 연산을 이용하는 방법이다.
- 각 요소가 두 가지 상태만을 가질 수 있을 때 사용한다.
- 각 원소가 포함되는지 0 or 1(존재하지 않는 경우 or 존재하는 경우) 등으로 구분하여 저장하는 식으로 사용할 수 있다.
- 재귀 함수
- 자기 자신을 호출하는 재귀 함수를 사용하는 방법이다.
- 조건을 만족하면 함수를 호출하고, 아니면 호출하지 않는 식으로 사용할 수 있다.
- 순열
- 서로 다른 N개를 일렬로 나열하는 방법을 말한다.
- 순열에 원소를 하나씩 채워가는 방식으로 사용할 수 있다.
- BFS/DFS
- 길 찾기에 주로 사용하는 방법으로, 추가적 연산(장애물 등)이 필요할 때 완전탐색을 병용하기도 한다.
- 주로 모든 경로를 확인할 때는 DFS, 최단 경로를 확인할 때는 BFS를 주로 사용한다.
- https://comhwang.tistory.com/19
[알고리즘] DFS/BFS
그래프 탐색 정점(node)와 그 정점을 연결하는 간선(edge)으로 이루어진 자료구조를 의미합니다. 그래프를 탐색한다는 것은 하나의 정점으로부터 시작해 차례대로 모든 정점들을 한번씩 방문하는
comhwang.tistory.com
완전탐색 문제
프로그래머스 Lv1. 최소 직사각형
https://school.programmers.co.kr/learn/courses/30/lessons/86491
프로그래머스
코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.
programmers.co.kr
def solution(sizes):
answer = 0
list2 = list(map(lambda x: [x[1],x[0]] if x[1]>x[0] else [x[0],x[1]],sizes))
max_val = [0,0]
for a,b in list2 :
if max_val[0] < a :
max_val[0] = a
if max_val[1] < b :
max_val[1] = b
answer = max_val[0] * max_val[1]
return answer
프로그래머스 Lv1. 모의고사
https://school.programmers.co.kr/learn/courses/30/lessons/42840
프로그래머스
코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.
programmers.co.kr
def solution(answers):
answer = []
students = [[1,2,3,4,5], [2,1,2,3,2,4,2,5], [3,3,1,1,2,2,4,4,5,5]]
students_answer = [0,0,0]
for i in range(3):
for j in range(len(answers)) :
if answers[j] == students[i][j%len(students[i])] :
students_answer[i]+=1
max_value = max(students_answer)
for i in range(3) :
if students_answer[i] == max_value :
answer.append(i+1)
return answer
프로그래머스 Lv2. 전력망을 둘로 나누기
https://school.programmers.co.kr/learn/courses/30/lessons/86971
프로그래머스
코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.
programmers.co.kr
from collections import deque
def solution(n, wires):
answer = n
# {1 : [1,2], 2: [3,4]} 등으로 각 송전탑과 이어진 송전탑의 관계 그래프를 만드는 코드
graph_arr = [[] for _ in range(n)]
for x,y in wires :
graph_arr[x-1].append(y)
graph_arr[y-1].append(x)
graph_dict = {i+1 : graph_arr[i] for i in range(n)}
# 각각의 wire를 끊었을 때 나뉘는 두 전력망 수의 차이를 bfs로 구현
for x,y in wires :
# 방문여부와 해당 wire를 끊었을때 한쪽의 전력망 수를 저장할 변수
visited = [0]*(n+1)
visited[x] = 1
cnt=1
graph_dict[x].remove(y)
graph_dict[y].remove(x)
queue = deque([x])
while queue :
cur = queue.popleft()
for nx in graph_dict[cur] :
if not visited[nx] :
queue.append(nx)
cnt+=1
visited[nx]=1
if abs(cnt - (n-cnt)) < answer :
answer = abs(cnt - (n-cnt))
# 끊었던 wire 복구
graph_dict[x].append(y)
graph_dict[y].append(x)
return answer
프로그래머스 Lv2. 모음사전
https://school.programmers.co.kr/learn/courses/30/lessons/84512
프로그래머스
코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.
programmers.co.kr
def solution(word):
answer = 0
list_char = ['A', 'E', 'I', 'O', 'U']
# 문자의 인덱스별 증가하는 양
# 경우의 수가 AEIOU 에 공백이 있다 : x5+1
list_up = [781,156,31,6,1]
# 문자를 하나씩 가져와 계산한 값을 answer에 더해준다.
for i in range(len(word)) :
answer+=list_char.index(word[i])*list_up[i]+1
return answer
'알고리즘 > 알고리즘 설명 및 예제' 카테고리의 다른 글
| [알고리즘] DFS/BFS (4) | 2023.04.08 |
|---|---|
| [알고리즘] 스택/큐 (2) | 2023.04.08 |
| 시간 복잡도 (1) | 2023.04.08 |
| [알고리즘] 그리디 알고리즘 (2) | 2023.04.07 |
| [알고리즘] 투 포인터 알고리즘 (1) | 2023.04.07 |