![](http://i1.daumcdn.net/thumb/C148x148/?fname=https://blog.kakaocdn.net/dn/yIEXj/btsFHmWvNwF/dD4iw6kqLCQXGF7GiCikL1/img.jpg)
Algorithm 공부 #16 - 다익스트라 알고리즘 ✏️ 다익스트라 알고리즘(Dijkstra Algorithm)다익스트라 알고리즘은 그래프 상에서 한 정점에서 다른 정점들간의 최단 거리를 구할 수 있는 알고리즘이다.즉 도착 정점 뿐만 아니라 모든 다른 정점가지 최단 경로로 방문하며 각 정점까지의 최단 경로를 모두 찾을 수 있다.매번 최단 경로의 정점을 선택해 탐색을 반복한다고 생각하면 될 것 같다.시간복잡도는 O(ElogV)이며 이때 특징으로는 에지값이 모두 양수여야 한다.최단 거리 알고리즘은 이외에도 벨만-포드 알고리즘, 플로이드-워셜 알고리즘이 있는데 이 알고리즘들은후에 포스팅을 할 예정이다. ✏️ 구현 방법출발 노드와 도착 노드를 설정'최단 거리 테이블'을 초기화(출발 지점을 0으로, 나머지는..
![](http://i1.daumcdn.net/thumb/C148x148/?fname=https://blog.kakaocdn.net/dn/b5Pcvo/btsFGDErn0m/p98K5TS5NRq8kehw2KFjk1/img.jpg)
Do it! 지옥에서 온 문서 관리자 깃&깃허브 입문Git 공부 일기 3일차 - 깃과 브랜치 브랜치 ● 버전 관리 시스템에서 데이터 흐름을 가리키는 말● 커밋을 가리키는 포인터라고 생각하기● main브랜치에서 새로운 브랜치를 만드는 것 => 분기(branch)● 새 브랜치에서 원하는 작업을 다 끝난 후 main브랜치하고 합치는 것 => 병합(merge) 실습하기 1. manual디렉터리 생성 + manual 디렉터리로 이동 + manual 디렉터리를 저장소로 만들기 2. work.txt 텍스트 파일 생성(content1입력) + 스테이징 + 커밋(메시지는 work 1) 3. work.txt 텍스트 파일 수정(content2입력) + 스테이징 + 커밋(메시지는 work 2) 4. work.tx..
![](http://i1.daumcdn.net/thumb/C148x148/?fname=https://blog.kakaocdn.net/dn/4Itew/btsFF9W6U8S/uTkj8wvkrkz8BF11xXpwfK/img.jpg)
Algorithm 공부 #15 - 그래프(위상 정렬) 위상 정렬(Topology Sort) ● 사이클이 없는 방향 그래프에서 노드 순서를 찾는 알고리즘 ● 항상 유일한 값으로 정렬되지 않음 ● 진입 차수 : 자기 자신을 가리키는 에지의 개수 ● 원리 파악하기 노드는 5개이고 각 노드는 1,2,3,4,5 1번 노드는 2번과 3번 노드를 / 2번 노드는 4번과 5번 노드를 / 3번 노드는 4번 노드를 4번 노드는 5번 노드를 가리키는 그래프가 있다고 가정하기 진입차수 배열 D[N] 1 2 3 4 5 0 1 1 2 2 진입 차수 배열에서 진입 차수가 0인 노드를 선택하고 선택된 노드를 정렬 배열에 저장하기 그 후 인접 리스트에서 선택된 노드가 가리키는 노드들의 진입 차수를 1씩 빼주기 이 과정을 모든 노드의 ..
![](http://i1.daumcdn.net/thumb/C148x148/?fname=https://blog.kakaocdn.net/dn/b4doZp/btsFDDSuemD/kQGLHVtn0WNnbCs87XJIM0/img.jpg)
Algorithm 공부 #14 - 유니온 파인드 ✏️ 유니온 파인드(Union Find)유니온 파인드는 합집합이라는 의미를 지니고 있으며, Disjoint Set이라고도 불린다. Disjoint Set은 상호 베타적 집합이라는 뜻을 가지고 있는데 상호 배타적인 부분 집합들로 나누어진 원소들을 저장하고 조작하는데 사용한다.상호 배타적이라는 단어가 헷갈릴 수 있는데, 그냥 부분 집합 간의 교집합에는 원소가 없고, 모든 부분 집합들의 합집합은 전체 집합과 같다는 뜻이다. 쉽게 말해서 여러 노드가 존재할 때 두개의 노드를 선택해서, 현재 두 노드가 서로 같은 그래프에 속하는지 판별하기 위해 사용한다고 생각하면 될 것 같다. ✏️ Union 연산Union 연산은 말 그대로 Union(합집합)을 만드는 과정이다..
- Total
- Today
- Yesterday
- 자료구조
- 알고리즘
- js
- 자바스크립트
- 이분 매칭
- DFS
- DP
- 세그먼트 트리
- 카운팅 정렬
- HTML5
- java
- Do it!
- c++ string
- CSS
- 알고리즘 공부
- 백준
- 유클리드 호제법
- 최단 경로
- C++ Stack
- 스택
- BFS
- 반복문
- 백준 풀이
- html
- 유니온 파인드
- C++
- 투 포인터
- 우선순위 큐
- 자바
- 에라토스테네스의 체
일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
1 | 2 | |||||
3 | 4 | 5 | 6 | 7 | 8 | 9 |
10 | 11 | 12 | 13 | 14 | 15 | 16 |
17 | 18 | 19 | 20 | 21 | 22 | 23 |
24 | 25 | 26 | 27 | 28 | 29 | 30 |
31 |