Redddy's Devlog

플로이드 워셜 알고리즘 (Floyd-Warshall Algorithm) 플로이드 워셜 알고리즘은 플로이드와 워셜이 개발한 알고리즘으로 그래프의 모든 노드에서 다른 모든 노드까지의 최단 경로를 모두 계산한다. 데이크스트라 알고리즘과 비슷하게 단계별로 거쳐 가는 노드를 기준으로 최소값을 갱신하지만, 데이크스트라 알고리즘은 매 단계마다 방문하지 않은 노드 중에 최단 거리를 갖는 노드를 찾아서 방문하였다면 이 플로이드 워셜 알고리즘은 아묻따 모든 노드를 탐색한다. 인접 행렬 형태의 2차원 테이블을 만들어 최단 거리 정보를 저장한다. 이전에 한번 한 연산은 다시 반복하지 않는다는 점에서 다이나믹 프로그래밍 유형에 속한다. 이 알고리즘은 각 단계마다 특정한 노드 k를 거쳐 가는 경우를 확인하여 갱신해준다. a에서 ..

🔈 문제 오민식은 세일즈맨이다. 오민식의 회사 사장님은 오민식에게 물건을 최대한 많이 팔아서 최대 이윤을 남기라고 했다. 오민식은 고민에 빠졌다.어떻게 하면 최대 이윤을 낼 수 있을까? 이 나라에는 N개의 도시가 있다. 도시는 0번부터 N-1번까지 번호 매겨져 있다. 오민식의 여행은 A도시에서 시작해서 B도시에서 끝난다.오민식이 이용할 수 있는 교통수단은 여러 가지가 있다. 오민식은 모든 교통수단의 출발 도시와 도착 도시를 알고 있고, 비용도 알고 있다. 게다가, 오민식은 각각의 도시를 방문할 때마다 벌 수 있는 돈을 알고있다. 이 값은 도시마다 다르며, 액수는 고정되어있다. 또, 도시를 방문할 때마다 그 돈을 벌게 된다. 오민식은 도착 도시에 도착할 때, 가지고 있는 돈의 액수를 최대로 하려고 한다. ..

🔈 문제 어떤 정수 X가 1보다 큰 제곱수로 나누어 떨어지지 않을 때, 그 수를 제곱ㄴㄴ수라고 한다. 제곱수는 정수의 제곱이다. min과 max가 주어지면, min보다 크거나 같고, max보다 작거나 같은 제곱ㄴㄴ수가 몇 개 있는지 출력한다. 📝입력 첫째 줄에 두 정수 min과 max가 주어진다. 📑출력 첫째 줄에 min보다 크거나 같고, max보다 작거나 같은 제곱ㄴㄴ수의 개수를 출력한다. ❗❗제한 - 1 ≤ min ≤ 1,000,000,000,000 - min ≤ max ≤ min + 1,000,000 📚 문제 풀이 제곱ㄴㄴ수는 제곱수로 나누어 떨어지지 않는 수, 예를 들어 1,2,3,5,6,7,10을 의미한다. 4와 8은 2의 제곱수 4로 나누어 떨어지기 때문에 제외 되는 것이다. 처음에는 후보 숫..

🔈 문제 +---+ | D | +---+---+---+---+ | E | A | B | F | +---+---+---+---+ | C | +---+ 주사위는 위와 같이 생겼다. 주사위의 여섯 면에는 수가 쓰여 있다. 위의 전개도를 수가 밖으로 나오게 접는다.A, B, C, D, E, F에 쓰여 있는 수가 주어진다.지민이는 현재 동일한 주사위를 N3개 가지고 있다. 이 주사위를 적절히 회전시키고 쌓아서, N×N×N크기의 정육면체를 만들려고 한다. 이 정육면체는 탁자위에 있으므로, 5개의 면만 보인다.N과 주사위에 쓰여 있는 수가 주어질 때, 보이는 5개의 면에 쓰여 있는 수의 합의 최솟값을 출력하는 프로그램을 작성하시오. 📝입력 첫째 줄에 N이 주어진다. 둘째 줄에 주사위에 쓰여 있는 수가 주어진다. 위의..

도커와 파이썬을 연결해보는 실습을 하였다. 그동안 노드로만 하다가 파이썬을 보니 매일 중국어 듣다가 한국어 들은 것처럼 매우 기뻤다...ㅎ from random import randint min_ = int(input('please enter min ')) max_ = int(input('please enter max ')) if (max_ < min_): print('Invalind input - shuttind down') else: rnd_num = randint(min_, max_) print(rnd_num) 이제 파이썬을 도커화해보자. FROM python WORKDIR /app COPY . /app CMD ["python", "rng.py"] 도커 터미널에서 이미지 빌드하고 컨테이너를 실행시킨..

