알고리즘

[그리디 Greedy] 곱하기 혹은 더하기

문제 각 자리가 숫자 0 ~ 9로만 이루어진 문자열 S가 있을 때, 왼쪽부터 오른쪽으로 하나씩 모든 숫자를 확인하며 숫자 사이에 * 혹은 + 연산자를 넣어 결과적으로 가질 수 있는 가장 큰 수를 구하는 프로그램을 작성하시오. 단, 일반적인 우선순위와 다르게 모든 연산은 왼쪽부터 순서대로 이루어진다고 한다. 또한 만들어 질 수 있는 가장 큰 수는 항상 20억 이하의 정수가 되도록 입력이 주어진다. 입력 조건 첫째 줄에 여러 개의 숫자로 구성된 하나의 문자열 S가 주어진다. (1

[그리디 Greedy] 문자열 뒤집기

문제 주인공은 0과 1로만 이루어진 문자열 S를 가지고 있다. 주인공은 이 문자열 S에 있는 모든 숫자를 전부 같게 만들려고 한다. 주인공이 할 수 있는 행동은 S에서 연속된 하나 이상의 숫자를 잡고 모두 뒤집는 것이다. 예를 들어 0001100일 때는 다음과 같다. 전체를 뒤집으면 1110011 4번째 문자부터 5번째 문자까지 뒤집으면 1111111이 되어서 두 번 만에 모두 같은 숫자로 만들 수 있다. 하지만 처음부터 4번째 문자부터 5번째 문자까지 뒤집으면 모두 0으로 한 번 만에 모두 같은 숫자로 만들 수 있다. 주인공이 해야하는 행동의 최소 횟수를 구하여라. 입력 조건 첫째 줄에 0과 1로만 이루어진 문자열 S가 주어진다. S의 길이는 100만보다는 작다. 출력 조건 첫째 줄에 주인공이 해야 하..

[그리디 Greedy] 모험가 길드

문제 한 마을에 모험가가 N명이 있고 모험가를 대상으로 공포도를 측정했다. 공포도가 X인 모험가는 반드시 X명 이상으로 구성한 모험가 그룹에 참여해야 여행을 떠날 수 있다는 규정이 있다. 길드장은 최대 몇 개의 모험가 그룹을 만들 수 있는지 궁금해한다. 길드장을 위해 N명의 모험가에 대한 정보가 주어졌을 때, 여행을 떠날 수 있는 그룹 수의 최대값을 구하는 프로그램을 작성하시오. 단, 몇 명의 모험가는 마을에 그대로 남아 있어도 되기 때문에, 모든 모험가를 특정한 그룹에 넣을 필요는 없다. 입력 조건 첫째 줄에 모험가의 수가 주어진다. (1

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

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