suffix array 깊이 이해하기 1 -반복되는 부분 문자열 찾기-

1. 반복되는 부분 문자열 찾기 전체 문자열에서 적어도 두번 이상 나타나는 부분문자열 보통 "가장 긴 반복 부분 문자열"을 찾는 것에 관심 있다 예를 들어 "abcefgabc"에서 "abc"가 두번 나타나면서, 가장 긴 반복 부분 문자열이다. 찾는 방법은 생각보다 간단한데, https://en.wikipedia.org/wiki/Substring Substring - Wikipedia From Wikipedia, the free encyclopedia Not to be confused with subsequence, a generalization of substring. "string" is a substring of "substring" In formal language theory and compute..

• format_list_bulleted 문자열 알고리즘
• · 2023. 8. 25.
• textsms

선분의 길이가 주어질때 볼록 다각형(conver polygon)이 될 조건

1. 문제 18044번: Polygon (acmicpc.net) 18044번: Polygon You are given n segments of lengths ℓ1, ℓ2, . . . , ℓn, respectively. Determine the largest possible circumference of a convex polygon that can be constructed using these segments (in any order, and not neccessarily all of them). The polygon must be www.acmicpc.net 2. 풀이 convex polygon은 앞으로 배울것 같지만... 지금은 모든 내각이 180도보다 작거나 같은 도형이라고 이해하면 될 것 같다 ..

• format_list_bulleted 기하학
• · 2023. 8. 25.
• textsms

정육면체가 쌓인 3차원 도형의 겉넓이를 구하는 방법

1. 문제 16931번: 겉넓이 구하기 (acmicpc.net) 16931번: 겉넓이 구하기 크기가 N×M인 종이가 있고, 종이는 1×1크기의 칸으로 나누어져 있다. 이 종이의 각 칸 위에 1×1×1 크기의 정육면체를 놓아 3차원 도형을 만들었다. 종이의 각 칸에 놓인 정육면체의 개수가 주어 www.acmicpc.net 2. 풀이 위,아래, 앞,뒤,왼쪽,오른쪽에서 보이는 면의 개수를 전부 더하면 될 것이며 면의 개수는 어떻게 구하지? n*m 크기의 바닥 아래에 정육면체를 쌓았을때, 위나 아래에서 봤을때는? 당연히 n*m개씩 보일 것이다. 왼쪽과 오른쪽에서 봤을때는? 위 그림이 1 3 4 2 2 3 1 2 4 와 같이 주어지는데, 왼쪽에서 본다면, 1 3 4 >>>>>> 2 2 3 1 2 4 처럼 상상해본..

• format_list_bulleted 기하학
• · 2023. 8. 25.
• textsms

모든 좌표까지 맨해튼 거리 합이 최소가 되는 위치를 구하는 방법

1. 모든 점까지 맨해튼 거리의 합이 최소가 되는 점의 위치? m차원의 n개의 점들 $P_{1}(x_{11},x_{12},...,x_{1m}), ... P_{n}(x_{n1},x_{n2},...,x_{nm})$에 대하여, 이들까지 맨해튼 거리의 합이 최소가 되는 점 X의 좌표를 구하라고 한다면, 어떻게 구할 수 있을까? 정답은 n개의 점들을 1,2,...,m차원의 좌표 값에 대하여 정렬한 다음, 중앙값에 해당하는 점의 좌표 $P_{median}$이 된다. 직관적으로 쉽게 눈치챌 수 있기는 한데, 왜 그런지 생각해보자. 2. 증명 먼저 점들의 좌표가 합에 서로 영향을 주지 않는다는 점을 관찰하자. 예를 들어 (3,5), (4,2), (5,1)에 대하여 (x,y)까지 맨해튼 거리의 합은.. $|x-3| + ..

• format_list_bulleted 기하학
• · 2023. 8. 24.
• textsms

이분 매칭(Bipartite matching) 알고리즘 배우기

https://justicehui.github.io/hard-algorithm/2018/12/21/BipartiteMatch/ [그래프] Bipartite Matching 이분 매칭이란? 이전 글에서 Max-Flow를 구하는 방법에 대해 알아보았고, 마지막 부분에서는 문제 하나를 풀어보았습니다. icpc.me/11375 문제를 풀어보았고, 문제를 그래프로 모델링하면 아래 사진처 justicehui.github.io 29. 이분 매칭(Bipartite Match.. : 네이버블로그 (naver.com) 29. 이분 매칭(Bipartite Matching) 지난 번에 네트워크 플로우(Network Flow) 알고리즘에 대해 공부하는 시간을 가졌습니다. 이... blog.naver.com Kuhn's Algo..

• format_list_bulleted 이분 매칭
• · 2023. 8. 23.
• textsms

모든 부분집합 원소의 곱의 합을 구하는 공식이 있다고?

1. 문제 9375번: 패션왕 신해빈 (acmicpc.net) 9375번: 패션왕 신해빈 첫 번째 테스트 케이스는 headgear에 해당하는 의상이 hat, turban이며 eyewear에 해당하는 의상이 sunglasses이므로 (hat), (turban), (sunglasses), (hat,sunglasses), (turban,sunglasses)로 총 5가지 이다. www.acmicpc.net 2. 풀이 경우의 수가 바로 안나오기는 한디... 경우를 나눠서 생각해보면 hat headgear sunglasses eyewear turban headgear headgear에 2가지 있고 eyewear에 1가지 있는데.. headgear에서 1가지를 뽑는 경우의 수 = 2가지 + eyewear에서 1가지 ..

• format_list_bulleted 확률론 알고리즘
• · 2023. 8. 20.
• textsms