브루트포스, BFS, DFS, 백트래킹

Jimin·2023년 7월 23일
알고리즘
0

알고리즘

목록 보기
71/71

브루트포스

  • 모든 문제를 푸는데 있어, 가장 단순하고 무식한 알고리즘
  • 그냥 모든 경우의 수를 확인하는 알고리즘
  • 절대 틀릴리는 없지만, 시간 복잡도 성능이 낮다.
  • 제한을 먼저 확인하고, 브루트포스를 가장 먼저 생각해보기.

브루트포스 문제

프로그래머스 모의고사

max(n1, n2, n3)
def solution(answers):
    answer = []
    people = {}
    people['m1'] = [[1, 2, 3, 4, 5], 5, 0]
    people['m2'] = [[2, 1, 2, 3, 2, 4, 2, 5], 8, 0]
    people['m3'] = [[3, 3, 1, 1, 2, 2, 4, 4, 5, 5], 10, 0]
    
    for i in range(len(answers)):
        for p in people:
            Len = people[p][1]
            if people[p][0][i%Len] == answers[i]:
                people[p][2] += 1
    
    M = max(people['m1'][2], people['m2'][2], people['m3'][2])
    
    if people['m1'][2] == M:
        answer.append(1)
    if people['m2'][2] == M:
        answer.append(2)
    if people['m3'][2] == M:
        answer.append(3)
        
    return answer

프로그래머스 카펫

def solution(brown, yellow):
    answer = []
    C = 0
    R = 0
    for row in range(1, brown + 1):
        for col in range(1, brown + 1):
            if (col * 2 + (row-2) * 2) == brown and (row*col - brown) == yellow:
                answer.append(col)
                answer.append(row)
                return answer

규칙 찾기
1. 갈색 개수: 2*세로 + 2*(가로-2) = 갈색 개수
2. 노란색 개수: 가로*세로-갈색
3. for 문 돌려서 모든 경우의 세로의 길이와 가로의 길이를 찾아야 함

1억번의 연산이 1초가 걸린다.

그래프

  • 노드
  • 간선

유향 그래프

그래프에 방향이 존재한다.

무향 그래프

그래프에 방향이 존재하지 않는다.

그래프 구현 방법

1. 인접 행렬

2. 인접 리스트

  • 각 노드가 이동할 수 있는 노드만 저장한다.
  • 인접 리스트가 더 많이 사용된다.
adj = [[] for i in range(5)]

DFS

  • 그래프 탐색 알고리즘의 한 종류
  • 모든 정점을 한 번씩 탐색하는 것
  • 깊이 우선 탐색 알고리즘의 약자이다.
  • 어떤 특정 노드 언제 방문하는가? 를 구하는 것이 목적
  • 어떤 특정 노드를 기준으로 탐색하는데, 깊이 를 기준으로 수행한다.
  • 한번 방문한 노드는 다시 방문하지 않는다.
  • 스택 자료구조를 구현한다.
# 각 노드가 방문한 정보를 리스트 자료형으로 표현
visited = [False]*N
stack = []

# graph는 연결 리스트(인접리스트)가 제공된다고 가정
def dfs(graph, start): 
	# start는 시작 위치이기 때문에 방문했다고 표시
    # start부터 그래프 탐색을 진행하기 위해 stack에 start 노드를 추가
    visited[start] = True
    stack.append(start)
    
    while len(stack) != 0:
    	# 스택의 마지막에 있는 노드를 기준으로 탐색 진행
        current = stack.pop()
        for next in graph[current]:
        	if visited[next] == False:
            	visited[next] = True
                stack.append(next)

dfs(graph, 1)

DFS 요약

  1. DFS 는 깊이를 우선으로 탐색하는 알고리즘이다.
  2. 노드의 개수를 V, 간선의 개수를 E라고 할 때,
    • 인접 행렬 방법의 시간복잡도 = O(V^2) (노드의 개수의 제곱)
    • 인접 리스트 방법의 시간복잡도 = O(V+E) (노드의 개수 + 간선의 개수)
  3. DFS 알고리즘은 스택을 사용하여 구현한다.
  4. 각 정점을 한 번씩 방문하는 과정에서 해당 정점과 연결된 간선을 스택에 추가한다.

DFS 문제

백준 바이러스

N = int(input()) # 컴퓨터 개수
visited = [False]*(N+1)
M = int(input()) # 네트워크 상에서 직접 연결되어 있는 컴퓨터 쌍의 수
stack = []
con = [[] for i in range(N+1)]
for i in range(M):
    a, b = map(int, input().split())
    con[a].append(b)
    con[b].append(a)

visited[1] = True
stack.append(1)
cnt = 0
while len(stack) !=0:
    cur = stack.pop()
    for next in con[cur]:
        if visited[next] == False:
            visited[next] = True
            stack.append(next)
            cnt += 1

print(cnt)

단방향이 아니라 양방향이라는 걸 생각해야한다.

