No Limitation

본 포스팅은 한동대학교 최혜봉 교수님 강의 자료를 참고했음을 밝힙니다. 최단 경로라는 것은 출발지에서 목적지까지 가는 경로에서 가장 비용이 적게 드는 최적 경로를 계산하는 것을 의미한다. 다음 피피티 슬라이드를 참고해보자 우선 최단 경로라는 것은 여러 특징들을 바탕으로 하는데 1. 하나의 최단 경로 내 부분 경로는 자체로 최단 경로를 이룬다. 2. 하나의 vertex에서 다른 vertex로 가는 최단 경로로 구성된 트리들이 있다. 이 2가지 특징이 기본으로 전제가 된다. 1번은 어떠한 것을 의미하냐면 예를 들어 A->B가 최단 경로라고 한다면, A -> x x -> y y -> B라고 하면 A -> x, x -> y, y -> B 각각도 최단 경로가 됨을 의미한다. 그렇다면 여기서 중요한 것은 또한 최단..

참고 포스팅 : https://shoark7.github.io/programming/algorithm/3-LIS-algorithms https://stackoverflow.com/questions/35075862/longest-bitonic-subsequence-in-onlogn-complexity 최장 증가 수열(Longest Increasing Subsequence)은 어떠한 수열에서 특정 부분을 지워서 만들어낼 수 있는 증가 부분 수열(increasing subsequence) 중 가장 긴 수열을 의미한다. 여기서 최장 증가 수열은 반드시 뒤의 숫자가 앞의 숫자보다 더 큰 경우만 의미를 하게 된다. LIS에서 핵심은 현재 내가 증가시키고 있는 수열에서 다음 수가 더 큰 경우에는 추가를 해주되 더 큰..

https://galid1.tistory.com/507 동적 프로그래밍은 큰 문제를 작은 문제로 나누어 푸는 점에서는 분할 정복과 맥락을 같이 하는데 동적 프로그래밍의 의의는 작은 문제들 사이에 중복이 발생하는 경우에 효과적이라는 것입니다. 즉 작은 문제들이 반복되는 경우 이 작은 문제들은 한 번만 풀고 그 뒤로 메모에 적어 놓아 똑같은 작은 문제가 나타날 경우 앞서 메모한 작은 문제의 결과 값을 이용하는 방법론입니다. 이러한 동적 프로그래밍을 풀 수 있는 조건은 다음과 같습니다. 작은 문제가 반복적으로 발생하는 경우 중복 문제들 끼리는 동일한 정답을 내 놓는 경우 [이게 바로 Divide and Conquer와의 차이점] 동적 프로그래밍은 이러한 중복을 효율적으로 처리하기 위해 기록을 해 놓는데 그 기..

참고 포스팅 https://ratsgo.github.io/data%20structure&algorithm/2017/11/12/disjointset/ 서로소 집합(Disjoint Set)이란: 서로 중복되지 않는 부분 집합들로 나눠진 원소들에 대한 정보를 저장하고 조작하는 자료구조. 다른 의미로는 그래프에서 Connected Components 들을 찾는 과정의 의미와 동치이다. 그렇다면 Connected components라는 것은 무엇일까? 다음 글을 참고해보자 In graph theory, a connected component of an undirected graph is a subgraph in which any two vertices are connected to each other by pat..

본 포스팅은 다음 자료들을 참고하였습니다 : 한동대학교 한다성 교수님 강의 자료 https://siyoon210.tistory.com/85 https://mangkyu.tistory.com/102 해시는 검색과 저장에 특화된 자료구조로 python의 경우 dictionary가 내재적으로 해시로 저장되어 있다...! 빠르게 저장할 수 있는 기저에는 데이터를 검색할 때 사용할 key와 실제 데이터의 값이 (value가) 한 쌍으로 존재하고, key값이 배열의 인덱스로 변환되기 때문에 검색과 저장의 평균적인 시간 복잡도가 O(1)로 수렴하게 된다. 예를 들어보자 (yscho, "1022") 를 담고 있는, 즉, 'yscho'를 key로 '1022'를 value로 가지고 있는 자료 구조라고 했을 때, 이 데이터..