BFS(Breadth First Search, 너비 우선 탐색)
- 같은 깊이에 해당하는 노드부터 탐색하는 알고리즘
- Queue를 이용하여 구현
- 시작 지점에서 가까운 노드부터 탐색
- V가 노드의 수 , E가 간선의 수일 때, 시간 복잡도는 O(V+E)
구현
function bfs(graph, start, visitied) {
let queue = [start];
visitied[start] = true;
while (queue.length) {
v = queue.shift();
console.log(v);
for(i of graph[v]) {
if (!visitied[i]) {
queue.push(i)
visitied[i] = true;
}
}
}
}
graph = [
[],
[2, 3, 8],
[1, 7],
[1, 4, 5],
[3, 5],
[3, 4],
[7],
[2, 6, 8],
[1, 7]
]
visitied = Array.from({length: 9}, () => false);
bfs(graph, 1, visitied);DFS(Depth-First Search, 깊이 우선 탐색)
- 그래프에서 최대한 깊은 노드부터 우선적으로 탐색하는 알고리즘
- stack을 이용하여 구현
- 시작 노드에서 깊은 것 부터 찾음
- V가 노드의 수 , E가 간선의 수일 때, 시간 복잡도는 O(V+E)
구현
function dfs(graph, v, visitied) {
visitied[v] = true;
console.log(v);
for(i of graph[v]) {
if (!visitied[i]) {
dfs(graph, i, visitied);
}
}
}
graph = [
[],
[2, 3, 8],
[1, 7],
[1, 4, 5],
[3, 5],
[3, 4],
[7],
[2, 6, 8],
[1, 7]
]
visitied = Array.from({length: 9}, () => false);
dfs(graph, 1, visitied);BFS, DFS 그림설명
그리디(Greedy)
- 매 선택에서 지금 이 순간 가장 최적인 답을 선택하는 알고리즘 ⇒ 최적해를 보장하지 않음
- 최적해를 구하는 알고리즘보다 빠른 경우가 많음
- 크루스칼, 다익스트라 알고리즘에 활용
Git의 목적
- Git: 분산 버전 관리 시스템
- 원하는 시점마다 버전을 만들고 버전 사이를 자유롭게 돌아다니는 것이 가능
- 내가 만든 버전 뿐 아니라 동료가 만든 버전으로 이동이 가능하고 동료와 내 버전을 비교해서 최신 코드로 업데이트가 가능
- 즉 버전 관리, 백업, 협업이 가능하게 하는 도구
Git의 기본 개념
- Working tree
- 현재 내가 작업하고 있는 공간, 수정한 내용이 들어있음
- Staging Area
- git repository에 저장하기 전 단계에 있는 공간, working tree에서 수정한 내용들중 commit하고 싶은(버전을 만들고 싶은) 파일들을 선택해서 repository에 올림
- Repository
- git repository, staging area에서 commit을 한 내용들이 저장됨
Git 초기 설정
- git config --global user.name “your name”
- git config --global user.email youremail@example.com
- git config --list → 설정한 config 목록을 확인
- git init .
- 현재 디렉터리를 git 버전 관리를 시작함. 생성되는 .git 파일은 git repository(저장소)이다.
- 내가 만든 버전 정보, 원격 저장소 주소 등이 저장됨
- 원격 저장소에서 내 컴퓨터로 코드를 받아오면 자동으로 생성됨
1. 버전(version) 관리
- git status
- working tree의 status를 알 수 있음
- git add
- staging area에 추가하고 싶은 파일들을 선택
- git commit -m "~"
- version 생성
- git commit -am “~”
- 최초 한 번은 add 되어있는 파일들에 대해 add를 하지 않아도 자동으로 add가 실행됨 즉 add와 commit을 한번에 실행함
- git log
- 버전 확인(생성한 커밋 확인)
- git log --stat
- commit에 연루되어있는 파일 출력
- git diff id1 id2
- 파일의 차이점 출력
- git log -p
- 각 commit간 diff한 결과를 나타냄
- git checkout (commit id or ‘main’)
- 현재 working tree를 특정 버전(commit)으로 변경할 수 있음, branch도 변경할 수 있음
2. 백업(backup)
- git push
- local repository(지역 저장소)에 있는 파일들을 remote repository(원격 저장소에 복사)
- git clone
- remote repository에 있는 파일들을 새로운 컴퓨터 즉 작업을 새로이 연결해서 시작하고자 하는 local repository에 복사하는 과정
- git pull
- remote repository에 있는 파일들을 local repository에 가져옴(clone은 전체 복사이고 pull은 다른점을 가져온다)
- git remote add origin ‘remote repository 주소’ → origin은 원격 저장소 별명이다.
- git remote -v → 연결되어있는 원격 저장소의 주소 확인
- git push --set-upstream origin main
- 지역 저장소는 여러개의 원격 저장소에 연결될 수 있는데 그 중에 어떤 원격 저장소에 기본적으로 연결할지 세팅하는 과정
- git push -u origin main 으로 줄일 수 있음
3. 협업(collaborate)
- 항상 git pull, git push를 자주 해야한다. 작업을 시작하기 전에 git pull은 필수!
- git pull = git fetch + git merge FETCH_HEAD
- git fetch → 원격 저장소의 내용만 업데이트
- git merge FETCH_HEAD → 가장 최근에 fetch했던 branch를 merge해준다.
Git branch
- 브랜치(Branch): 나뭇가지, 분기된 흐름 = 특정 커밋을 가리키는 포인터
- git branch → 현재 생성된 branch 목록 출력
- git branch ‘만들 branch 이름’ → 새로운 branch 생성
- git checkout ‘branch 이름’ → 해당 branch로 전환
- git log --all --graph --oneline → 아래의 그림과 같이 출력
merge(병합)
base: merge하려는 branch들의 공통의 부모(조상)을 말함
git merge ‘merge할 branch 이름’ → 현재 가리키고 있는 branch에서 입력한 branch를 merge한다.
conflict(충돌)
같은 파일의 같은 부분을 수정한 경우 위와 같이 conflict가 발생하게 된다.
======= → 구분자를 뜻하며 구분자 위쪽은 현재 branch의 내용이 master이고 구분자 아래쪽은 o2 branch의 내용은 o2임을 나타낸다.
이런 경우 파일을 수동으로 수정한 후 git add ‘해당 파일 이름’ → git commit을 입력하면 merge를 계속 진행할 수 있다.
fork
- 저장소를 통째로 복제하는 것
- 다른 사람의 저장소를 통째로 자기의 계정으로 복제해와서 커밋, 푸시를 하고 내 저장소와 포크 해온 저장소의 브랜치를 머지해달라고 요청하면 됨
brach vs fork
| 의미 | 장점 | 단점 | |
|---|---|---|---|
| branch | 하나의 원본 저장소에서 분기를 나눔 | 코드 커밋 이력을 확인하기 쉬움 | 많은 사용자가 브랜치를 만든다면 관리가 어려움 |
| fork | 여러 원격저장소를 만들어 분기를 나눔 | 원본 저장소에 영향을 미치지 않음 | 원본 저장소의 이력을 보려면 따로 주소를 추가해야함 |
⇒ 주로 소규모 팀 등 팀 단위일 때는 branch, 오픈 소스 등 대규모 팀 단위일 때는 fork를 사용함
pull request(merge request, PR)
main branch에 merge하기전 팀원들과 코드 리뷰를 통해 merge를 할지 말지를 결정하는 것 → 통합 branch의 안정성을 높일 수 있다.
assignees: 이 작업에 참여한 사람을 지정
reviewers: 이 코드에 리뷰를 줬으면 하는 사람을 지정
amend
- 가장 마지막에 commit한 내용을 수정할 때 사용
- git commit --amend
- 이력을 변경하기 때문에 주의해서 사용해야함(ex 다른 사람이 커밋을 pull해서 수정 중 내가 amend 해버렸다면 히스토리가 꼬이게됨 ⇒ 혼자 사용하는 브랜치에서 사용하자!)
stash
- 변경사항을 커밋하지 않고 기억만 해두고 싶을 경우 사용(ex 다른 브랜치로 급하게 옮겨야하는 경우가 있을 때 현재 브랜치에서 작업한 내용들을 기억해두고 싶다!)
reset
- 옛날 커밋으로 브랜치를 되돌리고 싶을 때 사용
- amend와 마찬가지로 혼자 사용하는 브랜치에서만 사용하는 것을 권장함
- git reset --hard (바꿀commit id)
- 입력한 commit id의 버전으로 리셋함
- --hard: 버전뿐만 아니라 수정본까지 삭제
- --soft: 수정본은 남겨두고 버전만 삭제
- --mixed: 변경 사항이 있는 파일들은 Working directory에 보존하고 HEAD와 branch만 이동하게 됨
checkout과 reset의 차이점
checkout은 HEAD를 바꾸기 때문에 change의 의미가 있고
reset는 branch를 바꾸기 때문에 delete의 의미가 있다.
- 만약 HEAD가 google을 가리키고 있는 생태에서 reset 1을 한다면 google은 1번 버전을 가리키게 된다.
revert
- git revert (revert할 commit id)
- 기존의 커밋(입력한 id)는 그대로 두고 해당 커밋에서의 수정사항을 취소함(여러 단계 전의 commit으로 돌아가고 싶다면 한번에 revert할게 아니라 역순으로 한 단계씩(한 개의 commit씩 revert를 해야 충돌을 피할 수 있다.)
- reset은 히스토리를 완전히 삭제시키지만 revert는 히스토리를 새로 쌓아가면서 변경함 ⇒ 다른사람과 같이 사용하는 브랜치에서 사용하면 좋음
cherry-pick
- 여러가지 커밋 중 원하는 커밋만 선택해서 지금 브랜치에 붙이고 싶은 경우 사용
- ex) 버그 수정이 된 커밋만 현재 커밋에 가져오고 싶은 경우
git flow model
branch를 어떻게 운영할 것인가에 대한 좋은 모델(사례)
main 브렌치의 최신 버전은 언제나 실행 가능한 상태여야한다!
- develop: 개발할 때 사용하는 브렌치
- feature branches: 신규 기능 개발 브렌치
- release branches: 출시 준비 시 사용하는 브렌치
- hotfixes: 긴급한 수정사항 반영
컴퓨터공학과 학생입니다