나보단 잘하자

문제 leetcode.com/problems/best-time-to-buy-and-sell-stock/ 풀이 사실 쉽다. 쉬운 문제인데, 난 항상 처음 생각을 하는 방식이 잘못됐다고 본다. 무조건 for문이 나오고 결국 2중 for문을 썼고, 시간복잡도를 늘려놓는 바람에 통과하지 못했다. 이게 dp인가? 라는 생각을 하긴 했지만 결국 제일 많은 추천을 받은 문제는 dp와 비슷하게 풀더라. 하지만 브루트포스였다. buy = prices[0]//처음 물건을 사는걸로 시작. mx_profit = 0//최종 정답이 될 이 값에 큰 값을 비교해 바꿔주는 형식. for i in range(1,len(prices)): profit = prices[i]-buy//이익은 산 값의 다음 값(초기값을 prices[0]으로 ..

문제 1463번: 1로 만들기 첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다. www.acmicpc.net 풀이 다이나믹 프로그래밍. 한국어로 동적 계획법을 이용해 풀어야 하는 문제이다. 동적 계획법은 상향식과 하향식이 있는데, 처음 두 수를 알기 때문에 상향식으로 문제를 풀었다. 상향식은 제일 작은 인덱스의 수 부터 목표하는 값으로 향하는 것이고, 하향식은 맨 위의 값에서 재귀로 제일 작은 인덱스를 향하는 것이다. 이 동적 계획법이 최솟값을 구하는 면에서 그리디 알고리즘이랑 뭐가 다른가 싶었는데, 그리디 알고리즘은 내가 생각한 처음 최적의 방법이 끝까지 반례 없이 적용이 되는 경우에 이용하고, 동적 계획법은 가능성을 모두 두고 그 안에 최솟값을 찾을 수 있기 때문에 뭔가 그..

문제 11576번: Base Conversion 타임머신을 개발하는 정이는 오랜 노력 끝에 타임머신을 개발하는데 성공하였다. 미래가 궁금한 정이는 자신이 개발한 타임머신을 이용하여 500년 후의 세계로 여행을 떠나게 되었다. 500년 후의 www.acmicpc.net 풀이 거창하지만 사실 별거 없다. A진법 수를 10진법으로 변환한 후 10진법 수를 B진법으로 변환하면 된다. 주의해야 할 점은 10진법 수를 B진법으로 변환할 때, 삽입했던 수의 반대로 정렬해야 하는데 무작정 반대로 정렬해버리면 예를 들어, 2 15 16을 정렬할 때, 16 15 2가 돼야 하는데, 61 51 2가 되기 때문에, 우선 리스트에 삽입 후 [::-1]로 정렬 해야 한다. 또한 출력 시 수를 자릿수에 따라 공백을 포함해 출력해야..

문제 1373번: 2진수 8진수 첫째 줄에 2진수가 주어진다. 주어지는 수의 길이는 1,000,000을 넘지 않는다. www.acmicpc.net 풀이 1. 10진수 -> 2, 8, 16진수 변환 파이썬에는 쉽게 진수 변환을 시켜주는 내장 함수들이 있다. print('10진수 -> 2진수: {}'.format(bin(10))) print('10진수 -> 8진수: {}'.format(oct(10))) print('10진수 -> 16진수: {}'.format(hex(10))) 여기서 앞의 접두어들을 제외시켜 주려면, [2:]를 붙여 세번째 인덱스부터 출력을 시켜 주는 방법도 있고 format을 이용할 수도 있다. 겉으로 감싸진 format은 print를 하기 위함이고 내부의 format을 보면 됨. prin..