monsterroute 님의 블로그 monsterroute 님의 블로그

Graph  그래프는 vertex(정점)과 edge(간선)으로 이루어진 비선형의 자료구조를 말한다. 예를 들어 geometrical (기하학적)으로 표현한 그래프는 이런 모양이고  이 그래프를 Mathmatical (수학적)으로 표현하면 아래와 같다.V = {0, 1, 2, 3}E = { (0, 1), (0, 2), (0, 3), (1, 2), (1, 3), (2, 3) } 방향이 있으면 이렇게 된다. ㅎㅎ 우재튜터님의 설명 덕에 그래프들이 귀엽게 보인다. 3번은 인기남❤️   즉, 방향이 있는 그래프와 없는 그래프로 나뉜다. Undirected Graph : 무방향(양방향) 그래프Directed Graph : 방향(단방향) 그래프 응?  이렇게 거울 보는 것처럼, 자기가 자기한테 오는 간선을 가진 노드..

트리 순회  문제이진 트리를 입력받아 전위 순회(preorder traversal), 중위 순회(inorder traversal), 후위 순회(postorder traversal)한 결과를 출력하는 프로그램을 작성하시오.예를 들어 위와 같은 이진 트리가 입력되면,전위 순회한 결과 : ABDCEFG // (루트) (왼쪽 자식) (오른쪽 자식)중위 순회한 결과 : DBAECFG // (왼쪽 자식) (루트) (오른쪽 자식)후위 순회한 결과 : DBEGFCA // (왼쪽 자식) (오른쪽 자식) (루트)가 된다.입력첫째 줄에는 이진 트리의 노드의 개수 N(1 ≤ N ≤ 26)이 주어진다. 둘째 줄부터 N개의 줄에 걸쳐 각 노드와 그의 왼쪽 자식 노드, 오른쪽 자식 노드가 주어진다. 노드의 이름은 A부터 차례대로 ..

