archives

https://qkqhxla1.tistory.com/700 그림을 다시 가져옴.아주 예전에 정리했었는데 c++이고.. 좀 복잡해서 지나면 잊어버린다. 파이썬 딕셔너리로 쉽게 구현한 버전이 있어서 가져왔다. MyPrettyPrinter클래스는 디버깅용이니 무시하고 Trie클래스만 보자. 소스 출처 : https://leetcode.com/problems/add-and-search-word-data-structure-design/discuss/59700/Python-trie-solution-search-using-dfs 여기서 가져와서 보기좋게 가공했다. addWord로 단어가 추가되면 트라이를 구성하는데, 단어가 어떻게 구성되는지는 아래에 print MyPrettyPrinter().pformat(t.tri..

https://leetcode.com/problems/next-permutation/discuss/13867/C%2B%2B-from-Wikipedia 의 댓글에 아주 잘 설명되어있다. 정리함. next permutation을 구하는 방법. 2,3,6,5,4,1로 알고리즘의 예를 듬. 1. 오른쪽에서 왼쪽으로 순회하면서 수가 증가하지 않는 부분을 찾는다. 2,3,6,5,4,1에서는 3 이다. 2-1. 수가 증가하지 않는 부분이 없으면 이 뜻은 permutation의 맨 마지막이라는 뜻이다. 이경우 맨 마지막의 다음은 맨 처음이므로 그냥 순서를 거꾸로 해주면 된다. 예로 6,5,4,3,2,1의 경우인데, 이 경우 그냥 거꾸로 순서를 해주면 맨 처음인1,2,3,4,5,6이다. 2-2. 수가 증가하지 않는 부분..

https://leetcode.com/problems/minimum-window-substring/discuss/26808/Here-is-a-10-line-template-that-can-solve-most-'substring'-problems 정리. 위 문서는 아래에 적을 슬라이딩 윈도우 알고리즘 템플릿으로 여러가지 문자열 안의 문자열 문제들을 풀 수 있다는걸 알려줌. 파이썬으로 설명. https://leetcode.com/problems/minimum-window-substring/ 문제의 해답임. 기본적으로 two pointer 알고리즘에서 만든 템플릿이다. 문제는 S와 T가 있는데 S안에 T단어 전체가 들어가는 가장 작은 윈도우의 길이를 리턴하는 문제이다. class Solution(object)..

이걸 왜 정리를 안해놨었는지 모르겠다. http://blog.naver.com/PostView.nhn?blogId=kks227&logNo=220795165570 역시 이분 블로그에 깔끔하게 정리와 설명이 너무 잘되있어서 내가 보고 추가할부분이 없다. two pointer라는 이름 그대로 두개의 시작점을 잡아놓고 조건에 맞도록 두개의 포인터를 좁혀주면 된다고 기억해놓자.

https://leetcode.com/problems/sum-of-two-integers/discuss/84278/A-summary%3A-how-to-use-bit-manipulation-to-solve-problems-easily-and-efficiently 의 글을 정리함. 파이썬 버전. 1. 숫자를 이진수로 변경했을때 1의 갯수 세기. def count_one(n): count = 0 while n: n = n&(n-1) count += 1 return count print count_one(3) 2.1 어떤 수가 2의 거듭제곱인지 판단. 2의 거듭제곱들은 이진수로 아래와 같다.1, 10, 100, 1000, 10000 .... 그리고 이것들보다 1 작은수의 이진수는 아래와 같다.0, 01, 011..

https://leetcode.com/problems/linked-list-cycle/ 문제로 설명함. 설명 : https://leetcode.com/problems/linked-list-cycle/discuss/44539/AC-Python-76ms-Floyd-loop-detection-in-7-lines 코드는 위에꺼 그대로 가져옴. def hasCycle(self, head): slow = fast = head while fast and fast.next: # fast는 두칸 뒤로 가고, slow는 한칸만 뒤로 감. # cycle이 없으면 while fast and fast.next에서 False가 나와서 루프가 끝날 것이고, # cycle이 있으면 fast가 속도가 더 빠르므로 slow를 결국에는 ..

