전체 글
0528_백준 1753번 : 최단경로/ 다익스트라(Dijkstra) 알고리즘/ Python
[문제 풀이] ✔ 주어진 시작점에서 모든 정점으로의 최단 경로 값을 구하는 문제 => 다익스트라(dijksta) 알고리즘 활용 ✔ 우선순위큐를 활용하기 위해 heapq 모듈을 불러와 사용함 (heappop, heappush 사용) ✔heapq 모듈 특성상, pop하게 되면 가장 작은 값을 가진 원소가 리턴되기 때문에 힙에 원소를 저장할 때 '경로값(cost), 노드(node)' 순으로 넣어야 다익스트라 알고리즘에서 원하는 결과를 얻을 수 있다. 왜냐면 경로값을 기준으로 최단 경로를 찾아 나가야 하는 로직이기 때문이다. 처음에 이 부분을 간과하여 노드, 경로값 순으로 넣었다가 계속해서 에러가 발생했다. (도움주신 덕봇기님 감사합니다😁🙌) [코드 구현] import heapq import sys input ..
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를 넣어주..
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..
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=' ') ..
0522_백준 1922번 : 네트워크 연결/ 최소신장트리 MST/ Prim 알고리즘/ Python
오늘 싸피 라이브강의에서 배운 개념인 최소신장트리(MST)는 크게 두 가지 알고리즘으로 구현할 수 있는데, 프림과 크루스칼이다. ① Prim 알고리즘 -> 시작점에서 끝점까지 단계적으로 확장, 정점 선택을 기준으로 최적 해 찾기 ② Kruskal 알고리즘 -> 가중치를 간선에 할당, 간선 선택을 기준으로 최적 해 찾기 기본적으로 MST는 네트워크(가중치를 간선에 할당한 그래프)에 있는 모든 정점들을 가장 적은 수의 간선과 비용으로 연결하는 로직인데, 이번 문제에서는 간선은 고려하지 않고 최소 비용을 구하는 유형이었다. MST의 주요 사례는 통신망, 도로망, 유통망에서 비용이나 전송시간, 길이 등을 최소로 구하는 경우이다. 아래는 프림 알고리즘과 관련있는 문제 풀이👇 [문제 풀이] - 최소신장트리로 풀이하..
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이 주어지고, 둘째 줄에는 촌수를 계산해야 하는..
0520_백준 17142번 : 연구소 3 / BFS 알고리즘/ Python
[문제 접근] - BFS(너비우선탐색)으로 최단 시간 구하는 문제(바이러스가 확산되며 1씩 증가하는 형태) - itertools 모듈에서 chain 불러오기, list(sum(arr, [ ])) 보다 list(chain(*arr))이 속도는 더 빠름. - 처음에는 바이러스 위치를 정하는 조합을 함수로 구현하려다가 실패한 후, 결국 itertools 모듈 콤비네이션을 활용함 - deepcopy로 배열을 똑같이 만들어도 되나, 이번 코드에서는 새로운 배열을 하나 만들었다. - 문법체크✔ ① print(min(res) if res else -1) : res에 값이 있으면 (True) ->min(res) 출력, 값이 없다면(False) -> -1 출력 ② 2차원 배열 1차원 리스트로 합치기 : list(sum(..
0519_백준 15683번: 감시 / 브루트 포스 알고리즘
[문제 접근] - 모든 경우의 수를 대입해보는 브루트 포스(Brute Force) 알고리즘 문제. - dfs로 완전탐색하는 코드 구현, 효율이 굉장히 낮아 pypy로 제출하여 통과함. - cctv 종류마다 탐색할 수 있는 모든 방향을 리스트에 담아 확인함. - 모든 경우의 수에서 탐색하며 감시가 가능한 영역을 표시하고 사각지대의 최소값을 확인해야 하기 때문에, deepcopy 배열을 활용함. [코드 구현] from copy import deepcopy import sys # 감시 가능 영역 표시하기 -> 영역 표시는 copy 배열에 def office(x, y, temp, d): for i in d: nx, ny = x, y while True: nx += dx[i] ny += dy[i] if 0