Binary Tree 이진 트리의 특징i 번째 레벨의 최대 노드 수: 2^(i-1)깊이가 k인 이진 트리의 최대 노드 수: 2^k-1 이진 트리 순회 Search == Traversal어떠한 값이 주어어졌을 때 해당 값이 일치하는 노드가 있는지 보는 것즉 모든 노드를 봐야 함 방법 (DFS / BFS)  DFS• 트리의 한 경로를 끝까지 탐색한 후 다른 경로를 탐색하는 방법• Strack or Recursive를 이용한 구현 세가지 구현 방법 Preorder Traversal (전위순회): 루트 > 왼쪽 > 오른쪽void preorder ( nptr bt ) { if ( bt ) { // 현재 노드(bt)가 NULL이 아닌 경우에만 실행 print ( bt->data ); // 현재 노드의..

자료구조 알고리즘 2차원 배열문제 우재튜터님이 내주신 문제 3개 중.. 어떻게 하나를 못 풀었다..ㅠㅠ이건 그 중 하나. 색종이 문제가로, 세로의 크기가 각각 100인 정사각형 모양의 흰색 도화지가 있다. 이 도화지 위에 가로, 세로의 크기가 각각 10인 정사각형 모양의 검은색 색종이를 색종이의 변과 도화지의 변이 평행하도록 붙인다. 이러한 방식으로 색종이를 한 장 또는 여러 장 붙인 후 색종이가 붙은 검은 영역의 넓이를 구하는 프로그램을 작성하시오.  먼저 종이에 휴.. 어떻게 시작해야해ㅠㅠㅠ 난 코드보다 생각하고 로직을 세우는 법을 훈련하는게 더 급선무인 것 같다.  결국 마음은 무겁게 양손은 가볍게.. 빈 손으로 스쿼드 출발..    우재튜터님의 설명을 들었다. 나도 튜터님처럼 사고하고 싶다.. 이..

알고리즘을 공부하면서.. 어렵고.. 힘이 빠졌다. 개념도 개념이지만..  예제문제를 보면 헛웃음이 나왔다.. '여러분 여기로 가면 됩니다' 하고 지도를 줬는데, 응?... 이게 뭐야 .. 어디로 가라는 거야..  뭘 하라는 거야.. 이런 생각 때문에..난.. 코드 구현은 고사하고  문제를 이해하는 데만 많은 시간을 썼다. 근데 우재튜터님이 알고리즘은 그럴 수 있다고.. 차근차근 진도를 따라가는 과목이 아니라고. 그 말씀을 들으니 불안했던 마음이 편안하게 불안해졌다. 아무튼 방향성을 바로잡고 다시.. 공부해보기로.. 먼저, 단기적으로 알아야 하는 자료구조들을 살펴보자. 적어도 여기서 선형구조와 비선형구조 안에 있는 자료구조는 꼭 알아야 한다.자료구조를 안다는 건, 이 자료구조가 어떤 데이터를 저장하기 위한..

class  파이썬은 그 자체로 객체라고 할 수 있을만큼 대표적인 객체 지향 프로그래밍(OOP) 언어이며,  class는 객체 지향 프로그래밍에서 사용되는 중요한 개념이다. class는 데이터 타입을 만든다는 거고, class에는 '속성'과 '행동'이 있어야 한다. 속성은 class 안에서 정의된 변수 → 즉, 객체가 가지고 있는 '데이터'행동은 class 안에서 정의된 함수 → 즉, '메서드'  [ 메서드의 종류 ] 1. 인스턴스 메서드우리가 주로 사용하는 메서드로, 인스턴스 번수를 사용하거나, 인스턴스 변수에 값을 설정한다.클래스 내부에 정의되는 기본 메서드다.호출 시, 첫번째 인자로 인스턴스 자기자신(self))가 자동으로 전달된다.메서드를 호출한 인스턴스를 의미하는 self 매개변수를 통해 인스턴..

BFS 저번시간에 배운 DFS는 깊이 우선 탐색으로, 탐색하는 노드를 갈 수 있는 한 최대한 깊이 따라갔다가 더이상 길이 없으면 백해서 다시 노드를 탐색하는 구조였다면 BFS는 Breadth-first search, 너비 우선 탐색이라는 뜻으로, 현재 노드를 시작으로 현재 노드에 인접한 모든 노드들을 먼저 방문한다. 즉, 아래 그래프에서 DFS가 1 > 2 > 5 > 9 > 3 순서로 방문한다면, BFS는 1 > 2 > 3 > 4 > 5 순서로 방문한다. 이번에도 코드로 구현해보자.우선 딕셔너리로 그래프를 작성하고graph = {1: [2, 3, 4],2: [5],3: [6, 7],4: [8],5: [9],6: [10],7: [],8: [],9: [],10: [],} Queue를 사용할거다. 일단 BFS..

DFS Depth First Search 깊이 우선 탐색 이라는 뜻으로, 아래와 같이 노드가 갈 수 있는 깊이만큼 계속 가다가 길이 없으면 다시 백해서 다른 방향을 탐색해서 가는 구조를 말한다.  DFS를 구현하는 방법은 재귀함수로 구현하는 방법과 스택으로 구현하는 방법 두가지가 있는데 재귀함수로 코드를 짤 때, 가장 중요한 포인트는 두가지이다. 1. 반복적으로 발생하는 일이 뭔지 아는 것2. 종료 조건을 아는 것각각의 숫자는 노드 노드 1을 방문하고 2, 5, 9 차례대로 방문할거다. 근데 2에 방문 했는데 2한테 자식이 있으니까 5한테 가기 전에 2의 자식인 3한테 가고 3의 자식인 4한테 갔다가 더이상 자식이 없음을 확인 후 백해서 2로 온 후 다른 자식이 있는지 확인하고 없으면 5한테 가는 순이다..