https://leetcode.com/problems/rotate-image/discuss/18872/A-common-method-to-rotate-the-image 되게 일반적인 문제인데 여태까지 이걸 몰랐다...;코드를 그대로 가져온다. /* * clockwise rotate * first reverse up to down, then swap the symmetry * 1 2 3 7 8 9 7 4 1 * 4 5 6 => 4 5 6 => 8 5 2 * 7 8 9 1 2 3 9 6 3 */ /* matrix의 길이를 n이라고 하면 0행과 n-1행을 변경, 1행과 n-2행을 변경, 등등등 반복 후 반복으로 돌면서 스왑해준다.*/ void rotate(vector &matrix) { reverse(matri..

http://www.secmem.org/blog/2019/03/09/rope/ Rope는 긴 문자열들에 대한 연산(자르기, 붙여넣기, 끼워넣기 등)을 효율적으로 처리하기 위해 고안된 자료구조입니다. 알아두면 유용할것 같아서 링크 저장해둠.

자세한 내용은 네이버 개발자 센터에 있다. : http://d2.naver.com/helloworld/711301 요약.유니크한 값이 어떤 자료구조 안에 있는지 정확하게 판단하려면 해쉬 셋 등을 만들어 모든 값을 넣어두고, 값을 가져와서 비교한 후 판단할수 있다. 하지만 이러한 방법은 메모리가 엄청 많이 먹게 된다.(모든 자료를 저장해야하므로) 정확한 값을 얻는데 드는 비용이 너무 크다면 비용을 월등하게 줄이는 대신 오차가 조금 있는 방법이 더 유용할 수도 있다. 이게 hyperloglog이다. 위 네이버 링크에 셰익스피어 작품에 나오는 유니크한 단어 수를 셀때, 자바의 hash set과 hyperloglog를 사용할때의 비교이다. (출처 위의 네이버 개발자 도구. 문제있을시 삭제하겠습니다.)hyperl..

http://bigocheatsheet.com/ 에서 그대로가져옴. 참고용

기초적이지만 그래도 정리... 파이썬 # -*- encoding: cp949 -*- def binary_search(l, data): low,high = 0,len(l) while low data: high = mid else: low = mid if bl==low and bh==high: return False return False a=sorted(map(int,raw_input().split())) print binary_search(a, input()) C++ #include #include #include #include #include #include #include using namespace std; bool binary_search(int l[100], int data) { int low..

첫 글을 너무 대충 정리해서... 공부하다보니 다이나믹 프로그래밍의 엄청난 공부량을 느끼고 재정리. 한개나 두개정도 글을 더 쓸수도 있을듯 싶다. 첫글 : http://qkqhxla1.tistory.com/585 다이나믹 프로그래밍의 프로그래밍 패턴. 1. 재귀적으로 짜는 패턴. dp = [[-1 for j in xrange(10)] for i in xrange(10)] def function(a, b): if ~~~: return ~~~ #기저 사례. 미로찾기면 끝에 도달했다던가 하는등. ret = dp[a][b] #c++에서는 참조형으로 int& ret = dp[a][b];처럼 쓴다. if ret != -1: return ret #이미 a,b에 대한 값을 구한 적이 있으면 즉시 반환. 위에서 리스트 ..

