📌문제당신은 화성 탐사 기계를 개발하는 프로그래머다. 그런데 화성은 에너지 공급원을 찾기가 힘들다. 그래서 에너지를 효율적으로 사용하고자 화성 탐사 기계가 출발 지점에서 목표 지점까지 이동할 때 항상 최적의 경로를 찾도록 개발해야 한다.화성 탐사 기계가 존재하는 공간은 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): ..
📌문제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..