G님
다이나믹 프로그래밍, LCS
J님
Linked List, pointer
나
그리디 알고리즘, Knapsack Problem
8시~9시 코어타임(9시 끝 맞나?)
이후 내일 낮까지 책을 읽어보고
진도를 결정하기로.
다이내믹 프로그래밍(Dynamic Programming)이란?
다이나믹 프로그래밍(Dynamic Programming)
최적화된 재귀.
다항 시간(pilynomial time)에 문제를 해결.
중복된 부분문제(subproblem)가 있다면
이에 대한 결과를 저장하고 동일한 부분 문제 발생 시 결과 재사용.
1. 부분 문제와 중복되는 문제(overlapping subproblem)
중복된 부분 문제로 이전 결과 사용.
2. 최적 부분 구조(optimal substructure)
부분 문제의 최적해를 이용하여 전체 문제의 최적해를 구성.
다이내믹 프로그래밍 구현
하향식 접근 (Top-down approach, Memoization) - 재귀
위에서부터 바로 호출하여,
dp[0] 상태까지 내려간 다음,
해당 결과값을 재귀를 통해 전이시켜 재활용하는 방식.
이미 이전에 계산을 완료했을 경우
메모리에 저장되어있던 내역을 꺼내서 활용하므로
가장 최근 상태의 값을 메모해두었다고 하여 Memoization이라고 부른다.
상향식 접근 (Bottom-up approach, Tabulation) - 반복문
부분 문제를 먼저 해결하고
table에 결과를 저장.
그 윗단계 문제를 table 결과 값을 사용해 연산.
대략 dp[0] 부터.... 하여 dp[n]에 도달.
? Tabulation?
반복을 통해 하나하나 채우는 과정을 table-filling이라 하여,
table에 저장된 값을 직접 접근하여 재활용하므로
tabulation이라고 한다.
두 가지 방법 중 무엇이 더 나은가?
알 수 없다....
파이썬은 스택오버플로우가 나오니 bottom-up 추천.
하나만 사용할 수 있는 경우는 있음.
문제 해결 접근 방식
- 다이내믹 프로그래밍임을 식별(성질 찾기.)
- 매개 변수(state)를 결정.
- 매개 변수를 부분 문제와 연결. (최적화된 부분 구조 설계)
3-1 변수간 관계식 만들기(점화식)
3-2 메모하기(memoization or tabulation)
3-3. 기저 상태 파악하기
1의 경우
특정 데이터 내 최대화, 최소화 계산 이나
특정 조건 내 데이터를 세거나, 확률등의 계산.(왜?)
3-3의 경우
가장 작은 문제의 상태를 파악.
f(0) = 0, f(1)= 1... 즉 시작 지점 값을 알아야함.
Diff Utility(LCS 기반),
Resource Allocation(0-1 배낭 문제 기반)
플로이드 워셜 알고리즘
벨만 - 포드 알고리즘
연관 검색어 검색(Edit distance 문제 기반)
[Java/알고리즘] 그리디 알고리즘(탐욕법, Greedy Algorithm) 이해하기
그리디 알고리즘(Greedy Algorithm)
각 단계에서 최적이라고 생각되는 것을 선택,
최종적인 해답에 도달.
항상 최적의 값을 보장하진않고,
최적의 근사한 값을 목표.
문제를 분할한 뒤, 각 문제들에 대한 최적해를 구해
이를 결합하여 전체 문제의 최적해를 구함.
주요 속성
탐욕 선택 속성(Greedy Choice Property)
최선의 선택시 전체 문제에 대해 최적해를 구할 수 있는 경우.
(각 단계에서 이상적 선택이 최적해로 이어지는 경우)
최적 부분 구조(Optimal Substructure)
전체 문제의 최적해가 부분 문제의 최적해로 구성되어있는 경우.
즉, 최선의 선택이 최적해로 이어지는 경로일뿐만 아니라
전체문체의 최적해도 부분문제의 최적해 자체가 쓰임.
단계
- 문제의 최적해 구조를 결정합니다.
- 문제의 구조에 맞게 선택 절차를 정의합니다 : 선택 절차(Selection Procedure)
- 선택 절차에 따라 선택을 수행합니다.
- 선택된 해가 문제의 조건을 만족하는지 검사합니다 : 적절성 검사(Feasibility Check)
- 조건을 만족하지 않으면 해당 해를 제외합니다.
- 모든 선택이 완료되면 해답을 검사합니다 : 해답 검사(Solution Check)
- 조건을 만족하지 않으면 해답으로 인정되지 않습니다.
1단계: 선택 절차(Selection Procedure)
‘현재 상태’에서 ‘최적인 선택’을 합니다. 이 선택은 이후에는 바뀌지 않습니다.
2단계 : 적절성 검사(Feasibility Check)
선택한 항목이 ‘문제의 조건’을 만족시키는지 확인합니다.
조건을 만족시키지 않으면 해당 항목은 제외됩니다.
3단계: 해답 검사(Solution Check)
모든 선택이 완료되면, ‘최종 선택’이 ‘문제의 조건을 만족’시키는지 확인합니다.
조건을 만족시키면 해답으로 인정됩니다.
vs 동적 계획법?
그리디 알고리즘은 중복 부분 문제를 해결하지 않는다.
또 각 단계의 최적으로는 최적이 아닌 경우는 해결하지 못한다.
동적계획법은 모든 상황을 계산하여 가능하지만,
시간이 너무 오래 걸린다.
[알고리즘] 그림으로 알아보는 LCS 알고리즘 - Longest Common Substring와 Longest Common Subsequence
알고리즘 - LCS(Longest Common Subsequence, 최장 공통 부분 문자열) 알고리즘
LCS(Longest Common Subsequence)
공통 부분 문자열 중 가장 길이가 긴 문자열을 찾는 알고리즘.
Substring : 전체 문자열에서 연속된 부분 문자열
[예] ABCDEFGHI 에서 Substring은 ABC, DEFG, ABCDEF, GHI, … 등이 있다.
Subsequence : 전체 문자열에서 꼭 연속된 문자열인 것은 아닌 부분 문자열
[예] ABCDEFGHI 에서 Subsequence 는 ABD, AEFGH, AFI, … 등이 있다.
(단, 앞에서부터가 아니라 순서가 뒤바뀐 IHE, BIDEHF 와 같은 문자열은 부분 문자열이 될 수 없다)
LCS는, 서로 다른 문자열 중에서 공통 Subsequence를 찾는데, 그 중 길이가 가장 긴 Subsequence를 찾으려 하는 것입니다.
LCS는 DP다.
사실 규칙은 알겠는데
왜 그런 규칙이 나왔는지 궁금해하자
진우님이 그...
다익스트라 알고리즘이 성립하는 이유를 설명해주시면서
성립하는...그... 원리를 ? 흐름을 설명해주심.
다익스트라 알고리즘은 하나씩
최적의 값을 넣어서
mst, 최종 집합, set에 넣는데,
여기에 들어가는 시점부터 이미,
최적의 값으로 넣기때문에,
이 전체의 해도 최적의 해라는 정의가 성립.
그래서 LCS의 규칙이 성립하는 이유도
그러한 전제나 로직이 있지 않을까 얘기해주셨다.
최장 공통 문자열(Longest Common Substring)
Knapsack Problem(배낭 문제)
배낭 문제(KnapSack Problem) 그림으로 쉽게 이해하기
나의 구원자 블로그
DP를 쓰는데....
결국 n kg 배낭에 k 가치, w 무게 보석을 넣었을 때의 최적해는
n-w kg + k 가치 상태에서 n-w kg 배낭의 최적해를 가져왔을 때의 해이기때문에
작은 단위의 배낭 무게가 큰 단위의 배낭 무게의 부분 최적해가 된다는 논리.
그래서
처음에는 물건 k가 배낭보다 큰 경우
물건 k > 배낭 w
dp[k][w] = dp[k-1][w]
못 들어가니까 이전 값과 동일.
물건 k < 배낭 w
dp[k][w] = max(dp[k-1][w], k + dp[k-1][w-k])
아예 안 넣은 경우의 최적해랑
넣어서, w-k무게 당한 배낭의 최적해의 합 중
가치가 더 큰 것을 채택.
대략 표에서는 현재 칸의 값은
바로 왼쪽칸의 값과,
바로 왼쪽 위쪽 값 + 가치의 값 중
큰 것으로 채워 나가서
모두 채운 뒤 가장 끝 값을 채택하면 됨.
...
설명을 해보니
표로는 설명이 가능한데
식까지 쓰고
추상화까지 설명했는데
뭔가? 잘? 연결이 안 되는?
설명이 안 되는 느낌을 받았다.
배낭 문제가 분할되는 예시를 잘 설명하려면
실제 수치, 예시 그래프를 기억해두는 게 좋을 것같다.
그런 예시를 잘 설정해야,
k나 n으로 보편화했을 때도 설명하기가 쉬운 듯.
아니면 아예 코드를 준비해두는 것도 좋은 것 같다ㅠ
분할 정복
Linked List
c언어야말로 연결 리스트를 쓰는 이유가 있음.
왜냐하면 파이썬의 경우
.remove(value) 시
알아서
[a,b,c,d]
에서
[a,b,d]
로 없애고 리스트 크기를 줄여주지만,
c의 경우 그 값만 지워도
[a,b,NULL,d]
로 공간은 여전히 유지되기때문이다.
그래서 c에서
어떤 값을 넣고 지우느냐에 따라
공간을 동적으로 움직이게 하기 위해서,
연결 리스트를 쓴다.
a -> b -> c
일때,
참조하는 주소만 바꾸어서
b->c
등으로 a를 호출하지 않는 등
(그러면 a 데이터 값은 그대로 남아있지만,
어차피 그 주소는 다른 값을 넣어 쓰는 등이 가능하다)
....
그렇지만,
직관적인 생각과 다르게,
연결 리스트의 맨 끝에 잇는 것은
c 언어에서는 오히려 코스트가 더 든다.
왜냐하면 n의 길이만큼 끝까지 탐색한 다음에,
NULL이 나오면,
거기를 대체하는 식이기때문에,
오히려 맨 앞에서 바로 넣는게 빠르다.
그건 헤더로 쓰이는 부분을 떼어내서
삽입할 값에 헤더를 붙이고
맨 앞 값이 그 삽입 값을 참조 시키게 하면 되기때문이다.
중간에 삽입하는 것도,
탐색을 하다 멈추고 삽입하는 식이다.
이렇게 알고리즘 자체가 다르기때문에,
c에서는 넣고자 하는 위치에 따라 기능을 구현해야한다.
포인터(pointer), & 연산자와 * 연산자
포인터.
포인터는,
일반적인 변수가
(주소, 데이터)를 갖는 것과 다르게
(주소) 만 갖는다.
대신, 포인터를 호출하면
일반적인 변수를 참조해서 가져온다.
팀원인 진우님이 짜주신..은혜로운 코드로
마저 필기..
int week = 3;
int *ptr = &week;
이렇게 하면,
ptr이라는 포인터는 week의 주소를
가져오겠다는 뜻이다.
그래서
week 출력 -> 3
&week 출력 -> (%p로 주소를 가져왔을 시) week의 주소
ptr 출력 -> week의 주소
*ptr 출력 -> 3 출력
&ptr 출력 -> ptr의 주소
아!
ptr은 단순히 week의 주소를 갖고 있을 뿐이고,
*가 붙어야 week의 데이터를 가져오는구나!
그래서...
c는 파이썬과 달리,
파이썬은 리스트를 불러올때
리스트 하나가 전체 요소의 주소를 갖고 있지만,
c는 리스트의 포인터가,
단순히 가장 앞의 요소를 가리키고 있을 뿐이라서,
요소마다의 주소를 출력하면,
메모리 크기 4byte(할당한 것에 따라 다르겠지만)
만큼 증가한 주소가 나온다.
char alphabet[3] = {'a', 'b', 'c'};
for (int i = 0; i < 4; i++) {
printf("%p\n", &alphabet[i]);
}역시 가장 앞의 요소의 주소가,
리스트의 주소와 동일하다.
그래서 이러한 점을 이용하면,
리스트의 주소에 +1씩 더해서 호출해도,
다음 요소가 알아서 불러와진다!
printf("%d\n", *alphabet); // output = a
printf("%d\n", *(alphabet + 1)); // output = b
*(alphabet + 2) = 'd';
printf("%d\n", *(alphabet + 2)); // output = d그리고.....
분명히
변수에 데이터를 지정해주고,
그에 대한 포인터를 만들어서,
그 포인터를 함수에 반환해도,
함수에 그 포인터만 넣으면
함수 내부에서만 반영되었다가 소멸되기때문에
main 함수에서 그 값이 유지되지 않는다.
그래서
int ko = 4;
int *p = &ko; // 포인터 p는 ko의 주소를 가르키고 있다
일때
foo(p) = ko 주소가 가서 p가 업데이트가 안됨
foo(&p) = p 주소가 넘어감
**p = 포인터 주소 받는 parameter(syntax)
p = &q 호환되지 않는 데이터 타입이라서 실행되지않음
*p = &q 실행시 main에 돌아가도 q 포인터가 참조하는 주소가 바뀌어서 돌아감아무튼 포인터 자체가 아니라
포인터의 주소를 반환해야,
전체 결과 값이 반영되는 것이다....
그렇게 참조참조참조 성질을 이용하면
이런것도 가능하다.
char *c[] = {"SOS", "Death", "Chaos", "Nihil"};
char **cp[] = {c+3, c+2, c+1, c};
char ***cpp = cp;
printf("%s\n", **++cpp); // output = Chaos (c+2를 가르킨다)
c라는 것은 이 문자열들을 참조할것임.
cp는 c..
...
...
cpp는 cp니까?
cp에서 c+2(**++를 했으니까)
가 되고?
그래서 0, 1, 2라서 chaos가 되는거 맞나?
맞겠지
