꿈꾸는 개발자의 devLog

다익스트라 알고리즘 - 한 지점에서 다른 특정 지점까지의 최단 경로를 구해야 하는 경우 사용 플로이드 워셜 알고리즘 - 모든 지점에서 다른 모든 지점까지의 최단 경로를 모두 구해야하는 경우 사용 다익스트라 알고리즘 - 그리디 / 플로이드 워셜 - 다이나믹 프로그래밍 [플로이드 워셜 알고리즘] - 점화식 사용 - A에서 B로 가는 최소 비용 / A에서 K를 거쳐 B로 가는 비용 , 이 두 비용을 비교 후 더 작은 값으로 갱신 - 2차원 리스트 사용 - 연결된 간선은 값을 채워넣고 그렇지 않으면 무한이라는 값 입력 - 자기 자신에서 자기 자신으로 가는 비용은 0 [Step1] 단순히 1번 노드를 거쳐 가는 경우 고려 - D23 = min(D23, D21 + D13) - D24 = min(D24, D21 + ..

** 힙 자료 구조 사용 ** 힙 : 우선 순위 큐를 사용하는 자료구조 - 우선 순위 큐 : 우선 순위가 가장 높은 데이터를 가장 먼저 삭제/데이터를 우선순위에 따라 처리하고 싶을 때 사용 PriorityQueue, headpq --> headq 라이브러리가 더 빠름 [우선 순위 값 표현] 예시) 물건 정보는 물건의 가치와 물건의 무게로만 구성된다고 가정 - 모든 물건 데이터를 (가치, 물건)으로 묶어서 우선순위 큐 자료구조에 삽입 가능 - 이후에 우선순위 큐에서 물건을 꺼내게 되면, 항상 가치가 높은 물건이 먼저 나오게 됨 - 일반적으로 첫 번째 원소를 기준으로 우선순위 설정 --> 예시에서는 '가치'값이 우선순위 값이 됨 [힙] 1. 최소 힙 - 값이 낮은 데이터가 먼저 삭제 2. 최대 힙 - 값이 ..

[최단 경로] - 그대로 가장 짧은 경로를 찾는 알고리즘 -> 길찾기 문제라고도 불림 - 다익스트라, 플로이드 워셜 ( 요 두개가 주로 나옴), 벨만 포드 알고리즘 [다익스트라 최단 경로 알고리즘] - 그래프에서 여러 개의 노드가 있을 때, 특정한 노드에서 출발하여 다른 노드로 가는 각각의 최단 경로를 구해 주는 알고리즘 - "음의 간선"이 없을 때 정상 동작 [다익스트라 동작 원리] 1. 출발 노드 설정 2. 최단 거리 테이블 초기화 3. 방문하지 않은 노드 중에서 최단 거리가 가장 짧은 노드 선택 4. 해당 노드를 거쳐 다른 노드로 가는 비용 계산하여 최단 거리 테이블 갱신 5. 3,4번 반복 ** 각 노드에 대한 현재까지의 최단 거리 정보를 항상 1차원 리스트에 저장하며 리스트를 갱신 - 매번 현재..

뭔가 다이나믹 프로그래밍의 점화식을 알아내는 방법을 찾아낸 것 같다. 사실, 막상 문제를 봤을 때 점화식도 안떠오르고 이걸 뭐 탑다운을 해야하는지 보텀업을 해야하는지 전-혀 감이 안잡혔다.. 제일 화나는 알고리즘 ㅠㅠ 근데 이번 문제를 풀면서 점화식을 어떻게 찾아내야 하는지에 대한 해결책을 알아냈다!!! (다른 사람한텐 쉽고 당연한 방법이지만....) 먼저 !! 일단 나는 문제 해석을 봐도 점화식이 이렇다! 라고 설명을 해줘도 왜 그런지 무슨 원리로 그런지 , 나만 이렇게 뚝딱 안 나오는 건지에 대해 조금 화가 났다,, 근데 생각해보니 그냥 작은 예시를 하나 잡아서 그 안에서 점화식을 찾으면 되는 거였다!!! 만약 주어진 문제에서 작은 예시를 내가 하나 설정해서 미리 답 다 구해보고 그 안에서 답을 찾는..

