알고리즘

[이것이 코딩 테스트다 with Python] 문자열 재정렬

문제 알파벳 대문자와 숫자(0~9)로만 구성된 문자열이 입력으로 주어집니다. 이때 모든 알파벳을 오름차순으로 정렬하여 이어서 출력한 뒤에, 그 뒤에 모든 숫자를 더한 값을 이어서 출력합니다. 예를 들어 K1KA5CB7 이라는 값이 들어오면 ABCKK13을 출력합니다. 입력 조건 첫째 줄에 하나의 문자열 S가 주어집니다. (1

최단 경로 (Shortest Path Problem) - 플로이드 워셜 알고리즘

플로이드 워셜 최단 거리 알고리즘 모든 노드에서 다른 모든 노드까지의 최단 경로를 모두 계산한다 플로이드 워셜(Floyd-Warshall) 알고리즘은 다익스트라 알고리즘과 마찬가지로 단계별로 거쳐 가는 노드를 기준으로 알고리즘을 수행한다 다만 매 단계마다 방문하지 않은 노드 중에 최단 거리를 갖는 노드를 찾는 과정이 필요하지 않다 플로이드 워셜은 2차원 테이블에 최단 거리 정보를 저장한다 플로이드 워셜 알고리즘은 다이나믹 프로그래밍 유형에 속한다 각 단계마다 특정한 노드 𝑘를 거쳐 가는 경우를 확인한다 𝑎에서 𝑏로 가는 최단 거리보다 𝑎에서 𝑘를 거쳐 𝑏로 가는 거리가 더 짧은지 검사한다 시간 복잡도는 O($N^3$) → N번의 단계 마다 O($N^2$)의 연산을 통해 현재 거쳐가는 모든 경로 고려 점화..

최단 경로 (Shortest Path Problem) : 다익스트라 알고리즘

최단 경로 알고리즘 이란? 가장 짧은 경로를 찾는 알고리즘 길 찾기 문제라고도 부른다. ✔ 다양한 문제 상황에 사용 한 지점에서 다른 한 지점까지의 최단 경로 (single-pair) 한 지점에서 다른 모든 지점까지의 최단 경로 (single-source) 한 지점으로 가는 모든 최단 경로 (single-destination) 모든 지점에서 다른 모든 지점까지의 최단 경로 (all-pair) 각 지점은 그래프에서 노드로 표현 지점 간 연결된 도로는 그래프에서 간선으로 표현 최단 거리 알고리즘은 다익스트라 최단 경로 알고리즘, 플로이드 워셜, 벨만 포드 알고리즘 등이 있다. 다익스트라 최단 경로 알고리즘 음의 가중치가 없는 그래프에서 한 노드에서 다른 모든노드까지의 최단 거리를 구하는 알고리즘 그리디 알고..

[이것이 코딩 테스트다 with Python] 1로 만들기 : Dynamic Programming

문제 정수 X가 주어질 때 정수 X에 사용할 수 있는 연산은 다음과 같이 4가지 입니다. a. X가 5로 나누어떨어지면, 5로 나눈다. b. X가 3으로 나누어떨어지면, 3으로 나눈다. c. X가 2로 나누어떨어지면, 2로 나눈다. d. X에서 1을 뺀다. 정수 X가 주어졌을 때, 연산 4개를 적절히 사용해서 1을 만들려고 한다. 연산을 사용하는 횟수의 최솟값을 출력하세요. 예를 들어 정수가 26이면 다음과 같이 계산해서 3번의 연산이 최솟값이다. 1. 26 – 1 = 25 (d) 2. 25/5 = 5 (a) 3. 5/5 = 1 (a) 입력 조건 첫째 줄에 정수 X가 주어진다. (1 ≤ X ≤ 30,000) 출력 조건 첫째 줄에 연산을 하는 횟수의 최솟값을 출력한다. ✔ Solution x = int(i..