오늘 한 일 (회고)

• tryhelloworld 에서 swift 강의를 들었다. 강의가 너무 어려워서 그런걸까? 아직 크게 재미를 느끼지 못했다.
• 바이너리 서치를 재귀적으로 리팩토링하려고 여러번 시도했지만 실패했다. 재귀함수! 넘어야 할 벽이다. 선생님 말처럼 외워버리고 유사한 문제를 많이 풀어봐야겠다. 전에 알고리즘 문제 풀 때 재귀적으로 해결한 다른 사람 풀이가 있었는데 다시 찾아봐야겠다.
  • 하노이 타워
  • 팩토리얼
  • 피보나치
  • 최대공약수
  • 최소공배수
  • 머지소트, 퀵소트
  • 바이너리 서치

    기본적으로 트리나 그래프의 순회나 정렬기법 등이 있겠고.. 점화식으로 표현된 수열은 모두 재귀적으로 표현가능합니다. 이항계수. 파스칼 삼각형. 행렬연산 등 모두 재귀적으로 표현됩니다. 또한 대부분의 반복문도 재귀로 대체가 가능하고요. 간단한예로 1부터 n까지합이나 구구단출력 모두 재귀적으로 가능합니다.

  • 참고글
• 영어공부 게시판에 사진 업로드 기능을 추가했다.

내일 할 일

• 컴퓨터공학 입문 수업 듣기

패스트캠퍼스 컴퓨터공학 입문 수업을 듣고 중요한 내용을 정리했습니다. 개인공부 후 자료를 남기기 위한 목적임으로 내용 상에 오류가 있을 수 있습니다.

바이너리 서치 - 이진탐색 (binary search)

• BigO : O(log N)
• 정렬된 자료를 반으로 나누어 탐색하는 방법
• 주의점 : 자료는 오름차순 으로 정렬된 자료여야 한다.
• 이진트리, 바이너리서치는 코딩 인터뷰 단골문제
• 퍼포먼스가 아주 좋고 구현하는 중에 dynamic programming, recursion을 볼 수 있다.

특징

• linear search (순차검색) : 순서대로 찾는다. 성능평가시 비교대상으로 사용한다.
• linear search는 정렬 방식이 상관 없다.
• binary search (이진탐색) : 반드시 정렬된 상태에서 시작해야한다. 로그실행시간을 보장한다.
• 참고로 insert sort (삽입정렬), bubble sort, selection sort는 O(n^2)의 성능을 갖고 있다. (참고)

구현을 위한 준비

• target : 찾고자 하는 값
• data : 오름차순으로 정렬된 list
• start : data 의 처음 값 인덱스
• end : data 의 마지막 값 인덱스
• mid : start, end 의 중간 인덱스

구현 개요

• 자료의 중간 값이 (mid) 찾고자 하는 값인지 검사
• 아니라면 대소관계를 비교하여 start, end 값 이동
• 동일 연산 반복 (재귀로 구현 가능)

바이너리 서치 구현 (python)

# 바이너리 서치
# data 중에서 target 을 검색하여 index 값을 return 한다.
# 없으면 None을 return한다.

def binary_search(target, data):
    data.sort()
    start = 0
    end = len(data) - 1

    while start <= end:
        mid = (start + end) // 2

        if data[mid] == target:
            return mid # 함수를 끝내버린다.
        elif data[mid] < target:
            start = mid + 1
        else:
            end = mid -1

    return None

# 테스트용 코드
if __name__ == "__main__":
  li = [i**2 for i in range(11)]
  target = 9
  idx = binary_search(target, li)

  if idx:
      print(li[idx])
  else:
      print("찾으시는 타겟 {}가 없습니다".format(target))

바이너리 서치 재귀적 구현 (python)

# data는 오름차순으로 정렬된 리스트
def binary_search_recursion(target, start, end, data):
    if start > end:
        return None

    mid = (start + end) // 2

    if data[mid] == target:
        return mid
    elif data[mid] > target:
        end = mid - 1
    else:
        start = mid + 1        

    return binary_search_recursion(target, start, end, data)

# 테스트용 코드
if __name__ == '__main__':
    li = [i*3 for i in range(11)]
    target = 6
    idx = binary_search_recursion(target, 0, 10, li)

    print(li)
    print(idx)

바이너리 서치 Big-0

