본문 바로가기

Algorithm/Baekjoon52

0528_백준 1753번 : 최단경로/ 다익스트라(Dijkstra) 알고리즘/ Python [문제 풀이] ✔ 주어진 시작점에서 모든 정점으로의 최단 경로 값을 구하는 문제 => 다익스트라(dijksta) 알고리즘 활용 ✔ 우선순위큐를 활용하기 위해 heapq 모듈을 불러와 사용함 (heappop, heappush 사용) ✔heapq 모듈 특성상, pop하게 되면 가장 작은 값을 가진 원소가 리턴되기 때문에 힙에 원소를 저장할 때 '경로값(cost), 노드(node)' 순으로 넣어야 다익스트라 알고리즘에서 원하는 결과를 얻을 수 있다. 왜냐면 경로값을 기준으로 최단 경로를 찾아 나가야 하는 로직이기 때문이다. 처음에 이 부분을 간과하여 노드, 경로값 순으로 넣었다가 계속해서 에러가 발생했다. (도움주신 덕봇기님 감사합니다😁🙌) [코드 구현] import heapq import sys input .. 2020. 5. 28.
0527_ 백준 11725번 : 트리의 부모 찾기/ DFS / Python [문제 풀이] - DFS(깊이우선탐색)으로 주어진 트리에서 노드의 부모를 찾는 문제 - 루트 1부터 시작해서 순차적으로 모든 노드의 부모를 찾아나가는 로직 - 처음에는 1부터 시작해서 목표로 하는 노드까지 찾아 내려가 부모를 찾는 로직을 짰다가, 런타임 에러가 나서 해결하지 못하고 코드를 수정하였다 => 1부터 시작해 중복 없이 모든 노드의 부모를 리스트로 저장했고, 덕분에 방문했는지 확인하는 VISIT 리스트도 생략할 수 있었다. [코드 구현] import sys input = sys.stdin.readline def dfs(adj, start, parent): s = [start] while s: tmp = s.pop() for i in adj[tmp]: # 부모 리스트에 i의 부모로 tmp를 넣어주.. 2020. 5. 27.
0526_백준 1759번 : 암호 만들기/ 완전탐색/ Python [문제 풀이] - 완전 탐색 문제 - 암호 후보를 만드는 dfs함수와 가능한 암호만을 출력하는 함수 두 가지를 구현 - itertools 모듈의 combinations 으로 구할 수도 있음 [코드 구현] # 암호 후보들을 만드는 함수 def dfs(l, c, k, idx): if (k == l): # 주어진 l 크기가 되면 암호 후보를 결과 리스트에 추가 res_lst.append(''.join(res)) return else: for i in range(c): if (visit[i] == 0 and idx = 1 and c_cnt >= 2: print(a) vowels = ['a', 'e', 'i', 'o', 'u'] l, c = map(int, input().split()) alphabets = so.. 2020. 5. 26.
0525_백준 7568번 : 덩치 & 백준 10448번 : 유레카이론 / Python *완전탐색문제 백준 7568번 덩치 : https://www.acmicpc.net/problem/7568 7568번: 덩치 우리는 사람의 덩치를 키와 몸무게, 이 두 개의 값으로 표현하여 그 등수를 매겨보려고 한다. 어떤 사람의 몸무게가 x kg이고 키가 y cm라면 이 사람의 덩치는 (x,y)로 표시된다. 두 사람 A 와 B의 덩� www.acmicpc.net wh_lst =[] for i in range(int(input())): wh_lst.append(list(map(int, input().split()))) for i in wh_lst: rank = 1 for j in wh_lst: if i[0] < j[0] and i[1] < j[1]: rank += 1 print(rank, end=' ') .. 2020. 5. 25.
0522_백준 1922번 : 네트워크 연결/ 최소신장트리 MST/ Prim 알고리즘/ Python 오늘 싸피 라이브강의에서 배운 개념인 최소신장트리(MST)는 크게 두 가지 알고리즘으로 구현할 수 있는데, 프림과 크루스칼이다. ① Prim 알고리즘 -> 시작점에서 끝점까지 단계적으로 확장, 정점 선택을 기준으로 최적 해 찾기 ② Kruskal 알고리즘 -> 가중치를 간선에 할당, 간선 선택을 기준으로 최적 해 찾기 기본적으로 MST는 네트워크(가중치를 간선에 할당한 그래프)에 있는 모든 정점들을 가장 적은 수의 간선과 비용으로 연결하는 로직인데, 이번 문제에서는 간선은 고려하지 않고 최소 비용을 구하는 유형이었다. MST의 주요 사례는 통신망, 도로망, 유통망에서 비용이나 전송시간, 길이 등을 최소로 구하는 경우이다. 아래는 프림 알고리즘과 관련있는 문제 풀이👇 [문제 풀이] - 최소신장트리로 풀이하.. 2020. 5. 22.
0521_백준 2644번 : 촌수계산 & 11724번 : 연결 요소의 개수/ BFS와 DFS 연습/ Python 오늘 라이브 강의에서는 그래프 유형의 알고리즘에 대해서 배웠다. 그래프를 표현하는 방법으로 인접행렬, 인접리스트를 학습하고 나아가 그래프를 탐색하는 방법인 DFS(깊이우선탐색)과 BFS(너비우선탐색)을 연습했다. 수업이 끝나고 이와 관련된 백준 문제를 정리해봤다👇 난이도는 높지 않지만 11724번 연결 요소의 개수는 python으로 제출하면 시간초과가 나서 pypy로 통과했다😂 "BFS(너비우선탐색) 유형" [문제 출처] 백준 2644번 촌수계산 https://www.acmicpc.net/problem/2644 2644번: 촌수계산 사람들은 1, 2, 3, …, n (1≤n≤100)의 연속된 번호로 각각 표시된다. 입력 파일의 첫째 줄에는 전체 사람의 수 n이 주어지고, 둘째 줄에는 촌수를 계산해야 하는.. 2020. 5. 21.

티스토리툴바