본문 바로가기

Algorithm 💡272

[DFS] DFS 알고리즘의 기본 개념 및 활용법 DFS DFS는 Depth-First Search, 깊이 우선 탐색이라고 부르며 그래프에서 깊은 부분을 우선적으로 탐색하는 알고리즘이다. 그래프의 기본 구조: 노드(Node) or 정점(Vertex) 간선(Edge) 그래프의 탐색이란 하나의 노드를 시작으로 다수의 노드를 방문하는 것을 말한다. 또한 두 노드가 간선으로 연결되어 있다면 두 노드는 인접(Adjacent)하다고 표현한다. 프로그래밍에서는 그래프를 크게 2가지 방식으로 표현할 수 있는데, 코딩테스트에서는 이 2가지 방식 모두 필요하니 두 개념에 대해 확실하게 알고 있도록 하자. 인접 행렬(Adjacency Matrix) : 2차원 배열로 그래프의 연결 관계를 표현하는 방식 인접 리스트(Adjacency List) : 리스트로 그래프의 연결 관계.. 2023. 2. 10.
[백준 3109번] 빵집 import sys input = sys.stdin.readline r,c = map(int,input().split()) area = [] result = 0 for _ in range(r): area.append(list(input().strip())) dx = [-1,0,1] dy = [1,1,1] def dfs(x,y): global result area[x][y] = 'o' if y == c-1: result += 1 return True for k in range(3): nx = x + dx[k] ny = y + dy[k] if 0 2023. 2. 9.
[백준 2217번] 로프 n = int(input()) solution = 0 weight_list = [] for i in range(n): weight_list.append(int(input())) weight_list.sort() list_len = len(weight_list) for i in range(list_len): temp = (list_len-i)*weight_list[i] if temp > solution: solution = temp print(solution) 이번 문제는 로프의 개수를 임의로 정하여 로프가 버틸 수 있는 최대 중량을 구하는 문제이다. 이 문제의 핵심은 로프들을 사용하여 각 로프가 w/k 만큼의 중량이 걸리게 된다면, 아무리 평균이 높더라도 결국 (각 로프 중량의 최소 값 * 나머지 로프의.. 2023. 2. 9.
[백준 5585번] 거스름돈 n = int(input()) change = 1000 - n money_unit = [500,100,50,10,5,1] count = 0 for i in money_unit: if change//i > 0: count += (change//i) change %= i print(count) 이번 문제는 그리디 알고리즘의 대표적인 기본 문제로, 그리디 알고리즘을 처음 공부할 때 내용을 이해하기 좋은 문제이다. 이 문제의 핵심은 잔돈을 최대한 적은 개수의 잔돈으로 거슬러주는 것인데, 위 문제와 같은 경우에는 모든 돈의 단위가 서로 배수 관계를 가지고 있기 때문에 단순히 금액이 큰 순서대로 거슬러 주어도 문제없이 풀 수 있다. 만약에 잔돈이 800원이고 가진 돈의 단위가 [500, 400, 100] 이라면 단.. 2023. 2. 8.
[백준 1541번] 잃어버린 괄호 expression = input() # '-'를 기준으로 분할 # ex) ['00009','00009+00008'] split_exp = expression.split('-') for i in range(len(split_exp)): # 분할된 문자열들을 순서대로 '+'를 기준으로 분할 후 합을 구하기(내부는 +로만 이루어져 있기 때문) # 그리고 동시에 앞에 0으로 채워진 문자열들을 정수화 시킨다 # ex) [9, 17] split_plus = list(map(int,split_exp[i].split('+'))) split_exp[i] = sum(split_plus) # 첫 번째 원소를 제외한 나머지 원소들은 '-'를 기준으로 파싱되었기 때문에 모두 빼주면 된다. # ex) 9 - 17 print(s.. 2023. 2. 8.
[백준 1026번] 보물 n = int(input()) a = list(map(int,input().split())) b = list(map(int,input().split())) a.sort() a_resort = [0] * n b_index = [] for i in range(n): b_index.append((i,b[i])) b_index.sort(key=lambda x:-x[1]) for i in range(n): a_resort[b_index[i][0]] = a[i] sum = 0 for i in range(n): sum += (a_resort[i] * b[i]) print(sum) 이번 문제는 전형적인 Greedy 알고리즘 문제로 난이도는 크게 어렵지 않았다. 이 문제의 핵심은 배열 A의 원소와 B의 원소간의 곱이 최.. 2023. 2. 7.

티스토리툴바