[이코테] 최단 경로 알고리즘 - 미래도시

실전 문제 INF = int(1e9) #무한을 의미하는 값으로 10억을 설정 #노드의 개수와 간선의 개수 입력받기. node,line = map(int,input().split()) #2차원 그래프 무한으로 채워서 선언. graph = [[INF]*(node+1) for _ in range(node+1)] #자기 자신에서 자기 자신으로 가는 비용은 0으로 초기화 for a in range(1,node+1): for b in range(1,node+1): if a == b: graph[a][b] = 0 #각 간선에 대항ㄴ 정보를 입력받아, 그 값으로 초기화. for _ in range(line): #A와 B가 서로에게 가는 비용은 1이라고 설정 a, b = map(int,input().split()) gr..

• format_list_bulleted Algorithm
• · 2020. 12. 15.
• textsms

[이코테] 플로이드 워셜 알고리즘(Floyd-Warshall Algorithm)

플로이드 워셜 알고리즘 저번에 공부했던 다익스트라 알고리즘은 '한 지점에서 다른 특정 지점까지의 최단 경로를 구해야 하는 경우'에 사용할 수 있는 최단 경로 알고리즘이다. 이번에 공부할 플로이드 워셜 알고리즘은 '모든 지점에서 다른 모든 지점까지의 최단 경로를 모두 구해야 하는 경우'에 사용할 수 있는 알고리즘이다. 다익스트라 알고리즘에서는 출발 노드가 1개이므로 다른 모든 노드까지의 최단 거리를 저장하기 위해서 1차원 리스트를 이용하였다. 반면에 플로이드 워셜 알고리즘에서는 다익스트라 알고리즘과는 다르게 2차원 리스트에 '최단 거리' 정보를 저장한다는 특징이 있다. 모든 노드에 대하여 다른 모든 노드로 가는 최단 거리 정보를 담아야 하기 때문이다. 그렇기 때문에 2차원 리스트를 처리해야 하므로 N번의 ..

• format_list_bulleted Algorithm
• · 2020. 12. 15.
• textsms

[BOJ/백준] 하노이 탑 이동순서

문제 세 개의 장대가 있고 첫 번째 장대에는 반경이 서로 다른 n개의 원판이 쌓여 있다. 각 원판은 반경이 큰 순서대로 쌓여있다. 이제 수도승들이 다음 규칙에 따라 첫 번째 장대에서 세 번째 장대로 옮기려 한다. 한 번에 한 개의 원판만을 다른 탑으로 옮길 수 있다. 쌓아 놓은 원판은 항상 위의 것이 아래의 것보다 작아야 한다. 이 작업을 수행하는데 필요한 이동 순서를 출력하는 프로그램을 작성하라. 단, 이동 횟수는 최소가 되어야 한다. 아래 그림은 원판이 5개인 경우의 예시이다. 입력 첫째 줄에 첫 번째 장대에 쌓인 원판의 개수 N (1 ≤ N ≤ 20)이 주어진다. 출력 첫째 줄에 옮긴 횟수 K를 출력한다. 두 번째 줄부터 수행 과정을 출력한다. 두 번째 줄부터 K개의 줄에 걸쳐 두 정수 A B를 빈..

• format_list_bulleted Algorithm
• · 2020. 12. 11.
• textsms

[BOJ/백준] 2477번 별 찍기 - 10

문제 재귀적인 패턴으로 별을 찍어 보자. N이 3의 거듭제곱(3, 9, 27,...)이라고 할 때, 크기 N의 패턴은 N×N 정사각형 모양이다. 크기 3의 패턴은 가운데에 공백이 있고, 가운데를 제외한 모든 칸에 별이 하나씩 있는 패턴이다. *** * * *** N이 3보다 클 경우, 크기 N의 패턴은 공백으로 채워진 가운데의 (N/3)×(N/3) 정사각형을 크기 N/3의 패턴으로 둘러싼 형태이다. 예를 들어 크기 27의 패턴은 예제 출력 1과 같다. 입력 첫째 줄에 N이 주어진다. N은 3의 거듭제곱이다. 즉 어떤 정수 k에 대해 N=3k이며, 이때 1 ≤ k < 8이다. 출력 첫째 줄부터 N번째 줄까지 별을 출력한다. 풀이 def check(n): # x,y = (1,4,7) : 3으로 나눈 나머지가..

• format_list_bulleted Algorithm
• · 2020. 12. 11.
• textsms

[BOJ/백준] 4344번 평균은 넘겠지

대학생 새내기들의 90%는 자신이 반에서 평균은 넘는다고 생각한다. 당신은 그들에게 슬픈 진실을 알려줘야 한다. 입력 첫째 줄에는 테스트 케이스의 개수 C가 주어진다. 둘째 줄부터 각 테스트 케이스마다 학생의 수 N(1 ≤ N ≤ 1000, N은 정수)이 첫 수로 주어지고, 이어서 N명의 점수가 주어진다. 점수는 0보다 크거나 같고, 100보다 작거나 같은 정수이다. 출력 각 케이스마다 한 줄씩 평균을 넘는 학생들의 비율을 반올림하여 소수점 셋째 자리까지 출력한다. 풀이 n = int(input()) for i in range(n): answer = list(map(int,input().split())) avg = sum(answer[1:])/answer[0] cnt = 0 for j in answer[..

• format_list_bulleted Algorithm
• · 2020. 12. 11.
• textsms

[BOJ/백준] 8958번 OX퀴즈

문제 "OOXXOXXOOO"와 같은 OX퀴즈의 결과가 있다. O는 문제를 맞은 것이고, X는 문제를 틀린 것이다. 문제를 맞은 경우 그 문제의 점수는 그 문제까지 연속된 O의 개수가 된다. 예를 들어, 10번 문제의 점수는 3이 된다. "OOXXOXXOOO"의 점수는 1+2+0+0+1+0+0+1+2+3 = 10점이다. OX퀴즈의 결과가 주어졌을 때, 점수를 구하는 프로그램을 작성하시오. 입력 첫째 줄에 테스트 케이스의 개수가 주어진다. 각 테스트 케이스는 한 줄로 이루어져 있고, 길이가 0보다 크고 80보다 작은 문자열이 주어진다. 문자열은 O와 X만으로 이루어져 있다. 출력 각 테스트 케이스마다 점수를 출력한다. 풀이 n = int(input()) for i in range(n): answer = li..

• format_list_bulleted Algorithm
• · 2020. 12. 11.
• textsms

<