본문 바로가기
반응형

전체 글150

[백준][DP] 11053번 가장 긴 증가하는 부분 수열 python (200922) www.acmicpc.net/problem/11053 11053번: 가장 긴 증가하는 부분 수열 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이 www.acmicpc.net 1. 문제 설명 2. 풀이 n = int(input()) a = list(map(int, input().split())) dp = [0 for i in range(n)] for i in range(n): for j in range(i): if a[i] > a[j] and dp[i] < dp[j]: dp[i] = dp[j] dp[i] .. 2020. 9. 22.
[백준][DP] 1463번 1로 만들기 python (200921) 1. 문제설명 2. 풀이 어제 설탕 문제처럼 단순히 조건문으로 풀수 있다고 생각했는데 아니었다 해당문제는 전형적인 DP 문제였음 우선 조건문으로 풀었을 때, def solution(input_num): chk = 0 num_dict = {} while input_num > 1: # print(input_num) if input_num % 2 !=0: # 홀수 경우 if input_num % 3 == 0: input_num /= 3 else: input_num -= 1 else: # 짝수 경우 if (input_num -1) % 3 == 0: input_num-=1 else: input_num /= 2 chk +=1 return chk 홀짝의 경우로 나누어서 풀었는데, 내 기준에서는 반례를 찾지 못했지만 .. 2020. 9. 21.
[백준][DP] 2839번 설탕 배달 python (200920) www.acmicpc.net/problem/2839 2839번: 설탕 배달 상근이는 요즘 설탕공장에서 설탕을 배달하고 있다. 상근이는 지금 사탕가게에 설탕을 정확하게 N킬로그램을 배달해야 한다. 설탕공장에서 만드는 설탕은 봉지에 담겨져 있다. 봉지는 3킬로그�� www.acmicpc.net 1. 문제설명 사실 이게 왜 DP 문제인 지 모르겠다. 풀이 예제들을 찾아봐도 DP 가 아니라 다 저마다의 룰로 푼 느낌이랄까? 2. 풀이 def solution(sugar): num = 0 while sugar >0 : if sugar % 5 !=0: sugar -= 3 if sugar < 0: return -1 num += 1 # 3개짜리 추가됨 elif sugar % 5 ==0: sugar -= 5 num += .. 2020. 9. 20.
[프로그래머스][DP] N으로표현 python (200920) 1. 문제설명 여기서 핵심은 이거다 N 이 5라고 했을 때 N의 사용횟수마다 나오는 숫자들을 구해보자면, 1번 사용 : 5 2번 사용 : 5 + 5 , 5 - 5, 5 * 5, 5 / 5, 55 3번 사용 : 1번 사용과 2번 사용의 조합으로 구해진다*** 1) 1번 사용 (+-/*) 2번 사용 --> 총 생성 갯수 : 1 (1번 사용 갯수) * 5 (2번 사용갯수) = 5 개 숫자 생성 5 + 5 + 5 , 5 - 5 + 5 , 5 * 5 + 5 , 5 / 5 + 5 , 5 55 2) 2번 사용 (+-/*) 1번 사용 --> 총 생성 갯수 : 5 (2번 사용갯수) * 1 (1번 사용 갯수) = 5 개 숫자 생성 5 + 5 + 5 + , 5 + 5 - 5 , 5 + 5 * 5 , 5 + 5 / 5 , 5.. 2020. 9. 20.
[백준][DP] 2193번 이친수 python (200919) 1. 문제 설명 2. 풀이 def solution(num): two_num = bin(num)[2:] fibo_list = [1,1] for fib_idx in range(2,num): fibo_list.append(fibo_list[fib_idx-2] + fibo_list[fib_idx-1]) if not fibo_list: return 0 return fibo_list.pop() num = int(input()) print(solution(num)) 간단히 6 까지만 손으로 그려보면 2 - 1개 3 - 2개 4 - 3개 5 - 5개 6 - 8개 7 - 5+8 = 13개 앞의 두 수를 더해서 만들어 지는 것을 알 수 있다. 피보나치 피보나치는 DP로 풀어야 한다. ! 그래서 리스트에 각 값을 저장해주는.. 2020. 9. 19.
[프로그래머스][DP] 정수삼각형 python (200917) 0. DP DP의 핵심 컨셉은 그때 그때 결과값을 저장해두고 그걸 불러오는 방식이다. www.fun-coding.org/Chapter14-dp_divide.html 파이썬과 컴퓨터 사이언스(기본 알고리즘): 동적 계획법과 분할 정복 - 잔재미코딩 프로그래밍 연습 피보나치 수열: n 을 입력받아서 다음과 같이 계산됨 n 을 입력받았을 때 피보나치 수열로 결과값을 출력하세요 함수를 fibonacci 라고 하면, fibonacci(0):0 fibonacci(1):1 fibonacci(2):1 fibon www.fun-coding.org 여기서도 그걸 적용해보자 ! 1. 문제 설명 2. 풀이 def solution(triangle): height = len(triangle) up_tri = triangle.co.. 2020. 9. 17.
ㅇㅇ https://huidea.tistory.com/93 2020. 9. 8.
[프로그래머스][stack] 사전순 부분문자열 (200903) def solution(sentence): stack = [] for alphabet in sentence: while len(stack) > 0 and stack[-1] < alphabet: # 탐색 알파벳이 , 현재 스택 맨 끝보다 정렬순서작으면 stack.pop() stack.append(alphabet) return ''.join(stack) 1. 문제 풀이 어떤 문자열 s가 주어졌을 때, s로부터 만들 수 있는 부분 문자열 중 사전 순으로 가장 뒤에 나오는 문자열을 찾으려 합니다. 부분 문자열을 만드는 방법은 다음과 같습니다. s에서 일부 문자를 선택해 새로운 문자열을 만듭니다. 단, 이때 문자의 순서는 뒤바꾸지 않습니다. 예를 들어 문자열 xyb로 만들 수 있는 부분 문자열은 다음과 같습니다... 2020. 9. 3.
코테 유형별 풀이법 (내나름 정리) 1) 입력 순서 그대로 둔채 / 숫자 혹은 문자 조합의 정렬이라면 --> 스택 or greedy : 뽑아 가면서 앞으로 탐색 - 스택 비슷한데 숫자 조합 정렬 그리디로 푼것 : https://huidea.tistory.com/51?category=879544 https://huidea.tistory.com/4 2) 입력 숫자/문자를 계속 업데이트 하면서 정렬해야하는 상황... --> 힙힙 자료구조 3) 리스트 인덱스 앞에서 부터 뽑아야 하는 상황이면 --> 큐 (deque 자료형태 만들고) 2020. 8. 28.
GPT- 한국어 적용 https://blog.pingpong.us/generation-model/ 2020. 8. 13.
반응형

티스토리툴바