2019.07.13 Tree

(TIL은 스스로 이해한 것을 바탕으로 정리한 것으로 오류가 있을 수 있습니다)

# 질문에 답하기

  1. 트리

스크린샷 2019-07-04 오후 3 16 21
  1. 어떤 노드 간에 경로가 존재해야 한다.( 즉 연결이 되어 있어야 한다) - connected
  2. 단 사이클이 없어야 한다 - acyclic
  3. set안에 tree와 tree가 있으면 forest이다
  4. 루트 노드가 없어지면 각각 분리집합으로 분할 가능

트리 용어

스크린샷 2019-07-04 오후 3 22 11
  • 레벨와 트리의 높이가 같다고 하면 한쪽으로 굉장히 치우진 것과 같다.
스크린샷 2019-07-04 오후 3 22 32

엣지와 노드와의 관계

이진트리

03C0592B-1945-4C29-BBCD-166E54B1B86E

이진트리의 특징

7E694D61-757A-46E8-B196-4A44EC01CEB2

완전 이진 트리

F8B61E1B-FD5A-4DE9-958B-A1D4DC04B71F

추가 공부할 사항

  • 포화 이진 트리
  • 편향 이진 트리

이진트리의 순회

  1. 스텍기반
    1. 전회순회
    2. 중위순회
    3. 후위순회
  2. 큐 기반
    1. 레벨 순회

전위순회(pre order)

8E201DED-3874-4ED4-BBB1-A5EC78ED01DC
class TreeNode:
    def __init__(self, data):
        self.data=data
        self.left=None
        self.right=None

def preorder(node):
    #base case
    if not node:
        return

    #노드를 방문했다고 치고 print로 찍어봄 실제로는 오퍼레이션을 넣고 방문할 떄 마다 실행
    print(node.data, end = "  ")
    # 왼쪽 자식
    preorder(node.left)
    # 오른쪽 자식
    preorder(node.right)

if __name__ == "__main__":
    n1 = TreeNode(1)
    n2 = TreeNode(2)
    n3 = TreeNode(3)
    n4 = TreeNode(4)
    n5 = TreeNode(5)
    n6 = TreeNode(6)
    n7 = TreeNode(7)

    n1.left = n2
    n1.right = n3
    n2.left = n4
    n2.right = n5
    n3.left = n6
    n3.right = n7

    preorder(n1)

중위순회(in order)

스크린샷 2019-07-04 오후 4 00 40

def preorder(node):
    #base case
    if not node:
        return


    # 왼쪽 자식
    preorder(node.left)

     #노드를 방문했다고 치고 print로 찍어봄 실제로는 오퍼레이션을         넣고 방문할 떄 마다 실행
    print(node.data, end = "  ")

    # 오른쪽 자식
    preorder(node.right)

후위순회 (post order)

스크린샷 2019-07-13 오전 9 38 25

def preorder(node):
    #base case
    if not node:
        return


    # 왼쪽 자식
    preorder(node.left)

    # 오른쪽 자식
    preorder(node.right)

     #노드를 방문했다고 치고 print로 찍어봄 실제로는 오퍼레이션을         넣고 방문할 떄 마다 실행
    print(node.data, end = "  ")

2019.07.13 TIL

(TIL은 스스로 이해한 것을 바탕으로 정리한 것으로 오류가 있을 수 있습니다)

# 질문에 답하기

  1. 자료구조

  2. 자료구조는 데이터베이스에 어떻게 데이터를 담을 것인지에 대한 이론이다.

  3. 서버 개발자로서 굉장히 중요한 부분이다.

1. 전체적인 흐름

  1. 동적배열(Dynamic array) vs 연결리스트(linked list)
    1. insert, delete, search에 따라서 효율이 다름
  2. BST(array list와 linked list의 단점 보완)
    1. insert, delete, search 모두 O(log(n))
    2. 트리의 깊이가 깊어지면 문제 발생
  3. 레드블랙트리(red black tree)
    1. self-balancing 기능이 생기면서 BST문제 해결
  4. B-Tree
    1. 캐시기능 추가 보완
  5. B+Tree

