알고리즘 :: 자료구조와 알고리즘_TIL#15

■ JITHub 개발일지 15일차

□  TIL(Today I Learned) ::

자료구조, 알고리즘(트리, 힙, 그래프, DFS, BFS, Dynamic programming)

1. 파이썬 알고리즘

 - 트리(Tree)

  : 계층형 비선형 자료 구조로 모습이 실제 가지가 달린 나무를 거꾸로 본 모습과 유사하여 '트리'라고 말한다. 방향성이 있고 부모 노드 아래에 여러 자식 노드가 연결되는 재귀적 형태의 자료구조이다. 이진 트리, 이진 탐색 트리, 균형 트리(AVL 트리, red-black 트리), 이진 힙(최대힙, 최소힙) 등 다양한 형태의 트리가 존재한다.

  (1) 이진트리(binary Tree) : 각 노드가 최대 두 개의 자식을 가지는 형태의 트리 자료구조

      o      Level 0 
    o o o    Level 1
   o  o  o   Level 2 # 이진 트리(X)

      o      Level 0 
    o   o    Level 1
   o o o     Level 2 # 이진 트리(O)

  (2) 완전 이진트리(complete binary tree) : 노드 삽입시 최하단 왼쪽 노드부터 차례로 삽입되는 자료구조.

      o      Level 0
    o   o    Level 1
     o o     Level 2  # -> 이진 트리 O 완전 이진 트리 X

      o      Level 0
    o   o    Level 1
   o o o     Level 2  # -> 이진 트리 O 완전 이진 트리 O

 트리의 높이(Height)는 루트 노드부터 가장 아래 리프 노드까지의 길이를 말한다.

 

 - 힙(Heap)

  : 완전 이진트리 중 하나로, 데이터에서 최대/최소값을 빠르게 찾을 수 있도록 고안된 자료구조이다. 항상 큰 값이 상위 레벨에 있고, 작은 값이 하위레벨에 위치하며, 즉, 부모 노드의 값이 항상 자식 노드의 값보다 큰 구조이다.

      8      Level 0
    6   3    Level 1
     2 1     Level 2  # -> 이진 트리 O 완전 이진 트리 X 이므로 힙이 아닙니다!

      8      Level 0
    6   3    Level 1  # -> 이진 트리 O 완전 이진 트리 O 인데 모든 부모 노드의 값이
   4 2 1     Level 2  # 자식 노드보다 크니까 힙이 맞습니다!


      8      Level 0
    6   3    Level 1  # -> 이진 트리 O 완전 이진 트리 O 인데 모든 부모 노드의 값이
   4 2 5     Level 2  # 자식 노드보다 크지 않아서 힙이 아닙니다..!

 heap은 데이터를 정렬하는 차순에 따라 max heap과 min heap으로 나눌 수 있다.

 - 그래프

  : 데이터의 연결 관계를 표현할 수 있는 자료구조를 말한다.

  (1) 그래프의 요소

    · 노드(Node) : 연결 관계를 가진 각 데이터를 의미하며, 정점(Vertex)이라고도 한다.
    · 간선(Edge) : 노드 간의 관계를 표시한 선을 말한다.
    · 인접 노드(Adjacent Node) : 간선으로 직접 연결된 노드(또는 정점)를 말한다.

 

  (2) 그래프의 종류

    · 유방향 그래프(Directed Graph) : 방향이 있는 간선을 갖는다. 간선은 단방향 관계를 나타내며, 각 간선은 한 방
향으로만 진행할 수 있다.
    · 무방향 그래프(Undirected Graph) : 는 방향이 없는 간선을 갖는다.

  (3) 그래프의 표현 방법

    · 인접 행렬(Adjacency Matrix) : 2차원 배열로 그래프의 연결 관계를 표현
    · 인접 리스트(Adjacnecy List) : 링크드 리스트로 그래프의 연결 관계를 표현

          2 - 3
          ⎜       
      0 - 1

# 1. 인접 행렬
  0  1  2  3
0 X  O  X  X
1 O  X  O  X
2 X  O  X  O
3 X  X  O  X

# 배열로 표현 시
graph = [
    [False, True, False, False],
    [True, False, True, False],
    [False, True, False, True],
    [False, False, True, False]
]

# 2. 인접 리스트

0 -> 1
1 -> 0 -> 2
2 -> 1 -> 3
3 -> 2

