모카의 촉촉한 개발 로그

방법 2 힙을 사용하여 구현은 어렵지만 빠르게 동작하는 코드 이번 방법은 최악의 경우에도 시간 복잡도 O(ElogV)를 보장할 수 있다.(V는 노드의 개수,E는 간선의 개수) 방법 1 에서는 매번 최단거리 테이블을 선형적으로(모든 원소를 앞에서부터 하나씩) 탐색해야 했다. 이 과정에서 O(V)의 시간이 걸렸다. 하지만 최단거리가 가장 짧은 노드를 단순히 선형적으로 찾는것이 아니라 더욱 빠르게 찾을수 있다면 시간 복잡도를 더 줄일 수 있다. 이 과정에서 힙 자료구조를 사용하게 된다. 힙을 사용하면 특정 노드까지의 최단 거리에 대한 정보를 힙에 답아서 처리하므로 출발 노드로부터 가장 짧은 노드를 더욱 빠르게 찾을 수 있다. 힙 자료 구조 힙 자료구조는 우선순위 큐를 구현하기 위하여 사용하는 자료구조 중 하나..

다익스트라 알고리즘의 동작원리 기본적으로 그리디 알고리즘으로 분류가 된다. '매번 가장 비용이 적은 노드를 선택'해서 임의의 과정을 반복하기 때문이다. 알고리즘의 원리는 아래와 같다. 1. 출발 노드를 설정한다. 2. 최단 거리 테이블을 초기화 한다. 3. 방문하지 않은 노드 중에서 최단 거리가 가장 짧은 노드를 선택한다. 4. 3에서 선택한 해당 노드를 거쳐 다른 노드로 가는 비용을 계산하여 최단 거리 테이블을 갱신한다. 5. 위 3,4번을 반복한다. '각 노드에 대한 현재까지의 최단거리' 정보를 1차원 리스트에 저장하며 리스트를 계속 갱신한다는 특징이 있다. 매번 현재 처리하고 있는 노드를 기준으로 주변 간선을 확인한다. 나중에 현재 처리하고 있는 노드와 인접한 노드로 도달하는 더 짧은 경로를 찾으면..

n가지 종류의 화폐를 사용해 m원을 만드는 최소한의 가지수를 출력하는 문제. 나의 코드 n,m=map(int,input().split()) coin=[] for i in range(n): coin.append(int(input())) dy=[10001]*(m+1) dy[0]=0 for i in range(n): for j in range(coin[i],m+1): dy[j]=min(dy[j],dy[j-coin[i]]+1) if dy[m]==10001: print(-1) else: print(dy[m]) 이번에도 문제를 풀지 못했다.. 30분 가량 끙끙된 이후 분명 이전에 봤던 문제 같아 인터넷 서칭을 해보니 이전에 봤던 유형이 맞았다..! 초반 dp테이블값을 0으로 모두 고정을 하고 접근을 하려다 보니 막..

N을 입력 받았을 떄 가로가 N 세로가 2인 바닥이 생긴다. 그떄 1 x2, 2x1, 2x2 크기의 3종류의 타일로 덮을수 있는 경우의 수를 찾아라. 나의 코드 n=int(input()) dp=[0]*(n+1) dp[1]=1 dp[2]=3 for i in range(3,n+1): dp[i]=dp[i-1]*2-1 print(dp[n]%796796) 음.. 이번 DP 문제도 확신이 안든다... 애초에 위 코드는 결국 다이나믹프로그래밍이 아니라 그냥 입력값*2-1을 출력한 값이기도 하고... 확실한 근거를 바탕으로 패턴을 찾아야 하는데 그 확실한 근거는 늘 안보이고 짜잘한 의심? 정도를 가지고 코드를 짜게 된다.. 나의 그 짜잘한 의심은 아래 사진과 같다. 보라색 선으로 표시한 부분을 보면 i번쨰의 경우의 수..

