이코테에서 효율적인 화폐 구성 문제와 비슷해서 비슷한 풀이로 풀 수 있었다.첫번째 코드n = int(input())#설탕이 최대 5000이므로 data = [5001] * (n+1)bag = [3, 5]for i in bag: if i > n: continue data[i] = 1#배열 n에...3키로,, 5키로for k in bag: for i in range(k, n+1): if data[i-k] != 5001: #가방 단위로 배달 가능하면... data[i] = min(data[i], data[i-k]+1)if data[n] != 5001: print(data[n])else: print(-1) 이전에 이 문제를 푼 코드가 있어서 확인해 봤더니 이전에 푼 코드가 더 빠르고..
알고리즘
만약 아래와 같이 주어졌다고 하면BFS탐색하면서 주변에 1로 된 노드를 탐색하면서 이전 노드의 최소 방문 횟수에 + 1을 해주면서 방문처리를 해주면 아래와 같다. 결국 마지막 노드에 있는 수를 출력해주면 동빈이가 방문하는 최소 노드 개수를 구할 수 있다.작성 코드from collections import deque#풀이시간: 28m 40s# 소스코드 날라가서 두번 풂..#이전 노드를 중심으로 상하좌우 bfs탐색 -> 이전 노드에는 해당 노드를 방문하기 위한 최소 노드 개수가 적혀져 있으므로 상하좌우 탐색하면서 이전 노드에 적힌 수 + 1을 하면 다음 노드로 가기 위한 최소 노드 개수를 구할 수 있음n, m = map(int, input().split())map = list(list(map(int, in..
이 문제는 이코테 책에서 DFS/BFS 파트의 문제인데 조합으로도 풀이가 가능해서 `itertools` 라이브러리의 `permutations`클래스를 사용해서 풀었다. 하지만 Python3로 제출했지만 시간초과 발생from itertools import permutationsn = int(input())lst = list(map(int,input().split()))op_cnt = list(map(int,input().split()))op = ['+', '-', '*', '%']op_idx = []for cnt, op_symbol in zip(op_cnt, op): for i in range(cnt): op_idx.append(op_symbol)op = list(permutations(op_idx..
리스트를 사용한 큐 보통 파이썬에서는 deque를 사용해서 큐를 구현한다리스트 내장 함수를 사용해서 큐 기능을 구현할 수도 있다.q = []q.append(1)q.pop(0)`append()`: 리스트 뒤쪽에 요소 넣기`pop(0)`: 리스트 맨 앞 요소 꺼내기 하지만 append나 pop은 일반적으로 '가장 뒤쪽의 원소'를 기준으로 수행한다.따라서 앞쪽에 있는 원소를 처리할 때에는 리스트에 포함된 데이터의 개수에 따라 많은 시간이 소요될 수도 있다는 점을 기억하자.deque를 사용한 큐 데이터의 시작 부분이나 끝 부분에 데이터를 삽입하거나 삭제할 때 매우 효과적으로 사용될 수 있다.시간복잡도가 O(1)이다.from collections import dequedata = deque([2,3,4])data..
이코테 책을 기반으로 작성된 글입니다. 카카오.... 나한텐 너무 먼 카카오... 코테 문제부터 심상치 않아... 도저히 모르겠어서 그냥 바로 해설보고 풀었다. 해설에서 알아두면 좋은 코드만 작성해보기로 했다 2차원 리스트 90도 회전#열쇠를 90도 회전하는 경우def rotate_a_matrix_by_90_degree(key): n = len(key) result = [[0]*n for _ in range(n)] for i in range(n): for k in range(n): result[k][n-i-1] = key[i][k] return result 3X3인 열쇠임을 가정해보자.key[0][0] -> result[0][2]key[0][1] -> result[1][2]key[..
동적 계획법이란? 크기가 크거나 복잡한 문제를 효율적으로 풀기위해 작거나 간단한 어러개의 문제로 나눠서 푸는 방법으로, 그리디 알고리즘과 같이 최적화 문제를 해결하는 알고리즘이다.입력 크기가 작은 문제들을 해결한 후에 그 해들을 이용하여 보다 큰 크기의 부분 문제들을 해결하고, 최종적으로 원래 주어진 입력의 문제를 해결하는 알고리즘 설계기법으로 프로그램 성능의 향성을 기대할 수 있다.피보나치 수를 구하는 함수에 DP알고리즘 적용하기 문제를 부분 문제로 분할fibonacci(0) = 0, fibonacci(1) = 1fibonacci(n) = fibonacci(n-1) + fibonacci(n-2) (n>=2) 가장 작은 부분 문제부터 해를 구한다.부분문제들의 해를 테이블에 저장하고 이를 이용하여 상위 ..
Memoization 이란동일한 계산을 반복적으로 해야할 때, 이전에 계산한 값을 메모리에 저장하여 중복적인 계산을 제거하여 전체적인 실행 속도를 빠르게 해주는 기법으로 동적 계획법(DP, Dynamic Programming)의 핵심이 되는 기술. 피보나치수열로 알아보는 재귀과 memoizationhttps://mystudylog.tistory.com/72 [파이썬] 10870 피보나치 수 5처음에 재귀함수로 풀이 하지만 재귀함수로 하면 겹치는 계산이 존재해서 다른 풀이도 찾아보았다. import sys def fibo(n): if n == 0: return 0 elif nmystudylog.tistory.comdef fibo_memo(n): global memo if n >= len(memo)..
접근 방법2차원 배열에 입력을 저장하고 더하자.n, m이 입력되면 [m][n]인 이중 배열을 선언하고i, j, x, y가 입력되면 이중 반복분으로 [j][i] ~ [y][x]를 더하자. 1차시도 (시간초과)2차시도 (pypy로 컴파일, 성공)import sysn, m = map(int, sys.stdin.readline().split())lst = [[0]*n for _ in range(m)]for i in range(n): for idx, k in enumerate(sys.stdin.readline().split()): lst[idx][i] = int(k)num = int(sys.stdin.readline())result = [0]*numfor idx in range(num): i,j,x,y ..
요세푸스 순열이 대체 무슨 규칙으로 정해지는 지 감도 안잡혔음. 맨처음에는 N을 기준으로 양 끝의 수를 더해서 N이 되도록해야하나? 예를 들어서 이면 3+4 = 7, 6+1 = 7, 2+5 = 7 했는데 그러면 3, 6, 2 이 순서는 어떻게 만들어질지 모름. 문제를 잘 보면 " 한 사람이 제거되면 남은 사람들로 이루어진 원을 따라 이 과정을 계속해 나간다."이게 포인트였던 거 같다. 한 사람이 제거되면 제거된 사람을 제외한 새로운 길이를 기준으로 삭제할 사람을 찾아내야 했다. 풀이과정 1. 입력으로 주어진 k의 인덱스가 어디있는 지 찾는다. 2. 제거한 사람의 인덱스를 새로운 배열에 저장하고 기존 리스트에서는 삭제. 3. k번째 사람이 제거된 리스트의 길이로 재조정하고, (기존 배열에서의 k번째 사람의..
