📌문제못생긴 수란 오직 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): ..
📌문제nxm 크기의 금광이 있습니다. 금광은 1x1 크기의 칸으로 나누어져 있으며, 각 칸은 특정한 크기의 금이 들어있다. 채굴자는 첫번째 열부터 출발하여 금을 캐기 시작한다. 맨 처음에는 첫번재 열의 어느 행에서든 출발할 수 있다. 이후 m번에 걸쳐서 매번 오른쪽 위, 오른쪽, 오른쪽 아래 3가지 중 하나의 위치로 이동해야 한다. 결과적으로 채굴자가 얻을 수 있는 금의 최대 크기를 출력하는 프로그램을 작성하시오. 📌풀이2차원 테이블을 이용한 다이나믹 프로그래밍1. 왼쪽 위에서 오는 경우2. 왼쪽 아래에서 오는 경우3. 왼쪽에서 오는 경우이 3가지 경우 중 가장 많이 금을 가지고 있는 경우를 테이블에 저장 📌코드for tc in range(int(input())): # 금광 정보 입력 n..
📌문제https://school.programmers.co.kr/learn/courses/30/lessons/60060 프로그래머스SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr 📌풀이각 단어를 길이에 따라 나눈 후 각 리스트를 정렬이진 탐색을 이용하여 쿼리에 해당하는 특정 단어의 개수를 계산 📌코드from bisect import bisect_left, bisect_right#값이 [left_value, right_value]인 데이터의 개수를 반환하는 함수def count_by_range(a, left_value, right_value): right_index=bisect_right(a, right_..
📌문제도현이의 집 N개가 수직선 위에 있다. 각각의 집 좌표는 x1, x2, x3...xN이고, 집 여러개가 같은 좌표를 가지는 일은 없다.도현이는 언제 어디서나 와이파이를 즐기기 위해 집에 공유기 C개를 설치하려고 한다. 한 집에는 공유기를 하나만 설치할 수 있고, 가장 인접한 두 공유기 사이의 거리를 가능한 크게하여 설치하려고 한다.C개의 공유기를 N개의 집에 적당히 설치해서 가장 인접한 두 공유기 사이의 거리를 최대로 하는 프로그램을 작성하시오. 📌풀이이진 탐색으로 가장 인접한 두 공유기 사이의 거리를 조절해가며 매 순간 C보다 많은 개수로 공유기를 설치할 수 있는지 체크C보다 많은 개수로 공유기를 설치할 수 있다면 가장 인접한 두 공유기 사이의 거리를 증가시켜서 더 큰 값에 대해서도 성립하는지..
📌문제고정점이란 수열의 원소 중 그 값이 인덱스와 동일한 원소를 의미한다. 하나의 수열이 N개의 서로 다른 원소를 포함하고 있으며, 모든 원소가 오름차순으로 정렬되어 있다. 이때 이 수열에서 고정점이 있다면 고정점을 출력하는 프로그램을 작성하시오. 고정점은 최대 1개만 존재한다.단 시간복잡도 O(logN)으로 알고리즘을 설계하시오. 📌풀이O(logN)으로 고정점을 찾으려면 선형 탐색으로는 시간 제한에 맞게 문제를 해결할 수 없음이진 탐색을 수행해서 빠르게 고정점을 찾아야 함찾고자하는 값이 중간점과 동일하다고 가정하고 탐색 수행중간점이 가리키는 위치의 값보다 중간점이 작은 경우, 왼쪽 부분을 탐색중간점이 가리키는 위치의 값보다 중간점이 큰 경우, 오른쪽 부분을 탐색 📌코드def binary_searc..
📌문제N개의 원소를 포함하고 있는 수열이 오름차순으로 정렬되어 있다. 이때 이 수열에서 x가 등장하는 횟수를 계산하시오.단 이 문제는 시간 복잡도 O(logN)으로 알고리즘을 설계하지 않으면 시간 초과 판정을 받습니다. 📌풀이모든 원소가 정렬이 된 상태로 입력되므로 이진 탐색을 이용하여 값이 x인 원소의 개수를 O(logN)에 찾아낼 수 있음수열 내 x가 존재한다면 연속적으로 나열되어 있음따라서 x가 처음 등장한 인덱스와 마지막으로 등장한 인덱스의 차를 계산 이진 탐색 함수 2개를 사용하여 문제 해결1. 가장 첫번째 위치를 찾는 이진 탐색 함수2. 가장 마지막 위치를 찾는 이진 탐색 함수 📌코드# 정렬된 수열에서 값이 x인 원소 개수를 세는 메서드def count_by_value(array, x)..
📌문제정렬된 두 묶음의 숫자 카드가 있을 때 각 묶음의 카드의 수를 A,B라고 하면 보통 두 묶음을 합쳐서 하나로 만드는데에는 A+B번의 비교를 해야한다.매우 많은 숫자 카드 묶음이 책상 위에 놓여 있다. 이들을 두 묶음씩 골라 서로 합쳐나간다면, 고르는 순서에 따라서 비교 횟수가 매우 달라진다. N개의 숫자 카드 묶음의 각각의 크기가 주어질 때 최소한 몇 번의 비교가 필요한지 구하시오. 📌풀이항상 가장 작은 크기의 두 카드 묶음을 합쳤을 때 최적의 해 보장매 상황에서 가장 작은 크기의 두 카드 묶음을 꺼내어 이를 합친 뒤 다시 리스트에 삽입우선순위 큐 사용(원소를 넣었다 빼는 것만으로 정렬된 결과 얻음) 📌코드import heapqn = int(input())# 힙에 초기 카드 묶음을 모두 삽입h..
📌문제https://school.programmers.co.kr/learn/courses/30/lessons/42889 프로그래머스SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr 📌풀이스테이지 번호를 1부터 N까지 증가시키며 해당 단계에 머물러 있는 플레이어들의 수를 계산플레이어들의 수 정보를 이용하여 모든 스테이지에 따른 실패율을 계산실패율 기준으로 내림차순 정렬 📌코드def solution(N, stages): answer=[] length=len(stages) #스테이지 번호를 1부터 N까지 증가 for i in range(1, N+1): #해당 스테이지에 머물러..