공부정리

1. AVL 트리

 이진 탐색 트리를 활용한 데이터의 탐색은 분명 O(logN) 까지의 성능을 보일 수 있지만 트리가 한 방향으로 치우쳐

생성될 경우 최악의 경우 O(N) 까지 성능이 떨어질 수 있다.  반대로 이진 탐색 트리가 항상 균형 이진 트리가 되도록

할 수 있다면 항상 O(logN)의 성능을 보장할 수 있을 것이다.  AVL 트리는 삽입, 삭제가 이뤄져도 항상 균형 상태를

유지하는 자가 균형 이진 탐색 트리이다. 

2. AVL 트리의 특징

• 어떤 노드를 기준으로 하더라도 좌, 우 서브트리의 높이(깊이)가 2 이상의 차이를 보이지 않는다.
• 노드의 삽입/삭제가 발생할 때마다 매번 서브트리의 회전을 통해 균형을 맞춘다.
• 균형을 거의 완벽하게 유지하기 때문에 탐색속도는 빠르지만 삽입/삭제의 속도가 이후에 설명할
  Red-black 트리에 비해 느린편이다.
• 삽입/삭제/탐색 모두 O(logN)을 보장한다.

3. 회전 알고리즘

 ① LL 회전

• 위 그림과 같이 기준이 되는 루트노드(1)의 좌측 서브트리와 우측 서브트리의 높이차이가 1보다 크고
  좌측 자식 노드 기준으로 좌측 서브트리의 높이가 우측 서브트리의 높이보다 큰 상태를 LL상태라고 한다.
• LL 회전은 LL 상태에서 일어난다.

• 먼저 루트 노드(1)의 왼쪽 자식노드를 왼쪽 자식노드(2)의 오른쪽 자식노드(null) 로 한다. 

• 원래 왼쪽 자식노드였던 2번 노드의 오른쪽 자식노드를 루트노드였던 1로 한다.

 ② RR 회전

• 위 그림과 같이 기준이 되는 루트노드(1)의 우측 서브트리와 좌측 서브트리의 높이차이가 1보다 크고
  우측 자식 노드 기준으로 우측 서브트리의 높이가 좌측 서브트리의 높이보다 큰 상태를 RR상태라고 한다.
• RR 회전은 RR 상태에서 일어난다.

• 먼저 루트 노드(1)의 오른쪽 자식노드를 오른쪽 자식노드(2)의 왼쪽 자식노드(null) 로 한다. 

• 원래 오른쪽 자식노드였던 2번 노드의 왼쪽 자식노드를 루트노드였던 1로 한다.

 ③ LR 회전

• 위 그림과 같이 루트노드 기준 좌측 서브트리 높이가 우측 서브트리보다 2이상 높고 좌측 자식노드 기준
  우측 서브트리의 높이가 좌측 서브트리보다 높은 상태를 LR 상태라고 한다.
• LR 회전은 LR 상태에서 일어난다.
• LL, RR 회전을 알고있다면 여기서부터는 간단하다. 루트노드(1)의 좌측 자식노드(2)를 기준으로 RR 회전을
  실행한 뒤, 루트 노드(1)를 기준으로 LL 회전을 실행해주면 된다.

 ④ RL 회전

• 위 그림과 같이 루트노드 기준 우측 서브트리 높이가 좌측 서브트리보다 2이상 높고 우측 자식노드 기준
  좌측 서브트리의 높이가 우측 서브트리보다 높은 상태를 RL 상태라고 한다.
• RL 회전은 RL 상태에서 일어난다.
• LR 회전과 반대로 루트노드(1)의 우측 자식노드(2)를 기준으로 LL 회전을 실행한 뒤, 루트노드(1)를 기준으로
  RR 회전을 실행해주면 된다.

4. AVL 트리의 연산

• 삽입/삭제(Insert, Delete)
  • 이진 탐색 트리의 방식대로 데이터를 삽입/삭제한다.
  • 루트 노드부터 시작하여 균형 재조정함수를 호출하여 균형을 재조정한다.
• 균형 재조정(Rebalance)
  • 루트 노드로부터 시작
  • 좌측 서브트리에 대해 균현 재조정 함수 재귀호출
  • 우측 서브트리에 대해 균형 재조정 함수 재귀호출
  • 좌측 서브트리와 우측 서브트리의 높이를 구한다.
  • 만약 두 서브트리의 높이차이가 2 이상이라면 현재 루트노드를 기준으로 트리가 어느 상태인지 파악한다.
  • 각 상태에 맞는 회전(LL, RR, LR, RL)을 실행한다.
  • 루트 노드를 환한다.

1. 수정 일시

 이번에는 게시글을 수정하고 삭제하는 기능을 추가할 것이다. 먼저 게시글과 답글에 수정 일시 정보를 넣기 위한

modify_date 속성을 추가해보자.

 pybo/models.py 를 위와 같이 수정하여 게시글과 답글 모델에 modify_date 속성을 추가해준다.  modify_date 는

수정사항이 발생했을 때만 생성되는 데이터이기 때문에 어떤 조건으로든 값을 비워둘 수 있음을 명시하기 위해

null=True, blank=True 로 설정한다.