동적배열 vs 연결리스트

스크린샷 2019-07-13 오전 9 04 25
  1. 동적배열(파이썬에서는 list가 동적배열이다 - 따라서 append와 pop은 O(1) )
    1. 장점 : search - (O(1) : 인덱싱때문에)
    2. 단점 : Insert, delete : O(n) - 최악의 경우는 제일 앞에 것을 지우고, 삭제할 때이다. 하나씩 다 옴겨줘야 한다.
    3. 할당되어 있는 전체 크기가 capacity라고 하는데, 만약 특정 위치에 값을 넣거나 삭제하려고 하면 자리를 계속 옴겨야 한다.
    4. 만약에 capacity가 꽉 찼는데 append해야 한다면 amortized analysis (분할 상환 분석-뒤에서 참고)
    5. 예) 파이썬의 list
  2. 연결리스트
    1. 장점 : insert, delete : O(1)
    2. 단점 : search : O(n)
    3. 예) 더미 더블링크드 리스트
  3. 만약에 쓴다고 하면 동적배열을 써야 한다. 정말 배열이 붙어있어서 지역성으로 캐시가 발생할 확률이 높다. 하드웨어의 이점을 받을 수 있다.
  4. 이거 2개를 보완해주는게 BST이다.

BST(이진탐색트리)

BBC3A0EB-8974-4B56-9491-890B65AA0023
  • 이진탐색트리
  • 루트를 기준으로 왼쪽에는 항상 더 작은 자료가 위치하고 오른쪽에는 더 큰 자료가 위치한다.
  • *insert, delete, search 모두 O(log(n))
  • 아무리 많이 해도 트리의 높이(height of tree)만큼만 하면 된다.log(n)
  • 트리에 있는 것은 파이썬에서 key값이라고 볼 수 있다.
    • dictionary이고 a collection of pairs(key, item)
    • 해당 key에 item을 참조하게만 해놓으면 문제해결

BST를 공부하기 위해서 기본적으로 Tree에 대해서 알아야 한다. Tree의 search, delete, insert에 대해서 공부해야 한다.

redblack tree

참고 : RedBlack Tree에 대해

스크린샷 2019-07-13 오전 9 20 52
  • 7,6,5,4,3,2,1 순서대로 삽입해서 이진탐색 트리(Binary Search Tree)를 만들어 보면 위의 그림과 같이 한쪽으로 치우처진 tree가 완성된다.

1을 찾으려고 한다면?

  • 항상 트리의 높이만큼 시간이 필요하다. 그렇다면 이진탐색 트리(Binary Search Tree)를 사용하는 이유가 없다.
  • 이러한 문제점을 해결하기 위해 나온 자료구조가 Balanced binary search tree의 한 종류인 RedBlack Tree이다.
스크린샷 2019-07-13 오전 9 23 11
  • 각 노드에 색깔을 저장하는 공간을 추가하여 색깔을 기준으로 균형을 맞추는 트리이다.

자세한 사항은 또 뒤에서 redblack tree만 다루어보자.

B TREE

참고 : B-Tree 개념 정리 | Jlog

  • 기존에 tree에서 할 수 없었던 캐시를(지역성) 추가하여 보완
스크린샷 2019-07-13 오전 9 25 41
  • 한 개의 노드에 여러개의 데이터가 들어갈 수 있다.
  • 지역성 문제를 해결하여 훨씬 효율을 높였다.

자세한 사항은 B tree만 다룬다.

추가

