Algorithm Problem/Python

[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..

[python] 백준 - 2410. 2의 멱수의 합

🤔문제 해결 S1 | 다이나믹프로그래밍 유사한 문제 [python] 백준 - 9084. 동전 🤔문제 해결 1. S1 | 다이나믹 프로그래밍 2. target(만들어야 하는 금액)의 길이만큼의 리스트를 만든다. 3. 내가 가진 동전을 하나하나 꺼내서 리스트의 인덱스(내가 만들 수 있는 금액)과 비교하�� deok2kim.tistory.com 동전 문제와 다른 점은 동전은 처음부터 사용할 값이 정해져 있지만 이 문제는 N의 크기에 따라 사용할 수 있는 값이 늘어난다. N이 7이면 1,2,4 이지만 N이 8이면 1,2,4,8 을 사용할 수 있다. 💨 💻소스 코드 def solution(N): nums = [2 ** x for x in range(21)] dp = [0] * (N + 1) dp[0] = 1 fo..

[python] 백준 - 4883. 삼각 그래프

🤔문제 해결 S1 | 다이나믹프로그래밍 최소가중치? 라고 생각해서 별 생각없이 다익스트라로 풀었더니 바로 시간초과 다시 읽어보니 경로가 각 지점마다 단순해서 다이나믹프로그래밍으로 푸는 문제였다. 문제에서 주어진 삼각그래프와 똑같은 크기의 2차원리스트를 만든다. 리스트의 각 요소는 i,j에 도달 할 때의 가장 최솟값을 저장한다. 이제 dp 값을 저장하는 방법을 설명하면 먼저 1행까지는 직접 값을 채워 넣고, 나머지는 for문을 돌린다. (1,0): (0,1)에서 오는 값 (1,1): (0,1), (1,0)에서 오는 값 (1,2): (0,1), (1,1), (0,1)+(0,2) 에서 오는 값 여기서 중요한건 노란색으로 표시한 저 부분이다. 문제에서 각 노드의 가중치는 정수이다. 다시 말해서 음수가 포함되어 ..

[python] 백준 - 13335. 트럭

🤔문제 해결 S1 | 스택 대기중인 트럭, 다리위의 트럭, 다리위의 트럭의 진입 시간 을 각각의 리스트로 구성한다. 다리 위의 트럭 중 가장 앞쪽의 트럭의 진입 시간 + 다리의 길이 가 현재시간과 같으면 그 트럭을 빼준다. (도착) 다리 위의 트럭 무게의 합 + 대기 중인 트럭 중 가장 앞쪽의 트럭 무게 가 다리의 하중보다 작으면 그 트럭을 대기중인 트럭에서 빼서 다리위의 트럭으로 넣어준다. (출발) 💨 💻소스 코드 from collections import deque def solution(n, w, L, trucks): trucks = deque(trucks) # 대기중인 트럭 on_the_bridge = deque() # 다리위의 트럭 departure_time_truck = deque() # 각 ..

[python] 백준 - 2617. 구슬 찾기

🤔문제 해결 S1 | 그래프, BFS 원래 그냥 막 풀어서 해결했는데 문제에서 BFS라고 하길래, 다시 풀어봤다. 그래프 문제를 해결할 줄 알면 문제는 간단했다. 두개의 인접리스트를 만든다. ( 나보다 무거운 애들, 나보다 가벼운 애들 ) 두개의 인접리스트를 만든다. ( 나보다 무거운 애들, 나보다 가벼운 애들 ) 모든 번호를 차례로 BFS 탐색한다. 그 때 각 번호마다 이웃들의 개수를 카운트해준다. 개수가 노드개수의 절반 이상이면 가운데 후보가 될 수 없으므로 답에 +1을 해준다. 💨 두번째에 있는 메모리 초과는 visited 배열을 따로 사용하지 않아서 중복이 많이 발생했다. 💻소스 코드 from collections import deque def solution(N, M, compare): answ..

[python] SWEA - 6019. 기차 사이의 파리

🤔문제 해결 D3 | 수학? 파리와 맞은 편 기차가 만나는 시간은 t 로 같다 파리와 맞은 편 기차가 이동한 거리의 합은 D 이다. 이렇게 저렇게 식을 계산 해보면 파리가 이동한 거리는 파리가 이동한거리는 따로 누적해주고, 파리의 속력과 이동한거리가 있으므로 시간을 구해주고 구한 시간으로 기차의 이동거리를 구해준다. 그럼 남은 기차사이의 간격은 (기존의 기차사이의 간격 - 두 기차의 이동거리) 💻소스 코드 if __name__ == "__main__": T = int(input()) for tc in range(1, 1 + T): # 사이의 거리, A 속력, B 속력, 파리 속력 D, A, B, F = map(int, input().split()) # s = v*t 파리가 날아간 거리 fly_d = 0 ..