잘 정리된 곳 : http://blog.naver.com/mycho/220725983486 개요. 특정 용량의 배낭이 있고 n가지의 물건을 담을 수 있다. n가지의 물건은 각각 가치와 무게가 있으며 가치가 최대로 되도록 배낭에 담는 형식의 문제. 이 배낭 알고리즘에는 3종류가 있다고 한다. 1. 물건 당 물건의 수량이 1개밖에 없고 물건을 쪼갤 수도 없는 경우.(0-1 Knapsack problem) 2. 물건 당 물건의 수량이 여러개이고, 쪼갤 수 없는 경우.(Bounded Knapsack problem) 3. 물건의 갯수가 무한개이고, 쪼갤 수 없는 경우(Unbounded Knapsack problem) 1. 0-1 Knapsack problem. 물건 당 물건의 수량이 1개이고, 물건을 쪼갤 수 없..

참조 1 : http://blog.naver.com/jyuno426/220794422838 참조 2 : https://algospot.com/wiki/read/Manacher's_algorithm 회문에 관한 알고리즘이라고 한다. 각 문자를 중심으로 하는 팰린드롬을 알아내는 알고리즘이라고 함. 각 문자를 중심으로하기때문에 짝수 길이의 팰린드롬은 찾을수 없다고 한다. 찾으려면 더미 문자를 끼워넣어서 a#b#c#d#d#c#b#a 꼴로 만들면 된다고 한다. ex) aaa의 중심은 중간의 a이고, 팰린드롬은 a와 aaa두개가 있다. aabaa의 중심은 b이고 팰린드롬은 b, aba, aabaa가 있다고 한다. 알고리즘 부분은 알고스팟에서 그대로 가져왔다.알고리즘은 다음과 같다:i는 0부터 n−1(n=|S|)까지..

https://www.acmicpc.net/blog/view/9 의 내용을 정리해왔습니다. 예로 길이 N의 배열 A가 있고 여기서 L~R구간의 합을 M번 구해서 출력해야한다고 가정합시다. 수행해야 하는 연산의 시간복잡도는 O(M(R-L)) 번입니다. 그런데 앞에서부터 차례대로 합을 구해놓는 방식으로 문제를 풀어서 시간복잡도를 줄일수 있습니다. S[i] = A[1] + ... + A[i] 라고 했을 때, i~j까지 합은 S[j] - S[i-1]라고 할수 있습니다. 만약 A배열의 중간에 어떤 값이 하나 바뀐다고 하면 S[i]값은 A배열의 처음부터 다시 세서 만들어줘야 합니다. 따라서 M과 중간의 값이 변경되는 양이 너무 크게 되면 시간이 너무 오래걸리게 됩니다. (O(M*변경되는양)의 시간복잡도가 걸리겠죠...

http://kks227.blog.me/220810623254 에서 가져와서 핵심만 정리했습니다. 어떤 그래프에서 유량을 흘리는데 최대 유량을 흘리고자 합니다. 그런데 최소한의 비용을 들여서 흘리는게 목적입니다. 비용은 간선마다 다르며, 어떤 간선의 비용이 d이고, 유량이 f만큼 흐른다고 하면 비용은 d*f입니다.(d*k라고 나와있는데 오타인 듯..) 예로 위에서 빨간색으로 유량이 흐른다고 할때 비용은 17입니다. 방법론 : 포드 폴커슨, 에드몬드 카프 알고리즘과 비슷한데 매번 찾는 경로가 최단 경로입니다. 매번 최단 경로를 찾고, 이 경로로 흐를수 있는 최대 유량을 흘려보내면서 경로값*유량을 더해주면 된다네요.(위의 d*f를 말하는듯) 주의점 : 음의 가중치가 있는 그래프에서도 잘 작동해야 함. 역방향..

http://kks227.blog.me/220796029558 에서 핵심만 가져와 정리해왔습니다. 이 그래프에서 a와 e를 분리시키고 싶다고 합시다. 자르는 방법은 여러가지가 될 수 있지만 아래처럼 자를수 있습니다.이처럼 자르면 A,B,C와 D,E로 분리됩니다. 이렇게 그래프를 자르는걸 컷이라고 한답니다. 컷에는 비용이 있는데 위처럼 자르면 선이 3개가 잘리므로 비용이 3입니다. A바로 오른쪽에서 자르면 비용이 2로 A와 E를 분리시킬수 있겠네요. 이렇게 임의의 두 정점을 정하고, 두 정점을 다른 컴포넌트로 분리시키는 비용을 최소화하는걸 미니멈 컷이라고 한답니다. 이처럼 가중치가 있는 그래프라면 단순히 선을 조금 자르는것보다 비용을 생각해서 자르는게 효율적입니다. 이렇게 자르면 비용이 9로 A와 E를 자..