물론 모델이 변경됐기 때문에 makemigrations 와 migrate 도 잊지말고 실행해줘야 한다.  author 속성을 추가했을 때와

달리 비워둘 수 있는 속성이기 때문에 별다른 문제없이 수행된다.

2. 질문 수정

 이제 게시글 수정 기능을 구현해보자.

먼저 templates/pybo/question_detail.html 을 위와 같이 수정하여 로그인한 유저가 이 게시글의 작성자일 때에 한해서

게시글 수정 버튼이 나타나도록 한다.

pybo/urls.py 에 위와 같이 pybo:question_modify 에 해당하는 url 매핑을 추가한다.

pybo/views.py 에 question_modify 함수를 추가한다.  비정상적인 접근을 대비해서 게시글 작성유저 본인이 맞는지

한번더 확인하여 본인이 아니라면 오류메시지를 띄우고 게시글 상세 페이지로 이동하고 작성자 본인이 맞다면

question 인스턴스와 함께 게시글 작성 페이지로 이동하도록 한다.

오류 메시지를 표시하기 위해 quesiton_detail.html 을 위와 같이 조금 더 수정한다. 

이제 유저 본인이라면 수정 버튼이 생기고 수정 버튼을 누르면 게시글 수정 페이지가 잘 보이는 것을 확인할 수 있다.

또한 url을 통해 비정상적으로 수정 페이지에 접근할 경우 수정 권한이 없다는 오류메시지를 띄우는 것도 확인 가능하다.

3. 질문 삭제

 다음은 질문을 삭제하는 기능을 구현할 차례이다. 

방금 전 수정 버튼을 추가한 자리 아래에 위와 같이 삭제 버튼도 만들어준다. 삭제버튼의 경우 정말로 삭제할 것인지

확인을 해야하기 때문에 href 를 #으로 하고 data-uri에 삭제 페이지 url을 저장, 클래스에 delete 속성을 넣어준다.

삭제 확인 메시지창이 뜨도록 하기 위해서는 자바 스크립트 코드가 필요하다. 그리고 자바 스크립트 코드를 실행하려면

jQuery 라이브러리를 로드할 필요가 있다.  우리는 이전에 부트스트랩의 적용을 위해 이미 jQuery 라이브러리를

base.html에 포함시켜 두었다.  base.html을 위와같이 조금 수정하여 자바스크립트의 호출이 반드시 jQuery 로드 이후에

오도록 하자.

그리고 question_detail.html 에서 body 블록 아래에 script 블록을 추가하여 삭제를 확인하는 메시지가 뜨도록 한다.

pybo/urls.py 에 data-uri 에 넣어준 question:delete 에 해당하는 url 매핑을 추가해준다.

pybo/views.py 에 question_delete 함수도 구현해준다.  수정과 마찬가지로 유저 본인확인을 한번 더 진행한 뒤

삭제가 이뤄지도록 하였다.

유저 본인의 게시물일 경우 삭제 버튼이 나타나고 클릭 시 확인 메시지가 나타난다.

삭제를 확인할 경우 게시글이 정상적으로 삭제된 것을 볼 수 있다.

4. 답변 수정

 이제 답글에도 수정, 삭제기능을 구현해야한다.  기본적인 흐름은 게시글과 같으나 답변 작성 화면은 원래 게시글

상세 페이지에 딸려있는 형태이기에 수정을 위한 템플릿을 별도로 만들어야한다.

question_detail.html 을 수정하여 게시글 상세 페이지의 답글에 수정 버튼을 추가한다.

pybo/urls.py 에 answer:modify 에 해당하는 url 매핑을 추가한다.

pybo/views.py 에 answer_modify 함수를 추가한다.

위와 같이 question_form.html 을 참조하여 answer_form.html 을 작성한다. 

이제 정상적으로 답글 수정이 가능한 것을 확인할 수 있다.

5. 답변 삭제

 답글 삭제도 게시글의 삭제와 마찬가지로 이루어진다.

먼저 question_detail.html 에서 답글의 수정버튼 옆에 삭제 버튼을 추가해준다.  게시글 삭제와 마찬가지로 href 를

#으로 하고 url은 data-uri 에 넣어준다.  또한 삭제버튼이 눌린것을 감지하기 위해 class에 delete 속성도 추가한다.

pybo/urls.py 에 answer:delete 에 해당하는 url 매핑을 추가한다.

pybo/views.py 에 answer_delete 함수를 위와같이 구현한다.  삭제되면 index로 나가야했던 게시글과 달리

답글은 삭제할 경우 answer.question.id 에 해당하는 question_detail 페이지로 이동하도록 한다.

삭제 확인을 위한 자바스크립트 코드는 이미 삽입되어있기 때문에 추가적인 작업이 필요하지 않다.

답글 삭제 기능이 정상적으로 동작하는 것을 확인할 수 있다.

6. 수정 일시 표시

 마지막으로 게시글과 답글에 수정이 발생한 경우 수정 일시를 표시하는 기능을 추가하자.

수정된 게시글과 답글에 정상적으로 수정일시가 표시되는 것을 확인할 수 있다.

1. 힙(Heap)

 힙은 최댓값, 최솟값의 탐색을 빠르게 하기 위해 고안된 완전 이진 트리를 기반으로 하는 자료구조이다.  