N 개의 숫자가 입력 될때 최소 한칸 이상씩은 간격을 두고 선택할 때 선택한 숫자의 합의 최댓값을 구하라. 입력 예시) 4 1 3 1 5 출력예시) 8 나의 코드 N=int(input()) arr=list(map(int,input().split())) arr.append(0) dy=[0]*(N+1) dy[1]=1 dy[2]=max(arr[0],arr[1]) for i in range(3,N+1): dy[i]=max(dy[i-1],max(dy[:i-1])+arr[i-1]) print(dy[4]) 음..그림을 그려가며 생각한 로직대로 짜서 입력값대로의 출력값은 나오긴 했는데 확신이 없다.. dp테이블은 한칸을 건너뛰어야 하니 '바로 이전 테이블 값'과 ' 두칸 이전 까지의 dp테이블 값의 최대값과 현재 ar..

정수 X가 주어질 때 아래와 같은 4가지 연산을 사용할 수 있다. 첫번째, 5로 나누어 떨어지면 5로 나눈다 두번째, 3으로 나누어 떨어지면 5로 나눈다. 세번째, 2로 나누어 떨어지면 2로 나눈다. 네번째, x에서 1을 뺸다. 위 연산 4개를 적절히 사용해서 1을 만들려고 한다. 연산을 사용하는 횟수의 최솟값을 구하라. 입력예시) 26 출력예시) 1 나의 코드 못품.. 꽤나 많은 시간 그림과 함께 이것저것 생각해 보았지만 구현 실패...으악 정답 코드 X=int(input()) dp=[0]*(X+1) for i in range(2,X+1): dp[i]=dp[i-1]+1 if i%2==0: dp[i]=min(dp[i],dp[i//2]+1) if i%3==0: dp[i]=min(dp[i],dp[i//3]+..

중복되는 연산을 줄이자 컴퓨터를 사용하여 해결하기 어려운 문제들 중에는 최적의 해를 찾는 데 많은 시간이 필요하거나 많은 메모리 공간이 필요한 문제들이 있다. 컴퓨터는 계산 속도와 메모리 공간을 제한하고 있기 때문에 이러한 문제들을 해결하는 데에는 제약이 많이 있다. 그래서 우리는 속도와 메모리 공간을 최대화할 수 있는 효율적인 알고리즘을 작성해야 한다. 그러나 일부 문제의 경우에는 약간의 메모리 공간을 더 사용하여 계산 속도를 현저하게 높일 수 있는 방법이 있다. 대표적인 방법 중 하나는 이 장에서 다루는 동적 프로그래밍이다. 먼저 동적 프로그래밍의 기본 아이디어를 소개하고, 그 다음 동적 프로그래밍의 두 가지 방법 (탑다운과 바텀업)을 알아보자. 특히, 동적 프로그래밍에서 자주 사용되는 메모이제이션 ..

N개의 떡이 있을때 길이가 H인 절단기로 잘랐을 때 남은 떡 길이의 합이 적어도 M이 되게 하는 최대의 H를 찾아라. 입력 예시) 4 6 19 15 10 17 나의 코드 n,m=map(int,input().split()) arr=list(map(int,input().split())) MM=0 left=0 right=max(arr) while left0: temp+=(x-mid) if temp>=m : left=mid+1 MM=mid elif temp

N개의 물건 중에 M개의 물건들이 있는지 확인을 하라. (1

순차 탐색 리스트 안에 있는 특정한 데이터를 찾기 위해 앞에서부터 데이터를 하나씩 차례대로 확인하는 방법 보통 정렬되어있지 않은 리스트에서 데이터를 찾아야 할때 사용 시간복잡도는 O(N)이다. 이진 탐색 데이터가 정렬되어 있어야만 사용할 수 있는 알고리즘이다. 시작점,끝점,중간점으로 범위를 나누어 탐색한다. 찾으려는 데이터와 중간점 위치에 있는 데이터를 반복적으로 비교해서 데이터를 찾는다 STEP 1 시작점과 끝점을 확인한 다음 둘 사이 중간점을 시작점과 끝점을 더한 값을 2로 나눈 값으로 한다. 다음으로 중간점[4]의 데이터와 8과 찾으려는 데이터 4를 비교한다. 중간점의 데이터 8이 더 크므로 중간저 이후의 값은 확인 할 필요가 없다. 그래서 끝점을 [4]의 이전인 [3]으로 변경 STEP 2 1과 ..