• 참고자료
• 우선, 이진 탐색을 반복할수록 남아있는 (탐색할) 자료의 개수는 1/2로 줄어든다.
• 1번째 실행시 탐색할 남은 자료의 개수: N
• 2번째 실행시 탐색할 남은 자료의 개수: N/2
• 3번째 실행시 탐색할 남은 자료의 개수: N/2 * 1/2
• 4번째 실행시 탐색할 남은 자료의 개수: N/2 * 1/2 * 1/2
• K번째 실행시 탐색할 남은 자료의 개수: N*(1/2)^K
• 탐색이 끝나는 시점에는 남은 자료의 개수가 1이 되어야 한다. 따라서 N*(1/2)^K = 1
• 양 변에 2^K를 곱해주면 2^K = N > K = log2^N
• K의 의미는 실행횟수 따라서 자료의 갯수 N에 따른 시행횟수는 log2^N
  시간 복잡도는 BigO 표기법으로 O(logN) 으로 나타낼 수 있다.

참고자료

• 수업자료 - 바이너리서치
• 생활코딩 자료구조
• 인프런 알고리즘 강좌
• 참고강의 - Binary Search Tree

추가적으로 공부한 자료를 정리합니다.

바이너리 서치트리

• 자신의 값보다 작은 값은 왼쪽 자식 노드로, 자신의 값보다 큰 값은 오른쪽 자식 노드에 위치한다.

Node

• 트리는 노드의 구성체, 노드가 연결되어 트리가 된다.

class Node:
	def __init__(self, item):
		self.val = item
		self.left = None
		self.right = None

참고자료

• 바이너리 서치트리

패스트캠퍼스 컴퓨터공학 입문 수업을 듣고 중요한 내용을 정리했습니다. 개인공부 후 자료를 남기기 위한 목적임으로 내용 상에 오류가 있을 수 있습니다.

재귀함수 (recursion)

• 함수 정의 내에 같은 이름의 함수가 올 때 이를 재귀함수라 부른다.
• 반드시 탈출조건이 있어야 stack overflow를 방지할 수 있다.
• 같은 행위가 반복될 때 재귀함수를 사용한다.

예시 - 순차탐색

def search(li, begin, end, target):
    if begin>end:
        return -1
    elif target == li[begin]:
        return begin
    else:
        return search(li, begin+1, end, target)

li = [1,6,10,7,2,5]
target = 10
search(li, 0, 5, 10) # 2

예시 - 2진수 변환