힙은 다음과 같은 조건을 만족한다.

• 어떤 노드 A의 키 값은 부모노드 B의 키 값과 대소관계를 가진다
• 형제노드 간에는 대소관계를 따지지 않는다.

2.  힙의 특징

• 부모노드의 키 값이 자식노드의 키 값 보다 항상 크다면 최대 힙, 항상 작다면 최소 힙이라고 한다.
• 최대 힙은 최댓값이, 최소 힙은 최솟값이 루트 노드가 되는 상태를 항상 유지한다.
• 힙의 종류에 따라 트리의 차수가 2보다 큰 경우도 있지만 대부분의 경우 힙이라고 하면 이진 힙을 가리킨다.
• 데이터의 삽입에 O(logN), 최댓값 혹은 최솟값 탐색에 O(1)의 시간복잡도를 보인다.
• 그 특성상 우선순위 큐 등의 자료구조를 구현하는데 사용할 수 있다.
• 정렬 알고리즘 중 하나인 힙 정렬에도 사용되는데, 내림차순 정렬에는 최대 힙을, 오름차순 정렬에는 최소힙을
  사용한다.
• 힙은 완전이진트리이기 때문에 일반적으로 배열로 구현된다. 루트노드의 인덱스는 0이며 어떤 노드의 인덱스가
  i일 때 왼쪽 자식노드는 i * 2 + 1, 오른쪽 자식노드는 i * 2 + 2 가 된다.

3. 힙의 연산(최소 힙 기준)

• 삽입(push)
  • 데이터를 배열의 맨 끝에 삽입한다.
  • 데이터가 삽입된 인덱스로부터 시작하여 부모노드가 존재하고 부모노드의 값이 자신보다 크다면
    부모 노드와 위치를 뒤바꾸는 작업을 더이상 위치변경이 발생하지 않을 때 까지 반복한다.
• 삭제(pop)
  • 배열의 맨 끝의 데이터를 맨 처음의 데이터에 덮어씌운다.
  • 삽입과는 반대로 자신보다 값이 작은 자식노드가 있다면 자식노드와 위치를 뒤바꾼다.
    양측 자식노드 모두 자신보다 작다면 둘 중 보다 작은 쪽과 뒤바꾼다.
  • 위 작업을 더이상 위치변경이 발생하지 않을 때 까지 반복한다.
• 힙 변환(heapify)
  • 루트노드가 0이고 배열의 길이가 n인 힙이 아닌 배열을 힙으로 변환
  •  i = n//2-1 부터 탐색시작, 좌측 자식노드인 i * 2 + 1, 우측 자식노드인 i * 2 + 2 와 비교
  • 만약 자식노드중 자신보다 작은 것이 있다면 자식노드와 위치를 뒤바꾼다.
  • 위치변경이 발생했다면 위치를 바꾼 대상 인덱스를 기준으로 다시 탐색
  • 위치변경이 발생하지 않았다면 i-1을 탐색
  • i >= 0 일 동안 위 작업을 반복
• 힙 변환(heapify) 코드

from heapq import heappop


def heapify(arr, cur):
    # 좌, 우 자식노드
    left, right = cur * 2 + 1, cur * 2 + 2

    # 위치를 바꿀 대상 => 자기 자신으로 초기화
    target = cur

    # 좌측 자식노드가 존재하고 현재 위치 변경 대상보다 키 값이 작을 경우
    # 위치 변경 대상을 좌측 자식노드로 갱신
    if left < len(arr) and arr[left] < arr[target]:
        target = left

    # 우측 자식노드가 존재하고 현재 위치 변경 대상보다 키 값이 작을 경우
    # 위치 변경 대상을 우측 자식노드로 갱신
    if right < len(arr) and arr[right] < arr[target]:
        target = right

    # 자기 자신이 아닌 위치 변경 대상을 찾았다면
    # 위치를 변경하고 변경된 위치에 대해 heapify 재귀호출
    if cur != target:
        arr[cur], arr[target] = arr[target], arr[cur]
        heapify(arr, target)


# 힙이 아닌 배열
a = [1, 5, 2, 3, 7, 4, 6]

