수정사항을 어떻게 판단할까 에서
깃허브는 어떻게 관리하지?로 나아가서 찾아보게됨
Hash
= 파일 하나가 같은지 다른지 판단
LCS
= 두 파일에서 어디가 같은지 찾음
Myers Diff
= 삭제/추가 기준으로 어디가 어떻게 바뀌었는지 찾음
Merkle Tree
= 파일 해시들을 폴더/전체 프로젝트 단위로 묶어서 빠르게 비교
CAS
= 해시값을 주소처럼 써서 저장
DAG
= 커밋들의 부모-자식 관계 그래프
DFS/BFS
= 커밋 그래프에서 공통 조상이나 경로를 찾는 탐색
| Hash | 변경 감지 |
| Diff | 무엇이 바뀌었나 |
| DAG | 버전 관계 관리 |
| DFS/BFS | 관계 탐색 |
| Merkle Tree | 대규모 빠른 비교 |
| CAS | 내용 기반 저장 |
HASH
개별 파일 단위 비교
각 학생의 지문
철수 지문
영희 지문
민수 지문
LCS(Longest Common Subsequence)
어디가 같은지 공통 부분 찾기
Myers Diff -
어디를 삭제하고 어디를 추가해야하는지 최소 수정 경로
Merkle Tree - 해시들을 트리 구조로 묶은 것, 해시를 계층적으로 묶어서 전체 구조를 빠르게 비교하는 방식
반 전체 출석부 지문
1학년 전체 지문
├─ 1반 전체 지문
│ ├─ 철수 지문
│ └─ 영희 지문
└─ 2반 전체 지문
철수 한 명이 바뀌면:
철수 지문 변경
↓
1반 전체 지문 변경
↓
1학년 전체 지문 변경
이렇게 위로 전파
https://jjjjqqq.tistory.com/81#google_vignette
git diff algorithm (myers algorithm)
깃에서 변경 내용을 어떻게 추적할까 궁금해져 찾아봤습니다 String A,B가 다음과 같이 주어져있다고 합시다 A = abcabba and B = cbabac A에서 문자를 삭제하거나 추가해서 B가 되었다고 했을 때,[삭제+
jjjjqqq.tistory.com
https://redjun89.tistory.com/119
git의 diff 알고리즘
오늘은 코치님의 멘토링이 있었다. 현재 우리 프로젝트는 LCS를 기반으로 한 diff 알고리즘을 형상 관리에 적용하고 있다. 그런데 코치님은 LCS에 기반한 diff 알고리즘은 비효율적이라고 다른 알고
redjun89.tistory.com
https://chanhuiseok.github.io/posts/algo-34/
알고리즘 - LCS(Longest Common Subsequence, 최장 공통 부분 문자열) 알고리즘
LCS 알고리즘이란?
chanhuiseok.github.io
쉽게 설명하는 블록체인 : 머클트리(Merkle Trees)란 | 뱅크샐러드
www.banksalad.com