분할 상환 분석(Amortized analysis)

  • 등장배경: 우리가 짜는 함수의 경우는 빅오를 구하기에 굉장히 애매한 경우가 많다. 따라서 대략적으로 빅오를 구하는 방법
  • DA(동적배열)에서 append를 할때 메모리(capacity)가 꽉 찬 경우
  • 메모리(heap)을 돌아다니면서 가능한 공간을 찾아다닌다. 가능한 위치를 찾아서 복사해서 넣게 되면 최소한 O(n)
  • heap이 linked list로 구성되어 있다.
  • 해결방안
    • 우리가 아는 데이터의 갯수가 200개이면 키자마자 250개를 잡아 놓는다.
      • 만약에 3개만 쓰게 되면 굉장히 비효율적이다.
    • 한 개씩 늘리면서 모든 공간이 다 차게 되면 크기를 X2 한다.
  • 가끔 한번씩 O(n)이 필요한데 그만큼 하고 나몬 지속적으로 O(1)이 되므로 이정도는 그렇게 치자.
  • ex) 데이터의 갯수가 3개이면 4개면 된다.
  • 이렇게 하면 캐시히트와 인덱싱을 유지할 수 있다.
  • heap안에 찾아다니면서 2배 크기가 가능한 곳을 찾아다니는 것이다.

2019.04.12 TIL

(TIL은 스스로 이해한 것을 바탕으로 정리한 것으로 오류가 있을 수 있습니다)

# 질문에 답하기

  1. 자료구조

자료구조에 대한 정의는 너무나도 많다.
그 중에 가장 마음에 와닿는 글이 있어서 정리를 해본다.

" 프로그래밍은 결국 데이터를 다루는 방법입니다. 데이터를 입력받고, 데이터를 처리하여 도출된 데이터를 출력합니다.

자료구조는 데이터를 입력 받아 어떻게 저장하는 지에 대한 학문입니다.
데이터를 어떻게 저장하는지(입력), 어떻게 찾는지(탐색), 어떻게 지우는지(삭제)가
자료구조의 종류에 따라 천차만별입니다.

그럼, 어떤 자료구조를 언제 사용해야 할까요? 이는 결국 성능과 효율적인 메모리 사용에 달려있습니다.
프로그래머가 처한 상황에서 가장 뛰어난 성능을 내고 또 가장 효율적으로 메모를 사용한다면 그 자료구조를 선택하면 됩니다.

알고리즘은 방법론입니다. 많은 알고리즘이 있지만, 자료구조에 연관된 알고리즘만 언급하겠습니다.
자료구조와 알고리즘은 매우 밀접한 연관을 가지고 있습니다. 위에 언급한 삽입 정렬과 병합 정렬은 엄밀히 말해 알고리즘입니다. 하지만 자료구조를 배울 때 반드시 마주치게 되지요. 알고리즘은 자료구조를 구현하는 방법이라고 보시면 될 것 같습니다. "

“프로그래머가 갖추어야 할 ‘기본’은 무엇인가?” 넥슨 개발자 컨퍼런스(NDC) 참관 후기 | 패스트캠퍼스

자료구조의 구성

  1. insert : 어떻게 데이터를 넣을 것인가?
  2. search : 어떻게 데이터를 찾을 것인가?
  3. delete : 어떻게 데이터를 삭제할 것인가?

자료구조의 분류

자료구조
  • 단순구조 : 프로그래밍에서 사용되는 기본 데이터 타입
  • 선형구조 : 저장되는 자료의 전후관계가 1:1 (리스트, 스택, 큐 등)
  • 비선형구조 : 데이터 항목 사이의 관계가 1:n 또는 n:m (트리, 그래프 등)
  • 파일구조 : 서로 관련된 필드들로 구성된 레코드의 집합인 파일에 대한 자료구조
  • 출처 : 강의노트 17. 알고리즘, 자료구조 개요 · 초보몽키의 개발공부로그