설명 잘된 블로그 : http://blog.qwaz.io/problem-solving/scc%EC%99%80-2-sat (설명보면 힐링..) 위의 블로그에서 가져와서 정리해왔습니다. SCC. scc는 strongly connected component로 강한 연결 요소를 뜻한다. 강한 연결 요소는 다음 조건을 만족한다.1. 같은 scc안의 임의의 두 정점은 서로 도달 가능하다.2. 어떤 정점이나 간선도 1의 조건을 만족하면서 scc에 추가될 수 없다. 임의의 방향 그래프가 주어졌을때 scc를 찾는 알고리즘으로 코사라주의 알고리즘과 타잔의 알고리즘이 있다고 한다. 둘 모두 시간복잡도는 O(V+E)라고 하지만 쉬운 코사라주의 알고리즘만 가져옴. 1. 방향 그래프 G, 빈 스택 S, G의 간선 방향을 뒤집은 ..

설명 잘됨 : http://jinsolkim.kr/50194124086 n명의 사람들이 파티에 왔다고 하자. 레크리에이션 강사가 생일이 같은 사람들끼리 팀을 구성하라고 한다. 사람들이 서로 그룹을 만드는데, 생일이 같은 사람들 찾으면 둘은 한 그룹이 되고 또다른 사람들을 찾아나설것이다. 만약 다른 팀을 찾았는데 생일이 같으면 또 그룹이 합쳐질것이다. 이런것들을 표현하는 자료구조라고 보면 된다. 이를 구현하기 위해 3가지 연산이 필요하다. 1. 초기화, 2. 합치기, 3. 찾기. 따로 상호 배타적 집합으로 쓰이기보다는 최소 신장 트리 등 다른 자료구조의 안에 쓰인다고 한다. 아래 소스코드에 다 구현되있다. #include #include #include #include using namespace std;..

문자열 변수를 비교할땐 문자열의 길이가 있으므로 정수등과 다르게 오래걸린다. 예로 어떤 한 문자열 a가 있고 문자열 b가 있다고 하자. a가 b문자열 안에 들어있는지 확인하는데는 너무 오래걸린다. 이를 해결하기 위해 문자열 특화 자료 구조의 대표적인 예가 트라이다. 문제점은 필요로 하는 공간이 너무 크다는 점. 그래서 트라이로 접미사 트리를 만들수 있지만 사용하기가 어렵다고 한다.(접미사가 필요하면 앞에 글중 하나인 접미사 배열 부분을 주로 쓴다.) 문자열 집함 s={"BE","BET","BUS","TEA","TEN"}; 이 있다고 할때 이걸 트라이에 저장하면 아래처럼 된다. 이처럼 접두사 뒤에 글자를 덧붙여 다른 접두사를 얻을 수 있을때 두 노드는 부모 자식 관계로 연결된다. 노드의 깊이가 늘어날수록 ..

아래 소스코드는 접미사 배열을 구하는 함수. 어떤 문자열의 모든 접미사를 사전순으로 정렬해둔것. 출처 : http://blog.myungwoo.kr/57 사진 뜻. 0번째 접미사 배열은 아래 문자열 banana의 5번째부터 끝까지다. == a 1번째 접미사 배열은 아래 문자열 banana의 3번째부터 끝까지다. == ana 2 : anana, 3 : banana, 4 : na, 5 : nana *같은 문자로 시작하는 접미사 배열은 인접해 있음. a로 시작하는 접미사배열은 0,1,2의 경우. b로 시작하는 접미사배열은 3, n은 4,5에 있다. LCP 란 i번째 접미사와 i-1번째 접미사의 '가장 긴 공통 접두사의 길이'라고 한다. ex) i번째 접미사 : a, i+1번째 접미사 : ana라고 하면 lcp..

