본문 바로가기

algorithm87

[BF] 브루스 포스 알고리즘의 개념 Brute Force 알고리즘이란 ? 복잡한 알고리즘을 굳이 생각하지않고, 컴퓨터의 빠른 연산력을 이용해 모든 경우를 전부 탐색하는 알고리즘을 의미합니다. brute force, BF, 완전탐색(exhaustive search), 완탐 정도로 불립니다. 최악의 경우라도 모든 경우를 컴퓨터로 살펴보기에 문제가 없다면 단순히 모든 경우를 살펴보면 됩니다. 단순히 모든 경우를 보는것도 하나의 알고리즘이라 할 수 있습니다. 결국 알고리즘으로 치자면 가장 쉬운 알고리즘이나, 활용 방법에 따라 최고의 효율을 보여줄 수 있는게 brute force 입니다. (컴퓨터로 적정한 시간내에 처리될 만한 수준의 데이터라면, 복잡하게 시간들여 생각할 것 없이 전부 탐색해보면 되기 때문) Brute Force 알고리즘의 종류 .. 2023. 5. 2.
[백준 2293번] 동전1 n, k = map(int,input().split()) # 1차원 DP 테이블을 사용한 풀이 prices = [0] * n for i in range(n): prices[i] = int(input()) # dp[i] -> i원을 만들 때 가능한 경우의 수 dp = [0 for _ in range(k+1)] # dp[0] -> 0원을 만들 때 가능한 경우의 수, 동전을 사용하지 않는 경우 이므로 1로 초기화 dp[0] = 1 for price in prices: for i in range(price,k+1): dp[i] = dp[i] + dp[i-price] print(dp[k]) # 2차원 DP 테이블를 사용한 풀이(시간초과) # prices = [0] * (n+1) # for i in range(1,.. 2023. 4. 11.
[백준 1520번] 내리막 길 import sys sys.setrecursionlimit(50000000); m, n = map(int,input().split()) area = [list(map(int,input().split())) for _ in range(m)] dp = [[-1]*n for _ in range(m)] nx, ny = [-1,1,0,0], [0,0,-1,1] def dfs(x,y): # 도착 지점에 도달하면 1 리턴 if x == (m-1) and y == (n-1): return 1 # 이미 방문한 길이라면 경우의 수를 구하지 않고 해당 위치에서 출발하는 경우의 수 리턴 if dp[x][y] != -1: return dp[x][y] way_count = 0 for i in range(4): temp_x = x.. 2023. 4. 10.
[백준 2583번] 영역 구하기 from collections import deque m,n,k = map(int,input().split()) area = [[0]*n for _ in range(m)] visited = [[False]*n for _ in range(m)] count_list = [] for i in range(k): x1, y1, x2, y2 = map(int,input().split()) for j in range(y1,y2): for k in range(x1,x2): area[j][k] = 1 def bfs(x,y): if visited[x][y] or area[x][y] == 1: return False count = 1 queue = deque([(x,y)]) visited[x][y] = True while .. 2023. 4. 6.
[백준 11725번] 트리의 부모 찾기 import sys sys.setrecursionlimit(50000000); n = int(input()) graph = [[] for _ in range(n+1)] result = [0]*(n+1) visited = [False]*(n+1) for _ in range(n-1): a, b = map(int,input().split()) graph[a].append(b) graph[b].append(a) def dfs(graph,v,visited): visited[v] = True for i in graph[v]: if not visited[i]: result[i] = v dfs(graph,i,visited) dfs(graph,1,visited) for i in range(2,n+1): print(res.. 2023. 4. 6.
[백준 2565번] 전깃줄 n = int(input()) data = [] dp = [1]*n for _ in range(n): data.append(list(map(int,input().split()))) data.sort(key=lambda x:x[0]) for i in range(1,n): for j in range(i): if data[i][1] > data[j][1]: dp[i] = max(dp[i], dp[j]+1) print(n-max(dp)) 이번 문제는 A와 B 전봇대 사이에 연결된 전깃줄의 정보와 전깃줄의 개수가 주어졌을 때, 모든 전깃줄이 서로 교차하지 않도록 하기 위해 제거해야 하는 전깃줄의 최소 개수를 구하는 문제이다. 처음에 이 문제를 접했을 때 이전에 풀던 DP 방식(n=1 부터 구하면서 점화식을 찾는 .. 2023. 3. 25.

티스토리툴바