📌문제암호화 방식 중에는 소수를 이용하는 것들이 많다. 보통은 매우 큰 두 개의 소수를 선택하고, 두 소수를 곱한 값을 암호화에서의 키로 사용하고는 한다. 이러한 방법이 좋은 이유는 일반적으로 매우 큰 수를 소인수분해 하는 것이 어렵기 때문이다.소수를 택할 때 큰 수를 택하면, 이 둘을 곱해서 얻어지는 키 값도 커지게 된다. 하지만 그 반대는 성립하지 않을 수도 있다. 즉, 키 값이 매우 큰 경우에도 이를 소인수분해 하는 것은 쉬울 수도 있다.따라서 암호문이 크랙되지 않도록 하기 위해서는, 키 값이 적절히 큰 수들의 곱으로 이루어져 있는지를 확인해야 할 필요가 있다. 키 값 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 ..
📌문제N명의 병사가 무작위로 나열되어 있다. 각 병사는 특정한 값의 전투력을 보유하고 있으며 병사를 배치할 때는 전투력이 높은 병사가 앞쪽에 오도록 내림차순으로 배치 하고자 한다.또한 배치 과정에서는 특정한 위치에 있는 병사를 열외시키는 방법을 이용한다. 그러면서도 남아있는 병사의 수가 최대가 되도록 하고 싶다.병사에 대한 정보가 주어졌을 때, 남아있는 병사의 수가 최대가 되도록 하기 위해서 열외시켜야하는 병사의 수를 출력하시오. 📌풀이가장 긴 감소하는 부분 수열의 길이를 계산하나의 수열이 주어졌을 때 값들이 감소하는 형태의 가장 긴 부분 수열을 찾음 📌코드n = int(input())array = list(map(int, input().split()))# 가장 긴 증가하는 부분 수열 문제로 변환a..
📌문제https://school.programmers.co.kr/learn/courses/30/lessons/43105 프로그래머스SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr 📌풀이특정 위치로 도달하기 위해서는 1. 왼쪽 위, 2. 바로 위에서만 내려올 수 있음모든 위치 기준으로 이전 위치로 가능한 2가지 위치까지의 최적의 합 중에 더 큰 합 가지는 경우 선택 📌코드n = int(input())dp = []for _ in range(n): dp.append(list(map(int, input().split())))for i in range(1, n): for j in range(i + 1): ..