BFS

  • 그래프 탐색 알고리즘의 한 종류이다.
  • 너비 우선 탐색 알고리즘의 약자이다.
  • 어떤 특정 노드를 언제 방문하는가? 를 구하는 것 이 목적이다.
  • 모든 곳을 똑같이 조금씩 조금씩 파며 내려간다.
  • 어떤 특정 노드를 기준으로 탐색을 진행하는데, 너비 를 기준으로 수행한다.
  • 큐 자료구조로 구현한다.

BFS 의 코드

from collections import deque

# 각 노드가 방문한 정보를 리스트 자료형으로 표현
visited = [False]*N
queue = deque()

# graph는 연결리스트가 제공된다고 가정
def bfs(graph, start):
	
    # start는 시작 위치이기 떄문에 방문했다고 표현
    # start부터 그래프 탐색을 진행하기 위해 queue에 start 노드를 추가
    visited[start] = True
    queue.append(start)
    
    # 큐가 빌 때까지 탐색을 진행
    while len(queue) != 0:
    	# 큐의 첫번째 노드를 기준으로 탐색 진행
        current = queue.pop()
        
        for next in graph[current]:
        	if visited[next] == False:
            	visited[next] = True
                queue.append(next)

bfs(graph, 1)

BFS 의 요약

  1. BFS는 너비를 우선으로 탐색하는 알고리즘
  2. 노드의 개수를 V, 간선의 개수를 E라고 할 때
    • 인접 행렬 방법의 시간복잡도 = O(V^2)
    • 인접 리스트 방법의 시간복잡도 = O(V+E)
  3. DFS 알고리즘은 큐를 사용하여 구현한다.
  4. 각 정점을 한 번씩 방문하는 과정에서 해당 정점과 연결된 간선을 큐에 추가한다.

BFS 문제

프로그래머스 게임 맵 최단 거리

from collections import deque

visited = [[-1 for i in range(100)] for j in range(100)]
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]

q = deque()
    
def solution(maps):
    answer = 0
    q.append([0, 0])
    visited[0][0] = 1
    N, M = len(maps), len(maps[0])
    
    while len(q) != 0:
        curr = q.popleft()
        x, y = curr[0], curr[1]
        for i in range(4):
            next_x = x +dx[i]
            next_y = y + dy[i]
            if 0 <= next_x and next_x < N and 0 <= next_y and next_y < M:
                if visited[next_x][next_y] == -1 and maps[next_x][next_y] != 0:
                    visited[next_x][next_y] = visited[x][y] +1
                    q.append([next_x, next_y])
        
    
    return visited[N-1][M-1]
  • 이동할 수 있는 각 칸을 노드로 본다.
  • 인접한 빈칸은 간선으로 연결되어 있다고 본다.

⇒ 그래프 탐색을 수행할 수 있다.

시작 노드로부터 목표 노드까지 거리를 최단 거리를 찾아야 한다.
⇒ 시작 노드 (1,1) 부터 시작하여 (N, M)까지의 최단 거리가 K 라고 구할 수 있다.

  • visited = [[-1 for i in range(100)] for j in range(100)]
  • dx = [-1, 1, 0, 0]
  • dy = [0, 0, -1, 1]
  1. visited, dx, dy, queue 생성하기
  2. 시작 값 정해주기
  3. while 문 돌리기
    • 현재값 pop
    • 4가지 방향의 곳으로 이동시키기
    • 좌표 범위 확인할 것
    • 방문 했는지, maps 를 통해 벽인지 아닌지 확인할 것

백트래킹

  • 브루트포스(완전탐색)의 한 종류
  • 현재 상태에서 가능한 모든 후보군을 따라 들어가며 탐색하는 알고리즘
  • 재귀 를 이용해서 구현한다.

백트래킹 문제

백준 15649 N과 M(1)

N, M = map(int, input().split())
num = [i + 1 for i in range(N)]
visited = [False]*N
answer = []
def dfs(cnt):
    # print(answer)
    if cnt == M:
        print(*answer)
        return
    for i in range(N):
        if visited[i] == True:
            continue
        visited[i] = True
        answer.append(num[i])
        dfs(cnt + 1)
        answer.pop()
        visited[i] = False
dfs(0)

연습문제

프로그래머스 최소직사각형

  1. 각 명함의 가로 세로 길이 비교해서 더 큰값 X, 더 작은 값 Y
  2. X 값 중 가장 큰 값
  3. Y 값 중 가장 큰 값
  4. X*Y가 정답

프로그래머스 네트워크

백준 N과 M (2)

프로그래머스 미로 탈출

프로그래머스 이모티콘 할인행사

profile
Jimin
https://github.com/Dingadung
이전 포스트

시간복잡도, 자료구조, 정렬

1개의 댓글

comment-user-thumbnail
happy
2023년 7월 23일

유익한 글이었습니다.

답글 달기