동적 계획법이란? 크기가 크거나 복잡한 문제를 효율적으로 풀기위해 작거나 간단한 어러개의 문제로 나눠서 푸는 방법으로, 그리디 알고리즘과 같이 최적화 문제를 해결하는 알고리즘이다.입력 크기가 작은 문제들을 해결한 후에 그 해들을 이용하여 보다 큰 크기의 부분 문제들을 해결하고, 최종적으로 원래 주어진 입력의 문제를 해결하는 알고리즘 설계기법으로 프로그램 성능의 향성을 기대할 수 있다.피보나치 수를 구하는 함수에 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번째 사람의..
수학적?으로 접근해서 매우 복잡하게 해석했다.. 좌표로 생각하면서 푸니까 서로 겹치는 부분을 찾기 위해 좌표가 주어지면 해당 좌표가 다른 좌표와 겹치는 지, 아닌지 검사하기 위해 조건문으로 다 걸러서 찾아냄 1차 시도 import java.io.*; import java.util.*; public class Main { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); long s = 0; int n = Integer.parseInt(br.readLine()); int[][] lst = new int[n][2]; fo..
d(n)이라는 함수를 만들어서 리스트에 셀프넘버가 아닌 것들을 저장하자 라는 생각으로 접근 시도1 lst = [] def d(n): #셀프넘버가 아닌 것들 num = n + int(n/1000) + int(n%1000/100) + int(n%100/10) + n%10 return num n=0 while(True): n += 1 if d(n) > 10000: break lst.append(d(n)) for i in range(1, 10001): if i not in lst: print(i) 아무리 생각해도 맞는거 같은데 자꾸 출력이 이상하게 나와.... 그래서 왜 이상한지 손으로 노가다로 풀어봤다 저 코드를 실행하면 9999가 출력되는데 n = 9972일때 d(n) = 9999를 반환 하지만 내 코드에서..
처음에 재귀함수로 풀이 하지만 재귀함수로 하면 겹치는 계산이 존재해서 다른 풀이도 찾아보았다. import sys def fibo(n): if n == 0: return 0 elif n
처음에 간단하게 그냥 5로나누고 나머지를 2로 나눠서 나눠떨어지지 않으면 -1출력하면 되는거 아닌가? 했지만 당연히 아니다. 거스름돈이 13원인 경우 5원 한개 2원 4개로 거스름돈을 거슬러 줄 수 있다. 그럼 어떻게 해야할까? 최소한의 동전 개수로 거스름돈을 거슬러 줘야하므로 먼저 5로 나눠주고 cnt= 거스름돈 / 5 저장하고, 나머지 = n % 5 나머지가 2로 나눠지지 않는다면 나머지 += 5로 5원을 회수하고 cnt -= 1을 해준다. (동전 회수 했으므로 cnt도 감소해야함) 그리고 다시 5를 더한 나머지가 2로 나눠지는지 확인.... 위 과정 반복하다가 나머지에 계속 +5를 하다보면 주어진 거스름돈의 값을 넘기는 경우에는 -1을 출력하고 프로그램 종료 import java.util.*; im..
EOF란? EOF는 End Of File의 약자로, 데이터 소스로부터 더 읽을 수 있는 데이터가없음을 나타내는 용어이다. 알고리즘 문제를 풀 때는 주로 입력값을 얼마나 받을지 명시하지 않을 경우 EOF를 사용함. 아래 문제 같은 경우 EOF 사용하여 문제 해결 https://www.acmicpc.net/problem/11034 11034번: 캥거루 세마리2 여러개의 테스트 케이스로 이루어져 있으며, 세 캥거루의 초기 위치 A, B, C가 주어진다. (0 < A < B < C < 100) www.acmicpc.net EOF 사용법 Scanner 클래스 사용할 경우 scanner 클래스는 hasNext() 메소드를 사용한다. hasNext()는 입력된 토큰이 있으면 ture를 반환, 아니면 false를 반환..