백준

[python] 백준 - 5014. 스타트링크

🤔문제 해결 G5 | BFS, 그래프 갈 수 있는 길이 2가지인 BFS 문제. 한 지점에서 올라가거나 내려가거나 하면서 원하는 층에 도착할 수 있는지 판별한다. 최초 시작점 S에서 올라가거나(U) 내려간다(D) 만약 올라갈 때 건물의 높이보다 높으면 못올라가고, 내려갈 때 1층보다 낮으면 못내려간다. 또 visited리스트를 만들어둬서 이미 방문했었는지 보고 방문을 안했던 층만 방문한다. BFS로 하기 때문에 이미 방문한 층에 한번 더 들르면 큰값이 들어가게 되므로 무조건 손해이다. 계속 방문을 하면서 원하는 지점(G)에 도착한다면 그 값을 리턴해주고, 도착하지 못한다면 'use the stairs' 를 리턴해준다. 💨 💻소스 코드 from collections import deque def bfs():..

[python] 백준 - 3055. 탈출

🤔문제 해결 G5 | BFS, 그래프? 단순히 최단거리를 찾는 것과 달리 맵이 계속 변하는 문제이다. 로직은 간단하다. 고슴도치를 상하좌우로 이동시킨다. 물도 상하좌우로 흘러넘친다. 다시 고슴도치를 상하좌우로 이동시킨다. (하지만 물에 잠겨있는 고슴도치는 이동할 수 없다) 다시 물을 상하좌우로 흘러넘치게한다. 위의 과정을 반복하면서 고슴도치가 굴에 도착하면 끝 💨 💻소스 코드 def flood(w): new_water = [] for x, y in w: for k in range(len(dx)): nx = x + dx[k] ny = y + dy[k] if 0

[python] 백준 - 1916. 최소비용 구하기

🤔문제 해결 G5 | 다익스트라, 그래프 하나의 정점에서 다른 모든 정점들의 최단 경로를 구하는 알고리즘 간선, 최소 등등 말이 나오면 다익스트라? 나의 경우 다익스트라를 풀 때 항상 우선순위 큐를 이용한다. (파이썬의 힙큐를 사용) A 에서 갈 수 있는 모든 정점들의 최소비용을 리스트에 담아두고 B 지점을 답으로 출력한다. 먼저 (가중치, 시작점)을 힙큐에 넣고 시작한다. 시작점에서 각 정점까지의 비용은 가장 큰 값(파이썬에서 float('inf')를 넣어두고 시작한다.) 힙큐에서 값을 하나씩 꺼낸다. 꺼낸 정점에서 이웃한 정점들 중에서 아직 방문하지 않았고, 이웃한 정점까지의 비용보다 현재비용 + 꺼낸 정점에서 이웃한 정점까지의 간선비용이 작으면 각 정점까지의 비용을 현재비용 + 꺼낸 정점에서 이웃한..

[python] 백준 - 2225. 합분해

🤔문제 해결 G5 | dp, 조합론 DP는 역시 손으로 해야 제맛이다. 예시의 20, 2는 너무 크기 때문에 6, 4로 바꿔서 구해봤다. 열은 N 행은 K이다. 즉 2열 3행은 2를 숫자 3개로 만드는 방법의 가짓수다. 딱 보면 규칙이 보일 것이다. i, j 는 i-1,j 와 i,j-1의 합이라는 것을... 원래의 규칙은 경우의 수를 모두 직접 구해보면 3열4행을 구할 때는 3행의 0~4열까지의 숫자를 더한 값이다. 그 이유는 0을 숫자 2개로: (0,0) 1을 숫자 2개로: (0,1), (1,0) 2를 숫자 2개로: (0,2), (1,1), (2,0) 각각의 경우의 수 뒤에 2, 1, 0 을 붙여주면 숫자 2를 3개로 구성하는 경우의 수는 6이 나온다. 💨 💻소스 코드 N, K = map(int, in..

[python] 백준 - 9251. LCS

🤔문제 해결 G5 | 다이나믹프로그래밍, 문자열 LCS란 최장 공통 부분 문자열(Longest Common Subsequence)이다. 순서는 맞지만 연속하지 않아도 되는 같은 문자열을 찾는 것이다. 예를 들어 ABCAB와 BDCB가 있다. ABCAB 와 BDCB 의 LCS는 BCB이다. LCS가 뭔지 안다고 해도 처음 접하면 구하는건 당연히 어렵다. 완전탐색을 하려고 했지만 역시나 시간초과가 발생했다. 문제 해결법이 DP이고 다른 고수들의 풀이방법을 참고해서 해결했다. 먼저 위와 같이 DP를 구성한다. 먼저 1번 째 행을 채워보면 AC와 C가 만나서 LCS는 1이다. 두번 째 행을 보자. A와 CA가 만나서 LCS는 1이다. ACA와 CA가 만나서 LCS는 2이다. 세번 째 행을 보자. A와 CAP =..

[python] 백준 - 11497. 통나무

🤔문제 해결 S1 | 정렬, 그리디 알고리즘 왼쪽과 오른쪽 끝을 최솟값으로 점점 채우는 방식으로 문제를 해결했음 리스트에서 최솟값을 꺼내는 방법은 힙큐를 사용 예시 [1, 2, 3, 4, 5, 6, 7] 위의 그림을 보면 가장 앞의 1과 가장 뒤의 2의 차이도 최소로 할 수 있음 다음 리스트 앞뒤로 값의 차이의 최댓값을 답으로 저장 💨 💻소스 코드 import heapq def solution(N, logs): heapq.heapify(logs) my_logs = [0] * N left = 0 right = -1 for _ in range(N // 2): my_logs[left] = heapq.heappop(logs) my_logs[right] = heapq.heappop(logs) left += 1 r..