선형구조(배열과 linked list 그리고 스택과 큐)

  1. 배열(array)
    1. 같은 자료형의 변수를 모아 놓은 것
    2. 인덱싱 활용 가능(search)
      1. 검색으로 배열을 이길 수는 없다.
    3. 데이터가 군집화 되어있다.
      1. 캐시히트의 가능성이 높다.
    4. 검색속도가 그 어떤 자료구조보다 빠르다.O(1)
    5. 데이터의 삽입과 삭제가 느리다. 최악의 경우 O(n)
      1. 맨 앞에 데이터를 삽입하게 되면 모든 데이터를 복사해서 한칸씩 다 옴겨야 한다.
      2. 배열은 공백을 인정하지 않는다. O(n)
  2. Linked list ( 데이터의 삽입과 삭제가 많고, 검색이 별로 없을 때)
    1. 검색 속도 최악 O(n)
    2. 데이터의 삽입과 삭제는 O(1)
      1. 어디든 데이터를 놓고 연결만 해주면 된다.
    3. 데이터가 흩어져 있다.
      1. 캐시히트의 가능성이 굉장히 떨어진다. -> 캐시미스 발생
      2. 페이지폴트까지 날수도 있다.
    4. 미리 힙을 주고 흩어져 있는 문제를 해결할 수 있다.
      1. 다이나믹 힙
  3. Stack
    1. 무언가를 쌓는다라는 의미를 가진 자료구조이다.
    2. LIFO(Last in, First out) : 후입선출
  4. Queue
    1. 우리의 일반적인 줄서기
    2. FIFO(First in, First out) : 선입선출

만약에 배열과 Linked list 2개 다 사용가능한 상황이면 무조건 배열을 쓴다.
배열은 메모리의 스택에 할당해서 사용한다.

파이썬에서의 list

파이썬의 list는 배열과 다르다.
파이썬은 포인터 배열이다.
포인터는 배열처럼 일렬로 되어 있으나, [1,2,3]
1은 class int 여서 상수객체이기 때문에 4바이트보다 훨씬 크다.

파이썬의 리스트는 파이썬에서는 같은 자료형의 변수를 모아 놓은 것이 아니다.
파이썬에는 배열이라는 자료구조가 없는 것이다. 즉 지원하지 않는다.

예시

얕은 복사

>>>    #얕은 복사
>>>    li = [1,2,3,4]
>>>    li3 = li.copy() # or copy.copy(li)도 가능
>>>    li3     #[1,2,3,4]
>>>    li3.append(5)
>>>    li3      #[1,2,3,4,5]
>>>    li       #[1,2,3,4]
>>>

위의 내용을 이해하기 위해서는 단순히 객체가 [1,2,3,4]의 형태처럼 메모리에 올라가 있다고 생각하면 안된다.
실제적으로 파이썬에서 list를 생성한다고 하더라도 모두 모여서 메모리에 올라가지 않는다. [* , * , * , * ]와 같은 형태로 생성되어 첫번째 * 은 1을 가르키고 두 번째 * 은 2를 가르키고 이런 형식이다. 얕은 복사는 [* , * , * , * ]를 복사해 온 것이다. 따라서 li3는 li의 [* , * , * , * ]를 복사해온 것이다. 따라서 li3에서 append를 통해 새로운 요소를 추가하게 되면 li3의 [* , * , * , * ]가 [* , * , * , * , * ]가 되어서 마지막 * 가 새로운 요소를 가르키게 된다. 따라서 li3가 변경되더라도 li는 변경되지 않는다.
하지만 여기에서도 예외는 있다.

>>>    #얕은 복사
>>>    li = [1,2,3,[4,5]]
>>>    li3 = li.copy()
>>>    li3    #[1,2,3,[4,5]]
>>>    li3[3].append(6)
>>>    li3    # [1,2,3,[4,5,6]]
>>>    li     # [1,2,3,[4,5,6]]
>>>

위에서 보면 알 수 있듯이 원래 얕은 복사에서라면 li3를 바꾼다고 해서 li가 바뀌어서는 안된다. 하지만 li는 변경되었다. 그렇다면 li3는 왜 변경되었을까? 위에 언급한대로 li3는 li의 [* , * , * , * ]를 복사해 온 것이다. 위에 예시에서 마지막 * 은 3번째 인덱스 [4,5]을 가르키고 있다. li3와 li 모두 [4,5]을 가르키고 있는 것이다. 따라서 li3를 통해 [4,5]를 변경하게 되면 마지막 *가 가르키는 것이 변경되는 것이므로 li 역시 변경되게 된다.(즉 li와 li3의 내부리스트는 각은 객체를 참조하기 떄문이다.)

