아직 재귀에 대한 개념도, Tree에 대한 개념도 확실히 잡히지 않았지만
더 놓치면 점점 되돌리기 어려워 질 것 같아서 그날 배운것 정도는 어느정도 이해하고 넘어가야겠다
Graph에는 대표적으로 BFS, DFS가 있으며
BFS(Breadth-First Search)의 특징으로는
... 같은 개념보다는
2차원 배열로 나타낸 매트릭스가 나는 도저히 이해가 잘 안간다
오늘은 Graph의 개념이나, 구현방법보다는 매트릭스를 먼저 이해해놔야 겠다
まだ再帰の概念も、Treeの概念もはっきりと理解してないけど
これ以上後回したらどんどん詰まりそうなので
その日学んだことくらいはある程度理解して進めよう
Graphには代表的にBFS、DFSがあり
BFS(Breadth-First Search)の特徴としては
... みたいな概念よりは
二次元配列で表した行列が俺には全く理解できない
今日はGraphの概念や実装方法よりは行列を理解しておこう
조건
0번째: 간선의 시작 정점 (0 이상의 정수)
1번째: 간선의 도착 정점 (0 이상의 정수)
2번째: 방향성 (1 == 일시 무향, 0 == 일시 방향)
입출력 예시
条件
0番目:幹線の始点(0 以上の整数)
1番目:幹線の終点(0 以上の整数)
2つ目:方向性(1 == 一時無香、 0 == 一時方向)
入出力例
int[][] output1 = createMatrix(new int[][]{
{0, 3, 0},
{0, 2, 0},
{1, 3, 0},
{2, 1, 0},
});
System.out.println(output1);
/**
* [
* [0, 0, 1, 1],
* [0, 0, 0, 1],
* [0, 1, 0, 0],
* [0, 0, 0, 0]
* ]
*/
int[][] output1 = createMatrix(new int[][]{ | |||
{0, 3, 0} | 시작정점 : 0 始点:0 |
도착정점 : 3 終点:3 |
일시 방향 有向 |
{0, 2, 0} | 시작정점 : 0 始点:0 |
도착정점 : 2 終点:2 |
일시 방향 有向 |
{1, 3, 0} | 시작정점 : 1 始点:1 |
도착정점 : 3 終点:3 |
일시 방향 有向 |
{2, 1, 0} | 시작정점 : 2 始点:2 |
도착정점 : 1 終点:1 |
일시 방향 有向 |
0정점 0頂点 |
1정점 1頂点 |
2정점 2頂点 |
3정점 3頂点 |
|
0정점 0頂点 |
0 | 0 | 1 | 1 |
1정점 1頂点 |
0 | 0 | 0 | 1 |
2정점 2頂点 |
0 | 1 | 0 | 0 |
3정점 3頂点 |
0 | 0 | 0 | 0 |
int[][] output2 = createMatrix(new int[][]{
{0, 2, 0},
{2, 4, 1},
{1, 3, 1},
{2, 1, 0},
]);
System.out.println(output2);
/**
* [
* [0, 0, 1, 0, 0],
* [0, 0, 0, 1, 0],
* [0, 1, 0, 0, 1],
* [0, 1, 0, 0, 0],
* [0, 0, 1, 0, 0],
* ]
*/
int[][] output2 = createMatrix(new int[][]{ | |||
{0, 2, 0} | 시작정점 : 0 始点:0 |
도착정점 : 2 終点:2 |
일시 방향 有向 |
{2, 4, 1} | 시작정점 : 2 始点:2 |
도착정점 : 4 終点:4 |
일시 무향 無向 |
{1, 3, 1} | 시작정점 : 1 始点:1 |
도착정점 : 3 終点:3 |
일시 무향 無向 |
{2, 1, 0} | 시작정점 : 2 始点:2 |
도착정점 : 1 終点:1 |
일시 방향 有向 |
0정점 0頂点 |
0 | 0 | 1 | 0 | 0 |
1정점 1頂点 |
0 | 0 | 0 | 1 | 0 |
2정점 2頂点 |
0 | 1 | 0 | 0 | 1 |
3정점 3頂点 |
0 | 1 | 0 | 0 | 0 |
4정점 4頂点 |
0 | 0 | 1 | 0 | 0 |
양방향(일시 무향)의 경우
예를들면 시작정점이 2, 도착정점이 4 일 경우
2행 4열과, 4행 2열 둘 다 값이 할당(간선이 연결됨)되게 되는것인가?
매트릭스 조건을 보면 이제 인접행렬을 어느정도 그릴수 있을거 같은데
이걸 어디다 쓰지...?
도대체 어떻게 응용하게 되는거지?
오늘로써 Section2 첫번째 페어학습이 끝나고
내일 두번째 페어학습이 시작된다
내일부터는 Coding Test 준비 커리큘럼이며
가장 먼저 배우게 될 것은 Greedy Algorithm 이다
그리드 알고리즘
탐욕이라는 건가?
정말 이름만 들어보면 가슴이 설레고 와 이건 뭘까 하는데
막상 껍질을 벗겨보면 그냥 모르는게 나았을걸 하고 후회하게 된다
어서 자야겠다
両方向(無向)の場合
例えば始点が2、終点が4の場合
2行4列と、4行2列の両方ともデータが与えられるようになるのか?
行列の条件を見ると、 隣接行列をある程度描けるように理解したと思うけど
これをどこに使うのか、、、
一体どうやって応用すればいいのか?
今日でSection2最初のペア学習が終わって
明日2回目のペア学習が始まる
明日からはCoding Test準備カリキュラムであり
最初に学ぶことはGreedy Algorithmだ
グリッドアルゴリズム
貪欲アルゴリズムってことかな?
本当に名前だけ聞いてみると胸がときめいて わぁ、これは何だろうと思うんですけど
いざ皮をむいてみれば、知らない方がよかったと後悔するようになる
早く寝よう
'BootCamp' 카테고리의 다른 글
2023-05-18 Greedy Algorithm (0) | 2023.05.18 |
---|---|
2023-04-21 [코드스테이츠] 객체와 클래스 (0) | 2023.04.21 |
2023-04-20 [코드스테이츠] 배열 (1) | 2023.04.20 |
2023-04-19 [코드스테이츠] 제어문 - 반복문 (0) | 2023.04.19 |
2023-04-18 [코드스테이츠] 연산자, 제어문 - 조건문 (1) | 2023.04.18 |