Trie는 문자열을 빠르게 탐색할 수 있게해주는 트리형 자료구조이다.루트 노드가 되는 가장 최상위 노드에는 어떠한 단어도 들어가지 않고, 루트 아래 노드부터 문자열들의 접두사가 하나씩 나타나게 된다. 이러한 특징 때문에 트라이는 접두사 트리(Prefix Tree) 라고

Binary lifting이란 Binary Search와 Divded & Conquer와 비슷하게 O(logN)에 특정 값을 찾는 것이다. 주로 트리에서 사용된다.예를들어 현재 노드 V에서 K번째 조상 노드를 찾고 싶다하면 그냥 연산을 통하면 O(n)의 연산, 정확하게

이분 그래프에서 A 그룹의 정점에서 B 그룹의 정점으로 간선을 연결 할 때,A그래프의 하나의 정점이 B그래프 하나의 정점만 가지도록 구성된 것이 이분 매칭이다.이분 그래프 :: 정점을 두개의 그룹으로 나누었을 때, 존재하는 모든 간선의 양 끝 정점이 서로 다른 그룹에

Strongly Connected Component

Number of Submatrices That Sum to Target해당글은 discuss에 있는 설명 글을 번역했음을 알립니다.다음 코드를 보고 한 번에 이해를 안되는 사람들을 위해 설명을 하려한다.이 삼중 반복문에서 무슨일이 일어 나는지 알아보기 위해 i=1,j

1. 플로이드-워셜(Floyd-Warshall) 알고리즘이란?

LCS는 주로 최장 공통 부분수열(Longest Common Subsequence)을 말하지만 최장 공통 문자열(Longest Common Substring)을 말하기도 한다.Subsequence와 Substring의 차이는 ABCD,ABED라는 두 문자열이 있을때 S

1. LIS란? 가장 긴 증가하는 부분 수열 구하기이다. 기본적으로는 다이나믹 프로그래밍을 이용하여 각각의 수를 모두 훑어 비교해가며 한 배열에다가 최장길이의 숫자를 저장하지만 이런 방식을 사용할 경우 시간 복잡도가 O(N^2) 나오므로 배열의 크기가 클 경우 사용

출처:https://www.youtube.com/watch?v=pSqmAO-m7Lk하나의 정점에서 다른 하나의 정점까지의 최단 경로를 구하는 문제(single source and single destination shortest path problem)하나의

투 포인터 알고리즘이란 N개가 있는 1차원 배열에서 부분 배열 중 합이 M이 되는 지점을 구하는것이다.사용 조건으로는 각 원소는 자연수이고 M 또한 자연수여야만 사용 할 수 있다. 알고리즘의 작동 방식은 우선 두 개의 포인터(start,end)를 지정한다. 이 변수는

출처: https://youtu.be/eL-KzMXSXXI위상정렬은 쉽게 말해 순서가 정해져있는 작업을 차례대로 정렬하는 것이다. 실생활 예로는 대학교 선수 과목프로그램 의존도이벤트 스케쥴링제조과정등등이 있다.작업의 순서가 정해져있을때 그 작업을 정확하게 정렬