# len(a)//2-1 부터 0까지의 노드에 대해 heapify 호출
for i in range(len(a) // 2 - 1, -1, -1):
    heapify(a, i)

# 힙 출력
# 결과: [1, 3, 2, 5, 7, 4, 6]
print(a)

# 힙이 정상적으로 만들어졌는지 확인
# 결과: 1, 2, 3, 4, 5, 6, 7
for _ in range(len(a)):
    print(heappop(a), end=" ")

 => heapify 와 heappop 을 구현하는 것 만으로 힙 정렬을 구현할 수 있다.  heapify가 거의 O(N)에 가까운 성능을

      보이며 heappop 이 O(logN)의 성능을 보이기 때문에 힙 정렬은 N개의 데이터에 대해 O(NlogN)의 성능을 보인다.

1. 질문 목록 페이지 수정

 이제 로그인한 유저만이 게시글과 답글을 작성할 수 있게 되었으니 게시글과 답글에 글쓴이를 표시해야한다.

우선 질문 목록 템플릿에 글쓴이를 표시해보자.

테이블 헤더의 텍스트가 가운데 정렬되도록 class 속성을 수정하고 제목 부분의 너비를 지정해준 뒤

제목 뒤쪽에 글쓴이 항목을 추가해준다.  그리고 나서 for 문에서도 제목은 왼쪽정렬 되도록 class 속성을

수정해주고 제목 뒤쪽에 글쓴이를 추가해준다.

이제 질문 리스트에서 게시글의 작성자를 확인할 수 있다.

2. 질문 상세 페이지 수정

 다음으로 질문 상세 템플릿에 글쓴이를 표시해보자.

templates/pybo/question_detail.html 을 위와 같이 수정하여 게시글과 답글의 작성일시를 표시하던 뱃지의

텍스트를 왼쪽으로 정렬시키고 작성일시 위에 작성자도 표시되도록 한다. 

이제 게시글과 답글 모두 작성자를 확인할 수 있다.

1. author 속성 추가

 지난 글에서 회원 가입 기능을 추가했지만 아직까지는 회원 가입 후 로그인을 한 채로 게시글이나 답글을 작성하여도 
로그인 하지 않은 상태일 때와 달라진 것이 없다.  먼저 게시판의 질문, 답변에 글을 작성한 사람이 누구인지 보여주는

"글쓴이" 항목이 필요하다.

pybo/models.py 를 위와 같이 수정하여 Question 과 Answer 모델에 author 속성을 추가해준다. 

python manage.py makemigrations
python manage.py migrate

모델이 변경되었으니 이를 반영시키기 위해 위와 같이 makemigrations 와 migrate 명령을 수행해줘야 한다.

그런데 makemigrations 를 수행하면 위와 같은 메시지가 나온다.  기존에 User 정보 없이 작성된 게시글과 답글들을

어떻게 처리할지 묻는 것이다.  1을 선택하면 디폴트 값을 지정하거나 해당 값을 null로 처리할 수 있으며 2를 선택하면

작업을 취소한다.  디폴트값을 지정하기 위해 1을 선택해보자.

위에서 1을 선택하면 파이썬 셸에 진입한다. 여기서 디폴트 값을 1로 설정하기 위해 1을 입력하자. 1을 디폴트 값으로

지정하는 이유는 우리가 처음 만든 계정인 관리자 계정의 id가 1이기 때문이다.  계정은 생성될 때 마다 1부터 id가

순차적으로 증가하며 자동으로 생성된다.  이 작업으로 지금까지 회원가입 없이 작성한 모든 게시글과 답글은 관리자

계정으로 작성한 것이 된다.

위의 작업을 두 번(answer, question) 해주면 위와 같은 메시지가 뜨면서 makemigrations 명령이 수행된다.

마지막으로 migrate 명령어를 수행하면 정상적으로 완료되는 것을 볼 수 있다.

※  author 속성에 null 허용하기

 경우에 따라서는 User 정보 없이도 글을 작성할 수 있도록 할 수도 있다.  이것을 허용하려면 author 를 정의할 때

author = models.ForeignKey(User, on_delete=models.CASCADE, null=True)

와 같이 null=True 를 지정해주면 된다.

2. author 정보 저장

 이제 모델에 author 속성이 추가됐으니 질문, 답변을 저장할 때 author 정보도 함께 저장해야한다.

pybo/views.py 를 위와 같이 수정하여 게시글과 답글 저장시에 유저 정보가 추가되도록 한다.

3. 로그인이 필요한 함수

게시글과 답글 등록 시에 author 정보를 저장하도록 수정한 후에 로그아웃 상태로 게시글이나 답글을 작성하려하면 

위와 같이 ValueError 가 발생한다.  로그아웃 상태여서 request.user 가 User가 아닌 AnonymousUser이기 때문이다.

request.user 를 사용하는 함수를 모두 로그인이 필요한 함수로 지정하면 해당 함수를 호출 시 자동으로 로그인 화면

으로 이동하도록 할 수 있다.

pybo/views.py 를 위와 같이 수정하여 answer_create 와 question_create 를 로그아웃 상태로 실행 시 자동으로

로그인 화면으로 이동하도록 한다.

이제 로그인 없이 로그인이 필요한 함수를 호출하면 자동으로 로그인 화면으로 이동하는 것을 확인할 수 있다.

이 때 url 에 보이는 ?next= ... 는 로그인이 수행되면 다시 이동할 페이지를 의미한다.  그러나 현재 상태로는 로그인이 완료되고도 그 페이지로 이동되지 않는다.  로그인 템플릿을 수정하여 이 기능을 추가해야한다.

templates/common/login.html 을 위와 같이 수정하여 로그인 성공 후 next에 해당하는 url로 이동하도록 한다.

여기까지 완료하면 로그인이 필요한 기능을 로그인 없이 사용하려하면 바로 로그인 화면으로 이동하고 로그인이

완료되면 해당 페이지로 다시 돌아가는 것을 확인할 수 있다.

4.  disabled

 게시글 작성의 경우 작성 화면에 진입하기 위해 로그인이 필요하기 때문에 그럴일이 없지만 답글 작성의 경우 

로그인하지 않아도 게시글 상세 페이지를 볼 수는 있기 때문에 답글창에 답글을 작성해놓고 로그인을 하지 않아서

기껏 작성한 글이 날아가버리는 불상사가 발생할 수 있다.  이를 막기 위해 로그인 상태가 아니면 애초에 답글을

작성할 수 없도록 해보자.

templates/pybo/question_detail.html 을 위와 같이 수정하여 로그인 상태가 아니면 답글 작성 칸이 비활성화 상태가

되도록 한다.

이제 로그인 상태에서만 답글 창이 활성화 되는 것을 확인할 수 있다.

1. 트리(Tree)

 트리는 그래프(Graph)와 유사한 형태를 가지며 어떤 의미로는 그래프의 일종이라고 볼 수도 있다.  

다만 모든 노드가 동등한 관계였던 그래프와는 달리 트리의 노드는 서로 부모/자식의 관계를 가진다. 

아래 예시를 보며 좀더 자세히 알아보자.

• 부모 노드를 가지지 않는 노드를 루트(root) 노드 라고 한다.
  
  
• 루트 노드를 제외한 모든 노드는 한 개의 부모 노드를 가진다.(두 개 이상의 부모 노드를 가질 수 없다)
  
  
• 자식 노드를 가지지 않는 노드들을 리프(leaf) 노드 라고 한다.
  
  
• 리프 노드를 제외한 모든 노드는 한 개 이상의 자식 노드를 가진다.
• 어떤 노드의 자식노드를 루트로 하는 트리를 그 노드의 서브 트리(subtree)라고 한다.
  
  
• 어떤 노드가 가지는 자식 노드의 갯수(혹은 서브트리의 갯수)를 노드의 차수(degree) 라고 한다.
  트리 전체의 차수는 노드들의 차수 중 가장 큰 값이 된다.
  
  
• 루트 노드로부터 어떤 노드 까지 거쳐야하는 간선의 갯수를 그 노드의 깊이(depth) 라고 한다.
  루트 노드의 깊이는 0이다.
  
  
• 서로 깊이가 같은 노드들의 집합을 레벨(level) 이라고 한다. 위 트리에서의 레벨 1에 해당하는 노드는
  3, 2, 0 이 있다.

2. 트리의 표현

• 배열을 사용한 트리의 표현
  • arr[0] 을 루트 노드로 한다
  • 노드 arr[i] 의 좌측 자식 노드는 arr[i * 2 + 1], 우측 자식 노드는 arr[i * 2 + 2] 에 저장된다.
  • 특수한 트리가 아니면 메모리의 낭비가 매우 심하다.
  • 완전 이진 트리를 나타내는 경우라면 빈 공간이 없고 자식 노드를 가리키기 위한 포인터가
    필요하지 않기 때문에 효율적이다.
    
    
• 연결 리스트를 사용한 트리의 표현
  • 자기 자신의 데이터와 좌측, 우측 자식노드를 가리키는 포인터를 가지는 노드 간의 연결로 표현한다.
  • 정확히 노드의 수 만큼만 메모리를 차지하기 때문에 대부분의 경우 배열을 사용한 방식보다
    메모리 효율이 좋다.
  • 특정 노드에의 접근이나 트리의 순회 등은 배열을 사용한 방식에 비해 느리다.

3. 트리의 순회(Traversal)

 트리의 순회방법 네 가지에 대해 알아본다.  모든 순회는 루트 노드로부터 시작한다.

1) 전위 순회(Preorder Traversal)

