본문 바로가기
반응형

Study/Algorithm & Data structure59

[프로그래머스][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.
[프로그래머스][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.
[백준][Greedy] 1931번 문제 - 회의실배정 python (200804) 1. 문제설명 즉, 여기서 중요한 거는 최대한 많은 회의실을 배정하게끔 알고리즘을 짜는건데 나는 이걸 회의시간 길이가 짧은 친구들을 중심으로 정렬하면 되겠다고 생각했다. 결론부터 말하자면, 이것은 틀린 접근... 2. 풀이 - 총 3번의 시도 - 3) 번이 정답 1) 딕셔너리로 풀기, 시작 시점 기준 정렬 - 런타임 에러 (이렇게 풀면 안됩니다) import sys N = int(input()) info_list = [] for idx in range(N): st,end = map(int, sys.stdin.readline().split()) dur = end - st info_list.append((st,end,dur)) info_list = sorted(info_list, key = lambda x:.. 2020. 8. 4.
[백준][Greedy] 10610번 문제 - 30 python (200804) 1. 문제 설명 2. 풀이 import sys n = list(sys.stdin.readline().rstrip()) n.sort(reverse=True) if n[-1] != '0' or sum(map(int, n)) % 3 != 0: print(-1) else: print(''.join(n)) 3의 배수 판정법 : 모든 숫자의 합이 3이면 됨. 처음엔 pop 으로 하나씩 뽑아서 판단하는 알고리즘을 만들어야하나 햇지만. 3의 배수는 개별 숫자가 아니라 전체 숫자 합으로 한번에 판명나기에 위의 방법을 선택했음 (아주 간단!) 그리고 해당 문제는 3의 배수가 아닌 30의 배수이기 때문에 1의 자리 숫자가 무조건 0 이어야 한다. 따라서 if 문에 조건 2개를 걸어주었다. 3. 응용 배수 판정법 - 위키백과.. 2020. 8. 4.
[백준][heap] 최대 힙, 절댓값 힙 python (200729) 최대힙과 절대값 힙은 앞에 포스팅에서 풀이를 했던 최소 힙에서 약간만 응용하면 아주 쉽게 풀린다 ! https://huidea.tistory.com/29?category=879544 [백준][heap] 최소힙 python (200726) 1. 문제 설명 https://www.acmicpc.net/problem/1927 1927번: 최소 힙 첫째 줄에 연산의 개수 N(1≤N≤100,000)이 주어진다. 다음 N개의 줄에는 연산에 대한 정보를 나타내는 정수 x가 주어진다. 만약 x가 자연수.. huidea.tistory.com 우선 최대힙 부터 살펴보자면, [ 최대힙 ] 1. 문제 설명 https://www.acmicpc.net/problem/11279 11279번: 최대 힙 첫째 줄에 연산의 개수 N(1≤.. 2020. 7. 29.
[백준][heap] 최소힙 python (200726) 1. 문제 설명 https://www.acmicpc.net/problem/1927 1927번: 최소 힙 첫째 줄에 연산의 개수 N(1≤N≤100,000)이 주어진다. 다음 N개의 줄에는 연산에 대한 정보를 나타내는 정수 x가 주어진다. 만약 x가 자연수라면 배열에 x라는 값을 넣는(추가하는) 연산이고, x가 0이� www.acmicpc.net 2. 풀이 핵심 개념 : heap 을 다뤄야 함. 0 이 아닌 다른 숫자가 들어왔을 때는 heappush 0 이 들어오면 heappop 한 뒤 print 이때 pop 할 숫자 없으면 print 0 1) 내 풀이 (런타임 에러) import heapq N = int(input()) heap_list = [] heapq.heapify(heap_list) for _ in.. 2020. 7. 26.
[프로그래머스][heap] 라면공장 python (200725) 1. 문제설명 1) 라면 공장에서는 하루에 밀가루를 1톤씩 사용합니다. 원래 밀가루를 공급받던 공장의 고장으로 앞으로 k일 이후에야 밀가루를 공급받을 수 있기 때문에 해외 공장에서 밀가루를 수입해야 합니다. 해외 공장에서는 향후 밀가루를 공급할 수 있는 날짜와 수량을 알려주었고, 라면 공장에서는 운송비를 줄이기 위해 최소한의 횟수로 밀가루를 공급받고 싶습니다. 현재 공장에 남아있는 밀가루 수량 stock, 밀가루 공급 일정(dates)과 해당 시점에 공급 가능한 밀가루 수량(supplies), 원래 공장으로부터 공급받을 수 있는 시점 k가 주어질 때, 밀가루가 떨어지지 않고 공장을 운영하기 위해서 최소한 몇 번 해외 공장으로부터 밀가루를 공급받아야 하는지를 return 하도록 solution 함수를 완성.. 2020. 7. 25.
728x90
반응형

티스토리툴바