🔈 문제 때는 2020년, 백준이는 월드나라의 한 국민이다. 월드나라에는 N개의 지점이 있고 N개의 지점 사이에는 M개의 도로와 W개의 웜홀이 있다. (단 도로는 방향이 없으며 웜홀은 방향이 있다.) 웜홀은 시작 위치에서 도착 위치로 가는 하나의 경로인데, 특이하게도 도착을 하게 되면 시작을 하였을 때보다 시간이 뒤로 가게 된다. 웜홀 내에서는 시계가 거꾸로 간다고 생각하여도 좋다. 시간 여행을 매우 좋아하는 백준이는 한 가지 궁금증에 빠졌다. 한 지점에서 출발을 하여서 시간여행을 하기 시작하여 다시 출발을 하였던 위치로 돌아왔을 때, 출발을 하였을 때보다 시간이 되돌아가 있는 경우가 있는지 없는지 궁금해졌다. 여러분은 백준이를 도와 이런 일이 가능한지 불가능한지 구하는 프로그램을 작성하여라. 📝입력 첫..

데이크스트라 알고리즘 (Dijkstra Algorithm) 최단 경로 알고리즘은 주어진 그래프에서 가장 빨리 도달할 수 있는 길을 찾는 알고리즘이다. 노드를 연결하는 간선에 비용 있어 간선의 갯수가 같다고 하여도 실제 이동시간은 다를 수 있기에 그런 것들을 잘 체크해주어야 한다. 데이크스트라 알고리즘은 음의 간선이 없을 때 정상적으로 작동한다. 음의 간선이란 0보다 작은 값을 가지는 간선을 의미하는데, 현실 세계에서 음의 간선이란 존재할 수 없다. 때문에 GPS 소프트웨어의 기본 알고리즘으로 채택되기도 한다. 데이크스트라 알고리즘의 동작 원리는 인접한 노드중에 가장 비용이 적은 노드를 선택하여 움직이기에 그리디 알고리즘으로 분류된다. 출발 노드를 설정한다. 최단 거리 테이블을 초기화 한다. 방문하지 않은..

🔈 문제 네 개의 명령어 D, S, L, R 을 이용하는 간단한 계산기가 있다. 이 계산기에는 레지스터가 하나 있는데, 이 레지스터에는 0 이상 10,000 미만의 십진수를 저장할 수 있다. 각 명령어는 이 레지스터에 저장된 n을 다음과 같이 변환한다. n의 네 자릿수를 d1, d2, d3, d4라고 하자 (즉 n = ((d1 × 10 + d2) × 10 + d3) × 10 + d4라고 하자) 1. D: D 는 n을 두 배로 바꾼다. 결과 값이 9999 보다 큰 경우에는 10000 으로 나눈 나머지를 취한다. 그 결과 값(2n mod 10000)을 레지스터에 저장한다. 2. S: S 는 n에서 1 을 뺀 결과 n-1을 레지스터에 저장한다. n이 0 이라면 9999 가 대신 레지스터에 저장된다. 3. L:..

🔈 문제 방향그래프가 주어지면 주어진 시작점에서 다른 모든 정점으로의 최단 경로를 구하는 프로그램을 작성하시오. 단, 모든 간선의 가중치는 10 이하의 자연수이다. 📝입력 첫째 줄에 정점의 개수 V와 간선의 개수 E가 주어진다. (1 ≤ V ≤ 20,000, 1 ≤ E ≤ 300,000) 모든 정점에는 1부터 V까지 번호가 매겨져 있다고 가정한다. 둘째 줄에는 시작 정점의 번호 K(1 ≤ K ≤ V)가 주어진다. 셋째 줄부터 E개의 줄에 걸쳐 각 간선을 나타내는 세 개의 정수 (u, v, w)가 순서대로 주어진다. 이는 u에서 v로 가는 가중치 w인 간선이 존재한다는 뜻이다. u와 v는 서로 다르며 w는 10 이하의 자연수이다. 서로 다른 두 정점 사이에 여러 개의 간선이 존재할 수도 있음에 유의한다. ..

🔈 문제 KOI 부설 과학연구소에서는 많은 종류의 산성 용액과 알칼리성 용액을 보유하고 있다. 각 용액에는 그 용액의 특성을 나타내는 하나의 정수가 주어져있다. 산성 용액의 특성값은 1부터 1,000,000,000까지의 양의 정수로 나타내고, 알칼리성 용액의 특성값은 -1부터 -1,000,000,000까지의 음의 정수로 나타낸다. 같은 양의 두 용액을 혼합한 용액의 특성값은 혼합에 사용된 각 용액의 특성값의 합으로 정의한다. 이 연구소에서는 같은 양의 두 용액을 혼합하여 특성값이 0에 가장 가까운 용액을 만들려고 한다. 예를 들어, 주어진 용액들의 특성값이 [-2, 4, -99, -1, 98]인 경우에는 특성값이 -99인 용액과 특성값이 98인 용액을 혼합하면 특성값이 -1인 용액을 만들 수 있고, 이 ..