이러한 것을 맡기 위해서는 깊은 복사가 필요하다.

깊은 복사

>>>    import copy     #deepcopy를 위해서는 copy를 import 해주어야 한다.
>>>    li = [1,2,3,4]
>>>    li4 = copy.deepcopy(li)
>>>    li4        # [1,2,3,4]
>>>    li4.append(5)
>>>    li4        # [1,2,3,4,5]
>>>    li         # [1,2,3,4]
>>>    li = [1,2,3,[4,5]]
>>>    li4 = copy.deepcopy(li)
>>>    li4        # [1,2,3,[4,5]]
>>>    li4[3].append(6)
>>>    li4        # [1,2,3,[4,5,6]]
>>>    li         # [1,2,3,[4,5]]

깊은 복사를 통해서는 완전히 동일한 새로운 객체를 생성하는 것이므로 li4에 어떤 요소를 추가해도 li는 전혀 영향을 받지 않는다. 따라서 상황에 맡게 단순 객체 복사, 얕은 복사, 깊은 복사를 사용해야 한다.

참고 : 2019_03_23_TIL(깊은 복사 얕은 복사)

비선형구조

트리

  • connected acyclic graph
    • 사이클(순환)이 없는 연결된 그래프
    • 루트노드(root)를 반드시 가진다.
    • 트리를 구성하는 노드 간에 단순 경로가 반드시 존재한다.
      • 단순경로란 지나왔던 접점을 다시 지나지 않는 경로
      • 한 개의 노드에서 다른 한개의 노드를 선택하면 단순 경로가 항상 존재
    • 루트 노드를 제외한 나버지 노드들은 분리집합으로 분할이 가능하며 이 집합들은 각각 하나의 트리를 구성한다(재귀적 정의)

트리 용어 정리

자료구조 용어 정리

부모노드와 왼쪽 자식노드 , 오른쪽 자식노드로 나누어짐

  • 루트노드 : 뒤로 뒤집어서 보면 여기서부터 쭉 퍼져나가므로 root(뿌리) 노드이다. 트리의 시작점
  • 에지 : 노드를 연결하는 선
  • 리프노드 : 자식노드가 하나도 없는 노드
  • 인터널노드 : 자식노드가 하나라도 있는 노드
  • 차수 : 자식노드의 갯수
  • 트리의 차수 : 트리에 있는 노드들 중 최대 차수

이진 트리

이진트리
  • 어떤 노드의 자식 노드의 수가 최대 2개인 트리

이진 트리의 종류

C9E60ED9-D5EA-4E44-9157-265B242B2B4F
  • 포화 이진 트리
    • 모든 레벨이 꽉 차 있다.
    • 즉 모든 노드들의 2개의 자식노드를 가지고 있다.(리프노드 제외)
4E72888E-46D9-46B1-95B6-BE894FD21905
  • 완전 이진 트리
    • 트리의 노드가 위에서 아래로, 왼쪽에서 오른쪽으로 채워지는 트리
    • 가장 높은 레벨 단계에서 항상 왼쪽에서 오른쪽으로 채워져 있어야 한다.

트리의 순회는 다음 장에서 추가로 공부한다!

  • 순회란 트리의 모든 노드를 중복하지 않으면서 방문하는 것을 말하며, 데이터를 찾고, 저장하고, 삭제하는데 쓰인다.

2019.03.11 TIL

(TIL은 스스로 이해한 것을 바탕으로 정리한 것으로 오류가 있을 수 있습니다)

# 질문에 답하기

  1. linear_search

li라는 list에서 특정한 target의 인덱스를 찾으려면 어떻게 해야할까?
li = [ 5, 7, 2, 8, 3, 9, 1] 이라는 것에서
3이라는 target의 인덱스를 찾을 수 있는 함수를 구현해보자.

