post-thumbnail

Trie

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

2021년 6월 1일
·
0개의 댓글
·
post-thumbnail

Binary lifting

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

2021년 5월 21일
·
0개의 댓글
·
post-thumbnail

이분매칭(Bipartite Matching)

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

2021년 5월 11일
·
0개의 댓글
·
post-thumbnail

Tarjan's Strongly Connected Component (SCC) Algorithm

Strongly Connected Component

2021년 4월 25일
·
0개의 댓글
·

2차원 배열의 부분합

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

2021년 4월 21일
·
0개의 댓글
·
post-thumbnail

Floyd-Warshall Algorithm

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

2021년 4월 13일
·
0개의 댓글
·
post-thumbnail

LCS

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

2021년 4월 9일
·
0개의 댓글
·
post-thumbnail

LIS (Longest Increasing Subsequence)

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

2021년 4월 9일
·
0개의 댓글
·
post-thumbnail

다익스트라

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

2021년 4월 5일
·
0개의 댓글
·
post-thumbnail

투포인터 & 슬라이딩 윈도우

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

2021년 4월 5일
·
0개의 댓글
·
post-thumbnail

위상정렬

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

2021년 4월 4일
·
0개의 댓글
·