로그 남기기

11053 - 가장 긴 증가하는 부분 수열 📌 문제 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이고, 길이는 4이다. 📋 코드 N = int(input()) arr = list(map(int, input().split())) dp = [1] * N for i in range(N): for j in range(i+1, N): if arr[i] < arr[j]: dp[j] = max(dp[j], dp[i] + 1) print(max(dp)) 💡 한마디 이 문제는 LIS (Longest Increasing Subsequence), 즉 최장 증가 수열로..

10815 - 숫자 카드 📌 문제 숫자 카드는 정수 하나가 적혀져 있는 카드이다. 상근이는 숫자 카드 N개를 가지고 있다. 정수 M개가 주어졌을 때, 이 수가 적혀있는 숫자 카드를 상근이가 가지고 있는지 아닌지를 구하는 프로그램을 작성하시오. 📋 코드 def binary_search(target, left, right): while left target: right = mid - 1 else: left = mid + 1 return 0 N = int(input()) card = list(map(int, input().split())) M = int(input()) check_card = list(map(int, input().split())) card.sort() result = [] for num in..

1753 - 최단경로 📌 문제 방향그래프가 주어지면 주어진 시작점에서 다른 모든 정점으로의 최단 경로를 구하는 프로그램을 작성하시오. 단, 모든 간선의 가중치는 10 이하의 자연수이다. 📋 코드 import heapq def dijkstra(start, distance): q = [] heapq.heappush(q, (0, start)) distance[start] = 0 while q: weight, v = heapq.heappop(q) if distance[v] >= weight: for i, cost in graph[v]: new_cost = weight + cost if distance[i] > new_cost: distance[i] = new_cost heapq.heappush(q, (new_c..

1647 - 도시 분할 계획 📌 문제 동물원에서 막 탈출한 원숭이 한 마리가 세상구경을 하고 있다. 그러다가 평화로운 마을에 가게 되었는데, 그곳에서는 알 수 없는 일이 벌어지고 있었다. 마을은 N개의 집과 그 집들을 연결하는 M개의 길로 이루어져 있다. 길은 어느 방향으로든지 다닐 수 있는 편리한 길이다. 그리고 각 길마다 길을 유지하는데 드는 유지비가 있다. 마을의 이장은 마을을 두 개의 분리된 마을로 분할할 계획을 가지고 있다. 마을이 너무 커서 혼자서는 관리할 수 없기 때문이다. 마을을 분할할 때는 각 분리된 마을 안에 집들이 서로 연결되도록 분할해야 한다. 각 분리된 마을 안에 있는 임의의 두 집 사이에 경로가 항상 존재해야 한다는 뜻이다. 마을에는 집이 하나 이상 있어야 한다. 그렇게 마을의 ..

출처 - 이것이 취업을 위한 코딩테스트다 with 파이썬 금광 📌 문제 n X m 크기의 금광이 있다. 금광은 1 X 1 크기의 칸으로 나누어져 있으며, 각 칸은 특정한 크기의 금이 들어 있다. 채굴자는 첫 번째 열부터 출발하여 금을 캐기 시작한다. 맨 처음에는 첫 번째 열의 어느 행에서든 출발할 수 있다. 이후에 m번에 걸쳐서 매번 오른쪽 위, 오른쪽, 오른쪽 아래 3가지 중 하나의 위치로 이동해야 한다. 결과적으로 채굴자가 얻을 수 있는 금의 최대 크기를 출력하는 프로그램을 작성하라. 📋 코드 T = int(input()) for _ in range(T): N, M = map(int, input().split()) tmp = list(map(int, input().split())) gold = [] ..

출처 - 이것이 취업을 위한 코딩테스트다 with 파이썬 고정점 찾기 📌 문제 고정점이란, 수열의 원소 중에서 그 값이 인덱스와 동일한 원소를 의미한다. 예를 들어 수열 a = {-15, -4, 2, 8, 13}이 있을 때 a[2] = 2이므로, 고정점은 2가 된다. 하나의 수열이 N개의 서로 다른 원소를 포함하고 있으며, 모든 원소가 오름차순으로 정렬되어 있다. 이때 이 수열에서 고정점이 있다면, 고정점을 출력하는 프로그램을 작성하라. 만약 고정점이 없다면 -1을 출력한다. 단, 이 문제는 시간 복잡도 O(logN) 으로 알고리즘을 설계하지 않으면 '시간 초과' 판정을 받는다. 📋 코드 def binary_search(arr, start, end): if start > end: return -1 mid..