• 절차
  ① 현재 노드를 탐색
  ② 좌측 자식 노드로 이동하여 해당 절차를 수행
  ③ 우측 자식 노드로 이동하여 해당 절차를 수행
  
  
• 결과
   4 - 2 - 3 - 5 - 7 - 1 - 9 - 8 - 6
• 순서의 맨 앞이 항상 루트 노드를 가리킨다.
• 일반적인 깊이 우선 탐색이 이와 같은 순서를 보인다.

2) 후위 순회(Postorder Traversal)

• 절차
  ① 좌측 자식 노드로 이동하여 해당 절차를 수행
  ② 우측 자식 노드로 이동하여 해당 절차를 수행
  ③ 현재 노드를 탐색
  
  
• 결과
   5 - 7 - 3 - 9 - 8 - 1 - 2 - 6 - 4

• 순서의 맨 뒤가 항상 루트 노드를 가리킨다.

3) 중위 순회(Inorder Traversal)

• 절차
  ① 좌측 자식 노드로 이동하여 해당 절차를 수행
  ② 현재 노드를 탐색
  ③ 우측 자식 노드로 이동하여 해당 절차를 수행
  
  
• 결과
   5 - 3 - 7 - 2 - 9 - 1 - 8 - 4 - 6

• 루트보다 먼저 방문한 쪽은 좌측 서브트리에, 나중에 방문한 쪽은 우측 서브트리에 속한다
• 이진 탐색 트리를 중위 순회 할 경우 노드들을 오름차순 정렬한 순서로 방문하게 된다.

4) 레벨 순회(Level-order Traversal)

• 절차
  ① 현재 레벨의 모든 노드를 좌측부터 순서대로 순회
  ② 다음 레벨로 이동하여 해당 절차를 수행
  
  
• 결과
   4 - 2 - 6 - 3 - 1 - 5 - 7 - 9 - 8