linear_search(li, target)--> idx
반환값은 target이 있다면 target의 인덱스
target이 없다면 None을 반환

def linear_search(li, target):
        for i in len(li):
            if li[i] == target:
                return i
        return None      # target이 없으면  None을 반환해라.

굉장히 간단한 함수이다. 하지만 함수의 성능을 보면 굉장히 비효율적으로 볼 수 있다.

알고리즘의 성능차이 비교 절대 시간을 비교 하면 안된다.
컴퓨터 성능이 차이나므로 상대 시간 : 어떤 알고리즘을 실행하는데 해비한 연산의 연산 횟수를 비교하자.
즉 데이터의 갯수에 따른 연산 횟수를 계산해서 성능을 계산하자

이 연산에 + - 등 보다는 그 알고리즘을 구성하는데 가장 헤비하게 미치는 연산은 for문이다.
일반적으로 for문 혹은 if문 비교 연산 if문을 많이 호출하면 느린거고 if문을 조금 호출하면 빠른 것이다.

또한 데이터가 늘어남에 따라 연산횟수가 얼마나 변화하는지를 비교해 봐야 한다.

성능을 평가할떄는 3가지 방법이 있다.

  1. 최선의 경우
  2. 평균의 경우 --> quick sort
  3. 최악의 경우 --> 알고리즘을 말할때는 항상 최악의 경우를 가정한다.
    • 이 알고리즘은 아무리 최악의 경우 몇회의 연산횟수를 보장한다.

성능 평가에 대해 조금 더 공부해보려고 한다.

What does T(n) mean in relation to O(n)?

When discussing an algorithm, the common usage of the symbol 𝑇T is to represent its time complexity.
𝑇T is a function. The input to this function is the input size, the output is the (worst-case) running time for an input of that size.
Therefore, 𝑇(𝑛)T(n) is a number: the number returned by the function 𝑇T when given the number 𝑛n. This number is the running time of our algorithm on an input of size 𝑛n.
The 𝑂O in "𝑂(𝑛)O(n)" is not a function. This is Big O notation. In particular, the symbol 𝑂(𝑛)O(n) represents the class of all functions that grow (asymptotically) at most as quickly as the linear function 𝑓(𝑛)=𝑛f(n)=n.
Big O notation gives us a convenient way to talk about upper bounds. For example, we can say "the time complexity of this algorithm is 𝑂(𝑛2)O(n2)" (formally: "𝑇∈𝑂(𝑛2)T∈O(n2)") to say that the running time of the algorithm is at most quadratic in the input size.
Sometimes, you can see both symbols being used in a single equation. For example, the time complexity of MergeSort is commonly described by the following recurrence: "𝑇(𝑛)=2𝑇(𝑛/2)+𝑂(𝑛)T(n)=2T(n/2)+O(n)".
The meaning of the above statement: For any 𝑛n, the time 𝑇(𝑛)T(n) needed to sort 𝑛n elements can be computed by taking the time 𝑇(𝑛/2)T(n/2) needed to sort 𝑛/2n/2 elements, multiplying that time by 2, and adding something extra. That something extra must be at most linear in 𝑛n.

What does T(n) mean in relation to O(n)? - Quora

해석 :

알고리즘을 논할 때, 기호 T의 일반적인 용도는 시간 복잡성을 나타내는 것이다.

T는 함수다. 이 함수에 대한 입력은 입력 크기, 출력은 해당 크기의 입력에 대한 (최악의) 실행 시간이다.

따라서, T(n)는 숫자다: n을 부여했을 때 T 함수가 반환하는 숫자다. 이 숫자는 크기 n의 입력에 대한 우리의 알고리즘의 실행시간이다.

"O(n)"의 O는 기능이 아니다. 이것은 Big O 표기법이다. 특히 기호 O(n)는 선형 함수 f(n)=n만큼 빠르게(증식적으로) 성장하는 모든 기능의 클래스를 나타낸다.