# 딕셔너리로 표현 시
graph = {
    0: [1],
    1: [0, 2]
    2: [1, 3]
    3: [2]
}

 - DFS, BFS

  : 자료나 트리, 그래프를 탐색하는 방법으로 상위 하나의 노드부터 시작하여 인접한 다른 노드들을 재귀적으로 탐색함으로써 전체 데이터를 탐색하는 방식을 말한다.

  (1) 깊이 우선 탐색(DFS, Depth First Search)

    : 하나의 노드로부터 자식노드의 최대 깊이까지 탐색하고, 더 이상 탐색할 노드가 없다면 리턴하여 상위로 올라와 다시 탐색하는 방식을 말한다. 그래프의 최대 깊이 만큼의 공간을 요구하고, 공간을 적게 쓰나 최단 경로르 탐색하기 어렵다.

1. 루트 노드부터 시작한다.
2. 현재 방문한 노드를 visited 에 추가한다.
3. 현재 방문한 노드와 인접한 노드 중 방문하지 않은 노드에 방문한다.
4. 2부터 반복한다.

 

  (2) 너비 우선 탐색(BFS, Breadth First Search)

    : 하나의 노드로부터 현재 인접한 노드들을 모두 방문하고, 그 다음에 다음 노드들도 재귀적으로 동일하게 탐색해나가는 방식이다. 최단 경로를 탐색하는데 용이하나, 모든 분기되는 수를 다 저장함으로써 공간을 많이쓰고, 탐색 시간이 더 오래걸릴 수 있다.

1. 루트 노드를 큐에 넣는다.
2. 현재 큐의 노드를 빼서 visited 에 추가한다.
3. 현재 방문한 노드와 인접한 노드 중 방문하지 않은 노드를 큐에 추가한다.
4. 2부터 반복한다.
5. 큐가 비면 탐색을 종료한다.

 

 - 동적 계획법(Dynamic Programming)

  : 복잡한 문제를 여러 개의 간단한 문제로 쪼개어 해결하는 방식을 말한다. 즉 여러 개의 하위 문제를 해결하고 이 결과를 기록하고 이용하여 문제를 해결하는 알고리즘을 뜻한다. 이는 재귀 알고리즘과 유사하나, 동적 계획법에서는 그 결과를 기록하고 이용한다는 점이 차이점이다. 

  (1) 메모이제이션(Memoization) : 결과를 기록하는 것

  (2) 겹치는 부분 문제(Overlapping Subproblem) : 문제를 조갤 수 있는 구조

 

 

2. 파이썬 이론 복습

  - 파이썬의 class에는 속성과 메서드가 있다.

class Person:
	species = "homo sapiens"		# 변수 정의는 속성!
    
    def walk(self):					# def는 메서드!
    	print("걷고 있습니다.")

 

  - class를 사용할 때에는 매개변수로 받는 변수명과 호출하는 변수명에 유의하여야 한다.

    예를들어 아래 코드에서 호출할 변수명 name과 이닛 메서드의 매개변수로 받는 anything을 잘 구분하여 사용해야 한다.

class Person:

	def __init__(self, anything):
    	print("이닛 메서드 안입니다.")
        self.name = anything
        
person1 = Person("홍길동")
person1 = Person("김철수")

print(person1.name)
print(person1.name)


# 출력
# 이닛 메서드 안입니다.
# 이닛 메서드 안입니다.
# 홍길동
# 김철수

 - 클래스의 __init__에서 지정한 매개변수는 인스턴스를 생성할 때 변수로 받아야 한다.

class Person:
	def talk(self)"
    	print("안녕하세요 저는" + self.name + "입니다.")
        
    def __init__(self, name, age, hobby):
    	print("이닛 함수 실행 중")
        self.name = name
        self.age = age
        self.hobby = hobby
            
x = Person("홍길동", "20", "피아노")
y = Person("김철수", "30", "럭비")
z = Person("이영희", "25", "테니스")
x.talk()
print(x.hobby)


# 출력
# 이닛 함수 실행 중
# 이닛 함수 실행 중
# 이닛 함수 실행 중
# 안녕하세요 저는 홍길동입니다.
# 20

 - 클래스에서 사용하는 변수는 클래스 밖에서 정의하지 않도록 한다.(클래스의 성격 캡슐화에 어긋난다)

---

□  TIF(Today I Felt) ::

  - 자료구조와 알고리즘 내용의 일부를 한 번 훑었다. 내용의 깊이가 있고, 파이썬을 활용해 이론을 적용해 보는 연습도 많이 필요한 것 같다. 온라인에 백준과 같은 다양한 알고리즘 학습 사이트를 통해 여러 문제들을 접해보고, 하나의 풀이가 아닌 다양한 알고리즘 이론들을 적용한 풀이를 해보면서, 시간복잡도, 공간복잡도를 비교해본다면 실력이 많이 늘 것이라고 생각된다.