1. 분할 정복(divide and conquer) 분할 = 큰 문제를 여러 개의 작은 문제로 쪼갠 다음 정복 = 작은 문제들의 답을 이용해 큰 문제의 답을 구하는 방법 충분히 크기가 큰 문제를 쉽게 해결할 수 있는 부분 문제로 분할해 나가고, 분할된 하위 문제를 해결하여 이 결과를 조합하여 윗단계 문제에 대한 답으로 낸다 2. 방법 정답을 쉽게 도출할 수 있을 때까지 재귀적으로 분할된 단위로 자신을 호출하면서 범위를 조금씩 줄여나감(분할단계) 답을 쉽게 도출하는 단계까지 도달한다면 재귀함수는 정답을 return하고 이렇게 return하면서 이를 이용해 재귀 stack에 쌓인 윗단계 재귀함수의 값을 return해나가는 것이 정복단계 def f(x): if (f(x)가 간단함): return f(x) el..
1. 두 다항식의 곱셈 다항식 f(x)=a0x0+a1x1+...+an−1xn−1과 g(x)=b0x0+b1x1+...+bn−1xn−1의 곱셈은.. f(x)g(x)=a0b0x0+(b0a1+a1b0)x1+...+an−1bn−1x2n−2로 나타날 것이다. 다항식을 각각 계수만을 가진 길이가 n인 벡터 A = [a0,a1,...,an-1], B = [b0, b1, ... , bn-1]로 나타낸다고 할때, 두 다항식의 곱셈은 길이가 2n-1인 벡터 C = [c0,c1,...,c(2n-2)]로 나타나며, $$c_{i} = \sum_{j=0..
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..
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 처럼 상상해본..
1. 모든 점까지 맨해튼 거리의 합이 최소가 되는 점의 위치? m차원의 n개의 점들 P1(x11,x12,...,x1m),...Pn(xn1,xn2,...,xnm)에 대하여, 이들까지 맨해튼 거리의 합이 최소가 되는 점 X의 좌표를 구하라고 한다면, 어떻게 구할 수 있을까? 정답은 n개의 점들을 1,2,...,m차원의 좌표 값에 대하여 정렬한 다음, 중앙값에 해당하는 점의 좌표 Pmedian이 된다. 직관적으로 쉽게 눈치챌 수 있기는 한데, 왜 그런지 생각해보자. 2. 증명 먼저 점들의 좌표가 합에 서로 영향을 주지 않는다는 점을 관찰하자. 예를 들어 (3,5), (4,2), (5,1)에 대하여 (x,y)까지 맨해튼 거리의 합은.. $|x-3| + ..
내 블로그 - 관리자 홈 전환 |
Q
Q
|
---|---|
새 글 쓰기 |
W
W
|
글 수정 (권한 있는 경우) |
E
E
|
---|---|
댓글 영역으로 이동 |
C
C
|
이 페이지의 URL 복사 |
S
S
|
---|---|
맨 위로 이동 |
T
T
|
티스토리 홈 이동 |
H
H
|
단축키 안내 |
Shift + /
⇧ + /
|
* 단축키는 한글/영문 대소문자로 이용 가능하며, 티스토리 기본 도메인에서만 동작합니다.