Free

다익스트라 알고리즘 한 지점에서 다른 특정 지점까지의 최단 경로를 구해야 하는 경우에 사용할 수 있는 최단 경로 알고리즘 그리디 알고리즘: 매 상황에서 방문하지 않은 가장 비용이 적은 노드를 선택해 임의의 과정을 반복 단계를 거치며 한 번 처리된 노드의 최단 거리는 고정되어 더 이상 바뀌지 않음 한 단계당 하나의 노드에 대한 최단 거리를 확실히 찾는 것으로 이해할 수 있음 간단한 다익스트라 알고리즘 소스코드 import sys input = sys.stdin.readline INF = int(1e9) n, m = map(int, input().split()) start = int(input()) # 각 노드에 연결되어 있는 노드에 대한 정보를 담는 리스트를 만들기 graph = [[] for i in r..

1로 만들기 정수 X가 주어질 때 정수 X에 사용할 수 있는 연산은 다음과 같이 4가지이다. X가 5로 나누어 떨어지면, 5로 나눈다. X가 3으로 나누어 떨어지면, 3으로 나눈다. X가 2로 나누어 떨어지면, 2로 나눈다. X에서 1을 뺀다. 정수 X가 주어졌을 때, 연산 4개를 적절히 사용해서 1을 만들려고 한다. 연산을 사용하는 횟수의 최솟값을 출력하시오. 답안 예시 x = int(input()) d = [0]*30001 for i in range(2, x+1): #현재의 수에서 1을 빼는 경우 d[i] = d[i-1]+1 #현재의 수가 2로 나누어 떨어지는 경우 if i%2 == 0: d[i] = min(d[i], d[i//2]+1) #현재의 수가 3으로 나누어 떨어지는 경우 if i%3 == 0..

