728x90 반응형 자료구조,알고리즘 개념정리2 [그래프] 그래프란 뭘까요? 그래프 정점들의 집합 v와 간선들의 집합 e로 구성된 자료구조 정점의 위치정보나 간선의 순서등은 그래프의 정의에 포함되지 않음 🥑 그래프의 종류 방향그래프 간선이 ‘방향’이라는 새로운 속성을 가짐 무향그래프 간선에 방향이 없는 그래프 가중치 그래프 간선에 ‘가중치’라는 실수 속성을 부여 다중 그래프 두 정점 사이에 두개 이상의 간선이 있을 수 있는 그래프 단순 그래프 두 정점 사이에 최대 한개의 간선만 있는 그래프 트리 혹은 루트없는 트리 부모 자식 관계가 없을 뿐 간선들의 연결 관계는 무향 그래프 이분 그래프 그래프의 정점들을 겹치지 않는 두개의 그룹으로 나눠서 서로 다른 그룹에 속한 정점 간에만 간선이 존재하도록 만들 수 있는 그래프 🥑 그래프의 경로 단순경로 : 경로 중 한 정점을 최대 한 번만 지.. 2022. 7. 10. [재귀] 하노이탑 이동순서 이해하기 A에 있는 탑을 C에 똑같이 쌓으려고 한다. 무조건 가장 큰 애를 밑에서 부터 쌓으려면 어떻게 해야할까? 재귀의 핵심은 큰 틀만 파악해서 코드를 짜고, 나머지 서브 경우의 수들은 틀만 잘 짜놓으면 알아서 딸려오게 끔 만드는 것이다. 그러면 서브 경우의 수를 다 빼고, 가장 밑에 있는 파란색 블럭이 C에 오려면 어떻게 해야할까? 우선 나머지 3개 블럭이 B에 있어야 한다. 그러면 파란색 블럭이 C로 이동할 수 있다. 이제 두번째로 큰 노란색 블럭이 C에 와야한다. 그러면 나머지 2개 블럭이 A에 있어야 노란색 블럭이 C로 갈 것이다. 연두색 블럭또한 마찬가지이다. 나머지 한개의 블럭을 B에 놓고 A에 C로 이동하면 된다. 즉 이 문제에서 중요한것은 가장 큰 블럭을 C로 옮기기 위해 나머지 블럭을 어딘가에 .. 2022. 7. 1. 이전 1 다음 728x90 반응형
