[백준 BOJ_11660] 구간 합 구하기 5 Python 풀이
출처: 백준 온라인 저지 문제 풀이 동적계획법으로 풀어주었습니다. graph의 각각 첫 번째 행과 열(graoh[0][i], graph[i][0])은 이 전의 값을 누적하며 더해주었습니다. 첫 번째 행과 열을 제외한 나머지 칸들은 왼쪽에 있는 값(graph[x-1][...
Recent posts
[백준 BOJ_2206] 벽 부수고 이동하기 Python 풀이
출처: 백준 온라인 저지 문제 풀이 BFS로 풀어주었습니다. visited를 다음과 같은 3차원 배열로 만들어줍니다. visited[y][x][0] = 좌표 (x, y)까지의 벽을 부수지 않은 상태에서의 최단 경로 visited[y][x][1] = 좌표 (x, ...
[백준 BOJ_1865] 웜홀 Python 풀이
출처: 백준 온라인 저지 문제 풀이 벨만-포드 (Bellman-Ford) 알고리즘을 이용하여 풀어주었습니다. 우선 벨만-포드 알고리즘은 가중치가 음수일 때에도 사용가능한 최단거리 알고리즘입니다. 벨만-포드 알고리즘에서는 모든 간선을 정점의 수만큼 반복하여 비교해주는데, ...
[백준 BOJ_12865] 평범한 배낭 Python 풀이
출처: 백준 온라인 저지 문제 풀이 동적계획법을 이용하여 풀어주었습니다. cache는 다음과 같습니다. cache[i][j] = i번째 물건까지 고려했을 때, 최대 j 무게를 가지는 물건의 가치 최대 합 물건의 무게(W)와 가치(V)를 입력받고, 1부터 K까지 돌려...
[백준 BOJ_1238] 파티 Python 풀이
출처: 백준 온라인 저지 문제 풀이 다익스트라(dijkstra)를 이용하여 구현해주었습니다. 간선들을 확인하여 인접리스트를 만들어주었습니다. 단방향이기 때문에 서로에게 추가해주는 것이 아닌 출발점을 key로 가지고, 도로의 길이와 도착점의 tuple을 heappush를 ...