본문 바로가기

분류 전체보기97

[백준 1916번] 최소비용 구하기 (Python) 해당 문제를 풀기 위해 다익스트라 개념에 대해 먼저 알고 있어야한다. 2024.03.28 - [CS/Algorithm] - [알고리즘 개념 정리] 다익스트라 최단 경로 알고리즘 (Python) 문제 링크 [백준 1916번] 최소비용 구하기 문제 요약 N개의 도시가 있고, 한 도시에서 출발해 다른 도시에 도착에 도착하는 M개의 버스가 있다. A번째 도시에서 B번째 도시까지 가는데 드는 최소 비용을 출력하기 (도시의 개수 1 2024. 3. 29.
[알고리즘 개념 정리] 다익스트라 최단 경로 알고리즘 (Python) [이것이 코딩 테스트다 with Python] 30강 다익스트라 최단 경로 알고리즘을 듣고 정리한 내용입니다. 최단 경로 알고리즘 - 가장 짧은 경로를 찾는 알고리즘을 의미한다. - 다양한 문제 상황 1. 한 지점에서 다른 한 지점까지의 최단 경로 2. 한 지점에서 다른 모든 지점까지의 최단 경로 3. 모든 지점에서 다른 모든 지점까지의 최단 경로 - 각 지점은 그래프에서 노드로 표현한다. - 지점 간 연결된 도로는 그래프에서 간선으로 표현한다. 다익스트라 최단 경로 알고리즘 - 특정한 노드에서 출발하여 다른 모든 노드로 가는 최단 경로를 계산한다. - 다익스트라 최단 경로 알고리즘은 음의 간선이 없을 때 정상적으로 동작한다. - 현실 세계의 도로(간선)는 음의 간선으로 표현되지 않는다. .. 2024. 3. 28.
[백준 2293번] 동전 1 (Python) 문제 링크 [백준 2293번] 동전 1 문제 요약 n가지 종류의 동전으로 합이 k원이 되는 경우의 수 구하기 접근 방법 정리 DP를 풀 때 중요하다고 강조했던 2가지를 생각해서 접근한다. 1. 큰 문제를 작은 문제로 나눠 작은 문제의 합으로 풀 수 있는지를 고민해야하고 2. 동일한 작은 문제를 반복적으로 해결할 수 있는지 고민 1번에 해당하는 것은 합이 k원을 구하는 큰 문제에서 각 금액을 만들 수 있는 경우의 수를 차례대로 계산해나가는 것이다. 2번에 해당하는 것은 1번으로 구해놓은 정보를 바탕으로 반복문을 수행해 DP 배열을 업데이트 한다. 코드 n, k = map(int, input().split()) nums = [int(input()) for _ in range(n)] dp = [0 for i .. 2024. 3. 27.
[알고리즘 개념 정리] 다이나믹 프로그래밍 (Python) [이것이 코딩 테스트다 with Python] 28강 다이나믹 프로그래밍 개요를 듣고 정리한 내용입니다. 다이나믹 프로그래밍 (= 동적 계획법) - 메모리를 적절히 사용하여 수행 시간 효율성을 비약적으로 향상시키는 방법이다. - 이미 계산된 결과는 별도의 메모리 영역에 저장하여 다시 계산하지 않도록 한다. 메모이제이션 : 한번 계산한 결과를 메모리 공간에 메모하는 기법이다. 즉, 같은 문제를 다시 호출하면 메모했던 결과를 그대로 가져온다. 값을 기록해 놓는다는 점에서 캐싱이라고도 한다. - 다이나믹 프로그래밍의 구현은 일반적으로 2가지 방식(top-down과 bottom-up)으로 구성된다. top-down(메모이제이션) 방식 (=하향식): 재귀함수를 이용함 bottom-up 방식 (=상향식): 반복문을.. 2024. 3. 27.
[백준 11404번] 플로이드 (Python) 2024.03.25 - [CS/Algorithm] - [알고리즘 개념 정리] 플로이드 워셜 (Python) 플로이드 워셜을 학습한 뒤 풀은 플로이드 워셜을 활용하는 문제를 풀었다 🐥 문제 링크 [백준 11404번] 플로이드 문제 요약 도시들 사이의 최단 거리를 구하는 문제로, 도시 간 이동 비용을 최소화하는 것이 목표 첫번째 줄에 도시의 개수 n이 주어진다 (2 2024. 3. 26.
[백준 1389번] 케빈 베이컨의 6단계 법칙 (Python) 2024.03.25 - [CS/Algorithm] - [알고리즘 개념 정리] 플로이드 워셜 (Python) 플로이드 워셜을 학습한 뒤 풀은 플로이드 워셜을 활용하는 문제를 풀었다 🐥 문제 링크 [백준 1389번] 케빈 베이컨의 6단계 법칙 문제 요약 지구에 있는 모든 사람들은 최대 6단계 이내에 서로 아는 사람으로 연결될 수 있다는 케빈 베이컨의 법칙 이론을 바탕으로 하는 문제다. 케빈 베이컨의 수란, 한 사람이 모든 사람과 케빈 베이컨 게임을 했을 때 나오는 단계의 합을 의미한다. 백준 유저 사이에서 케빈 베이컨의 수가 가장 작은 사람을 찾아 출력하는 것이 목표다. (만약, 그런 사람이 여러 명이면 번호가 가장 작은 사람을 출력) 유저의 수 n과 친구 관계의 수 m이 주어진다. 이어서 m개의 줄에 걸쳐.. 2024. 3. 26.

티스토리툴바