부품 찾기 동빈이네 전자 매장에는 부품이 N개 있다. 각 부품은 정수 형태의 고유한 번호가 있다. 어느 날 손님이 M개 종류의 부품을 대량으로 구매하겠다며 당일 날 견적서를 요청했다. 동빈이는 때를 놓치지 않고 손님이 문의한 부품 M개 종류를 모두 확인해서 견적서를 작성해야 한다. 이때 가게 안에 부품이 모두 있는지 확인하는 프로그램을 작성해보자. 내 답안(정답) n = int(input()) list_n = list(map(int, input().split(' '))) m = int(input()) list_m = list(map(int, input().split(' '))) for i in list_m: if i in list_n: print("yes", end=' ') else: print("no"..

성적이 낮은 순서로 학생 출력하기 N명의 학생 정보가 있다. 학생 정보는 학생의 이름과 학생의 성적으로 구분된다. 각 학생의 이름과 성적 정보가 주어졌을 때 성적이 낮은 순서대로 학생의 이름을 출력하는 프로그램을 작성하시오. n = int(input()) array = [] for _ in range(n): name, score = input().split() array.append((name, int(score))) array = sorted(array, key=lambda student: student[1]) for student in array: print(student[0], end = ' ') 람다를 사용하여 리스트를 정렬할 수 있다. 사실 난 처음에 딕셔너리로 풀었으나 리스트 답안이 더 깔끔하..

선택 정렬 array = [7, 5, 9, 0, 3, 1, 6, 2, 4, 8] for i in range(len(array)): min_index = i for j in range(i+1, len(array)): if array[min_index] > array[j]: min_index = j array[i], array[min_index] = array[min_index], array[i] print(array) 배열 인덱스 첫번째부터 i로 지정 그 이후 배열에서 최소값을 찾아 해당 인덱스를 j로 지정한 뒤 스와프(swap)를 통해 자리를 바꿔준다. 즉, 배열의 최소값을 맨 앞으로 이동 이를 반복하여 맨 앞에서부터 차례대로 하나씩 지정 삽입 정렬 array = [7, 5, 9, 0, 3, 1, 6, ..

음료수 얼려 먹기 NxM 크기의 얼음 틀이 있다. 구멍이 뚫려 있는 부분은 0, 칸막이가 존재하는 부분은 1로 표시된다. 구멍이 뚫려 있는 부분끼리 상, 하, 좌, 우로 붙어 있는 경우 서로 연결되어 있는 것으로 간주한다. 이때 얼음 틀의 모양이 주어졌을 때 생성되는 총 아이스크림의 개수를 구하는 프로그램을 작성하시오. 다음의 4x5 얼음 틀 예시에서는 아이스크림이 총 3개 생성된다. 내 답안 from collections import deque n, m = map(int, input().split()) arr = [] for _ in range(n): arr.append(list(map(int, input()))) count = 0 def bfs(arr, i, j): global count queue ..

스택 구현 stack = [] stack.append(5) stack.append(2) stack.append(3) stack.append(7) stack.pop() stack.append(1) stack.append(4) stack.pop() print(stack[::-1]) print(stack) 큐 구현 from collections import deque #큐(Queue) 구현을 위해 deque 라이브러리 사용 queue = deque() queue.append(5) queue.append(2) queue.append(3) queue.append(7) queue.popleft() queue.append(1) queue.append(4) queue.popleft() print(queue) #먼저 들..

시각 정수 N이 입력되면 00시 00분 00초부터 N시 59분 59초까지의 모든 시각 중에서 3이 하나라도 포함되는 모든 경우의 수를 구하는 프로그램을 작성하시오. 예를 들어 1을 입력했을 때 다음은 3이 하나라도 포함되어 있으므로 세어야 하는 시각이다. - 00시 00분 03초 - 00시 13분 30초 반면에 다음은 3이 하나라도 포함되어 있지 않으므로 세면 안되는 시각이다. - 00시 02분 55초 - 01시 27분 45초 내 답안 n = int(input()) count = 0 for h in range( n+1): for m in range(60): for s in range(60): print(h, m, s) if h%10 == 3 or m%10 == 3 or s%10 == 3: count +=..

큰 수의 법칙 '큰 수의 법칙'은 일반저긍로 통계 분야에서 다루어지는 내용이지만 동빈이는 본인만의 방식으로 다르게 사용하고 있다. 동빈이의 큰 수의 법칙은 다양한 수로 이루어진 배열이 있을 때 주어진 수들을 M번 더하여 가장 큰 수를 만드는 법칙이다. 단, 배열의 특정한 인덱스(번호)에 해당하는 수가 연속해서 K번을 초과하여 더해질 수 없는 것이 이 법칙의 특징이다. 예를 들어 순서대로 2, 4, 5, 4, 6으로 이루어진 배열이 있을 때 M이 8이고, K가 3이라고 가정하자. 이 경우 특정한 인덱스의 수가 연속해서 세 번까지만 더해질 수 있으므로 큰 수의 법칙에 따른 결과는 6+6+6+5+6+6+6+5인 46이 된다. 단, 서로 다른 인덱스에 해당하는 수가 같은 경우에도 서로 다른 것으로 간주한다. 예..

1이 될 때까지 어떠한 수 N이 1이 될 때까지 다음의 두 과정 중 하나를 반복적으로 선택하여 수행하려고 합니다. 단, 두번째 연산은 N이 K로 나누어 떨어질 때만 선택할 수 있습니다. 1. N에서 1을 뺍니다. 2. N을 K로 나눕니다. 예를 들어 N이 17, K가 4라고 가정합시다. 이때 1번의 과정을 한 번 수행하면 N은 16이 됩니다. 이후에 2번의 과정을 두 번 수행하면 N은 1이 됩니다. 결과적으로 이 경우 전체 과정을 실행한 횟수는 3이 됩니다. 이는 N을 1로 만드는 최소 횟수입니다. N과 K가 주어질 때 N이 1이 될 때까지 1번 혹은 2번의 과정을 수행해야 하는 최소 횟수를 구하는 프로그램을 작성하세요. 내 답안 import time start = time.time() N, K = ma..