JB의 이모저모

LIS(Longest Increasing Subsequence) 수열이 주어졌을 때 가장 긴 증가하는 부분 수열을 구하는 문제이다. 이 문제를 푸는 두 가지 방법이 존재한다. 1. Dynamic Programming (동적 계획법) 2. Binary Search (이분 탐색) 두가지 방법 모두 알아야하는 이유는 DP는 O(n^2)의 시간복잡도를 가지고 이분탐색은 O(nlogn)을 가지기 때문에 두 방법 모두 익혀야한다. 본인도 dp 방법만 익히고 이분 탐색 방법을 공부하지 않아 시간초과 이유로 공부할 겸 기록을 남긴다. Dynamic Programming (동적 계획법)을 활용한 문제 풀이 가장 긴 증가하는 부분 수열 11053번: 가장 긴 증가하는 부분 수열 수열 A가 주어졌을 때, 가장 긴 증가하는 ..

https://www.acmicpc.net/problem/12865 12865번: 평범한 배낭 첫 줄에 물품의 수 N(1 ≤ N ≤ 100)과 준서가 버틸 수 있는 무게 K(1 ≤ K ≤ 100,000)가 주어진다. 두 번째 줄부터 N개의 줄에 거쳐 각 물건의 무게 W(1 ≤ W ≤ 100,000)와 해당 물건의 가치 V(0 ≤ V ≤ 1,000) www.acmicpc.net 문제 이 문제는 아주 평범한 배낭에 관한 문제이다. 한 달 후면 국가의 부름을 받게 되는 준서는 여행을 가려고 한다. 세상과의 단절을 슬퍼하며 최대한 즐기기 위한 여행이기 때문에, 가지고 다닐 배낭 또한 최대한 가치 있게 싸려고 한다. 준서가 여행에 필요하다고 생각하는 N개의 물건이 있다. 각 물건은 무게 W와 가치 V를 가지는데,..

※파이썬 문제를 풀다보면 2진수로 변환하여 문제를 해결하는 경우가 종종 있다. 그런 경우에는 bin()함수를 이용하여 문제를 해결하였다. 그런데 2진수가 아니라 8진수 16진수 혹은 3진수 이런 문제가 나오면 풀 자신이 없어서 공부할 겸 기록을 남긴다. n진수 → 10진수 int() 함수를 사용 int(string,base) 위와 같은 형식으로 사용 base에는 진법을 넣는다. print(int('111',2)) print(int('111',3)) print(int('111',6)) print(int('ACF',16)) 7 13 43 2767 ※ 주의 print(int(111,2)) TypeError: int() can't convert non-string with explicit base 위와 같이 s..