[개미 전사] - 개미가 메뚜기 마을의 식량 창고 공격 - 개미 전사는 일직선상에 존재하는 식량 창고를 약탈할 때 최소한 한 칸 이상 떨어진 식량창고 약탈해야 함 - 가장 많이 가져갈 수 있는 식량의 양을 구해야 함 개미가 갈 수 있는 모든 경우의 수 - 최대 양을 구하기 위해서는 현재 식량 창고 위치를 기준으로 왼쪽의 식량창고 양과 비교 - 0, 1 위치 값은 제외 (첫번째 창고만 있다면 1, 두번째 창고까지 본다해도 3이 최대이기 때문) - 그럼 위치 값 2부터 시작해서 왼쪽으로 두번째까지만 확인 (세번째까지 갈 필요가 없음 - 5는 무시하고 현재 식량창고를 세번째인 1을 선택했다면? - 왼쪽으로 -1 한 값 하나와 , -2한 값 + 자신의 값 이 둘을 비교하여 둘 중 뭐가 더 큰지 확인 그럼 3이냐..

이전 글은 재귀 방법을 사용하였는데 이는 큰 문제를 해결하기 위해 작은 문제를 호출하는 탑다운 방식임 !! 근데 단순히 반복문을 이용하여 작은 문제부터 차근 차근 답을 도출 할 수 있는 보텀업 방식도 있음 !! [코드 예시] d = [0] * 100 d[1] = 1 d[2] = 1 n = 99 for i in range(3, n+1) : d[i] = d[i-1] + d[i-2] print(d[n]) [1로 만들기] - 정수 X에 사용할 수 있는 연산은 아래와 같이 4가지 1. X가 5로 나누어떨어지면, 5로 나눔 2. X가 3으로 나누어떨어지면, 3으로 나눔 3. X가 2로 나누어 떨어지면, 2로 나눔 4.X에서 1을 뺌 - 정수 X가 주어졌을 때 연산 4개를 적절히 사용해서 1을 만들려고 함 - 연산을..

다이나믹 프로그래밍이라고 한다면 바로 떠올려야 하는 것이 피보나치 수열! 1,1,2,3,5,8, 13, 21 ... 앞에 숫자들을 더하고 더하는!! 이것만은 기억하고 있었다 ㅎㅎㅎㅎ 이게 메모제이션이라는 기법이다. 한 번 구한 결과를 메모리 공간에 메모해두고 같은 식을 다시 호출하면 메모한 결과를 그대로 가져오는 기법 (aka. 캐싱) 이전의 값을 기억을 해놓기 때문에 추가적으로 다시 이전으로 돌아가서 연산을 안해도 된다 먼저 피보나치의 예시 코드는 아래와 같음 def fibo(x): if x == 1 or x == 2: return 1 else: return fibo(x-1) + fibo(x-2) 근데 사실 이렇게 작성하면 안됨 메모리 초과 발생한다 [다이나믹 프로그래밍 사용 조건] 1. 큰 문제를 작..

[떡볶이 떡 만들기] - 떡 절단기에 높이를 지정하면 떡을 한 번에 절단 - 높이가 H(절단기 높이)보다 긴 떡은 H위의 부분이 잘리고, 낮은 떡은 잘리지 않음 예시) - 만약, 19, 14, 10, 17 cm인 떡이 나란히 있고 절단기 높이를 15cm로 지정하면 자른뒤 남은 떡의 높이는 총 6이 됨 * 파라메트리 서치 - 원하는 조건을 만족하는 가장 큰 값을 찾으라는 최적화 문제를 결정 문제 (yes or no)로 바꿔서 푸는 방법 즉, 적절한 높이를 찾을 때까지 절단기의 높이를 반복해서 조정 해석) - 가장 길이가 긴 떡의 길이를 기준으로 시작점, 중간점, 끝점 설정 - 첫번째 중간점은 9, 그럼 9를 기준으로 떡을 잘랐을 때 남는 떡의 길이는 총 25 - 필요한 떡의 길이는 6인데 이보다 크므로 시..