Big O 표기법은 우리에게 상위에 대해 이야기할 수 있는 편리한 방법을 제공한다. 예를 들어, 우리는 "이 알고리즘의 시간 복잡성은 O(n2)"(공식적으로 "TOO(n2))라고 말할 수 있다.

때때로, 당신은 하나의 방정식에 두 개의 기호가 사용되는 것을 볼 수 있다. 예를 들어, MergeSort의 시간 복잡성은 일반적으로 "T(n)=2T(n/2)+O(n)"에 의해 설명된다.

상기 문장의 의미 : 어떤 n에 대해서도 n 요소를 분류하는데 필요한 T(n/2)는 n/2 요소를 분류하는 데 필요한 시간을 취하고 그 시간을 2로 곱한 후, 어떤 것을 추가함으로써 계산할 수 있다. 그 어떤 특별한 것은 n에 가장 직선적일 것이다.

---->> T 함수는 함수에 대한 최악의 실행시간이다. T(n)은 숫자인데 n 크기에 대한 자료를 함수에 넣었을 때 걸리는 실행시간이다.

---->> 우리가 말하는 알고리즘의 성능이 어떤 것인지 T of N 을 항상 구할 수는 없으므로 big O를 구하는 것을 배운다.

binary_search

def binary_search(li, target):
    """
    binary_search(li, target)--> idx
    반환값은 target이 있다면 target의 인덱스
    target이 없다면 None을 반환
    """
binary search

binary_search는 기본적으로 들어오는 자료가 정렬이 되었다고 가정하고 시작한다.
이를 통해 우리는 정렬된 자료의 중간값과 target을 비교하고, target이 중간값보다 작다면
중간값 이후의 배열에는 신경쓰지 않고 중간값이 전의 값들로만 비교하겠다는 것이다.
이를 통해 우리는 for 문을 돌렸을 때보다 훨씬 좋은 성능의 알고리즘을 구현할 수 있다.
(실제로도 많이 쓰이는 알고리즘이다)

구현

def binary_search(li, target):
        start = 0       #(인덱스는 0부터 시작하므로)
        end = len(li) - 1       #(인덱스를 기준으로 해야함으로 1을 빼줘야 한다)
        while start <= end:
                mid = (start + end) // 2
                if li(mid) > target:
                    end = mid - 1
                elif li(mid) < target:
                    start = mid + 1
                else:
                    return mid   # 이러면 실제로 리턴 값에만 들어가게 되므로 시스템적으로 나오는 것은 없다. 따라서 꼭 print를 해서 화면에 나오게 해줘야 한다. or 이 함수를 다른 변수에 할당하고 그 변수를 print하도록 한다.
        return None

[
참고자료] (https://github.com/fabl1106/CS/blob/master/data_structure/binary_search/binary_search.pdf)

새롭게 알게 된 중요한 사실

def exam():
        return 1

exam() 

을 실행해보면 아무것도 나오지 않는다. 숫자 혹은 string을 적어도 마찬가지 이다.

여기서 중요하게 알아야 할 것은 return을 해주는 것은 그 함수에서 리턴 값을 거기에 할당해주는 것이기 때문에 화면에는 나타나지 않는다.
이것을 해결하기 위해서는 return 위에 print 를 적어 화면에 표시하고 싶은 것을 적고 아래에
return 만을 적어서 함수를 빠져나오게 하거나
exam()을 특정변수에 할당해주어서 ( a = exam() ) 그 변수를 print 하는 방법이 있다.

다시 방법을 적어보면

def exam():
        print(1)
        return
exam()        # 이렇게 하면 return 값은 None이 반환된다. 따라서 상황에 따라 return 뒤에 1을 적어줘야 한다.

혹은

def exam():
        return 1

a = exam()
print(a)     #print를 해주어야 한다. 정 위와 같이 해주고 싶다고 하면 exam() 앞에 print를 해주면 된다.

def exam():
        return 1
print(exam())

+ Recent posts