• 너비 우선 탐색이 이와 같은 순서를 보인다.
• 큐(Queue) 를 사용하여 구현할 수 있다.

4. 트리의 종류 - 이진 트리

  1) 이진 트리(Binary Tree)

• 차수가 2인 트리, 즉 노드가 가질 수 있는 자식 노드의 최대 갯수가 2인 트리를 의미한다.

  2) 이진 탐색 트리(Binary Search Tree)

• 어떤 노드의 좌측 서브 트리에는 자신보다 작은 값을 가지는 노드만이, 우측 서브 트리에는 자신보다 큰 값을 
  가지는 노드만이 존재하는 상태의 이진 트리이다.
  
  
• 균형이 잘 잡힌 이진 탐색 트리의 경우 트리 내의 특정 데이터를 탐색하는데 O(logN) 의 시간복잡도를 보인다.

  3) 완전 이진 트리(Complete Binary Tree)

• 마지막 레벨을 제외한 레벨이 완전히 채워져있으며 마지막 레벨의 노드가 왼쪽에서부터 채워진 상태인
  이진 트리이다.
  
  
• 배열로 표현했을 때 빈 칸이 생기지 않는 트리이다.
  
  
• 위 그림에서 A는 완전 이진 트리지만 B는 레벨 2가 완전히 채워지지 않았기 때문에, C는 마지막 레벨의 노드 8, 9 가
  왼쪽에서부터 채워지지 않았기 때문에 완전 이진 트리가 아니다.

 4) 정 이진 트리(Full Binary Tree)

• 모든 노드가 자식노드를 두 개 가지거나 아예 가지지 않는, 즉 자식 노드를 하나만 가지는 노드가 없는 트리이다.
  
  

 5) 포화 이진 트리(Perfect Binary Tree)

• 마지막 레벨까지 빈 공간 없이 완전히 채워진 이진 트리이다.

 6) 균형 이진 트리(Balanced Binary Tree)

• 명확한 정의가 있는 것은 아니지만 트리 B와 같이 치우친 상태가 아닌 A와 같이 균형을 이룬 상태의 
  이진 트리이다.
• 균형의 기준을 어떻게 세우느냐에 따라 다른 형태가 될 수 있지만 일반적으로는 모든 노드에 대해
  좌측과 우측의 서브트리의 높이 차이가 일정이상 나지 않을 것을 기준으로 한다.

1. 계정 생성

 지난 글에서 로그인/로그아웃 기능을 추가했으니 이번에는 회원가입 기능을 추가해야한다.

templates/common/login.html 을 위와 같이 수정하여 "로그인"이라는 제목과 우측 상단의 회원가입 링크를 만든다.

common/urls.py 을 위와 같이 수정하여 signup 에 해당하는 url 매핑을 추가한다.

common/forms.py 파일을 생성하여 위와 같이 회원가입을 위한 UserForm 클래스를 작성한다.  UserForm 클래스는

django.contrib.auth.forms 의 UserCreationForm 을 상속하여 만든다.  UserCreationForm 을 그대로 사용할 경우

username 과 password1, password2 만을 입력받을 수 있기 때문에 이메일 등의 추가 속성을 입력받기 위해서는

UserCreationForm 클래스를 상속하여 직접 만들어야 한다. 

common/views.py 를 위와 같이 작성하여 GET으로 요청됐을 때는 UserForm 을 생성하여 signup.html 을 렌더링하고

POST로 요청됐을 때는 UserForm에 들어있는 데이터를 기반으로 계정을 생성, 자동으로 로그인까지 한 뒤 index

페이지로 리다이렉트 되도록 한다.

마지막으로 templates/common/signup.html을 생성하여 위와 같이 작성하면 회원 가입 화면까지 완성된다.

2. 테스트

로그인 화면의 우측 상단에서 회원가입 링크를 확인할 수 있다.

링크 클릭 시 회원 가입 화면이 정상적으로 표시된다.

잘못된 입력값이 주어질 경우 form_erros.html에 따라 폼 에러 항목들을 보여준다.

정상적인 데이터를 입력할 경우 가입과 동시에 자동으로 로그인 후 index 화면으로 이동하였다.

admin 페이지에서 슈퍼유저 계정으로 로그인하여 사용자 목록을 확인해보면 위와 같이 가입된 계정을 확인할 수 있다.

이것으로 회원 가입 기능까지 구현이 완료되었다.

1. 그래프(Graph)

 그래프는 정점(Vertex)들과 그 정점들 사이를 연결하는 간선(Edge)으로 이루어진 비선형자료구조이다.  정점은 

노드(Node) 라고도 부른다.  또한 각 노드에 연결된 간선의 갯수를 그 노드의 차수(Degree) 라고 한다.

위의 예시는 0부터 5 까지의 숫자를 담고있는 6개의 노드와 그 사이를 잇는 8개의 간선으로 이루어진 그래프이다.

2. 그래프의 종류

  1) 유향 그래프(Directed Graph)

• 위와 같이 간선에 방향성이 있는 그래프를 의미한다.  노드 사이의 경로가 왕복 불가능한 것이어야할 경우 사용된다.

  2) 무향 그래프(Undirected Graph)

