1. 문제 https://www.acmicpc.net/problem/1463 1463번: 1로 만들기 첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다. www.acmicpc.net 1이상의 정수 x가 주어질때, 1) x가 3으로 나누어 떨어지면 3으로 나눈다 2) x가 2로 나누어 떨어지면 2로 나눈다 3) x에서 1을 뺀다 3가지 연산을 적절히 사용해서 1을 만들고 싶다 연산을 사용한 횟수의 최솟값을 출력한다면? 2. 나의 풀이 다이나믹 프로그래밍 연습문제니까 다이나믹 프로그래밍을 써야겠지 기본이 바텀업이고 반복문 구현이라고 배웠으니까 이에 따라보자 작은 문제부터 구해놓고, 이들을 이용해서 반복문을 구현한다면.. 1이상이니까 dp[0] = 0, 1은 연산을 안해도 1이니까 d..
1. 중복되는 연산을 줄이기 현실 세계의 다양한 문제중에 컴퓨터를 활용해도 해결하기 어려운 문제란..? 최적의 해를 구하는데 시간이 매우 많이 필요하거나, 메모리 공간이 매우 많이 필요한 문제 등이 컴퓨터로도 해결하기 어려운 문제 컴퓨터는 연산 속도에 한계가 있고, 메모리 공간을 사용할 수 있는 데이터의 개수도 한정적 그래서 연산속도와 메모리 공간을 최대한 활용할 수 있는 효율적인 알고리즘이 필요하다 2. 다이나믹 프로그래밍 어떤 문제는 메모리 공간을 약간 더 사용하면 연산 속도를 비약적으로 증가시킬 수 있는 방법이 있다 대표적인 방법이 다이나믹 프로그래밍(동적계획법)이다. 다이나믹 프로그래밍으로 해결할 수 있는 대표적인 문제가 피보나치 수열 피보나치 수열은 이전 두 항의 합을 현재의 항으로 설정하는 특..
1. 문제 N개의 block이 일렬로 있고 0부터 N-1까지 숫자가 붙어있다. 사이가 안좋은 개구리가 하나의 block위에 함께 있는데 이들이 서로 최대한 멀리 떨어지려고 한다. 만약 J와 K, J= s_h: s_h = h first += 1 else: break 현재 s-1에 첫번째 개구리가 시작할건데 blocks의 s부터 오른쪽으로 순회를 해서 h라고 두는거임 만약 h가 시작높이 s_h보다 크거나 같으면 점프할 수 있고 현재 개구리 높이 s_h를 h로 두고 first에 1을 더해서 개구리 위치를 갱신한다 근데 점프를 못하는 순간 더 이상 오른쪽으로는 못간다는 소리이므로 반복문을 탈출 s_h = blocks[s] #second frog for ind,h in enumerate(blocks[s::-1])..
1. 동적계획법? 다이나믹 프로그래밍(dynamic programming) ‘하나의 문제는 단 1번만 풀도록 하는 알고리즘’ 2개의 가정 하에 사용할 수 있다 1-1) 큰 문제를 작은 문제로 나눌 수 있다. 1-2) 작은 문제에서 구한 정답은 그것을 포함하는 큰 문제에서도 동일하다. 크고 어려운 문제가 있으면 그것을 먼저 잘게 나누어서 해결한 뒤에 각각을 처리한 다음 나중에 전체의 답을 구하는 것 이 과정에서 이미 계산한 결과는 배열에 따로 저장한다음 나중에 동일한 계산을 할때 저장된 값을 단순히 호출하여 반환하기만 하면 된다 2. 피보나치 수열 피보나치 수열의 점화식은 $$a_{n}=a_{n-1}+a_{n-2}$$ 특정한 위치의 숫자를 구하기 위해 바로 이전의 숫자와 두번 이전의 숫자의 합을 구함 초기..
딥러닝/머신러닝, 통계학, IT프로그래밍, 알고리즘을 좋아하는 사람 https://github.com/yundaehyuck