소수를 구할때 프로그래밍을 처음 하는 사람이 아니고서는 에라토스테네스의 체를 쓴다. 쉬운 개념이므로 링크만 걸고 코드만 올려놓는다. https://en.wikipedia.org/wiki/Sieve_of_Eratosthenes # -*- encoding: cp949 -*- def prime_number(max_n): p = [0 for i in xrange(max_n+1)] for i in xrange(2,max_n+1): for j in xrange(i*2,max_n+1,i): p[j] = 1 prime = [i for i in xrange(2,max_n+1) if p[i]==0] return prime print prime_number(100) #2~100까지 소수 목록을 리스트로 반환. 100 포함한..

n개의 정점이 있을때, 두개씩 짝지어 주는 방법론. 각각의 연결된 정점은 끝점을 공유하지 않는다. 아래의 왼쪽 그림처럼 끝점을 공유하면 안되고, 오른쪽의 녹색 라인처럼 2개씩 짝지어져야함. ex)1. 아래와 같은 그래프가 있다. 파란 선은 도달 가능함을 의미한다. A부터 시작해서 하나씩 매칭해보자. A에서 2로 도달 가능하므로 이어준다.2. B에서 매칭을 시도하는데 B에서도 2로 가는게 가능하다. A에서 2 대신 5와 매칭이 가능하므로 A-5로 다시 매칭을 해주고 B는 2와 이어준다. 이런식으로 매칭을 시켰을때 가장 많은 쌍을 구하는걸 최대 매칭 문제라고 한다.

현실세계의 인터넷이라고 가정하자. 서버 s에서 집 컴퓨터 t까지 경로가 여러개 있고, 각각의 경로에는 보낼수 있는 최대한의 대역폭이 있다. 집 컴퓨터 t에서 자료를 다운로드받는다고 하면 s에서 보낼 수 있는 대역폭의 최대량은 얼마일까? (받는 쪽에서는 들어오는 만큼 다 받을수 있다고 가정한다.) 를 구하는 문제이다. 역시나 설명 잘된 블로그 : http://kks227.blog.me/220796029558 1. s에서 t로 최대한 보낼 수 있는 대역폭의 양은 얼마일까? 아주 잠깐 살펴보면 (D에서 T로 가는) 2 + (E에서 T로 가는) 5 인 7이 일단 보이는 최대값임을 알수 있다. 하지만 만약 E로 도달할수 있는 길이 C에서 E하나뿐이고, C->E 대역폭이 4라면 E->T 대역폭이 5라도 최대 대역폭..

역시나 이분 블로그 참조 : http://kks227.blog.me/220796029558 간선과 정점들이 있을때 서로 연결되서 가중치의 합을 최소인 트리가 스패닝 트리. 주의 : 사이클이 생기면 안된다, 한 정점에서 다른 정점으로 도달하여야 한다. 시간 복잡도는 ElongE라고 한다. 아래는 예시. 1. 아래와 같은 정점들과 간선들에 대한 가중치가 있다고 하자. 아직 하나도 연결 안됬다. 간선들을 가중치순서대로 오름차순으로 정렬한다.2. 가중치가 가장 낮은 AE부터 시작해서 서로 연결이 되어있지 않으므로 연결해준다. A와 E는 이제 하나의 집합으로 보자. 3. 순서대로 잇다 보면 3까지 아래처럼 잇게 된다. 4. 그다음 차례인 4를 이어야되는데 이걸 잇게 되면 사이클이 생기게 된다. 그러므로 잇지 않고..