• 위와 같이 간선에 방향성이 없는 그래프를 의미한다.  단순히 두 노드가 연결되어있다는 정보만을 제공한다.
  
  
• 일반적으로 그래프라고 하면 무향 그래프를 의미하는 경우가 많다.  두 노드 사이의 경로가 왕복 가능한 경로일
  경우 사용된다.

  3) 가중 그래프(Weighted Graph)

• 위와 같이 간선에 가중치가 존재하는 그래프를 의미한다. 
  
  
• 가중치의 의미는 노드 사이의 이동에 드는 비용이나 두 노드 사이의 거리 등 경우에 따라 다르다.

  4) 완전 그래프(Complete Graph)

• 위와 같이 임의의 두 노드 사이에 반드시 하나의 간선이 존재하는 그래프를 의미한다. 
  
  
• 이 경우 간선의 갯수는 (노드의 갯수 * (노드의 갯수 - 1)) / 2 개가 된다. 

  5) 부분 그래프(SubGraph)

• 어떤 그래프 U 의 모든 노드와 간선이 다른 그래프 V 에 속한다고 할 때, 그래프 U는 그래프 V 의 부분 그래프이다.
  위 예시에서 그래프 B와 C는 모두 그래프 A의 부분그래프이다.
   
• 그래프 C와 같이 임의의 두 노드간의 관계가 그래프 A의 두 노드간의 관계와 동일한 부분 그래프를 유도 부분
  그래프(Induced SubGraph) 라고 한다. 그래프 B의 경우 노드 3과 5의 연결관계가 그래프 A와 다르기 때문에
  그래프 A의 유도 부분 그래프가 아니다.
  
  
• 그래프 B와 같이 노드의 집합(Node Set)이 그래프 A와 동일한 부분 그래프를 신장 부분 그래프(Spanning
  SubGraph) 라고 한다. 그래프 C의 경우 노드 0이 빠져있기 때문에 그래프 A의 신장 부분 그래프가 아니다.

  6) 유향 비순환 그래프(Directed Acyclic Graph)

• 위와 같이 유향 그래프 중에서도 한번 지나친 노드를 다시 방문할 수 없는, 즉 순환(Cycle)이 존재하지 않는
  유향 그래프를 유향 비순환 그래프(DAG)라고 한다.  위상 정렬이 존재하는 그래프라고 생각하면 편하다.
  
  
• 선후 관계가 정의된 데이터를 그래프화 하여 표현하기에 좋다.  대표적인 예시로 스프레드 시트에서 셀 간의
  참조관계를 표현하는데 활용할 수 있다.

3. 그래프의 표현

 그래프를 표현하는 두 가지 대표적인 방법을 알아본다.  여기서는 무향 그래프를 기준으로 설명한다.

  1) 인접 행렬

• 위와 같이 노드간의 연결관계를 행렬로 나타내는 방식이다.  mat[i][j] = 1이라면 노드 i와 j가 연결되어있음을,
  0이라면 연결되어있지 않음을 의미한다.  가중 그래프를 나타낼 경우 1 대신 가중치를 사용하면 된다.
  
  
• 예시와 같이 무향 그래프일 경우에 한해서 인접행렬은 대각 성분을 기준으로 대칭을 이루는 성질을 가진다.
  
  
• 구현이 간단하고 임의의 두 노드간의 연결여부를 확인에 O(1) 의 시간복잡도를 보인다는 장점이 있다.
• 특정 노드와 연결된 모든 노드를 탐색하기 위해 반드시 노드의 총 갯수만큼의 탐색이 필요하다는 단점이 있다.
  노드 갯수가 V인 그래프에서 한 노드에 연결된 노드를 탐색하는데 O(V)의 시간복잡도를 보인다.
  
  
• 위의 특성으로 인해 노드 갯수에 비해 간선의 갯수가 적은 희소 그래프(Sparse Graph)일 경우 메모리와 시간낭비가
  심해진다.

  2) 인접 리스트

• 위와 같이 노드간의 연결관계를 각 노드에 연결된 노드들의 리스트로 나타내는 방식이다.  가중 그래프를 나타낼
  경우 노드 번호와 가중치를 함께 리스트의 요소로 넣어주면 된다.
  
  
• 한 노드에 연결된 모든 노드를 탐색하기 위해 그 노드에 연결된 노드의 갯수만큼의 탐색만이 필요하며
  간선의 갯수만큼의 메모리만 차지하기 때문에 메모리와 시간을 절약 가능하다는 장점이 있다.
  
  
• 임의의 두 노드 u, v 간의 연결 여부를 알기 위해 list[u] 또는 list[v] 의 길이만큼의 탐색이 필요하다는 단점이 있다.

1. common 앱

 로그인/로그아웃과 같이 다른 여러 앱들에도 공통적으로 적용되어야하는 기능들은 하나의 앱에 종속되지 않도록

분리하는 것이 좋다. 여기서는 이러한 공통 기능들은 common 이라는 앱을 생성하여 그 안에 구현하기로 한다.

pybo 앱을 처음 만들었을 때 처럼 터미널에서 django-admin startapp 명령어를 실행하여 common 앱을 만든다.