def print_binary(n):
    if n<2:
        print(n, end='')
    else:
        print_binary(n//2)
        print(n%2,end='')

print_binary(15) #1111		

예시 - 배열의 합

• li[0]에서 li[n-1] 까지의 합을 구하여 리턴
• 재귀적 사고방식: li[n-1] + (li[n-2] 까지의 합) 을 구한다

def sum(n, li):
    if n<=0 or n >= len(li):
        return 0
    return li[n-1] + sum(n-1, li)

예시 - 0~n 까지의 합계 구하기

def sum(n): # 이 함수의 목표는 0~n 까지의 합을 구하는 것이다
    if n == 0: # n=0 이면 합은 0이다
        return 0
    return n + sum(n-1) # n이 0보다 크면 0에서 n 까지의 합은, n-1까지의 합에 n을 더한 것이다.

sum(4) # 10

예시 - 1~n 까지의 곱 구하기

def factorial(n):
    if n == 0:
        return 1
    return n * factorial(n-1)

factorial(4)

예시 - x^n 구현

def power(x, n):
    if n == 0:
        return 1
    return x * power(x, n-1)

power(2,10) # 1024

예시 - 피보나치 수열

# 피보나치 수열의 index n의 값을 리턴
# 피보나치 수열 : 1, 1, 2, 3, 5, 8, 13, 21, 34 ...
def fibo(n):
    # 재귀함수는 탈출조건이 꼭 필요하다.
    if n == 0 or n == 1:
        return 1
    return fibo(n-2) + fibo(n-1)

# index n까지의 피보나치 수열 구하기
def fibo_list(n):
    for i in range(n):
        print(fibo(i), end= " ")

예시 - 최대공약수 (유클리드 호제법)

• 참고: 두수의 곱을 최대공약수로 나누면 최소공배수가된다.

def gcd(m, n):
    if m < n:
        m, n = n, m
    if m % n == 0:
        return n
    else:
        return gcd(n, m%n)

print(gcd(48, 60)) # 12

예시 - 하노이 타워

• 참고
• A에 있는 n개의 원반 중 맨 아래에 있는 n번째 원반을 제외한 나머지 원반을 모두 B로 옮긴다.
• A에 남은 하나의 원반을 C로 옮긴다.
• B의 모든 원반을 C로 옮긴다.

def hanoi(num, _from, _by, _to):
    #탈출 조건
    if num == 1:
        print("{}에서 {}로 {} 번째 원반 이동".format(_from, _to, num))
        return

    hanoi(num-1, _from, _to, _by)
    print("{}에서 {}로 {} 번째 원반 이동".format(_from, _to, num))
    hanoi(num-1, _by, _from, _to)

if __name__ == "__main__":
    while 1:
        numOfTray = int(input("원반의 개수를 입력하세요!(종료 : 0) :"))
        if numOfTray == 0:
            break
        hanoi(numOfTray, 'A', 'B', 'C')

참고자료

• 인프런 - 알고리즘강좌
• 하노이타워
• 생활코딩 자료구조

오늘 한 일 (회고)

• tryhelloworld 에서 swift 강의듣기
• ibooks swift 원서읽기

내일 할 일

• 과제 : 바이너리 서치를 재귀적으로 리팩토링

패스트캠퍼스 컴퓨터공학 입문 수업을 듣고 중요한 내용을 정리했습니다. 개인공부 후 자료를 남기기 위한 목적임으로 내용 상에 오류가 있을 수 있습니다.

multithreading

• 프로세스 : 현재 실행중인 프로그램 (RAM에 올라와있다.)
• 프로그램은 하나지만 프로세스는 여러개를 띄울 수 있다 (메모장 여러개 띄우기) 그리고 각각 가상 주소공간을 할당받는다. (모든 프로세스는 각각 4G의 가상 주소 공간 (메모리공간X) 을 부여받는다. (code, data, heap, stack)
• 쓰레드(thread) : 프로세스에 시간이라는 개념을 추가, 프로세스에서의 실행 흐름
• 싱글스레드 (single thread) : 시간이 흐르면서 실행되는 코드의 줄기가 하나 (코드를 위에서부터 한줄한줄 해석)
• 멀티스레드 (multi thread) : 동시에 여러개의 코드를 실행 (A코드 1번줄, B코드 1번줄 … 5ms 마다 반복)
• 컴퓨터의 cpu는 한 쓰레드 밖에 처리하지 못하지만 빠르게 진행되기 때문에 사람 눈에는 동시처럼 보인다.
• 멀티쓰레드는 순서가 없다.
• 싱글쓰레드보다 멀티쓰레드가 빠르다 (하지만 크게 차이나지는 않는다.)

context switching

• 각 스레드마다 데이터 저장공간을 따로 마련하고, cpu안의 register 정보를 해당 저장공간에 저장한다.
• 프로세스는 독립적인 메모리공간을 갖기 때문에 서로 통신하려면 IPC를 통해야 한다.
• 프로세스가 여러개가 병렬적으로 실행(멀티스레드)되기 위해서는 독립적인 메모리 공간으로 컨텍스트 스위칭이 발생한다.

메모리공간에서의 스레드

• 쓰레드는 프로세스의 heap, static, code 영역을 공유한다.
• 각각의 프로세스가 독립적인 stack, heap, code, data 영역을 가진 반면에, 한 프로세스에 속한 쓰레드는 stack 영역을 제외한 메모리 영역은 공유한다.
• 각 쓰레드간에 IPC 없이도 통신이 가능하다. (프로세스 간의 통신보다 스레드 간의 통신 비용이 적다) (스레드 간의 통신시 데이터를 주고받는 방법은 메모리 공간을 공유하므로 데이터 세그먼트, 즉 전역 변수를 이용하여 규현한다.)
• 쓰레드는 공유하고 있는 메모리 영역 덕분에 컨텍스트 스위칭 때문에 발생하는 오버헤드(overhead)가 프로세스에 비해 적다.
• 멀티 스레드로 작업을 실행하는 경우, 프로세스를 생성하여 자원을 할당하는 시스템 콜이 줄어들어 자원을 효율적으로 관리할 수 있다.

race condition, mutual exclusion

• 경합조건 (race condition) : 다중 프로그래밍 시스템이나 다중 처리기 시스템에서 두 명령어가 동시에 같은 기억 장소를 액세스할 때 그들 사이의 경쟁에 의해 수행 결과를 예측할 수 없게 되는 것.
• 상호배제 (mutual exclusion) : 여러 개의 병렬 프로세스가 공통의 변수 또는 자원에 접근할 때 그 조작을 정당하게 실행하기 위하여 접근 중인 임의의 시점에서 하나의 프로세스만이 그 접근을 허용하도록 제어하는 것.

참고

• 프로세스와 스레드의 차이
• 메모리 관점에서 본 쓰레드(thread)