소피it블로그

https://www.acmicpc.net/problem/11053 11053번: 가장 긴 증가하는 부분 수열 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이 www.acmicpc.net https://youtu.be/5Lu34WIx2Us 병사 배치하기 문제를 풀려다가 이 문제 먼저 푸는 게 나을 것 같아서 풀어보았다. 역시나 다이나믹 프로그래밍의 일종으로, 동빈님의 강의의 도움을 받았다. 가장 긴 증가하는 부분 수열(Longest Increasing Subsequence) D[i] = arr[i]를 마..

문제, 풀이 출처: https://youtu.be/5Lu34WIx2Us 이 문제 역시 1) 최적의 부분 구조와 2) 중복되는 부분 문제라는 조건을 만족시키기 때문에 다이나믹 프로그래밍으로 접근하여 풀 수 있다. 핵심은, 한 칸 이상씩 떨어진 식량 창고를 털어야 하기 때문에 마지막 n번째 식량 창고에 대하여 1) i - 1 번째 식량 창고까지의 최적의 해 2) i - 2 번째 식량 창고까지의 최적의 해 + i번째 식량 창고에 저장된 식량 둘 중 더 큰 값을 선택하면 된다는 것. 그리고 각각은 부분 문제로 반복된다는 점을 파악하는 게 중요하다. i번째 창고까지의 최적의 해를 Ai라고 하고, i번째 창고에 있는 식량의 양을 Ki라고 한다면 다음과 같은 점화식이 성립한다. Ai = max(Ai-1, Ai-2 +..

자료 출처: https://youtu.be/cswJ1h-How0 알고리즘 천민에게 한 줄기의 빛 같은 동빈님의 강의를 요약해서 정리하고 있다. 열심히 정리하고 학습한 후에는 오직 문제풀이 맹연습뿐.... 알고리즘 양반까지는 힘들더라도 중인까지는 올라가보도록 노력을 거듭해보자 홧팅홧팅 1. 소수 판별 알고리즘 약수의 성질을 이용하면 더 쉽게 풀 수 있다. 약수의 성질이란? 모든 양수는 가운데 약수를 기준으로 대칭이라는 것 따라서 특정 자연수의 모든 약수를 찾을 때, 가운데 약수(제곱근)까지만 확인하면 됨 시간 복잡도: O(N^1/2) 2. 소수 판별 알고리즘 파이썬 구현 import math def is_prime_number(n): for i in range(2, int(math.sqrt(n)) + 1)..

자료 출처: https://youtu.be/aOhhNFTIeFI 1. 위상 정렬 사이클이 없는 방향 그래프의 모든 노드를 방향성에 거스르지 않도록 순서대로 나열하는 알고리즘 진입 차수(Indegree): 특정 노드로 들어오는 간선의 개수 진출 차수(Outdegree): 특정 노드에서 나가는 간선의 개수 2. 큐를 이용하는 위상 정렬 알고리즘 진입 차수가 0인 모든 노드를 큐에 담는다. 큐가 빌 때까지 다음을 반복한다: 큐에서 원소를 꺼내 해당 노드에서 나가는 간선을 그래프에서 제거함 새롭게 진입 차수가 0이 된 노드를 큐에 넣음 결과적으로는, 각 노드가 큐에 들어온 순서와 위상 정렬을 수행한 결과가 동일하다. 위상 정렬에는 여러 가지 답이 존재할 수 있다. 모든 원소를 방문하기 전에 큐가 빈다면? 사이클..

자료 출처: https://youtu.be/acqm9mM1P6o 1. 플로이드 워셜 알고리즘 최단 경로 알고리즘으로, 모든 노드에서 다른 모든 노드까지의 최단 경로를 구하는 알고리즘 다익스트라 알고리즘의 경우 한 노드에서 다른 모든 노드까지의 최단 경로를 구하는 알고리즘인데 반해, 플로이드 워셜 알고리즘은 모든 노드에서 다른 모든 노드까지의 최단 경로를 구한다는 점이 차이점이다. 거쳐가는 노드를 기준으로 알고리즘을 수행하는 것은 다익스트라 알고리즘과 동일하나, 매 단계마다 방문하지 않은 노드 중 최단 거리를 갖는 노드를 찾는 과정이 필요 없다는 점이 다르다. 2차원 테이블에 최단 거리 정보를 저장한다. 다이나믹 프로그래밍 유형에 속하며, 삼중 반복문을 사용한다. 시간 복잡도는 O(N^3) 노드의 개수가 ..

자료 출처: https://youtu.be/acqm9mM1P6o 동빈북을 사두고 생각보다 어려워서 많이 못 봤는데, 이 강의 시리즈를 보다보니 이해가 쉽게 가고 재밌어서 대강 쭉 봤다. 요즘 블로그에 정리하는 내용들도 강의 요약본이나 마찬가지인데, 어려운 알고리즘들은 계속 읽어보며 완전히 이해가 될 때까지 못 넘기겠어서 하나하나 코멘트를 다는 중. 투머치이긴 하지만 내가 이해하기 위한 것이기 때문에 그냥 적으려 한다. 1. 최단 경로 알고리즘 개요 한 지점에서 다른 한 지점까지 한 지점에서 다른 모든 지점까지: 다익스트라 알고리즘 모든 지점에서 다른 모든 지점까지: 플로이드 워셜 알고리즘 이 때 각 지점은 노드로, 지점 간을 연결하는 도로는 간선으로 표현한다. 2. 다익스트라 최단 경로 알고리즘 특정 노..