📌문제도현이는 바구니를 총 N개 가지고 있고, 각각의 바구니에는 1번부터 N번까지 번호가 매겨져 있다. 바구니에는 공이 1개씩 들어있고, 처음에는 바구니에 적혀있는 번호와 같은 번호가 적힌 공이 들어있다.도현이는 앞으로 M번 공을 바꾸려고 한다. 도현이는 공을 바꿀 바구니 2개를 선택하고, 두 바구니에 들어있는 공을 서로 교환한다.공을 어떻게 바꿀지가 주어졌을 때, M번 공을 바꾼 이후에 각 바구니에 어떤 공이 들어있는지 구하는 프로그램을 작성하시오. 📌풀이바구니 리스트에 바구니 번호와 같은 번호로 공의 번호를 초기화공을 바꿀 두 바구니 번호(A, B)를 입력받고 바구니 A의 값을 임시로 저장해 둔 후 다른 바구니 B의 값을 A에 저장이후 바구니 B에 임시로 저장해 둔 바구니 A의 값을 저장해서 리스..
📌문제도현이는 바구니를 총 N개 가지고 있고, 각각의 바구니에는 1번부터 N번까지 번호가 매겨져 있다. 또, 1번부터 N번까지 번호가 적혀있는 공을 매우 많이 가지고 있다. 가장 처음 바구니에는 공이 들어있지 않으며, 바구니에는 공을 1개만 넣을 수 있다.도현이는 앞으로 M번 공을 넣으려고 한다. 도현이는 한 번 공을 넣을 때, 공을 넣을 바구니 범위를 정하고, 정한 바구니에 모두 같은 번호가 적혀있는 공을 넣는다. 만약, 바구니에 공이 이미 있는 경우에는 들어있는 공을 빼고, 새로 공을 넣는다. 공을 넣을 바구니는 연속되어 있어야 한다.공을 어떻게 넣을지가 주어졌을 때, M번 공을 넣은 이후에 각 바구니에 어떤 공이 들어 있는지 구하는 프로그램을 작성하시오. 📌풀이(공을 넣을 바구니 시작 번호, 공..
📌문제암호화 방식 중에는 소수를 이용하는 것들이 많다. 보통은 매우 큰 두 개의 소수를 선택하고, 두 소수를 곱한 값을 암호화에서의 키로 사용하고는 한다. 이러한 방법이 좋은 이유는 일반적으로 매우 큰 수를 소인수분해 하는 것이 어렵기 때문이다.소수를 택할 때 큰 수를 택하면, 이 둘을 곱해서 얻어지는 키 값도 커지게 된다. 하지만 그 반대는 성립하지 않을 수도 있다. 즉, 키 값이 매우 큰 경우에도 이를 소인수분해 하는 것은 쉬울 수도 있다.따라서 암호문이 크랙되지 않도록 하기 위해서는, 키 값이 적절히 큰 수들의 곱으로 이루어져 있는지를 확인해야 할 필요가 있다. 키 값 K와 정수 L이 주어졌을 때, K를 인수분해 했을 때, 항상 L 이상의 값으로만 이루어져 있는지를 확인하고 싶다. 물론 인수분해 ..
📌문제알파벳 소문자로만 이루어진 단어 S가 주어진다. 각 알파벳이 단어에 몇 개가 포함되어 있는지 구하는 프로그램을 작성하시오. 📌풀이ord 함수하나의 문자를 인자로 받고 그 문자에 해당하는 유니코드 정수 반환 +) chr 함수하나의 정수를 인자로 받고 그 정수에 해당하는 유니코드 문자 반환 ord('a')=97이기 때문에 알파벳 시작인 a부터 인덱스를 0으로 맞추기 위해서 97을 뺀다 📌코드s = input()list = [0] * 26 # 초기화for i in s: list[ord(i) - 97] += 1for i in list: print(i, end=" ")
📌문제준원이는 저번 주에 살면서 처음으로 코스트코를 가 봤다. 정말 멋졌다. 그런데, 몇 개 담지도 않았는데 수상하게 높은 금액이 나오는 것이다! 준원이는 영수증을 보면서 정확하게 계산된 것이 맞는지 확인해보려 한다.영수증에 적힌,구매한 각 물건의 가격과 개수구매한 물건들의 총 금액을 보고, 구매한 물건의 가격과 개수로 계산한 총 금액이 영수증에 적힌 총 금액과 일치하는지 검사해보자. 📌풀이구매한 물건 종류의 총 수 N만큼 반복하면서 구매한 각 물건의 가격과 개수를 곱한 금액들을 매번 sum에 합한 후 마지막에 영수증 총 금액과 일치하는지 확인 📌코드x = int(input())n = int(input())sum = 0for _ in range(n): a, b = map(int, input()..
📌문제동빈이는 숨바꼭질을 하면서 술래로부터 잡히지 않도록 숨을 곳을 찾고 있다. 동빈이는 1~N번까지의 헛간 중에 하나를 골라 숨을 수 있으며 술래는 항상 1번 헛간에서 출발한다. 전체 맵에 M개의 양방향 통로가 존재하며 하나의 통로는 서로 다른 두 헛간을 연결한다. 또한 전체 맵은 항상 어떤 헛간에서 다른 헛간으로 도달이 가능한 형태로 주어진다.동빈이는 1번 헛간으로부터 최단 거리가 가장 먼 헛간이 안전하다고 판단하고 있다. 이때 최단 거리의 의미는 지나야 하는 길의 최소 개수를 의미한다. 동빈이가 숨을 헛간 번호를 출력하는 프로그램을 작성하시오. 📌풀이다익스트라 알고리즘으로 1번 노드로부터 다른 모든 노드까지의 최단 거리를 계산한 뒤에 가장 최단 거리가 긴 노드를 찾음 📌코드import heap..
📌문제당신은 화성 탐사 기계를 개발하는 프로그래머다. 그런데 화성은 에너지 공급원을 찾기가 힘들다. 그래서 에너지를 효율적으로 사용하고자 화성 탐사 기계가 출발 지점에서 목표 지점까지 이동할 때 항상 최적의 경로를 찾도록 개발해야 한다.화성 탐사 기계가 존재하는 공간은 NxN크기의 2차원 공간이며 각각의 칸을 지나기 위한 비용이 존재한다. 가장 왼쪽 위 칸인 [0][0] 위치에서 가장 오른쪽 아래 칸인 [N-1][N-1] 위치로 이동하는 최소 비용을 출력하는 프로그램을 작성하시오. 📌풀이NxN 크기의 맵이 주어졌을 때 맵의 각 칸을 노드로 보고 상하좌우로 모든 노드가 연결되어 있다고 생각다익스트라 최단 경로 알고리즘 사용 📌코드import heapqimport sysinput = sys.stdin...
📌문제n개의 도시가 있고, 한 도시에서 출발하여 다른 도시에 도착하는 m개의 버스가 있다. 각 버스는 한 번 사용할 때 필요한 비용이 있다. 모든 도시의 쌍에 대해서 도시 A에서 B로 가는데 필요한 비용의 최솟값을 구하시오. 📌풀이도시 A에서 B로 가는 간선이 여러개일 경우 비용이 짧은 간선만 고려초기에 간선 정보를 입력받을 때 가장 짧은 간선 정보만 저장한 후 플로이드 워셜 알고리즘 수행 📌코드INF = int(1e9) # 무한# 노드의 개수, 간선의 개수 입력n = int(input())m = int(input())# 2차원 리스트(그래프)를 만들고 무한으로 초기화graph = [[INF] * (n + 1) for _ in range(n + 1)]# 자기 자신에서 자기 자신으로 가는 비용 0f..
📌문제두개의 문자열 A,B가 주어졌을 때 문자열 A를 편집하여 문자열 B로 만들고자 한다. 문자열 A를 편집할 때는 다음 세 연산 중 한번에 하나씩 선택하여 이용할 수 있다.1. 삽입: 특정한 위치에 하나의 문자를 삽입2. 삭제: 특정한 위치에 있는 하나의 문자를 삭제3. 교체: 특정한 위치에 있는 하나의 문자를 다른 문자로 교체 이때 편집 거리란 문자열 A를 편집하여 문자열 B로 만들기 위해 사용한 연산의 수를 의미한다. 문자열 A를 B로 만드는 최소 편집 거리를 계산하는 프로그램을 작성하시오. 📌풀이최소 편집 거리를 담을 2차원 테이블1. 행과 열에 해당하는 문자가 서로 같다면, 왼쪽 위에 해당하는 수를 그대로 대입2. 행과 열에 해당하는 문자가 서로 다르다면, 왼쪽(삽입), 위쪽(삭제), 왼쪽 ..
📌문제못생긴 수란 오직 2,3,5만을 소인수로 가지는 수를 의미한다. 다시 말해 오직 2,3,5를 약수로 가지는 합성수를 의미한다. 1은 못생긴 수라고 가정한다. 따라서 못생긴 수들은 1,2,3,4,5,6,8,9,10,12,15... 순으로 이어지게 된다. 이때 n번째 못생긴 수를 찾는 프로그램을 작성하시오. 📌풀이못생긴 수에 2,3,5를 곱한 수 또한 못생긴 수에 해당 📌코드n = int(input())ugly = [0] * n # 못생긴 수를 담기 위한 테이블ugly[0] = 1 # 첫번째 못생긴 수는 1# 2배, 3배, 5배를 위한 인덱스i2 = i3 = i5 = 0# 처음에 곱셈값을 초기화next2, next3, next5 = 2, 3, 5# 1부터 n까지 못생긴 수 찾기for l in ..