잘 설명된 블로그 : http://kks227.blog.me/220796029558 (알고리즘 설명이 진짜 잘 되있네요) 앞의 다익스트라 알고리즘은 a에서 b로 갈때 가중치가 음수가 아니라고 가정한 상태에서 코딩을 한다. 하지만 이 벨만 포드 알고리즘으로 가중치가 음수일 경우까지 판별이 가능하다. 음수 검사까지 하므로 시간복잡도는 늘어나서 O(VE)이다. 사진은 역시 저 블로그에서 가져왔다. 0에서 2까지 가는 최소거리를 찾을때 다익스트라 알고리즘은 음수가 아니라고 가정한 상태이므로 8로 최소값을 잡는다. 그런데 진짜 최소거리는 1을 거쳐서 가는 5다. 이러한 음수판별까지하는게 벨만 포드 알고리즘이다. 그런데 음의 가중치가 있는 그래프를 판별시 항상 무한대 사이클을 염두해 두어야 한다.이 무한대 사이클을..

설명 잘 된 블로그 : http://kks227.blog.me/220796029558 블로그에 나온 것처럼 그래프에서 어떤 정점에서 다른 정점으로 갈 경우 최소값을 구하는 알고리즘이다. 다익스트라 알고리즘은 모든 비용이 음수가 아닐 경우에만 동작한다. 시간 복잡도 : O(|E|lg|V|) (정점 V, 간선 E) 그림은 위의 블로그에서 퍼왔다. 1. 정점 0이 시작점이고 여기서 출발하여 다익스트라로 각 점까지의 최솟값을 구한다고 하자. 각 점까지의 거리는 초기치를 무한대로 설정해놓는다. 2. 첫 정점에서 갈수 있는 점들을 큐에 저장해놓고 가장 비용이 적은 점부터 방문한다. 방문후 비용을 초기화해준다. 3. 다음 시작점중 비용이 가장 적은 1부터 방문한다. 왜 비용이 적은것부터 방문하냐면, 아래 그림의 3이..

https://docs.python.org/2/library/heapq.html 여기껄 클래스화시켰다. 큐의 순서는 출력해보면 알겠지만 우선순위에 따라서 출력된다.# -*- encoding: cp949 -*- from heapq import * class priority_queue(): def __init__(self): self.pq = [] # list of entries arranged in a heap self.entry_finder = {} # mapping of tasks to entries self.REMOVED = '' # placeholder for a removed task def put(self, task, priority=0): 'Add a new task or update the ..

잘 설명된 문서: https://1ambda.github.io/91/algorithm/algorithm-part2-4/ 시간복잡도는 하나하나 검사할경우 O(N*M)이지만 KMP는 O(N+M)이란다. 방법론.1. next배열을 만든다. 아래는 패턴 10100111에 대한 next배열을 만드는거다.사진에 대해서 설명하면.0) next배열을 구하기 위해서 위쪽과 아래쪽에 같은 문자열을 둔다. 아래쪽은 한칸 오른쪽인 상태로 시작한다.2) 불일치가 발생하면 아래쪽의 비교문자열을 불일치 이후에 첫글자가 첫번째로 일치하는 곳으로 이동시켜준다. 또 j==4일때 불일치가 발생했는데 불일치가 발생한 곳부터 1을 검색해보면 바로 뒤에 1이 있으므로 거기로 위치를 옮겨준다. 이런식으로 계속 한다.불일치가 발생하지 않으면, 아..

예전에 알고리즘 수업시간에 과제로 짜놨던건데 유용하게 쓰일것 같아서 올려놓는다. 언어는 c++이다. #include #include #include using namespace std; const int N = 500000; void printList(int a[], int n) { int i; for (i = 1; i l;i--) b[i-1] = a[i-1]; for(j=m;j=1; j/=2){ if(a[v] >= a[j]){ swap(a,v,j); v = j; } else break; } } void HeapSort2(int a[], int n) { ..