그 다음 config/settings.py 에서 pybo 앱을 만들었을 때 처럼 앱을 등록해준다.

pybo의 url 매핑을 등록했을 때 처럼 common 앱의 url 매핑 파일도 config/urls.py 에 등록해준다.

마지막으로 common 앱에 실제로 urls.py 를 생성하여 위와같이 작성해주면 common 앱의 설정이 완료되었다.

아직 common 내부에 구현한 기능이 없기에 url 패턴 리스트는 비어있는 상태이다.

2. 로그인 화면

 본격적인 로그인 기능을 구현하기 위해서는 먼저 로그인 화면이 필요하다. 

네비게이션 바를 추가했을 때 만들었던 로그인 링크를 위와 같이 수정한다.

그리고 common 앱의 urls.py 에 위와 같이 실제로 login 에 해당하는 매핑을 추가해준다.  로그인 뷰는 별도로 만들

필요 없이 django.contrib.auth 의 LoginView 를 사용한다. 

3. 로그인 템플릿 구현

 지금 상태에서 로그인 페이지에 접속하려하면 login.html 템플릿이존재하지 않는다는 오류가 발생한다.  로그인 화면을

띄우기 위해 호출되는 LoginView는 registration 이라는 디렉토리에서 login.html 파일을 찾기 때문에 이 login.html

파일을 구현해줄 필요가 있다.  다만 여기서는 로그인 기능을 common 앱 내에 구현할 것이기 때문에 login.html

파일을 registration 이 아닌 templates/common 디렉토리에 만들 것이다.

먼저 common 앱의 urls.py 를 위와 같이 수정하여 LoginView 가 registration 이 아닌 common앱의 템플릿 디렉토리를

참조하도록 한다.

그리고 templates 디렉토리에 common 디렉토리를 생성하고 그 안에 login.html을 위와 같이 작성한다. 

마지막으로 login.html에서 include 된 form_errors.html 을 templates 디렉토리의 하위에 위와 같이 작성해준다.

4. 로그인 실행

여기까지 완료했으면 로그인 기능 자체는 구현이 완료되었다.  pybo 에 접속하여 실제로 로그인을 실행해보자.

먼저 로그인 링크를 클릭하면 이제 로그인 화면을 볼 수 있다.  아직까지 로그인 가능한 계정은 슈퍼유저로 등록했던

계정 뿐이다.  슈퍼유저로 로그인을 시도해보자.

base_url/accounts/profile/ 페이지를 찾을 수 없다는 404 에러가 발생한다.  이는 django.contrib.auth 패키지를 사용하여

로그인 기능 구현 시, 로그인이 성공하면 디폴트로 위 url로 이동하기 때문에 발생하는 문제이다. 

config/settings.py 의 마지막 줄에 LOGIN_REDIRECTED_URL 로 '/' 를 지정해주면 로그인 이후 자동으로 base_url/ 로

이동하게 된다. 

마지막으로 config/urls.py 를 위와 같이 수정하여 base_url/ 요청시 pybo/views.py의  index 함수가 호출되도록 매핑을

추가한다. 

이제 로그인 후 정상적으로 게시판 화면으로 이동하는 것을 확인할 수 있다.  그러나 로그인을 했는데도 로그인 링크가

여전히 존재하는 것을 확인할 수 있다.  다음은 로그아웃을 구현하여 이를 해결할 차례이다.

5. 로그아웃 

 먼저 내비게이션 바의 템플릿 코드를 로그인한 경우 로그인 버튼 대신 로그아웃 버튼이 나타나도록 수정해야한다.

위와 같이 user.is_authenticated 를 사용하여 로그인 상태인지를 판별, 로그인 되어있다면 로그인 대신 로그아웃 링크를

표시하도록 내비게이션 바의 템플릿을 수정한다.

물론 common 앱의 urls.py 에도 logout 에 해당하는 url 매핑을 정의해준다.  로그아웃 기능에 별도의 화면이 필요하진

않기 때문에 로그인 구현과 같이 템플릿 경로 수정등의 작업은 필요하지 않다.

마지막으로 config/settings.py 에 로그아웃 리다이렉트 url도 추가해주면 로그아웃의 구현도 끝이다.

6. 테스트

로그인 전의 페이지이다. 로그인 링크가 표시되고있음을 확인 가능하다.

로그인 화면이다.  슈퍼계정을 사용하여 로그인을 시도해본다.

로그인이 성공하자 첫 페이지로 리다이렉트되며 로그인 링크 대신 로그아웃 링크가 표시되는 것을 확인할 수 있다.

로그아웃 링크를 클릭하면 다시 첫 페이지로 리다이렉트되며 다시 로그인 링크가 표시되는 것을 볼 수 있다.

이제 pybo 에는 로그인/로그아웃 기능이 성공적으로 구현되었다.  

이번에는 게시글 리스트에서 게시글 제목의 우측에 게시글에 달린 답글의 갯수를 표시해주는 기능을 추가해보자.

question_list.html 의 게시물 제목을 출력하는 코드 아래에 만약 question.answer_set 에 들어있는 답글의 갯수가 1개

이상이라면 그 갯수를 출력하도록 코드를 추가해준다.

간단하게 답글 갯수 표시 기능이 추가된 것을 확인할 수 있다.