본문 바로가기

AI HW/자료구조·알고리즘18

AI・SW KHU-MOOC https://khu-mooc.goorm.io/ AI・SW KHU-MOOC - 구름EDU 구름EDU는 모두를 위한 맞춤형 IT교육 플랫폼입니다. 개인/학교/기업 및 기관 별 최적화된 IT교육 솔루션을 경험해보세요. 기초부터 실무 프로그래밍 교육, 전국 초중고/대학교 온라인 강의, 기업/ khu-mooc.goorm.io 2024. 2. 15.
10. 그래프 알고리즘 Dijkstra / 최단거리 개념 - 최단거리 개념 우리는 앞에서 BFS를 통해 최단거리를 계산할 수 있다는 것을 학습했습니다. 그러나 그래프에서 간선에 적혀있는 가중치가 전부 동일하지 않다면, 최단거리를 구하는 일은 생각보다 복잡해집니다. 위의 그림에서 S에서 E로 가는 최단거리는 실제 4입니다. 하지만 BFS를 이용하면 가장 가까이에 있는 노드부터 순차적으로 보게 되므로 바로 S와 바로 붙어있는 E의 최단거리를 100이라 판단하게 될 것입니다. 이런 문제를 해결하기 위해, 정말 다양한 알고리즘이 나오게 되었습니다. 우리는 그 다양한 알고리즘 중 두 가지를 학습할 것입니다. 2023. 8. 29.
04. 이진탐색 - 이진탐색, 순차탐색, lower/Upper Bound 앞에서 배열에서 원하는 값을 찾기 위해선, 모든 값들을 하나씩 다 확인해야 하므로 O(N)이 나온다. 배열 속 값이 수백만, 수천만, 심지어 수억개라면 어떨까요? 우리는 검색을 빠른 시간내에 할 필요가 있기 때문에, 탐색을 할 수 있는 다른 방법을 찾아야 합니다. 업/다운 게임이라는 것을 들어보셨나요? 한 사람이 수를 생각하고, 다른 사람이 수를 예측해서 부르면 그것보다 큰지, 작은지 불러주면서 최대한 빨리 그 수를 맞추는 게임입니다. 많은 사람들이 수를 처음 예측할 땐 범위의 가운데에 해당하는 숫자를 부르고, 그 이후엔 업/다운에 맞춰 특정 구간의 가운데를 부르는 방법으로 수를 추측합니다. 이진탐색의 아이디어도 저것과 동일합니다. 찾아야 하는 수의 범위 중 가운데의 값과 찾.. 2023. 8. 24.
08. DP - String Matching, Greedy 알고리즘 LCS는 Longest Common Subsequence의 약자로, 최장 공통 부분 수열이라고 해석됩니다. 부분 수열이란, 순서대로 뽑아서 나올 수 있는 수열을 의미하며 예를 들어 ABCK는 ACBCK의 부분 수열입니다. 그 중에서도 두 문자열에게 공통으로 부분 수열인 경우를 공통 부분 수열이라 부르고, 그 중 가장 길이가 긴 경우를 최장 공통 부분 수열이라고 부릅니다. 예를 들어, ABABA와 BAAB의 LCS는 BAB 이므로, LCS의 길이는 3이 됩니다. 이때 저희는 ACAYKP(문자열 A), CAPCAK(문자열 B) 간의 LCS를 구해보려고 합니다. 이를 구하기 위해 저희는 동적계획법을 이용해보려고 합니다. 먼저 dp[i][j]를 문자열 A의 i번째까지와 문자열 B의 j번째까지를 활용하여 만들 수.. 2023. 8. 20.
08. DP - 전진하는 DP, 아이템 고르는 문제 다음과 같이 4개의 행으로 이루어진 직각삼각형 모양으로 된 판에 숫자들이 주어졌을 때, 최상단에서 시작하여 최하단으로 이동했을 때 얻을 수 있는 최대 합을 구해보려고 합니다. 단, 특정 위치 (r, c)에서의 이동은 (r+1, c) 혹은 (r+1, c+1) 지점으로만 가능합니다. 그렇다고 큰 숫자로만 따라 내려간다고 항상 더 좋은 값을 기대할 수는 없습니다. 예를 들어 다음 경우에는 우측처럼 아래로만 내려가는 것이 더 좋은 결과를 가져오게 됩니다. 이때 dp[i][j]를 마지막으로 방문한 위치를 (i, j)라 했을 때, 얻을 수 있는 최대 합이라 정의한다면 (i, j)에 도달하는 경우는 다음과 같이 2가지 경우를 생각해볼 수 있을 것입니다. - (i, j)에 최.. 2023. 8. 20.
08. DP - 동적계획법, Memoization, Tabulation, subproblem을 그대로 합치면 되는 DP 동적계획법이란 큰 문제에 대한 답을 얻기 위해 동일한 문제이지만 크기가 더 작은 문제들을 먼저 해결한 뒤, 그 결과들을 이용해 큰 문제를 비교적 간단하게 해결하는 기법을 뜻합니다. 예를 들어 1부터 N까지의 곱을 구하는 코드를 작성해본다고 했을 때, 점화식을 이용해 해결해보려고 합니다. F(N)을 1부터 N까지의 곱이라고 정의한다면, 다음과 같이 점화식을 세워볼 수 있습니다. - F(N) = F(N - 1) * N (N > 1) - 점화식 - F(1) = 1 - 초기조건 이러한 점화식을 이용하면, 다음과 같이 답이 구해진다고 생각해볼 수 있습니다. 이를 코드로 구현할 수 있는 방법은 크게 2가지가 있습니다. 첫 번째는 for loop을 이용하는 것입니다. 점화식을 통해 F[i - 1].. 2023. 8. 20.

티스토리툴바