백준

n(2 ≤ n ≤ 100)개의 도시가 있다. 그리고 한 도시에서 출발하여 다른 도시에 도착하는 m(1 ≤ m ≤ 100,000)개의 버스가 있다. 각 버스는 한 번 사용할 때 필요한 비용이 있다. 모든 도시의 쌍 (A, B)에 대해서 도시 A에서 B로 가는데 필요한 비

11053번은 가장 긴 증가하는 부분수열(LIS)의 길이를 다이나믹 프로그래밍으로 풀고, 14002는 길이 뿐만 아니라 그 수열도 구하는 문제이다 수열 A = {10, 20, 10, 30, 20, 50} 에서 가장 긴 증가하는 부분수열은 10, 20, 30, 50이고

Lis를 다이나믹 프로그래밍 방식으로 구하면 시간복잡도만 O(n^2)이 걸린다. 이를 이분탐색을 통해 구한다면 O(N\*logN)으로 줄일 수 있다12015번은 lis의 길이만 구해도 되는 문제이고, 14003번은 lis가 무엇인지 수열도 구해야 된다. 두 문제는 풀이

알고리즘 종류: 분할정복혼자서 풀었는가?: O...문제 자체는 그렇게 복잡하지 않고 한번에 이해할 수 있는 문제였으나 왜인지 모르게 하루 종일 붙잡고 있었던 문제이다... (일단 merge sort 구현하는 것 자체가 헬이었다 아니 개념은 다 알면서 인간아) 덕분에 머

알고리즘 종류: 분할 정복혼자서 풀었는가?: O샤워실 바닥 타월 깔기 문제를 푼 뒤라서 그렇게 어렵게 풀지는 않았다 처음에는 문제 그대로 재귀로 풀면서 배열을 만들고 거기에 값을 넣을 생각을 했으나, N이 15까지 커질 수 있어서 이렇게하면 시간초과가 뜬다고 한다 따라

알고리즘 종류: 분할 정복혼자서 풀었나요?: O처음에는(정사각형 한 변의 길이가 최대 4일 때) 1. 배수구가 있는 사분면을 찾고 2. 해당 사분면은 배수구 위치를 제외한 모든 원소를 같은 숫자로 채운 다음에 3. 나머지 3개의 사분면은 모였을 때 가운데에 ㄱ자 모양