Algorithm/Baekjoon
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
0518_백준 11403번 : 경로찾기 / 플로이드-워셜 알고리즘
[문제 풀이] 이번 경로찾기 문제는 전형적인 DFS문제이다. 처음 예제를 확인할 때는 주어진 정점 간의 연결 상태를 파악하는 게 다소 이해가 안 갔는데, '플로이드-워셜 알고리즘'을 통해 간단하게 문제를 해결할 수 있었다. 플로이드-워셜 알고리즘(Floyd-Warshall Algorithm)은 그래프에서 가능한 모든 노드 쌍에 대해 최단 거리를 구하는 알고리즘이다. 임의의 노드 s에서 e까지 가는 데 걸리는 최단거리를 구하기 위해, s와 e 사이의 노드인 m에 대해 s에서 m까지 가는 데 걸리는 최단거리와 m에서 e까지 가는 데 걸리는 최단거리를 이용한다. (출처_나무위키https://namu.wiki/w/%ED%94%8C%EB%A1%9C%EC%9D%B4%EB%93%9C-%EC%9B%8C%EC%85%9C..
0514_백준 14890번/경사로_파이썬
"가로 세로 모두 확인해야 함, zip으로 전치행렬 활용" 새로 써본 것은 ziiiiiiip! [풀이 과정] - 특별한 알고리즘 없이 주어진 조건을 빠짐없이 고려하여 푸는 문제 - 가로행, 세로열 두번 탐색해야 해서 -> zip 함수 활용 zip(*iterable)은 동일한 개수로 이루어진 자료형을 묶어 주는 역할을 하는 함수 - 내가 고려한 조건들은 아래와 같다. ① 경사로를 놓는 방법을 크게 '높은 곳에서 낮은 곳으로 향하는 것', '낮은 곳에서 높은 곳으로 향하는 것' 두 가지로 나눔. 그리고 경사 높이 차이를 비교 -> 1차이가 나는지 확인 ② 범위를 벗어나지 않게 인덱스 위치 확인 ③ 경사로를 놓았는지 확인해주기 위해 visit 배열 활용 - 한 행, 한 열씩 돌아가며 길이 되는지 확인하는데 이..
0513_백준 14891번/ 톱니바퀴_파이썬
"deque 모델의 rotate 메소드 사용하기" [문제 접근] - 처음에는 주어진 톱니바퀴 번호에 따라 분기처리 하여 하드코딩 했다가, 중간에 실패했다. 이유는 톱니바퀴 4개가 한번에 돌아야 하는데 내가 구현한 코드는 순차적으로 돌아가다 중간에 끊겨서 제대로 된 결과를 얻기 힘들었다. - 타 블로거님들의 코드를 참고하여 다시 풀었는데, collections 모듈의 deque(double ended queue)의 rotate 메소드를 활용했다. - rotate의 기본적인 구조 : rotate(n) 요소 n의 값에 따라 음수면 n만큼 왼쪽 회전, 양수면 n만큼 오른쪽 회전(시계방향) - 시작 톱니를 잡아 ①12시 방향을 기준으로 2번, 6번에 위치한 톱니의 극(1 또는 0) 정보와 ② 회전방향(시계 또는 ..
0512_백준/14499번/주사위 굴리기_파이썬
[문제 접근 방법] - 특별한 알고리즘이 있지 않고, 주어진 상황을 코드로 구현하는 문제였다. - 기본적인 로직은 주어진 명령의 방향에 따라 주사위의 면을 바꿔주는 것이다. - 기타 조건으로는 배열의 인덱스 에러 여부를 확인해주는 것 그리고 지도 위의 이동 칸이 0인지 아닌 지에 따라 주사위면과 이동칸의 숫자를 바꿔주는 로직을 넣어줘야 했다. - 주어진 상황을 빠짐 없이 조건으로 넣어주면 풀 수 있는 문제 [피드백] - 주사위의 윗면과 아랫면이 정해져 있는데, 처음에 문제를 잘못 읽어서 아랫면이 1이라고 착각했었다. - 주사위의 면을 방향에 따라 어떻게 바꿔줄지를 많이 고민했지만, 결국 하드 코딩으로 작성했다. [코드 구현] n, m, x, y, k = map(int, input().split()) ar..