IT 업계에서 근무하면서 느끼는 건 개발자 수준에 따라 같은 문제를 참 다양한 방식으로 푼다는 것이다. 내가 풀었을 때는 수행시간이 3분인데, 또 내 선임이 손 대면 3초로 끝나는 마법!

왜 그러는 것일까? 그냥 내가 단순 무식하게 빨리 일을 끝내려고 해서 그런건 아니였을까?

피보나치 수열을 다양한 방식을 적용하여 풀어보고 수행시간 변화를 확인해 보자.

피보나치 수열이란?

고등학교 1학년 수학시간에 배우는 피보나치 수열은 너무나 유명한 '수'이다.

제 0항을 0으로, 제 1항을 1로 두고, 둘째 번 항부터는 바로 앞의 두 수를 더한 수로 놓는다. 이를 점화식 형태로 표현하면 다음과 같다.

$$
F_{0} = 0,\quad F_{1} = 1$$ $$ F_{n+2} = F_{n+1} + F_{n}$$

재귀적으로 풀기

재귀적인 풀이는 위의 점화식 정의를 충실히 따른다. 수학적인 반복관계를 그대로 구현하면 된다.

def fibonacci(n)
    if n > 2:
        return n
    else
        return fibonacci(n-1) + fibonacci(n-2)

위 방법은 매우 간단 하지만 실용적이지는 않은데, 너무 느리기 때문이다. n=100만 넣어도 원하는 시간에 답을 구할 수 없다. 그 이유는 지속적인 반복 호출 때문인데, 재귀 트리를 그려보면 그 이유를 알 수 있다. 그림을 보면 fibonacci(5)를 계산 하기 위해 fibonacci(3)은 두번 호출되었고, fibonacci(2)는 세번 호출된다. 그리고 fibonacci(1)은 5번이나 호출되는 것을 알 수 있다.

재귀 트리에서 하나의 노드 당 2개씩 자식 노드가 증가하고 있음을 주목해야 한다. n번 호출하면, $$2^{n}$$ 번씩 호출되는 것이다. 이를 $$Big-O$$ 표기법으로 표시하면 $$O(2^{n})$$이 되고, 이 함수의 수행속도는 n 이 증가 함에 따라 급격히 느려질 것이다.

그럼, n=100일때 몇 번 호출 될까? $$2^{100}$$ 을 계산해 보면 126,7650,6002,2822,9401,4967,0320,5376 된다. 나는 이 수를 어떻게 읽어야 하는지도 모르겠다.

우리는 정말 n=100 도 못구하는 풀이를 풀었다고 할 수 있을까?

동적 계획법 적용하기

단순 재귀적 풀이는 반복 호출이 문제였다. 답을 구하기 위해서 했던 계산을 또 하고 또 하고 계속해야 한다면, 전에 했던 계산을 저장해 놓으면 되지 않을까?

동적 계획법은, 동일한 계산을 반복해야 할 경우 한 번 계산한 결과를 메모리에 저장해 두었다가 꺼내 쓰는 것이다. 그래서 "컴퓨터 과학이 여는 세계"에서 이광근 교수는 동적 계획법을 기억하며 풀기로 표기하였다.

하향식으로 접근하기

동적 계획법에는 하향식 접근과 상향식 접근법 두가지가 있는데, 먼저 하향식 접근법을 적용해 보자. 하향식 접근은 위에서 아래로 가는 것이다. $$F_{n}$$을 구하기 위해서 $$F_{n-1}$$ 부터 $$F_{0}$$ 까지 n을 감소 시켜가는 것이 하향식 접근이다.

def fibonacci(n)
    if n > 2:
        return n
    else
        return fibonacci(n-1) + fibonacci(n-2)

재귀적 풀이를 보면 fibonacci(n) 을 구하기 위해 fibonacci(n-1), fibonacci(n-2)를 지속적으로 호출하고 있다. n을 감소시키면서 호출하고 있다. 이는 하향식 접근을 따르는 풀이이고, 반복 호출 문제를 가지고 있다.

이 문제를 해결하기 위해 fibonacci(i)를 계산 할 때 마다 dictionary 타입 변수 cahce에 저장한다. 그리고 필요할 때 그 값을 꺼내서 사용하도록 한다.

def fibonacci(n) -> int:
    cache = {0:0, 1:1}

    def fibonacci_inner(n):
        if n in cache:
            return cache[n]
        else:
            cache[n] = fibonacci_inner(n-1) + fibonacci_inner(n-2)
        return cache[n]

    return fibonacci_inner(n)

동적 계획법을 사용한 풀이의 재귀 트리를 그려보면 아래와 같다.(사각형으로 표시된 부분은 캐시값을 그대로 사용하는 경우이다.) 노드의 개수가 수행시간이 되는데, 각 노드의 자식 노드는 한 개 이므로 N에 대한 총 노드의 개수는 대략 $$2\times n$$가 된다. 따라서 수행 시간을 $$Big-O$$표기 법으로 표현하면 $$O(n)$$이 된다.

n=100을 넣어보면 성능이 얼마나 개선되었는지 알수 있는데, 재귀적인 풀이와 다르게 결과 값를 바로 리턴하는 것을 확인 할 수 있다. 수행 시간 $$O(n)$$ 과 $$O(2^{n})$$은 엄청난 차이가 있음을 체감할 수 있다.

상향식으로 접근하기

상향식 접근은 아래에서 위를 향해가는 것이다. $$F_{n}$$을 구하기 위해서 $$F_{0}$$에서 부터 n을 증가시켜 가는 것이다.

피보나치 점화식에서, $$F_{0} = 0,\quad F_{1} = 1$$ 이라 정의한 것을 기억하자. 이 둘을 이용해서 $$F_{2}$$를 계산하고, 차례로 $$F_{3}, \quad F_{1}$$ 등을 이전의 결과를 이용해 계산한다.

def fibonacci(n):
    fib_n = 0 # fibonacii(0)
    fib_n_plue_1 = 1 # fibonacii(1)
    fib_n_plue_2 = 0 # fibonacii(n+2)

    if n < 2:
        return n

    for i in range(2,n+1):
        fib_n_plue_2 = fib_n_plue_1 + fib_n
        fib_n = fib_n_plue_1
        fib_n_plue_1 = fib_n_plue_2 
    return fib_n_plue_2

상향식 접근법의 수행 시간 for문이 하나으로 $$O(n)$$이 되고, iterative 한 풀이와 완벽하게 같다.

행렬과 분할 정복법 적용하기

$$
F_{0} = 0,\quad F_{1} = 1$$ $$ F_{n+2} = F_{n+1} + F_{n}$$

분할 정복법을 사용하기 위해서, 피보나치 수열의 점화식을 행렬의 곱으로 표현해 보자.

$$ \begin{pmatrix} F_{n+2} \ F_{n+1} \end{pmatrix}= \begin{pmatrix} 1 & 1 \ 1 & 0 \end{pmatrix} \begin{pmatrix} F_{n+1} \ F_{n} \end{pmatrix}$$ 행렬의 곱을 풀어보면 점화식과 동일하게 됨을 확인 할 수 있는데, 위의 식은 아래와 같이 표현이 가능하다. $$ \begin{pmatrix} F_{n+2} \ F_{n+1} \end{pmatrix}= \begin{pmatrix} 1 & 1 \ 1 & 0 \end{pmatrix} \begin{pmatrix} 1 & 1 \ 1 & 0 \end{pmatrix} \begin{pmatrix} F_{n} \ F_{n-1} \end{pmatrix}$$

$$F_{n+1}$$ 와 $$F_{n}$$을 $$F_{1}$$ 와 $$F_{0}$$ 까지 확장시켜보면 아래의 식 형태가 되고 $$ \begin{pmatrix} F_{n+2} \ F_{n+1} \end{pmatrix}= \begin{pmatrix} 1 & 1 \ 1 & 0 \end{pmatrix}^{n} \begin{pmatrix} F_{1} \ F_{0} \end{pmatrix}$$

$$\begin{pmatrix}1 & 1 \1 & 0\end{pmatrix}^{n}$$ 행열의 제곱을 풀어보면 결국 $$a_{1,1}$$ 원소는 $$F_{n}$$과 같음을 확인 할 수 있다.

결국, 행렬의 제곱으로 표현된 피보나치 수열의 관계식을 갖게 된다. $$\begin{pmatrix} 1 & 1 \ 1 & 0 \end{pmatrix}^{n} = \begin{pmatrix} F_{n} & F_{n-1} \ F_{n-1} & F_{n-2} \end{pmatrix} $$

이제 우리는 $$if\quad n>2$$일 때, M=[[1,1],[1,0]] 의 거듭 제곱한 결과의 M[0][0] 을 리턴하기만 하면 된다.

일단 가장 익숙한 interative 한 방법으로 풀면, 반복문 하나 사용되고 이 풀이의 수행시간은 $$O(n)$$이 된다.

def fibonacci(n):
    M=[[1,1],[1,0]]
    F = [[1,1],[1,0]]
    if n==0:
        return 0
    if n == 2 or n == 1:
        return 1
    for i in range(n-2):
        x = F[0][0]*M[0][0] + F[0][1]*M[1][0]
        y = F[0][0]*M[0][1] + F[0][1]*M[1][1]
        z = F[1][0]*M[0][0] + F[1][1]*M[1][0]
        w = f[1][0]*M[0][1] + F[1][1]*M[1][1]

        F[0][0] = x
        F[0][1] = y
        F[1][0] = z
        F[1][1] = w

    return result[0][0]

정복법에 의해 $$O(\log{n})$$ 의 수행 시간의 풀이로 최적화 할 수 있는데 방법은 매우 간단하다.

예를 들어, $$2^8$$ 를 풀어보자. $$2^8$$ 을 푸는 방법은 두가지가 있는데,

첫째는, $$2 \times 2 \times 2 \times 2 \times 2\times 2\times 2\times 2$$ 이렇게 2를 8번 곱하는 것이다.

두번째는, 지수의 특성을 이용하는 방법으로 $$((2^2)^2)^2$$ 제곱된 값을 제곱하는 것이다. 이런식으로 계산하면 8번 계산 했던걸 3번만 계산하면 된다. 그리고 3은 $$\log_{2}8$$ 값과 동일하다.

즉, 지수계산은 지수의 특성을 이용해서 $$O(\log{n})$$ 수행시간으로 풀수 있다.

def matrix_fibonacii(n):
    F = [[1, 1],[1, 0]]
    if n == 0:
        return 0
    else:
        power(n-1, F)
        return F[0][0]

def multi(F, b):

    x = (F[0][0] * b[0][0]) + (F[0][1] * b[1][0]) 
    y = (F[0][0] * b[0][1]) + (F[0][1] * b[1][1])
    z = (F[1][0] * b[0][0]) + (F[1][1] * b[1][0])
    w = (F[1][0] * b[0][1]) + (F[1][1] * b[1][1])

    F[0][0] = x
    F[0][1] = y
    F[1][0] = z
    F[1][1] = w

def power(n, F):

    if( n == 1 or n == 0):
        return
    else:
        power(n//2, F)
        multi(F,F)
        if (n % 2) != 0:
            M = [[1, 1],[1, 0]]
            multi(F,M)

에필로그

재귀적인 방법에서는 어떻게 반복적인 연산을 처리 했는지 확인하는 것이 중요했고, 동적 계획법에서는 어떻게 반복 연산을 제거하려고 했는지가 중요했다. 행렬과 분할 정복법을 적용은 문제를 바라보는 관점의 전환이 중요하지 않았을까?

개발자라면, 최적화 하기위해 고민하고 또 고민해야 한다.

'어떻게 하면 반복하는 것을 줄일 수 있을까?'에 대한 해답을 찾으려고 노력해야 한다. 한번에 완벽하게 끝나는 경우는 없더라. 수많은 테스트와 검증이 필요하더라.

기업들이 코딩 테스트를 하는 건, 능력 있는 개발자를 뽑기위한 방법일까? 능력 없는 개발자를 거르기 위한 방법일까?

참고 사이트

• 나무위키-피보나치 수열
• geeksforgeeks-Program for Fibonacci numbers
• star7sss-[분할정복/DQ]백준 11444 피보나치 수 6 - 파이썬
• falling_star3-[프로그래머스 Level2][Python] 행렬의 곱셈
• shoark7-피보나치 수열 알고리즘을 해결하는 5가지 방법
• jsSyntaxTree

• 19^th April 2023

🔑 Problem

m = {0:0, 1:1}

def func(n):
    if n in m:
        # to do something

이런 표현식이 보인다. 무슨 뜻이지?

🛰️ Reference Site

• 파이썬 - 기본을 갈고 닦자!-17. dictionary(딕셔너리)

🎽 Learn

We can test if a key is in a dictionary or not using the keyword in. Notice that the membership test is only for the keys and not for the values.

'in' keyword

Dictionary에 key가 있는지 없는지 알기 위해서 in 키워드를 사용한다. value가 아니라 key를 검사하는데 사용하는 것을 주의해야 한다.

m = {0:0, 1:1}

def func(n):
    if n in m:
        print('The key, ' + str(n) + ', is in m')
    else:
        print('The key, ' + str(n) + ', is not in m')

func(1)
func(10)

output

The key, 1, is in m
The key, 10, is not in m

어떤 문제를 재귀적으로 풀어내는 것. 그게 나에게는 너무 어렵다. 계속 Iterative 하게 생각하게 된다. Recursive 하게 생각하는 방법으로 바꿔보자.

📍 재귀란 무엇일까?

함수가 자기 자신을 직접적으로(Directly) 또는 간접적(Indirectly)으로 호출할 때 우리는 재귀(Recursion)라고 한다. 그리고 그 함수를 재귀 함수(Recursive Function)라 부른다.

# An example of direct recursion
def directRecFun():
    # some code...
    directRecFun()
    # some code...

# An example of indirect recursion
def indirectRecFun1():
    # some code...
    indirectRecFun2()
    # some code...

def indirectRecFun2():
    # some code...
    indirectRecFun1()
    # some code...

📍 언제 재귀(Reclusion)을 사용할까?

"N번째 ... 를 계산하라", "첫 N를 나열하는 코드를 작성하라", "모든 ...를 나열하라" 등의 문제들은 재귀적으로 풀수 있는 경우가 많다. 그리고 가장 전통적인 문제로 하노이탑 문제가 있으며, 삼성 알고리즘 테스트에 단골로 출제되는 깊이우선 탐색(Depth-First Search) 문제들도 재귀적인 방법을 사용해서 푼다.

📍 재귀는 어떻게 구현할까?

재귀를 구현하기 위한 가장 보편적인 방법은 아래의 단계를 따르는 것이다.

• Step1: 종료 조건을 정의한다.
• Step2: 재귀적으로 호출하는 함수를 정의한다.(문제를 더 작은 하위문제로 나눈다.)
• Step3: 재귀가 종료되는지 확인한다.
• Step4: 하위 문제의 솔루션을 결합하여 문제를 해결한다.

이중 중요한 단계를 뽑자면 Step1 과 Step2라고 할 수 있는데, 종료조건(Step1)이 적절하지 않으면 무한루프에 빠게되고, 문제를 하위문제(Step2)로 나눌수 없으면 재귀가 성립하지 않는다. 그래서 구현할 때는 Step1 과 Step2 단계에 집중해야 한다.

📍 재귀 호출에서 메모리는 어떻게 할당될까?

모든 함수가 호출되면, 함수 정보(Local variable, return address, function pointer)가 스택에 저장되는데 이는 재귀 함수에서도 동일하게 적용된다. 스택의 특성에 따라 먼저 호출된 함수는 스택 아래, 나중에 호출된 함수는 스택 위에 위치한다. Base Case(종료조건) 에 이르면 return value를 Caller(호출한 함수)에게 전달하고 메모리는 해제된다.

예를 통해서 재귀함수가 어떻게 동작하는지 살펴보면,

def printFun(n):

    if(n < 1):
        return n
    else:
        print(n, end=" ")
        printFun(n-1)
        print(n, end=" ")
        return


n=3
printFun(3)

output

3 2 1 1 2 3

'

1. printFunc(3) 이 main()에 의해서 불려진다. n=3으로 초기화되고, 실행해야 할 구분이 다이어그램에서 보이는 것 처럼 Stack에 Push 된다.
2. printFunc(3)은 첫번째 구문을 실행하여 3을 출력 하고, printFunc(2)를 호출한다.
3. printFunc(2)는 n=2으로 초기화되고, Statement 1부터 4를 Stack에 Push 한다.
4. printFunc(2)은 2를 출력하고, printFunc(1)를 호출한다.
5. printFunc(1)는 n=1으로 초기화되고, Statement 1부터 4를 Stack에 Push 한다.
6. printFunc(1)은 1을 출력하고, printFunc(0)를 호출한다.
7. printFunc(0)은 if 문을지나 printFunc(1)로 리턴된다.
8. printFunc(1) 은 3번째 Statement 인 Print(n) 구문을 실행하고 printFunc(2)로 리턴된다.
9. printFunc(2)도 마찬가지로 Print(n) 구문을 실행하여 2를 출력하고 printFunc(3)으로 리턴된다.
10. printFunc(3)에서 Print(n) 구문을 실행하여 3을 출력하면 모든 함수가 종료된다.

이제 왜 함수의 실행 결과가 3 2 1 3 2 1 이 아니라 3 2 1 1 2 3 이렇게 출력되는지 이해할 수 있다. 이는 재귀적 호출이 Stack의 특성 사용하기 때문이다.

재귀를 이해하기 위해서는 Stack의 특성을 이해하는 것이 중요하다. 유명한 피보나치 수열을 구하는 재귀함수 F(n) = F(n-1) + F(n-2) 의 실행을 생각해 보면, 이 함수는 F(n-1)에서 파생된 모든 스택에 있는 함수와 구문을 처리한 다음, F(n-2) 에서 파생된 스택에 내용을 처리하게 된다.

📍 재귀를 이용한 문제해결

나의 경우, 이해하는 것과 직접해보는 것에 꽤 많은 차이를 느끼는데 그 차이를 줄이는 방법은 많이 해보는 것 밖에 없었다.

문제를 해결 절차는 앞서 설명한 재귀함수 구현 방법을 따르면서, 단순한 문제들을 의식적으로 Reclusion하게 풀어보자.

Problem 1. 1 부터 N까지 합을 구하는 함수를 재귀적으로 작성하시오.

• Step1 - Define a base case

  if ( n == 0 ):
    return n

• Step2 - Define a recursive case

  sum(n) = n + sum(n-1)

• Step3 - Ensure the recursion terminates

  # if sum(0) is called, then recursion terminates

• Step4 - Combine the solution

  def reclusiveSum(n):
  if (n == 0):
      return n
  else:
      return n + reclusiveSum(n-1)

  Problem 2. 회문(Palindrome) 똑바로 읽으나 거꾸로 읽으나 동일한 단어인지 확인하는 함수를 재귀적으로 구현하시오.

• Step1 - Define a base case

  # 단어의 길이가 1이거나 0이면 가장 짧은 회문이므로 True 반환
  if (len(str) == 0 | len(str) == 1))
    return True
  

양 끝이 같지 않으면 회문이 아니므로 False 반환

if ( str[0] != str[-1] ) return False

* Step2 - Define a recursive case
```python
# 양 끝이 같으면 양 끝을 뺀 문자열로 다시 비교
# 만약, abba 이면 양 끝 a 를 빼고 bb 만 다시 비교
if(str[0] == str[-1]):
    return fun(str[1:-1])

• Step3 - Ensure the recursion terminates

  # str = "a" 일때, fun(str) 이 호출되면 재귀함수는 종료 됨

• Step4 - Combine the solution

  def isPalindrome(str):
  
    if(len(str) == 0 | len(str)==1):
        return True
    elif(str[0] == str[-1]):
        return isPalindrome(str[1:-1])
    else:
        return False

Problem 3. Reverse String

• Step1 - Define a base case

  # Returns "" if the length of the string is zero.
  if (len(str) == 0):
    return ""

• Step2 - Define a recursive case

  fun(str[1:]) + str[-1]

• Step3 - Ensure the recursion terminates

  # The recursion terminates when the string length is zero.

• Step4 - Combine the solution

  def reverseString(str):
  
    if (len(str) == 0):
        return ""
    else:
        return reverseString(str[1:]) + str[-1]

Problem 4. decimal to binary conversion

• Step1 - Define a base case

  if(number == 1)
    return str(number)
  else:
    return ""

• Step2 - Define a recursive case

  fun(number//2) + str(number%2)

• Step3 - Ensure the recursion terminates

  # If you continue to divide by 2, finally the quotient is either 0 or 1.

• Step4 - Combine the solution

  def decimalToBinary(number):
  
    if(number ==1):
        return str(number)
    elif(number == 0)
        return ""
    else:
        return decimalToBinary(number//2) + str(number%2)

📍 마무리

재귀적으로 문제를 풀기위해서는 아래 4가지를 기억하면 된다.

• 재귀적 프로그래밍에는 Recursive Case와 Base Case가 존재한다.
• Base Case는 프로그램을 종료 시키는 역할을 한다.
• 재귀적 호출은 새로운 각각의 함수를 생성하여 스택에 저장하도록 한다.
• 무한 재귀 호출은 실행시 OutOfStackMemory를 이끈다.

Iterative하게 구현하는 것과 다른 건, 스택의 특성을 사용한다는 것과 반복문에서 하던 작업을 스스로 호출을 통해 처리한다는 점이다.

📍 에필로그

Reclusive Programing과 Iterative Programing의 장단점 따위는 신경 쓰고 싶지 않았다. 오로지 구현에만 집중하고 싶었다. 재귀용법 으로 해결 할 수 있는 문제가 얼마나 될까? 하지만 재귀용법을 이해하지 못하면 다음 단계로 가지 못한다. 내가 DFS 문제를 풀때 헤메는 이유. 그 문제의 답을 보아도 이해가 가지 않는 이유가 거기에 있지 않을까?

📍 참고 사이트

• Introduction to Recursion – Data Structure and Algorithm Tutorials
• Python: Recursion - Exercises, Practice, Solution

🔍 About Bubble Sort

버블 정렬의 Key Concept은 현재 원소가 그다음 원소의 값보다 크면 바꾸는 것이다. 이 작업을 정렬이 완료될 때까지 반복하면 된다.

Key Concept

• 현재 원소(A_[i])와 다음 원소(A_[i+1])를 비교한다.
• 현재 원소가 다음 원소 보다 크면 서로의 자리를 바꾼다.

⛏️ Implementation

def bubble_sort(list):
    list_length = len(list)
    for try_count in range(0, list_length-1):
        sorted = False
        for index in range(1, list_length - try_count):
            if list[index-1] > list[index]:
                list[index-1], list[index] = list[index],  list[index-1]
                sorted = True

        if sorted == False:
            break 

    return list

📍 Insertion Sort

🔍 About Insertion Sort

삽입 정렬의 Key Concept은 카드를 정렬하는 방법과 동일하다.

생각해 보자. 카드를 일렬로 펼쳐서 카드 배열을 만든다. 그 다음 두번째 카드를 선택하고 첫 번째 카드와 비교한다. 만약, 두번째 카드가 값이 작으면 첫번째 자리에 두번째 카드를 삽입한다. 이제 이 카드 배열은 두 번째 카드까지 정렬되었다. 다음에는 세번째 카드를 선택한다. 그리고 앞으로 가면서 값을 비교하여, 세번째 카드의 값이 작다면 그 앞에 카드를 삽입한다. 첫 번째 카드까지 이 동작을 반복한다. 이제 세번째 카드 위치까지 정렬되었다. 다음은 네 번째 카드, 다섯 번째 카드, 그리고 마지막 카드까지 이 동작을 반복한다.

Key Concept

• 선택한 원소(A_[i+1])의 왼쪽(from A_[i-1] to A_[0]) 은 정렬되어 있다.
• 왼쪽의 정렬된 배열의 정렬된 상태가 유지될 수 있도록 선택한 원소의 위치를 찾아 삽입한다.

⛏️ Implementation

def insert_sort(list):
    for standard in range(1, len(list)-1):
        for index in range(standard, 0, -1):
            if list[index] < list[index-1]:
                list[index-1], list[index] = list[index], list[index-1]

    return list

📍 Selection Sort

🔍 About Selection Sort

선택정렬의 Key Concept은 배열에서 최소값을 찾아 맨 앞에 위치한 값과 교체하는 것이다.

Key Concept

• 가장 작은 값부터 정렬시켜 나가는 전략을 취한다.
• 배열의 정렬되지 않은 부분에서 가장 작은 값을 찾는다. ( 회가 거듭할 수록 배열의 왼쪽 부분은 정렬되어 간다. 반면, 오른쪽은 정렬되어 있지 않은 상태를 유지한다. )
• 가장 작은 값을 정렬되지 않은 부분의 맨 앞의 값과 교체한다.

⛏️ Implementation

def selection_sort(list):
    for stage in range(0, len(list)):
        min_index = stage
        for index in range(stage+1, len(list)):
            if list[min_index] > list[index]:
                min_index = index
        list[stage], list[min_index] = list[min_index], list[stage]

    return list

🛰️ Reference

• hackerearth-Bubble Sort
• hackerearth-Insertion Sort
• hackerearth-Selection Sort
• geeksforgeeks-Bubble Sort Algorithm

최대 힙(Max Heap)은 트리의 마지막 단계(Level)에서 오른쪽을 뺀 나머지 부분이 가득 채워져 있다는 점에서 완전 이진 트리이다. 그리고 각 노드의 원소가 자식들의 원소보다 크다는 특성을 갖는다. 따라서 루트는 트리의 가장 큰 원소가 된다.

Max Heap 특성

• 완전 이진 트리이다.
• 각 노드의 원소가 자식들의 원소보다 크다
• 루트는 노드의 가장 큰 원소가 된다.

Heap은 최소 힙(Min Heap)과 최대 힙(Max Heap)으로 구분할 수 있는데, Max Heap은 각 노드의 원소가 자식들의 원소보다 크다는 특성을 갖고, Min Heap은 각 노드의 원소가 자식들의 원소보다 작다는 특성을 갖는다.

🏷️ Requirement

내가 구현하려는 Max Heap의 요구사항은 두 가지이다.

1. Max Heap 의 특성을 을 유지하면서 노드를 삽입하는 insert 함수를 구현하라.
2. Max Heap 의 특성을 을 유지하면서 최대 노드를 삭제하는 extract_max 함수를 구현하라.

⛏️ Implement

일반적으로 Max Heap 은 배열(Array) 자료구조를 활용하여 구현하게 되는데, 배열을 활용하는 이유는 인덱스를 사용하여 접근할 수 있기 때문이다. 아래의 그림은 부모 노드 Index와 자식노드 Index사이에 특별한 규칙 표현하고 있다. Heap 이 어떻게 배열로 대칭되는지 쉽게 확인 할 수 있다.

※ 구현의 편의를 위해 배열의 시작 인덱스는 1부터 시작하는 것으로 한다.

규칙

• 왼쪽 자식 노드 인덱스 = 부모 노드 인덱스 X 2
• 오른쪽 자식 노드 인덱스 = ( 부모 노드 인덱스 X 2 ) + 1
• 부모 노드 인덱스 = 자식 노드 인덱스 / 2

규칙을 python code으로 표현하면 아래와 같다. 이 함수들을 구현에 활용한다.

def __get_parent_node_index(self, parent_index):
    return parent_index // 2

def __get_left_child_node_index(self, parent_index):
    return 2 * parent_index

def __get_right_child_node_index(self, parent_index):
    return (2*parent_index) + 1

def __is_leaf(self, parent_index):
    max_index = self.__get_max_index()

    return (parent_index * 2) > max_index

def __get_max_index(self):
    return len(self.maxheap) - 1

📍 MaxHeap Class를 정의한다.

구현의 편의를 위해 배열의 시작 인덱스는 1부터 시작하는 것으로 했으므로 MaxHeap Class의 __init__는 0번 index에는 None을 입력하고, 1번 index에는 인자로 받은 value를 값을 저장하도록 한다.

class MaxHeap:
    def __init__(self, value):
        self.maxheap = list()
        self.maxheap.append(None)
        self.maxheap.append(value)

📍 MaxHeap Class에 insert 기능을 구현한다.

MaxHeap에서 insert 함수의 구현은 2 Step으로 나누어 생각한다.

1. 데이터를 마지막에 삽입한다.
2. 부모노드와 비교하여 값이 크다면, 부모노드와 위치를 바꾼다.

def insert(self, value):
    # 1. just insert the value at the end
    self.maxheap.append(value)
    # 2. if the child node value is greater than the parent node, replace iteratively

    current_index = len(self.maxheap) - 1

    while (True):
        is_swap, parent_node_index = self.__is_moveup(current_index)

        if(not is_swap):
           break;

        self.maxheap[parent_node_index], self.maxheap[current_index] = 
        self.maxheap[current_index], self.maxheap[parent_node_index]
        current_index = parent_node_index


def __is_moveup(self, current_index):
    return_value = False

    parent_node_index = self.__get_parent_node_index(current_index)

    if (parent_node_index == 0):
        return return_value, parent_node_index

    if(self.maxheap[parent_node_index] < self.maxheap[current_index]):
        return_value = True
        return return_value, parent_node_index

    return return_value, parent_node_index

📍 MaxHeap Class에 extract_max 기능을 구현한다.

MaxHeap에서 extract_max 함수의 구현은 3 Step으로 나누어 생각한다.

1. 최상단 노드(Root) 를 삭제한다.
2. 가장 마지막에 추가한 노드를 Root 노드에 복사한다.
3. Root 노드 값이 Child 노드 보다 작을 경우, Root 노드의 Child 노드 중 가장 큰 값을 가진 노드와 Root 노드 위치를 바꾸주는 작업을 반복한다.

def __is_movedown(self, current_index):
    return_value = False

    if(self.__is_leaf(current_index)):
        return return_value, current_index
    else: 
        left_child_node_index = self.__get_left_child_node_index(current_index)
        right_child_node_index = self.__get_right_child_node_index(current_index)
        max_index = self.__get_max_index()

        # has just left node
        if (right_child_node_index > max_index):
            if(self.maxheap[left_child_node_index] > self.maxheap[current_index]):                    
                return_value = True
                return return_value, left_child_node_index
            else:
                return_value = False
                return return_value, current_index
        # has two children node
        else:
            greater_value_node_index = self.__get_greater_value_node_index(left_child_node_index, right_child_node_index)
            if(self.maxheap[greater_value_node_index] > self.maxheap[current_index]):                    
                return_value = True
                return return_value, greater_value_node_index
            else:
                return_value = False
                return return_value, current_index   

def extract_max(self):
    current_index = 1
    max_value = self.maxheap[1]
    last_node_value = self.maxheap.pop()

    self.maxheap[1] = last_node_value

    while(True):
        is_movedown, child_node_index = self.__is_movedown(current_index)
        if(not is_movedown):
            break;

        self.maxheap[child_node_index], self.maxheap[current_index] = 
        self.maxheap[current_index], self.maxheap[child_node_index]
        current_index = child_node_index

    return max_value

📍 Max Heap Class에 기능을 확인한다.

이제 구현된 Max Heap Class 의 기능을 점검한다.

• insert 기능 확인 : 위 모양의 Max Heap를 insert 함수를 통해 만들고 값을 출력한다.

• extract_max 기능 확인 : extract_max 를 이용해 값을 삭제 했을 때 Heap 의 특성이 유지되는지 확인한다.

• ** insert 기능 확인**

  maxheap = MaxHeap(15)
  maxheap.insert(10)
  maxheap.insert(8)
  maxheap.insert(5)
  maxheap.insert(4)
  maxheap.insert(20)
  maxheap.insert(6)
  maxheap.insert(9)
  maxheap.insert(3)
  maxheap.insert(2)
  

maxheap.print()

**output**

parent_value : 20 left_child_value : 10 right_child_value : 15 parent_value : 10 left_child_value : 9 right_child_value : 4 parent_value : 15 left_child_value : 8 right_child_value : 6 parent_value : 9 left_child_value : 5 right_child_value : 3 parent_value : 4 left_child_value : 2

* ** extract 기능 확인**
```python
extract_value = maxheap.extract_max()
print("Extract Value : " + str(extract_value))
maxheap.print()

output

Extract Value : 20
parent_value : 15 left_child_value : 10 right_child_value : 8
parent_value : 10 left_child_value : 9 right_child_value : 4
parent_value : 8 left_child_value : 2 right_child_value : 6
parent_value : 9 left_child_value : 5 right_child_value : 3

🛰️ Reference Site

Stranger's LAB-배열을 이용한 Heap 구현하기 geeksforgeeks-Min Heap in Python CrazyforCode-Heap Data Structure

이진 탐색 트리(Binary Search Tree)는 최대 두 개의 자식 노드를 가지는 트리형태의 자료구조로, 아래의 특징을 갖는다.

• 이진트리는 루트가 있다.

• 모든 노드가 적어도 두 개의 자식 노드를 가진 정렬 트리이다.
• 루트 트리는 당연히 레벨(루트로부터의 거리)이라는 개념을 가지고 있다.
• 모든 노드에 대해서 하위 레벨로 연결되는 노드로 자식 노드의 개념을 정리할 수 있다.

위 이진 트리의 특성에 아래 네가지 특성을 더 하면 이진 탐색 트리가 된다.

• 각 노드에 값이 있다.

• 값들은 전순서가 있다.
• 노드의 왼전 서브트리에는 그 노드의 값보다 작은 값들을 지닌 노드들로 이루어져 있다.
• 노드의 오른쪽 서브트리에는 그 노드의 값보다 큰 값들을 지닌 노드들로 이루어져 있다.
• 좌우 하위 트리는 각각이 다시 이진 탐색트리여야 한다.

🏷️ Requirement

내가 구현하려고 하는 이진탐색트리의 요구사항은 총 4가지이다.

• 노드를 검색하여 값이 존재하면 노드를 리턴한다.
• 노드를 검색하여 값이 존재하지 않으면 None을 리턴한다.
• 이진 탐색 트리를 유지하면서 노드를 삽입한다.
• 이진 탐색 트리를 유지하면서 노드를 삭제한다.

⛏️ Implement

📍 데이터를 저장하는 Node Class를 정의한다.

Node 클래스는 노드값(value)와 좌/우 노드(left, right) 이렇게 총 세 개의 속성을 갖는다.

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

    def __str__(self):
        return str(self.value)        

📍 Binary Search Tree를 유지하며 Node를 관리할 BinarySearchTree Class 를 정의한다.

class BinarySearchTree:
    pass

📍 BinarySearchTree Class 에 insert 기능을 구현한다.

새로운 값은 트리의 잎 노드에 연결된다. 구현 할 때 고려해야 할 사항은 새로운 값을 연결시킬 잎 노드의 부모 노드를 찾는 것이다.

1. root 가 None 이면 root 에 insert_node를 연결시킨다.

2. insert_node보다 크면 오른쪽으로, insert_node보다 작으면 왼쪽으로 순회하면서 leaf node를 찾는다.

3. 크면 오른쪽에, 작으면 왼쪽에 insert_node를 연결시킨다.

   def insert(self, value):
    insert_node = Node(value)
   
    # if first
    if self.root is None:
        self.root = insert_node
        return
   
    current_node = self.root
   
    # search parent node for linking
    while current_node is not None:
        if current_node.value < value:                
            parent_node = current_node
            current_node = current_node.right
        else:
            parent_node = current_node
            current_node = current_node.left
   
    # connect parent node with insert node
    if(parent_node.value < value ):
        parent_node.right = insert_node
    else:
        parent_node.left = insert_node

📍 BinarySearchTree Class 에 Inorder Traversal 기능을 구현한다.

Inorder Traversal은 중위 순회라고 한다. 중위 순회는 다음과 방법으로 진행된다.

1. 왼쪽 서브트리를 중위 순회한다.
2. 노드를 방문한다.
3. 오른쪽 서브 트리를 중위 순회 한다.

간략히 이야기 하면 Left -> Root -> Right 순서로 노드를 방문한다. 트리를 중위 순회하면 노드의 값을 오름차순으로 방문하게 된다. 그래서 중위 순회는 이진 탐색 트리에서 값을 찾을 때 많이 사용된다.

def inorder(self):
    stack = []
    current_node = self.root

    while((current_node is not None) or (len(stack) != 0)):
        if(current_node is not None):
            # print("current node:" + str(current_node.value))
            # print("current left:" + str(current_node.left.value))
            stack.append(current_node)
            current_node = current_node.left
        else:
            parent_node = stack.pop()
            print(parent_node.value)
            current_node = parent_node.right

📍 BinarySearchTree Class 에 search 기능을 구현한다.

BinarySearchTree 에서 값을 찾아 해당 노드를 Return하는 함수를 구현한다.

1. subtree root 값과 찾으려 하는 값을 비교한다.

2. 값이 동일하면 종료한다.

3. 값이 크면 오른쪽 서브트리로 이동한다.

4. 값이 작으면 왼쪽 서브트리로 이동한다.

5. 값을 찾을때 까지 1번과 4번을 반복한다.

6. 값이 존재하지 않으면 None 을 리턴한다.

   def search(self, search_value):
    current_node = self.root
   
    while current_node is not None:
        if(current_node.value == search_value):
            return current_node
   
        if(current_node.value > search_value):
            current_node = current_node.left
        else:
            current_node = current_node.right
   
    return None

   📍 BinarySearchTree Class 에 delete 기능을 구현한다.

   원하는 노드를 삭제하는 함수를 구현한다. 삭제기능의 구현은 조금 까다로운데, 삭제 후에도BinarySearchTree의 특성을 유지해야 하기 때문이다. 자식 노드가 없다면 그냥 삭제하면 되지만 자식노드가 존재하는 경우는 어떻게해야 하나? 노드를 삭제하고 나면 자식 노드들과의 연결이 다 끊겨서 접근이 불가능해 질 텐데 말이다.

아래의 그림에서 값 4를 가진 Node를 삭제하면, 저 저리에 어떤 노드를 두어야 BinarySearchTree의 특성 유지할 수 있을지 고민해야 한다.

전체를 한 번에 바라 보려면 어렵게 때문에 BinarySearchTree에서 삭제는 3가지 경우의 수로 나누어 생각한다.

Case1. Leaf Node, 자식이 없는 노드를 삭제할 때

• 단순히 삭제 한다.

Case2. 자식을 하나 가지고 있는 노드를 삭제할 때

• 자식 노드를 삭제할 노드에 복사한다.
• 노드를 삭제한다.

Case3. 자식을 두개 가지고 있는 노드를 삭제할 때

• 후임자(삭제할 노드의 오른쪽 자식 중 가장 작은 값)를 가진 노드를 찾는다.
• 후임자를 삭제할 노드에 복사한다.
• 노드를 삭제한다.

이를 Loop와 Reclusive(재귀함수)를 사용하여 각각 구현하면 아래와 같다.

Loop를 이용한 구현

def delete_using_loop(self, delete_value):
    # step1. search node
    current_node = self.root
    parent_node = self.root
    search = False

    while current_node is not None:
        if current_node.value == delete_value:
            search = True
            break

        parent_node = current_node
        if current_node.value > delete_value:
            current_node = parent_node.left
        else:
            current_node = parent_node.right

    if current_node is None:
        print("can not find the node you want to delete")
        return search

    # step2. delete
    # case 1. leaf node
    if current_node.left is None and current_node.right is None:
        del(current_node)
        if parent_node.value > delete_value:
            # print("greater than :" + str(parent_node.value))
            parent_node.left = None
        else:
            # print("less than: " + str(parent_node.value))
            parent_node.right = None
        # End case 1.
        return 

    # case 2. only one child
    if current_node.left is None or current_node.right is None:
        if parent_node.value > delete_value:
            if current_node.left is not None:
                parent_node.left = current_node.left
            else:
                parent_node.left = current_node.right
        else:
            if current_node.left is not None:
                parent_node.right = current_node.left
            else:
                parent_node.right = current_node.right
        # End case 2.
        return

    # case 3. two children
    if current_node.left is not None and current_node.right is not None:
        minimum_parent_node = current_node.right
        minimum_node = minimum_parent_node

        while minimum_node.left is not None:
            temp = minimum_node
            minimum_node = minimum_parent_node.left
            minimum_parent_node = temp
        # print('minimum node value : ' + str(minimum_node.value))

        if parent_node.value > delete_value:
            parent_node.left = minimum_node
        else:
            parent_node.right = minimum_node

        if minimum_node.left is None and minimum_node.right is None:
            minimum_parent_node.left = None
            minimum_node.left = current_node.left
            minimum_node.right = current_node.right
        elif minimum_node.left is None and minimum_node.right is not None:
            minimum_node.left = current_node.left

        del(current_node)
        # End case 3.
        return

재귀를 이용한 구현

def search_min_node(self, root):
    if root.left is None:
        return root
    else:
        minimum = self.search_min_node(root.left)
    return minimum

def delete_using_reclusive(self, delete_value):
    self._delete_value(self.root, delete_value)

def _delete_value(self, root, delete_value):
    if root is None:
        return

    if root.value > delete_value:
        root.left = self._delete_value(root.left, delete_value)
    elif root.value < delete_value:
        root.rigth = self._delete_value(root.right, delete_value)
    else:
        # case 1. leaf node or only one child
        if root.left is None:
            temp = root.right
            root = None
            return temp
        elif root.right is None:
            temp = root.left
            root = None
            return temp
        else:
            # case 2. it has two children.
            # search minimum node
            minimum = self.search_min_node(root.right)
            # copy minimum node
            root.value = minimum.value
            # delete minimum node
            root.right = self._delete_value(root.right, minimum.value)
    return root

📍 BinarySearchTree의 기능을 확인한다.

아래 모양의 BinarySearchTree를 insert 함수를 통해 만들고, search 함수를 통해 값을 검색해 보고, 두 개의 delete 함수를 사용하여 노드를 삭제해 보면서 기능을 검증한다.

• insert 기능 확인

  bst = BinarySearchTree()
  bst.insert(6)
  bst.insert(2)
  bst.insert(1)
  bst.insert(4)
  bst.insert(3)
  bst.insert(5)
  bst.insert(8)
  bst.insert(7)
  bst.insert(10)
  bst.insert(9)
  

bst.inorder()

#### output

1 2 3 4 5 6 7 8 9 10

* **`search` 기능 확인**
```python
searched_node = bst.search(7)
if searched_node is not None:
    print("search value: " + str(searched_node.value))
else:
    print("There is no data.")

output

search value: 7

• delete 기능 확인

  # case3: delete the node has 2 children
  bst.delete_using_loop(2)
  # case2: delete the node has only child
  bst.delete_using_reclusive(9)
  # case1: delete leaf node
  bst.delete_using_loop(1)
  

bst.inorder()

#### output

3 4 5 6 7 8 10

```

🛰️ Reference Site

• wikipedia-이진 트리
• ratsgo's-이진 탐색 트리
• Binary Tree Traveral에 대해 알아보자
• wikipedia-트리 순회
• geeksforgeeks-Binary Search Tree | Set 1 (Search and Insertion)
• geeksforgeeks-Deletion in Binary Search Tree
• 파이썬을 사용한 이진 트리와 순회 알고리즘 구현 (1)

나는 데이터 전달을 보장하는 솔루션을 운영한다. 파일을 주고받는 단순한 요건을 처리하는데 에러가 발생했다. Target Directory에 파일이 저장되지 않는다.

"어? 왜이러지?"

🎪 System Configuration Diagram

먼저, 문제를 분석하기 위해 환경 구성을 확인한다. 정상적인 환경과 비정상적인 환경을 비교하여 차이점을 찾는다. 대부분 답은 다름에 있다.

환경 구성은 단순하다. Middleware를 통해 Endpoint는 File을 전달 받는다. 특이한 점이 있다면 2개의 다른 파일 시스템을 쓴다는 것!

1. Middleware로 부터 파일 조각을 전달 받는다.
2. 파일 조각을 /home/usr/temp 경로에 순차적으로 write한다.
3. /home/usr/temp 에 파일이 전체가 write 되면 /app/dist 로 파일을 옮긴다.

※ /home/usr/temp 는 /app/dist 서로 다른 파일 시스템이다.

🔑 Problem

로그를 보니 아래의 코드에서 문제가 발생했다. 임시 경로인 /home/usr/temp 에는 정상적으로 파일이 존하는데, Target Dirctory인 /app/dist는 파일이 존재하지 않는다. rename 함수를 통해 로 옮기는 부분에서 0이 아니라 -1이 리턴하면서, 파일이 정상적으로 수신되지 않은 것 처럼 보이는 것이다.

if(0 != rename(frompath, targetpath)) {
    sprintf("Error write target file")
}

🔪 Analysis

rename 함수는 <stdlib.h> C언어의 표준 라이브러리에서 제공하는 함수인데 왜 안되지? rename 함수에는 문제가 있을리 없다. 단지, 내가 모르는 부분이 있을 뿐!

🔍 How to implement rename function in C language?

rename 함수의 실제 구현을 살펴보면 로직은 매우 단순한데 아래 두개의 Step 이 전부다.

• __link 함수를 통해 old 파일에 new라는 hard link 를 생성한다.

• __unlink 함수를 통해 기존 hard link old 를 제거한다.

rename 함수에서 hard link가 주요한 역할을 함으로 주의 깊게 살펴보아야 할 것 같다.

int
rename (const char *old, const char *new)
{
  int save = errno;
  if (__link (old, new) < 0)
    {
      if (errno == EEXIST)
    {
      __set_errno (save);
      /* Race condition, required for 1003.1 conformance.  */
      if (__unlink (new) < 0
          || __link (old, new) < 0)
        return -1;
    }
      else
    return -1;
    }
  if (__unlink (old) < 0)
    {
      save = errno;
      if (__unlink (new) == 0)
    __set_errno (save);
      return -1;
    }
  return 0;
}

🔍 Managing Hard Link

컴퓨팅 시스템에는 파일을 위한 2개의 링크가 존재한다. 하나는 Hard Link 이고 또 다른 하나는 Soft Link 이다. 나는 이 두개를 이렇게 이해하는데,

• Hard Link는 파일 이름으로 실제 데이터에 접근할 수 있도록 하는 것

• Soft Link는 바로가기. 원본 파일의 이름 시스템(Hard Link?)을 가르키도록 하는 것

  사실 Hard Link는 Inode와 관련되어 있고, Inode 대한 건 여기서 확인 할 수 있다.

'Hard Link는 파일 이름으로 실제 데이터에 접근할 수 있도록 한다.'라고 정의하면 왜 모든 파일이 적어도 하나의 Hard Link 가 존재해야 하는지 이해 수 있다. 바로, 파일 이름으로 실제 데이터(physical data)에 접근해야 하기 때문이다.

아래의 그림은 Hard Link의 동작 방법을 표현한 그림이다. 디렉터리 dirA, dirB, dirC의 파일 이름 name1, name2, name3은 Inode 12345를 가르키고 있다. Inode 12345에는 파일에 대한 내용과 그리고 Hard Link의 갯수에 대한 정보를 가지고 있다.

여기서 dirD에 파일 이름 name4로 Hard Link를 추가하면, 추가된 Hard Link는 Inode 12345를 가르키고 Hard Link 수를 4로 변경한다. Inode를 새로 생성하지 않는다.

반면에, Soft Link 를 생성하면 Inode가 생성된다. 그리고 Inode에 실제 파일 경로를 저장한다. 아래 그림은 Soft Link의 동작 방법을 보여준다. dirA의 파일 이름 name1은 Inode 12345를 가르키고 있다. 여기에 dirB의 name2 라는 Soft Link를 생성하면 새로운 Inode 13579가 생성된다. Inode 13579는 실제 파일(physical data)의 /dirA/name 의 경로를 가르킨다.

dirA에 있는 name1 파일을 삭제하면, dirB에 있는 Soft Link 파일 name2는 존재하지 않는 파일 경로를 가리키 때문에 액세스할 때 오류가 발생한다.

🔍 Hard Link of Limitation

Hard Link에는 제약 사항이 존재한다.

• Hard Link는 디렉토리에 생성할 수 없다.
• Hard Link는 같은 파일 시스템에서 사용가능하다. 그 대신 Soft Link를 사용해야 한다.
• 하나의 파일에 대한 Hard Link의 최대 개수는 2<sup>32</sup> 이다.

🌠 How to Solve the Problem

Hard Link에 대해 공부하다 보니 문제 발생 원인이 명확하게 보인다.

Hard Link 제약사항과 System Configuration Diagram을 보면 내가 운영하는 솔루션이 Hard Link의 제약사항을 위반 하고 있음을 알 수 있다.

Hard Link는 같은 파일 시스템에서 사용가능하다.

/home/usr/temp 과 /app/dist 은 서로 다른 파일 시스템이기 때문에 문제가 발생하는 것이다.

문제의 해결법은 두가지 이다.

첫째, rename 함수를 사용하지 않는 것 둘째, Target Directory 와 Temp Directory를 같은 파일 시스템으로 변경하는 것

팀원들과 협의 끝에 나는 두 번째 방법을 선택해 수정했다.

🍰 Epilogue

일을 하면 할 수록 운영체제와 컴퓨터 구조론과 같은 Computer Sicence이 지식이 필요함을 느낀다. 다 필요한 것들인데 대학에서 공부 할 때는 왜 이리 쓸모 없게 느껴졌을까?

🛰️ Reference Site

• rename-gcc
• rename-codebrowser
• [운영체제] 파일 시스템, inode 방식에 대하여
• C program to create hard link and soft link
• 아이노드-Wikipedia
• Managing Hard Links-HP
• Hard link-wikipedia
• 파일 테이블과 파일 디스크립터

시스템을 재시작하고 클라이언트 연결이 정상적으로 되지 않는 문제가 발생했다. 관련자들이 모여 재현 테스트를 진행하는데 시작부터 기분이 좋지 않다. 문제를 해결하려고 하는 사람이 보이지 않는다. 모두 자기 문제가 아니라고 한다. 그중 한 명은 테스트가 종료가 되지도 않았는데 로그하나 던져주고는 이렇게 말한다.

"이제 어떻게 정리하실 거에요?"

근데 다들 저 로그가 뭘 뜻하는지 알고나 저렇게 말하는 건지! 애들 대하 듯 하나하나 로그를 읽어 주었다. 그랬더니 이렇게 말한다.

"여기는 그런거 볼 사람 없어요!" ** 아 진짜!! 모르는 건 자랑이 아닌데! 계속 모른다고! 몰라서 못 한다고만 한다. 👊 **

🎪 System Configuration Diagram

문제를 해결하기 위해서는 주변을 먼저 파악하는 것이 중요하다. 먼저, 시스템이 어떤구성으로 이루어져 있는지 확인한다. 아래는 내가 운영하는 시스템을 도식화한 그림이다.

간단하게 설명하면,

• 고객은 JEUS Application Server(AS)에서
• 내가 배포한 my-api.jar 를 이용하여
• 내가 운영하는 JBoss AS와 연결한다.
• 이 기종 WAS 를 연결하는 기술로는 JNDI 와 RMI 가 사용된다.

🔑 Problem

위 구성에서 JBoss AS를 재시작 하니 JEUS AS 와 연결을 맺지 못 한다. 문제를 일으키는 부분은 InitialContext 를 생성 하는 부분으로 아래와 같다. org.jnp.interfaces.NamingContextFactory 의 진입점을 JEUS에서 못 찾는 듯하다.

Problem Code

Properties properties = new Properties();
properties.put(Context.SECURITY_PRINCIPAL, "guest");
properties.put(Context.SECURITY_CREDENTIALS, "guest");
properties.put(Context.PROVIDER_URL, "IP:PORT");
properties.put(Context.INITIAL_CONTEXT_FACTORY, 
"org.jnp.interfaces.NamingContextFactory");

// the error occur on this line!
Context context = new InitialContext(properties);

Error Log

🔪 Analysis

로그 의 javax.naming.InitialContext.init 부분을 통해 에러는 JNDI 관련 부분에서 발생하는 것을 확인 할 수 있다. 그럼 JNDI 를 시작점으로 차근차근 분석 해볼까!

🔍 What is JNDI?

JNDI 는 J2EE 서비스 중 하나로 The Java Naming and Directory Interface 의 줄임말이다. 왠지 영어가 기니까 어렵게 느껴지는데. 단지 용어가 낯선 것일 뿐이지 쉽다. Naming Service 와 Directory Service 만 이해하면 된다. 글을 읽는데 필요한 정도로만 이해해 보자.

🚩 Naming Service 이름을 이용해 컴퓨터 자원을 접근하도록 도와 주는 서비스

🚩 Directory Service 디렉터리 안에 속성(attribute) 대해서 생성, 추가, 조회, 수정, 조회 할 수 있도록 인터페이스를 제공하는 것

낯선 이름 이지만 우리는 해당 서비스를 이미 사용해 왔다. 단지 너무 자연스러워 사용하는 것 조차 몰랐을 뿐!

우리가 run.sh 라는 shell script 를 사용하여 프로그램을 실행 시킬 수 있는 건, File System 이 run.sh 에 해당하는 reference 를 이미 연결시켰기 때문에 가능한 일이다. File System 은 우리가 가장 많이 사용하는 Naming Service 로 생각할 수 있다.

run.sh

디렉터리 안에 어떤 자원을 찾기 위해 때로는 find 명령을 사용하는 데, 이는 File System이 해당 디렉터리안에 속성을 모두 관리하기 때문에 사용 가능 하다. 그럼 File System 은 Directory Service 로도 생각할 수 있다.

# 현재 위치에서 log가 들어가는 파일 모두 찾기
find . -name "*log*"

JNDI는 앞에 Java가 붙었으니까 이렇게 이해하면 된다.

🚩 JNDI 는, Java Language에서 객체를 이름으로 접근할 수 있도록 도와주는 인터페이스이다.

🔍 JNDI Architecture

앞서 JNDI 가 무엇을 하는 것인지 알았음으로 JNDI를 좀더 들여다 보자. 그림에서 보는 것처럼 JNDI는 API 와 SPI 로 구성된다.

🚩 Application Programming Iterface(API) 는 개발자가 사용한다. 🚩 Service Provider Interface(SPI) 는 Vendor 가 구현하여 제공한다.

이렇게 두개의 Layer를 두는 이유는 Vendor 의 종속성을 제거하기 위해서 인데, 이를 통해 Application의 변경을 최소화 할 수 있다.

이상적으로, (아주 이상적으로) Application이 운영되는 환경이 Jboss 에서 WebSphere 로 변경된다 하여도 우리는 Application 을 변경할 필요가 없어진다. 단지 참조하는 jar 를 WebSphere 에서 제공하는 jar 로 교체하기만 하면(SPI Layer만 교체하면) 될 뿐이다. 그럼 Application은 WebSphere 환경에서 정상적으로 동작한다.

아래 그림은 JNDI 구조를 내가 운영하는 환경에 맞게 투형시킨 것이다.

JESU에서 JBoss JNDI Service에 접속하기 위해 아래의 절차로 동작하는데, 로그를 통해 유추해 보면 문제는 SPI 구현체를 찾는 부분 2번에서 발생하는 듯 보인다.

1. Application은 JNDI Format를 사용하여 연결을 요청한다.
2. JNDI API 는 Namging Manager를 이용하여 SPI 구현체를 찾는다.
3. 그리고 SPI 구현체를 초기화 한다.
4. JNDI SPI는 요청을 SPI 구현체, 즉 Jboss Naming Service에 보낸다.
5. Jboss Naming Service 는 요청을 처리하여 응답을 반환한다.
6. JNDI SPI는 응답을 JNDI Format 으로 변경한다.
7. Namging Manager는 구현체 이름을 등록한다.
8. JNDI API 는 응답을 Application 에 보낸다.

Application 은 내가 배포한 my-api.jar 를 사용하여 JNDI 연결을 시도한다.

🔍 Using JNDI API

Java 에서는 실제로 Namaing Service에 접근하기 위한 클래스를 제공하는 데 그중 가장 중요한 클래스는 Context와 InitialContext이다.

🚩 javax.naming.Context

• JNDI 명세에 기반한 Interface 이다.
• Object 를 생성, 추가, 조회, 수정, 조회 가능한 Method를 제공한다.
• 이 인터페이스는 Vendor에 의해서 구현되어야 한다.

🚩 javax.naming.InitialContext

• javax.naming.Context 의 구현체이다.
• 객체 이름을 확인하기 위한 시작점을 제공한다.
• Naming Service의 환경 정보는 InitialContext 생성자 파라미터로 전달된다.
• InitialContext를 생성할 때 Context를 바로 생성 할지 아니면 사용 전까지 대기 할지는 Vendor 의 구현을 따른다. "젠장, 문제의 원인을 밝히기 위해서는 JBoss의 Naming Service가 어떻게 동작하지는도 확인해 봐야 할 것 같다. 💧"

javax.naming.InitialContext 생성을 위서는 Servier Provider 정보가 필요한다. 속성값으로 전달한다.

첫째, INITIAL_CONTEXT_FACTORY 설정

• KEY: Context.INITIAL_CONTEXT_FACTORY
• VALUE: org.jnp.interfaces.NamingContextFactory

org.jnp.interfaces.NamingContextFactory는 javax.naming.spi.InitialContextFactory의 구현체로 JBoss Naming Service를 사용할 수 있게 해준다.

둘째, PROVIDER_URL 설정

• KEY: Context.PROVIDER_URL
• VALUE: IP:PORT

IP:PORT는 해당 IP와 PORT로 Naming Service 제공하는 서버를 가르킨다.

전체 코드는 🔑 Problem 파트에서 보여준 Problem Code 와 동일하다. jboss-as-all-client.jar가 ClassPath에 있다면 해당 코드는 문제 없이 컴파일 되는 것을 확인 할 수 있다. JNDI Connect Code

public class App {
    public static void main(String[] args) {
        try {
            Properties properties = new Properties();
            properties.put(Context.SECURITY_PRINCIPAL, "guest");
            properties.put(Context.SECURITY_CREDENTIALS, "guest");
            properties.put(Context.PROVIDER_URL, "IP:PORT");
            properties.put(Context.INITIAL_CONTEXT_FACTORY, 
            "org.jnp.interfaces.NamingContextFactory");

            // the error occur on this line!
            Context context = new InitialContext(properties);
        } catch (NamingException e) {
            throw new RuntimeException(e);
        }
    }
}

그럼 동일한 코드인데 왜 에러가 발생하고 Reconnect이 되지 않았을까? 우리는 그 단서를 로그에서 찾을 수 있다.

at jeus.service.archive.ArchiveArrayClassLoader.getResources(ArchiveArrayClassLoader.java:256)
at com.sun.naming.internal.ResourceManager.getApplicationResources(ResourceManager.java:571)
at com.sun.naming.internal.ResourceManager.getInitialEnvironment(ResourceManager.java:256)
at javax.naming.InitialContext.init(InitialContext.java:251)
at javax.naming.InitialContext.<init>(InitialContext.java:227)

InitialContext 에서 Context를 생성하기 위해서 뭔가를 찾는거 같은데 뭘 찾는 걸까? 🚩 javax.naming.InitialContext에서 이야기했지만 Context를 생성하는 건 Vendor 의존적이다. Reconnect 할때 InitialContext 에서 발생하는 에러를 이해하기 위해서는 JBoss Naming Service가 동작하는지 먼저 이해해야 한다.

🔍 Understanding the JBossNS

JBossNS 는 Java socket과 RMI 기반의 javax.naming.Context 인터페이스의 구현체이다. Client와 Server 구조로 되어있어 서로 다른 JVM에서 서비스를 연결하는 것에 최적화 되어 있다. 같은 JVM 을 사용할 경우 socket이 사용하지 않으며, 그대신 global singleton 처럼 객체에 접근을 가능하도록 설계되어 있다.

아래 JBossNS 를 구성하는 주요 클래스 구성도만 보아도 앞서 이야기한 JNDI Connect Code 가 어떻게 동작할지 대략적으로 짐작할 수 있을 것 같다.

하지만 왜 에러가 발생하는지 원인을 알기 위해서는 javax.naming.InitialContext가 어떻게 javax.naming.Context를 생성하는지 상세히 알아야 한다.

Client에서 JBossNS 속성과 함께 InitialContext 를 생성할 때, Context 를 생성하기 위해서 org.jnp.interfaces.NamingContextFactory 가 사용된다. NamingContextFactory 는 javax.naming.spi.InitialContextFactory 인터페이스의 JBossNS 구현체 이다. NamingContextFactory 가 Context 를 생성하라고 요청받으면, InitialContext 의 생성자 파라미터의 환경 정보와 전역 JNDI Namespace를 이용하여 org.jnp.interfaces.NamingContext를 생성한다.

JNDI determines each property's value by merging the values from the following two sources, in order:

1. The first occurrence of the property from the constructor's environment parameter and (for appropriate properties) the applet parameters and system properties.
2. The application resource files (jndi.properties). 출처 : javadoc-InitialContext

NamingContext는 실제 Context의 구현체이고, JBossNS 서버에 연결하는 작업을 수행한다. Context.PROVIDER_URL는 NamingServer 의 RMI Reference 를 가르키고 있다.

NamingContext 인스턴스와 NamingServer 의 연결은 Context의 첫 번째 동작에서 이루어진다. 즉, InitialContext를 생성할 때 Context를 생성하지 않는다 뜻이다. Lazy Fashion하게 동작한다. Context 에서 어떤 작업을 수행할 때, NamingContext는 NamingServer와 연결을 확인한다. 연결이 없다면 NamingContext는 Context.PROVIDER_URL 값을 확인한다. PROVIDER_URL 값이 존재 한다면, NamingContext 는 Naming 인스턴스를 찾기위해 NamingContext class static map에서 host와 port 값으로 이루어진 Key를 찾는다. Key(Host와 Port 의 쌍으로 이루어진 값)가 존재하면 Naming 인스턴스가 이미 생성되어 JVM상에 존재하고 있으므로 이미 생성된 Naming 인스턴스를 사용한다. Key가 없으면, NamingContext는 java.net.Socket을 사용하여 Naming RMI stub을 JBossNS Server로 부터 얻어온다. NamingContext는 새로이 얻어온 Naming 객체를 NamingContext server map 저장한다.

요약하면,

1. org.jnp.interfaces.NamingContextFactory 는 org.jnp.interfaces.NamingContext 생성
2. NamingContext 는 이미 JBossNS Server연결 하여 Naming(JBossNS에서의 Context) 객체가 JVM에 있는지 확인
3. 없고 처음이면 JBossNS Server 부터 Naming를 받아 옴
4. 받아온 Naming 객체를 Chache에 저장

Context.PROVIDER_URL 값이 존재 하지 않는 경우는 단순하게 Main MBean 에서 값을 가져온다.

Context 의 구현체인 NamingContext는 모든 동작을 Naming 인스턴스에 위임한다. 대신, NamingContext 는 전달받은 JNDI Name을 JBossNS server 가 인식할 수 있는 이름으로 변경한다. 왜냐면 JNDI Name 은 매우 상대적이거나 URL 일수 있기 때문이다. 이런 기능을 제공함으로써 NamingContext는 Naming 의 Context 역할을 수행한다.

정상적인 상황에서 Heap Dump 와 Thread Dump를 확인해 보면 필요한 클래스가 모두 있다는 걸 확인 할 수 있다.

3CLTEXTCLASS               org/jnp/interfaces/NamingContextFactory(0x0000000031587200)

3CLTEXTCLASS               org/jnp/interfaces/NamingContext(0x0000000031589D00)

3CLTEXTCLASS               org/jnp/server/NamingServer_Stub(0x0000000031595600)

3CLTEXTCLASS               org/jnp/interfaces/Naming(0x0000000031594F00)

문제의 발생은 org/jnp/interfaces/Naming 각 Heap 존재 하지 않아 발생하는 것이 아닐까? 유추해 볼수 있다.

4월에 있을 다음 재현 테스트 내 가정이 맞을지 틀릴지 확인 할 수 있겠지!

🍰 Epilogue

글로 정리하는게 너무 어려웠다. 솔직히 너무 어려워 이 글을 누가 볼까 싶다. 이 글을 완성하고 나서 더러운 기분이 모두 사라졌다. 내가 세운 논리가 완벽하고 조화롭다. 여기까지 스스로 생각하고 이루어낸 내가 너무도 대견하다. 👏

나는 돈을 은행에 보관하고 싶다. 은행 계좌가 없으므로 은행가서 계좌를 만들었다. 그 은행계좌를 종이에 적어 금고에 넣어 둔다. 은행에 송금하려고 하는데 송금이 되지 않는다. 난 계좌가 적힌 종이를 확인하려 금고를 열었다. 어! 종이는 있는데 계좌가 지워져 있네. 계좌번호를 알기위해 난 어떻게 해야 할까?

🛰️ Reference Site

• Java Naming and Directory Interface (JNDI), JNDI Architecture
• Java Authentication Service Provider Interface for Containers
• 6.2. The JBossNS Architecture
• 6.3. The Naming InitialContext Factories
• Looking Up the Data Source Using JNDI To Obtain a Connection
• InitialContext
• jndi tutorial
• ibm jvm-classloader-hierarchy
• classloader
• How to do Log4j2 Vulnerability Analysis with Wireshark
• J2EE Platform Overview

• 20<sup>th</sup> January 2023

🔑 Problem

강의를 듣는데 처음보는 ord() 함수! 너는 누구니?

🛰️ Reference Site

• ord() function in Python

🎽 Learn

1. About ord() function

• ord() 는 인수(argument) 에 해당하는 Unicode를 반환한다.
• 인수(argument)는 8bit string 이다.

2. ord() syntax

ord(ch)

3. ord() example

ord() 는 8bit로 표현할 수 있는 unicode를 인수(argument)로 받을 수 있음을 확인 한다.

** 🚩 영문자를 인수로 넘기면,**

• 'a' 를 인수로 넘기면 'a'에 해당하는 97을 반환한다.

  print(ord('a'))

output

97

** 🚩 한글을 인수로 넘기면,**

• ord()는 인수(argument)로 8bit string 를 허용한다.
• '가' 를 파라미터로 넘기면 44032가 반환된다.

  print(ord('가'))

output

44032

** 🚩 특수문자를 인수로 넘기면,**

print(ord('★'))

output

9733

** 🚩 8bit 이상되는 문자를 인수로 넘기면,**

• 8bit를 초과 했으므로 에러가 발생한다.

  print(ord('ab'))

output

Traceback (most recent call last):
  File "d:\vscode_ws\DataStructure_N_Algorithm\ord_function_example.py", line 10, in <module>
    print(ord('ab'))
TypeError: ord() expected a character, but string of length 2 found

Linked List 를 구현하기 전에 간단하게 Linked List 에 대해 정리하고 넘어가자.

Linked List 는 문자 그대로, item 이 물리적으로 연결된 구조를 갖는다. Linked List에 item을 node 라고 부르는데, node는 2개의 field로 이루어져 있다.

1. Data : 값을 저장하고 있다.
2. Next : 다음 node 참조 값을 저장하고 있다.

그림으로 표현하면 아래와 같이 생겼다.

Linked List에서 가장 앞의 node 를 특별하게 head라고 부르는다. 우리는 head를 시작점으로 list를 순회 할 수 있다.

Requirement

내가 제작하려는 Linked List 의 요구사항은 아래와 같다.

• List 를 이용하여 Linked List 를 초기화 할 수 있을 것.
• print() 함수를 사용하여 Linked List 의 모든 Node 를 출력할 수 있을 것.
• Linked List를 iterable 하게 구성할 것.
• Node 를 제일 앞에 추가하는 함수를 구현할 것.
• Node 를 제일 끝에 추가하는 함수를 구현할 것.
• 특정 Node 앞에 새로운 Node 를 추가하는 함수를 구현할 것.
• 특정 Node 뒤에 새로운 Node 를 추가하는 함수를 구현할 것.
• 특정 Node 를 삭제하는 함수를 구현할 것.

Implement

A. 데이터를 저장하는 Node Class를 정의한다.

class Node:
    def __init__(self, data):
        self.data = data
        self.next = None

    def __str__(self):
        return str(self.data)

B. Node를 관리하는 LinkedList Class를 정의한다.

class LinkedList:
    pass

C. LinkedList Class에 List를 이용하여 Linked List를 초기화 하는 init() 함수를 구현한다.

def __init__(self, nodes=None):
    self.head = None

    if nodes is None:
        return

    node = Node(nodes[0])
    self.head=node

    nodes.remove(nodes[0])

    for element in nodes:
        nextNode = Node(element)
        node.next = nextNode
        node = nextNode

List 를 사용하여 LinkedList를 초기화 할수 있는지 확인한다.

linkedList = LinkedList(["A", "B", "C", "D", "E"])

node = linkedList.head
while node is not None:
    print(node.data)
    node = node.next

Output:

A
B
C
D
E

D. print()를 손쉽게 하기 위해 str() 함수를 추가한다.

def __str__(self):
    nodes = []
    node = self.head
    while node is not None:
        nodes.append(str(node.data))
        node = node.next

    nodes.append(str(None))
    return ' -> '.join(nodes)

___str__() 함수가 정상적으로 동작하는지 확인한다.

linkedList = LinkedList(["A", "B", "C", "D", "E"])
print(linkedList)

Output:

A -> B -> C -> D -> E -> None

E. LinkedList Class 를 iterable하게 만든다.

iterater 프로토콜을 구현하기 위해 __iter__() 함수를 Generator 로 구현한다.

def __iter__(self):
    node = self.head
    while node is not None:
        yield node
        node = node.next

LinkedList 가 iterable 하기 때문에 이제 for 문을 사용할 수 있다.

linkedList = LinkedList(["A", "B", "C", "D", "E"])


for element in linkedList:
    print(ele)

Output:

A
B
C
D
E

F. Data를 LinkedList 제일 앞에 추가하는 함수를 구현한다.

def add_first(self, data):
    node = Node(data)
    node.next = self.head
    self.head = node

1. 새로운 Node의 next를 head를 가르키게 한다.
2. head를 새로운 Node로 변경한다.

linkedList = LinkedList(["A", "B", "C", "D", "E"])
print(linkedList)
linkedList.add_first("0")
print(linkedList)

Output

A -> B -> C -> D -> E -> None
0 -> A -> B -> C -> D -> E -> None

G. Data를 LinkedList 제일 끝에 추가하는 함수를 구현한다.

def add_last(self, data):
    newNode = Node(data)

    node = self.head
    while node.next is not None:
        node = node.next

    node.next = newNode

1. 맨 마지막 노드(node.next 가 None 인 것)를 찾는다.
2. 마지막 노드에 새로운 Node 를 추가한다.

linkedList = LinkedList(["A", "B", "C", "D", "E"])
print(linkedList)
linkedList.add_last("F")
print(linkedList)

Output

A -> B -> C -> D -> E -> None
A -> B -> C -> D -> E -> F -> None

H. 특정 노드 앞에 Data를 추가하는 함수를 구현한다.

def add_before(self, target, addData):
    newNode = Node(addData)

    node = self.head
    while True:
        if node is None:
            raise Exception('Can not find value: ' + str(addData))

        if node.data == str(target):
            preNode.next = newNode
            newNode.next = node
            break
        preNode = node
        node = node.next

1. node 가 None 이면 Exception을 발생시킨다. 1-1. node 가 None이라는 건 데이터를 찾지 못한 경우이다.
2. node.data 가 target 과 동일 한지 확인한다.
3. 동일하면, 3-1. 이전 node.next에 newNode를 추가한다. 3-2. newNode.next에 현재 node를 추가한다.

target 앞에 추가해야 함으로, 이전 node 정보를 저장하고 있어야 한다.

preNode = node
node = node.next

target을 못 찾는 경우, 에러가 발생하는지 확인한다.

linkedList = LinkedList(["A", "B", "C", "D", "E"])
linkedList.add_before("F", "0")
print(linkedList)

output

Traceback (most recent call last):
  File "d:\vscode_ws\DataStructure_N_Algorithm\LinkedList.py", line 75, in <module>
    linkedList.add_before("F", "0")
  File "d:\vscode_ws\DataStructure_N_Algorithm\LinkedList.py", line 61, in add_before
    raise Exception('Can not find value: ' + str(addData))
Exception: Can not find value: 0

C 앞에 0을 추가한다.

linkedList = LinkedList(["A", "B", "C", "D", "E"])

print(linkedList)
linkedList.add_before("C", "0")
print(linkedList)

output

A -> B -> C -> D -> E -> None
A -> B -> 0 -> C -> D -> E -> None

I. 특정 노드 뒤에 Data를 추가하는 함수를 구현한다.

def add_after(self, target, addData):
    newNode = Node(addData)

    node = self.head
    while True:            
        if node is None:
            raise Exception('Can not find value: ' + str(target))

        if node.data == str(target):
            newNode.next = node.next
            node.next = newNode
            break

        node = node.next

1. node 가 None 이면 Exception을 발생시킨다. 1-1. node 가 None이라는 건 데이터를 찾지 못한 경우이다.
2. node.data 가 target 과 동일 한지 확인한다.
3. 동일하면, 3-1. newNode.next에 node.next를 연결 시킨다. 3-2. node.next에 newNode를 연결 시킨다.

C 뒤에 0을 추가한다.

linkedList = LinkedList(["A", "B", "C", "D", "E"])

print(linkedList)
linkedList.add_after("C", "0")
print(linkedList)

output

A -> B -> C -> D -> E -> None
A -> B -> C -> 0 -> D -> E -> None

J. 특정 노드를 삭제하는 함수를 구현한다.

def remove(self, target):

    if self.head.data == str(target):
        self.head = self.head.next
        return

    node = self.head

    while True:
        if node is None:
            raise Exception('Can not find value: ' + str(target))

        if node.data == str(target):
            preNode.next = node.next
            del node
            break

        preNode = node
        node = node.next

1. head.data 와 target 동일하다면, 1-1. head가 head.next를 가르키게 한다.
2. head.data 와 target 다르면, 2-1. 순회하면서 target 같은 값을 가진 Node를 찾는다.
3. node.data 가 target 과 동일하면 3-1. 이전 node.next에 현재 node.next를 연결시킨다. 3-2. 현재 node를 삭제한다.

head 값, 제일 앞에 있는 값을 삭제한다.

linkedList = LinkedList(["A", "B", "C", "D", "E"])
print(linkedList)
linkedList.remove("A")
print(linkedList)

output

A -> B -> C -> D -> E -> None
B -> C -> D -> E -> None

중간 값을 삭제한다.

linkedList = LinkedList(["A", "B", "C", "D", "E"])
print(linkedList)
linkedList.remove("B")
print(linkedList)

output

A -> B -> C -> D -> E -> None
A -> C -> D -> E -> None

마지막 값을 삭제한다.

linkedList = LinkedList(["A", "B", "C", "D", "E"])
print(linkedList)
linkedList.remove("E")
print(linkedList)

output

A -> B -> C -> D -> E -> None
A -> B -> C -> D -> None

Reference

Linked Lists in Python: An Introduction

• 10<sup>th</sup> January 2023

🔑 Problem

Buffer에 쓴다고 하는데 read() 함수를 사용한다. Buffer로 부터 읽는데 write() 함수를 사용한다.

이해가 되지 않는다. 도대체 왜 저리 만들었을까?

Writing Data to a Buffer

//read into buffer.
int bytesRead = inChannel.read(buf); 

Reading Data from a Buffer

//read from buffer into channel.
int bytesWritten = inChannel.write(buf);

* note *

개발하면서 Channel과 Buffer를 사용했던 기억이 있다. 근데 왜, 모르는 것이냐!

🛰️ Reference Site

• Java NIO Buffer

🎽 Learn

1. Channel 과 Buffer의 사전적 정의

일단 Channel 과 Buffer를 사전적 정의를 확인하자.

• Channel

  noun. a medium for communication or the passage of information

• verb.* direct toward a paricular end or object

• Buffer

  noun. COMPUTING a temporary memory area in which data is stored while it is being processed or transferred, especially one used while streaming video or downloading audio.

Buffer는 컴퓨터 공학에서 어떤 의미로 사용되는지 사전에서 확인 할 수 있다. 하지만 Channel은 우리가 아는 것과 조금 다르다. 단순히 TV Channel이 아니다.

Oxford Languages 에 따르면 Channel의 정의에는 의사 소통 또는 정보 전달을 위한 매개체 정의가 포함되어 있다.

2. Channel 과 Buffer의 역할

우리는 매개체(medium)라는 말에 집중 할 필요가 있다. 매개체는 맺어 주는 행위에 집중하는 단어이다. Java NIO에서도 Channel은 매개체이다.

매개체 중간에서 어떤 일을 맺어 주는 것.

현실에서 매개체가 끝이라고 생각하지 않듯 Programming에서도 Channel 끝이 아니다. Programming에서 끝은 정보를 저장할 수 있는 무엇이라 생각할 수 있다. Programming에서 끝은 파일과 메모리이다. Programmer는 끝에 접근하여 데이터를 변경한다. 매개체를 이용하여 데이터를 전송한다.

• Programmer는 Channel을 이용하여 데이터를 전송한다.
• Programmer는 Buffer에 접근하여 데이터를 변경한다.

3. read() 와 write() 동작

이제 Channel의 read()와 write() 가 어떻게 동작하는지 살펴보자.

Channel 얻어오기

아래는 FileChannel 을 얻어 오는 코드이다.

RandomAccessFile file = new RandomAccessFile("data/data.txt", "rw");
FileChannel fileChannel = file.getChannel();

FileChannel 은 file.getChannel() 함수를 통해 얻어지는 것을 확인 할 수 있다. 그러므로 FileChannel은 File에 종속되어 있다. 동일하게 SocketChannel 은 Socket 에 종속되어 있고 ServerSocketChannel 은 ServerSocket에 종속되어 있다.

Channel 의 read() 함수

read() 함수는 Channel이 종속된 Datasource에서 데이터를 읽어온다. 아래의 소스 코드에서 Datasource는 File이다. Channel은 File에서 데이터를 읽어와 Buffer 로 보낸다.

RandomAccessFile file = new RandomAccessFile("data/data.txt", "rw");
FileChannel fileChannel = file.getChannel();

ByteBuffer buffer = ByteBuffer.allocate(48);
int bytesRead = fileChannel.read(buffer)

• Channel은 Datasource 로 부터 데이터를 읽는다.

  

• 읽은 데이터를 Buffer 에 쓴다.

  

Channel 의 write() 함수

read() 함수는 Channel이 종속된 Datasource에 데이터를 쓴다. 그럼 어떤 데이터를 쓸까?? Buffer 에 있는 데이터를 Datasource에 쓴다.

• Channel은 Datasource에 데이터를 쓴다.

  

• Buffer 로 부터 읽어온 데이터를 쓴다.

  

🎁 Summary

이렇게 정리하면 될 것 같다.

FileChannel fileChannel = file.getChannel();
SocketChannel socketChannel = SocketChannel.open();
ServerSocketChannel serverSocketChannle = ServerSocketChannel.open();

• Channel은 Datasource 종속된 매개체이다.

int bytesRead = inChannel.read(buf); 

• Channel 이 read() 하는 대상은 Datasource 이다.
• read() 한 데이터를 어디로 보낼까 ? Buffer로 보낸다.

//read from buffer into channel.
int bytesWritten = inChannel.write(buf);

• Channel 이 write() 하는 대상은 Datasource 이다.
• 어떤 데이터를 write() 할까? Buffer 있는 데이터이다.

시스템을 잘 관리하기 위해서는 프로그램을 주기적으로 Restart 해주는 것이 좋다. 서버를 Restart하면 더 좋고! 하지만, 대부분의 시스템은 복잡하게 얽혀 있어 시스템을 재시작하는 건 간단하지 않다. 신경 쓸 것이 한 두개가 아니다.

그중에 가장 신경 써야 하는 건 고객들! 정해진 시간 동안 시스템에 접근할 수 없다고 고객에게 공지해야 한다. 그리고 정상적으로 연결 되었는지 확인하라고 요청해야 한다. 고객들에게 정중하게 메일을 보낸다.

"고객님, 시스템 휴지가 있습니다. 2시간 동안 시스템 접근이 불가능합니다."

문제가 발생하자 고객은 일단 메일을 받은 적이 없다고 우긴다. 결국, 우린 너무 고귀해서 모니터링 같은거 못하겠다고 한다. 시스템 모니터링은 너희가 해줘야 하는 서비스라고 한다.

고객님! 이러시면 안 되요! 👿

🔑 Problem

내가 관리하는 시스템은 서버 역할하고 고객 시스템은 클라이언트 역할을 한다. 서버와 클라이언트가 연결되어 있는 상태에서 서버를 재 시작한다. 서버는 어떤 클라이언트가 성공적으로 연결되었는지 알 수 있으나, 연결되지 않은 클라이언트가 어떤 상태인지는 알 수 없다.

• 고객 시스템에 연결 상태를 알 수 없다.

💡 Idea

시스템 상태는 로그에 쓰여진다. 우린 로그만 있으면 고객 시스템의 상태를 확인 할 수 있다.

• 원격지에 있는 EndPoint의 로그를 수집하자!

📝 Requirement

고객의 요구사항은 다음과 같다.

• 시스템 변경을 최소화 해야 함.
  • 고객 시스템에 새로운 프로그램 설치 금지
  • 참조 Library 변경 최소화
  • Cross Platform 지원
  • Perform에 영향을 미치지 않을 것
• Logstash Input plugins이 제공되는 Middleware를 사용해야 함.

✂️ Analyze

내가 관리하는 시스템의 로깅 환경부터 확인한다.

• jdk1.7
• log4j1.2.11

🍰 Solve

나는 이 문제를 SocketAppender를 이용해 풀어보려한다. 일단 컨셉일 뿐이고 대용량 시스템에 어떻게 적용해야 할지는 꽤나 많은 검증이 필요하다. 아래 소스코드는 Github 에서 확인 가능하다.

1. SocketAppender를 사용한다.

SocketAppender를 선택한 이유는 3가지 이다.

• Log4j1.2.11에서 제공하는 기본적인 Appender
• 현재 상태에서 추가되는 라이브러리 없음
• Logstash 에서 SocketAppender를 위한 Input Plugins를 제공 함

SocketAppender는 고객 요구사항에 완벽하게 부합한다.

2. SimpleSocketServer 실행시키자!

SimpleSocketServer 는 특정 Port 로 부터 송신된 로그를 수신한다. 그리고 자체적으로 로그를 생성한다. 사용 방법은 매우 단순하며, log4j1.2 Javadoc에서 확인 할 수 있다.

Usage: java org.apache.log4j.net.SimpleSocketServer port configFile where port is a part number where the server listens and configFile is a configuration file fed to the PropertyConfigurator or to DOMConfigurator if an XML file.

SimpleSocketServer 가 사용하는 <Port> 는 9999를 사용하기로 한다. 자제적으로 생성하는 로그는 <configFile>을 통해 설정하는데, 단순하게 콘솔화면으로 출력하도록 구성한다.

# log4j-server.properties
log4j.rootLogger=INFO,stdout

# stdout
log4j.appender.stdout=org.apache.log4j.ConsoleAppender
log4j.appender.stdout.layout=org.apache.log4j.PatternLayout
log4j.appender.stdout.layout.ConversionPattern=%t :: %d :: %m%n

위 내용을 log4j-server.properties 파일로 적당한 위치에 저장한다. 나 같은 경우는 D:/log4j-socket-server에 저장하였다. 그리고 아래 명령으로 서버를 실행한다.

java -classpath d:/log4j-socket-server/Log4j-1.2.11.jar org.apache.log4j.net.SimpleSocketServer 9999 D:/log4j-socket-server/log4j-server.properties

3. SocketAppender 구성하자!

다음으로 SimpleSocketServer로 로그를 전송하는 SocketAppender를 구성하자. SocketAppender 는 LoggingEvent 객체를 원격 로그 서버로 전송하는 역할을 담당한다.

SocketAppender의 특성은 log4j1.2 Javadoc 에서 확인 할 수 있다.

내가 관리하는 시스템은 Programatically 하게 log4j 를 사용하므로 아래와 같이 Log4jSocketAppenderTest.java 를 작성하여 실행한다.

package com.choong.log4j.test;

import org.apache.log4j.ConsoleAppender;
import org.apache.log4j.Logger;
import org.apache.log4j.PatternLayout;
import org.apache.log4j.net.SocketAppender;

public class Log4jSocketAppenderTest {
    public static void main(String[] args) {
        Logger logger = Logger.getLogger(Log4jSocketAppenderTest.class);

        PatternLayout patternLayout = new PatternLayout("%t :: %d :: %m%n");

        ConsoleAppender consoleAppender = new ConsoleAppender(patternLayout);
        SocketAppender socketAppender = new SocketAppender("localhost", 9999);

        logger.addAppender(consoleAppender);
        logger.addAppender(socketAppender);

        logger.info("Hello, ChoongYul!");
    }
}

4. SimpleSocketServer 출력결과

마지막으로 SimpleSocketServer 의 출력결과를 확인한다.

ouput:

D:\>java -classpath d:/log4j-socket-server/Log4j-1.2.11.jar org.apache.log4j.net.SimpleSocketServer 9999 D:/log4j-socket-server/log4j-server.properties
main :: 2023-01-08 12:57:10,386 :: Listening on port 9999
main :: 2023-01-08 12:57:10,417 :: Waiting to accept a new client.
main :: 2023-01-08 12:57:25,681 :: Connected to client at /127.0.0.1
main :: 2023-01-08 12:57:25,682 :: Starting new socket node.
main :: 2023-01-08 12:57:26,117 :: Waiting to accept a new client.
main :: 2023-01-08 12:57:25,774 :: Hello, ChoongYul!
Thread-0 :: 2023-01-08 12:57:26,385 :: Caught java.net.SocketException closing conneciton.

• 9999 Port로 새로운 클라이언트가 연결되었고,
• 클라이언트는 'Hello, ChoongYul!' 이라는 로그를 전송했다.
• SimpleSocketServer는 log4j-server.properties에서 설정한 ConsoleAppender를 통해 'Hello, ChoongYul!'을 출력하였다.

🛰️ Reference Site

• log4j: How to use SocketAppender?
• Using log4j's SocketAppender
• sockAppender로 log4j 로그 입력
• SimpleSocketServer.java
• Log4j SocketAppender. Logstash :

• 5<sup>th</sup> January 2023

🔑 Problem

• python으로 LinkedList 를 자료구조를 구현해보라고?

* note *

LinkedList 를 언제쯤 구현할 수 있을까? 이제 __iter__() 함수가 보인다. iterator 와 iterable 의 차이는 또 무엇인고? 아~ 진짜 LinkedList 만들기 어렵다.

🛰️ Reference Site

• iterable
• iterator
• iterator-types
• generator-types

🎽 Learn

왜? Iterable 과 Iterator 를 나누어 놓아서 혼란스럽게 하나? 굳이 구분해야 싶기도 하다.

일단 모르니, 정의 부터!

1. Iterable 과 Iterator 의 정의

파이썬 공식문서를 보면 Iterable 과 Iterator 를 아래와 같이 정의한다.

• Iterable

  An object capable of returning its members one at a time. Examples of iterables include all sequence types (such as list, str, and tuple) and some non-sequence types like dict, file objects, and objects of any classes you define with an __iter__() method or with a __getitem__() method that implements sequence semantics. Iterables can be used in a for loop and in many other places where a sequence is needed (zip(), map(), …). When an iterable object is passed as an argument to the built-in function iter(), it returns an iterator for the object. This iterator is good for one pass over the set of values. When using iterables, it is usually not necessary to call iter() or deal with iterator objects yourself. The for statement does that automatically for you, creating a temporary unnamed variable to hold the iterator for the duration of the loop. See also iterator, sequence, and generator.

• Iterator

  An object representing a stream of data. Repeated calls to the iterator’s __next__() method (or passing it to the built-in function next()) return successive items in the stream. When no more data are available a StopIteration exception is raised instead. At this point, the iterator object is exhausted and any further calls to its __next__() method just raise StopIteration again. Iterators are required to have an __iter__() method that returns the iterator object itself so every iterator is also iterable and may be used in most places where other iterables are accepted. One notable exception is code which attempts multiple iteration passes. A container object (such as a list) produces a fresh new iterator each time you pass it to the iter() function or use it in a for loop. Attempting this with an iterator will just return the same exhausted iterator object used in the previous iteration pass, making it appear like an empty container.

그래서 저 영어 속에서 차이를 어떻게 찾아내야 하냐고!

2. Iterable 과 Iterator 의 차이

Iterator 는 간단히 말해

* 연속적인 데이터를 저장하고 객체이다. 그리고 반복적인next() 를 사용하여 연속적인 item 에 접근할 수 있어야 한다. *

An object representing a stream of data. Repeated calls to the iterator’s __next__() method (or passing it to the built-in function next()) return successive items in the stream.

여기서 한번 더 집고 넘어가야 할건! next() 함수를 _명시적_으로 사용할 수 있어야 Iterator 이다.

그럼, Iterable 은 무엇일까?

한 번에 하나씩 저장된 값들을 가져올 수 있는 객체다.

An object capable of returning its members one at a time.

아래의 MyCount 클래스는 Iterable 하지만 Iterator는 아니다.

for 문으로 한 번에 하나씩 저장된 값들을 가져 올 수 있지만, 명시적으로 iter() 와 next()를 호출 할수 없기 때문이다.

class MyCount:
    def __init__(self, stop):
        self.start = 1
        self.stop = stop

    def __iter__(self):
       while self.start != self.stop:
        yield int(self.start)
        self.start = self.start +1

myCount = MyCount(10)
for i in myCount:
    print(i)

iterMyCount = iter(myCount)
print(next(iterMyCount))

output

1
2
3
4
5
6
7
8
9

Traceback (most recent call last):
  File "/workspace/firstContainer/data_structure/Iterable_Test.py", line 15, in <module>
    next(myCount)
TypeError: 'MyCount' object is not an iterator

MyCount 같은 클래스를 Generator Types의 iterator 라고 한다.

🎁 Summary

자! 이렇게 정리하자!

• Iterator : 명시적으로 next() 와 iter()를 호출할 수 있는 것
• Iterable : 암묵적으로 next() 와 iter()를 호출할 수 있는 것

• 3<sup>rd</sup> January 2023

🔑 Problem

• python으로 LinkedList 를 자료구조를 구현해보라고?

* note *

LinkedList 를 구현한 걸 인터넷에서 찾아 보니 __repr__(self) 함수가 보인다. 안의 내용은LinkedList 내부 노드를 출력하기 위해 한 것인데 처음 보는 놈이다. 아놔 저건 뭐하는 놈인고!

🛰️ Reference Site

• Understanding The Python repr Mehtod
• 점프 투 파이썬 - 라이브러리 예제 편 - 05 str() 함수와 repr() 함수

🎽 Learn

클래스를 정의할 때 __init__ 함수를 정의하게 된다. 이렇게 함수명 앞뒤로 __ 가 붙어 있는 함수를 Dunder 또는 Magic 함수 라고 부른다.

1. Dunder 또는 Magic 함수 란?

• 파이썬에서 Dunder 또는 Magic 함수란 함수명 앞뒤로 __ 언더스코어가 붙은 함수를 말한다.
• 파이썬 내장 클래스인 int 함수를 살펴보면, 많은 Dunder 함수가 정의되어 있음을 확인할 수 있다.

>>> print(dir(int))

output:

['__abs__', '__add__', '__and__', '__bool__', '__ceil__', '__class__', '__delattr__', '__dir__', '__divmod__', '__doc__', '__eq__', '__float__', '__floor__', '__floordiv__', '__format__', '__ge__', '__getattribute__
', '__getnewargs__', '__gt__', '__hash__', '__index__', '__init__', '__init_subclass__', '__int__', '__invert__', '__le__', '__lshift__', '__lt__', '__mod__', '__mul__', '__ne__', '__neg__', '__new__', '__or__', '__
pos__', '__pow__', '__radd__', '__rand__', '__rdivmod__', '__reduce__', '__reduce_ex__', '__repr__', '__rfloordiv__', '__rlshift__', '__rmod__', '__rmul__', '__ror__', '__round__', '__rpow__', '__rrshift__', '__rshi
ft__', '__rsub__', '__rtruediv__', '__rxor__', '__setattr__', '__sizeof__', '__str__', '__sub__', '__subclasshook__', '__truediv__', '__trunc__', '__xor__', 'bit_length', 'conjugate', 'denominator', 'from_bytes', 'i
mag', 'numerator', 'real', 'to_bytes']

__repr__ 함수를 처음 봤을 때는 java 의 toString 과 비슷한 줄 알았다. 하지만, 공식 문서를 찾아 보니 전혀 아니다.

2. repr(object) 함수란?

Return a string containing a printable representation of an object. For many types, this function makes an attempt to return a string that would yield an object with the same value when passed to eval(); otherwise, the representation is a string enclosed in angle brackets that contains the name of the type of the object together with additional information often including the name and address of the object. A class can control what this function returns for its instances by defining a __repr__() method. If sys.displayhook() is not accessible, this function will raise RuntimeError.

"Return a string containing a printable representation of an object" 문장 때문에 __repr__() 을 __str__() 처럼 재 정의 해서 사용하는 경우가 있는 것이 아닌지?

더 중요한 건!

* eval(repr(object)) 를 했을 때 객체를 생성할 수 있어야 한다는 것! * 이다.

예를 들어 설명하면,

• repr() 함수를 사용하면 eval() 함수로 객체를 생성할 수 있다.

  a = 'Difference between str() and repr()'
  b = repr(a)
  c = eval(b)
  

print(c)

output:

Difference between str() and repr()

* `str()` 을 사용하면 `eval()` 함수로 객체를 사용할 수 없다.

```python
a = 'Difference between str() and repr()'
b = str(a) # b에 str(a) 를 사용한 것에 집중!
c = eval(b)

output:

Traceback (most recent call last):
  File "/workspace/firstContainer/data_structure/Person.py", line 27, in <module>
    c = eval(b)
  File "<string>", line 1
    Difference between str() and repr()
                     ^
SyntaxError: invalid syntax

3. __repr()__ 함수를 재정의 해보자!

이제 __repr()__ 함수를 재정의 하여 eval() 를 이용하여 객체를 생성할 수 있도록 하자.

class Person:
    def __init__(self, name, age):
        self.name = name
        self.age = age

클래스를 위와 같이 정리해 놓고 객체를 생성하여 print() 로 출력해 보자. 한 번은 그냥 출력하고, 또 한번은 repr() 함수를 사용하여 출력한다.

tom = Person('Tom', 20)
print(tom)
print(repr(tom))

output:

<__main__.Person object at 0x7f85cd1dd490>
<__main__.Person object at 0x7f85cd1dd490>

print(tom) 와 print(repr(tom)) 모두 동일한 값을 출력 함을 알 수 있다.

이제 __str()__ 함수를 재정의 하고 객체를 print() 로 출력해 보자.

class Person:
    def __init__(self, name, age):
        self.name = name
        self.age = age

    def __del__(self):
        print('Bye! Bye! ' + self.name)

    def __str__(self):
        return 'My name is ' + self.name + '. I am ' + str(self.age) + '.'

tom = Person('Tom', 20)
print(tom)
print(repr(tom))

output:

My name is Tom. I am 20.
<__main__.Person object at 0x7f27e44a9590>

자, 이제 eval() 함수를 이용하여 객체를 생성할 수 있도록 __repr()__ 를 재정의하자.

** 어려울 것 없다. **

그 객체에 해당하는 ** 생성자 ** 를 호출하는 구문을 넘겨주면 된다. Tom 의 경우는 repr(tom) 을 했을 경우 Person('Tom', 20) 값이 반환되면 된다.

class Person:
    def __init__(self, name, age):
        self.name = name
        self.age = age

    def __del__(self):
        print('Bye! Bye! ' + self.name)

    def __str__(self):
        return 'My name is ' + self.name + '. I am ' + str(self.age) + '.'

    def __repr__(self):
        return 'Person(\''+ self.name +'\', ' + str(self.age) +')'

print(tom)
print(repr(tom))
print(eval(repr(tom)))

output:

My name is Tom. I am 20.
Person('Tom', 20)
My name is Tom. I am 20.

print(repr(tom)) 값이 생성자를 호출하는 문자열 임을 결과에서 볼수 있다. 그리고 eval() 함수를 통해 객체를 생성하고 print() 함수를 호출했을 때, __str__(self) 가 호출되어 결과가 나오는 것을 확인 할 수 있다.

💎 Thinking

• class 를 정의할 때 print() 함수 대신 __str__(self) 를 정의해서 쓰자!
• __repr__(self) 는 eval() 을 사용하여 객체를 사용할 수 있도록 재정의 하자!
• __str__(self) 가 정의되어 있지 않으면, default 로 __repr__(self) 가 호출된다는 것을!

• 1<sup>st</sup> January 2023

🔑 Problem

• python으로 LinkedList 를 자료구조를 구현해보라고?

* note *

python 으로 클래스를 만드는 법은 확인했다. 그럼 어떻게 객체를 초기화하고, 어떻게 삭제하는 거지? Check! Check!

🛰️ Reference Site

• 파이썬 객체지향 프로그래밍

🎽 Learn

1. 생성자 : __init__(self)

• 객체가 생성될 때 자동으로 호출된다.
• Method 이므로 첫 번째 Argument는 반드시 self 이다.

  class Person:
   def __init__(self, name, age):
       self.name = name
       self.age = age
  

tom = Person('Tom', 20)

> `self` 는 `class` 가 아닌 `object` 를 나타낸다.

#### 2. 소멸자 : `__del__(self)`
* 객체가 소멸할 때 자동으로 호출된다.
* Method 이므로 첫 번째 Argument는 반드시 `self` 이다.
```python
class Person:
    def __init__(self, name, age):
        self.name = name
        self.age = age

    def __del__(self):
        print('bye! bye! ' + self.name)

tom = Person('Tom', 20)
del tom

Output

Bye! Bye! Tom

💎 Thinking

생성자 함수와 초기화 함수에 대해

ptyhon 에서는 생성자 함수와 초기화 함수가 분리되어 있다고 한다.

• __init__ 은 초기화 함수
• __new__ 는 생성자 함수

별거 없지 않나, 그냥 메모리를 할당하는 부분과 변수를 초기화 하는 부분이 다른 언어와 다르게 분리되어 있다는 것! 근데 문법을 보면 이해가 간다.

### 파이썬에서 객체 생성하기
tom = Person('Tom', 20)

// JAVA에서 객체 생성하기
Person tom = new Person("Tom", 20);

JAVA 에서 보는 뚜렷한 new 키워드! JAVA 문법을 풀어보면

• new 메모리를 할당하라!
• Person("Tom", 20) 변수를 초기화 하라! 위와 같이 되지 않을까?

• 23<sup>rd</sup> December 2022

🔑 Problem

• python으로 LinkedList 를 자료구조를 구현해보라고?

* note *

LinkedList 를 구현하기 위해서는 데이터를 저장하는 변수 data 와 다음 데이터의 위치를 저장하는 next 가 필요하다. data 와 next 를 하나로 관리하기 위해서 class 를 만들어보자. 근데 python 으로 class 를 어떻게 만드는 거야? python 문법 부터 공부! 공부!

🛰️ Reference Site

• 파이썬 객체지향 프로그래밍

🎽 Learn

1. class 를 선언하자

   class Person:
    pass
   

* `class` 키워드 뒤에 유일한 클래스 이름을 지어준다.
* 클래스명은 PEP Coding Convention에 가이드된 대로 각 단어의 첫 문자를 대문자로 하는 CapWords 방식을 사용한다.
* 클래스 이름 뒤에는 `:` 을 반드시 붙여준다.

2. `attribute` 를 넣어보자
```python
class Person:
    name = name = 'No Name'
    age = 20

• Person 을 대표 할 수 있는 name 과 age 를 attribute 로 넣는다.

3. attribute 에 접근해 보자

   tom = Person()
   

tom.name tom.age

* `object_name.attribute` 이런 형식으로 `attribute` 에 접근한다.  `class` 명이 아니라 `object` 를 사용한다는 점. 그리고 `.` 을 이용한다는 점을 기억한다.

4. `method` 를 넣어보자
```python
class Person:
    name = 'No Name'
    age = 20

    def print_your_name(self):
        return "my name is " + self.name

• 파이썬 Method는 항상 첫 번째 파라미터로 self를 사용해야 한다.
• Method 안에서 클래스 attribute를 접근할 때는 self.attribute 로 접근해야 한다.

5. 객체의 Method 에 접근해보자

   class Person:
    name = 'No Name'
    age = 20
   
    def print_my_name(self):
        return "My name is " + self.name
   
    def set_my_info(self, name, age):
        self.name=name
        self.age=age

• 객체명.method명 으로 접근한다.

  tom = Person()
  tom.set_my_info('Tom', 20)
  tom.print_my_name()

  실행결과:

  My name is Tom

🎁 Summary

Python OOP

• class를 선언하기 위해 class 키워드를 사용한다.
• self 키워드는 instance 를 나타내는 의미 이외에는 존재하지 않는다.
• instance 귀속 된 method 와 attribute 에 접근할 때 명확하게 하기위해 self 키워드를 사용하는 것 뿐이다.

어느덧 12월인가 싶더니 벌써 12월 마지막 주가 되었다. 올 12월은 유난히 빨리 흐르는 듯하다. 그리고 모든 것들이 살짝 느슨해진다. 내 마음도, 내 생활도.

2023년을 위해 얼마 남지 않은 2022년을 정리하려 한다. 열심히 살았던 2022년의 내 발걸음이 밑거름이 되어 다가올 2023년을 더 풍성하게 할 것을 믿으니까 말이다.

새로운 업무에 적응하기!

2021년 7월, 운영 조직으로 팀을 옮겼다. 6개월 동안은 배움의 기간을 가졌고 2021년 12월에 내가 운영해야 할 사이트를 배정받았다. 2021년 12월부터 일이 몰려들기 시작하더니 오랜만에 컴퓨터 앞에서 단내 나는 경험을 했다. 퇴근할 때면 뻐근해져 오는 손목과 마르는 입안을 느끼며 한숨을 쉬었다. 그렇게 한 달을 채워갔다. 한 달이 지난 후 월급의 숫자는 나를 또 한숨 쉬게 만들었다. 이 돈 받고 개미처럼 일하는 것에 회의를 느끼게 했다.

‘이직을 해야겠다.’ 는 생각이 마음 속에 가득 차기 시작했다.

10년 넘게 관리하지 않았던 이력서와 경력기술서를 손보고 몇 군데 회사에 지원했다. 하지만 결과는 면접조차 가지 못했다.

언제나 문제는 나에게 있다.

‘뭐가 문제야!’

울분이 쌓이고 마음이 시리더라. 하지만 어쩌랴 결국 문제는 나에게 있는걸. 답이 정해져 있는 시키는 일만 했던 과거의 업보였다. 업무에 임하는 마음을 바꿔야겠다고 다짐했다.

답을 찾는 건 당연한 것! 먼저, 문제 정의하자! 내가 찾은 문제를 내가 제일 먼저 풀어 버리자!

주변에 문제들을 애써 외면하며, 누군가 시키면 마지못해 일했던 나에게서 벗어나야 했다. 주변을 살펴 문제를 정의하고 그 문제에 답을 찾는 연습 통해 실력을 키워야 했다. 그다음 이직을 진행하기로 마음 먹었다.

반드시 안해도 되는 일에 도전하기!

업무가 바뀐 지 얼마 되지 않아 업무에서 문제를 발견하는 건 쉽지 않았다. 그 대신, 안해도 되는 일. 누가 시키지 않을 일을 찾았다.

• 사내 MSA 자격시험
• 진급 시험
• 빅데이터 분석 기사 시험
• PM 시험

2022년 동안 총 4개의 시험에 응시했다. 결과는 모두 합격! 마지막 시험을 보고 결과를 확인할 때는 마음이 조금 '허'하더라.

'틈'을 어떻게 메우느냐에 따라 나의 삶은 달라진다.

2022년을 보내며, 시간이 없는 핑계로 항상 도전하지 않고 살았던 지난날의 나를 반성한다. 시간이 없다고 생각하니 시간이 없는 거였다. 언제나 ‘틈’은 있고, 그 ‘틈’을 어떻게 메우느냐에 따라 하루의 밀도가 달라지는 경험을 했다.

딱 정해진 시간에 무언가를 하려 하면 그 시간은 절대 오지 않더라. 설령 그 시간이 온다고 해도, 또 다른 핑계를 만들어 난 달아나 버리더라.

‘그냥, 하면 된다. 경계를 무너트리고, 틈이 날 때마다.’

뿌리 깊은 나무가 되길!

2023년에는 나의 역량의 근본을 다져야겠다. IT 쪽 일을 하고 있으니 IT의 근간인 컴퓨터 공학, 자료구조, 알고리즘에 관한 학습을 해야겠다. 이제서야 깨달은 것 같다. ‘뿌리가 단단한 나무는 흔들리지 않는다’는 말의 의미를.

잘가라! 2022년! 환영한다! 2023년!

• 22<sup>nd</sup> December 2022

🔑 Problem

• 내가 자랑스러워 하는 내모습은 어떤 모습일까?

🛰️ Reference Site

• 나는 나이기에 가치있고, 나 다울 때 가장 빛납니다. (생각의 기쁨 - 유병욱 지음)

💎 Thinking

점심을 먹고 나오는 길에 동료가 내 머리를 보며 이야기했다. "혹시, 매달 파마하는 거예요?"

"아니요. 저 원래 곱슬이에요" 라고 난 답했다.

그 말에 동료는 매우 놀라며 "아니, 자연산 곱슬이 왜 이리 이뻐!" 라고 말했다.

신기한 경험이었다. 내가 가진 것들 중 가장 싫어하는 것 중 하나인 곱슬머리가 남에게 좋아 보일 수 있다니. 사실, 난 저 곱슬거리는 머리 때문에 항상 힘들었다. 어렸을 때는 친구에게 머리에 폭탄 맞았냐며 놀림을 당했다. 좀 더 커서는 뭘해도 정리되지 않은 저 머리 때문에 계속해서 신경 쓰였고, 대학 기간 동안 삭발하고 다녔던 기간도 꽤 있었다. 다시 태어난다면 길게 뻗은 직모로 태어나고 싶었다.

'근데, 내 머리가 예쁘다니!'

정말 책에 있는 그대로인 것 같다.

'내가 남들의 어떤 부분을 부러워하는 만큼, 누군가가 어딘가에서 나의 어떤 부분을 부러워하고 있나 보다.' (생각의 기쁨 중에서)

어차피 바꿀 수 없는 것! 이럴바에야! 남들에게서 부족한 부분을 찾으려 하는 것이 아니라, 나에게 시선을 돌려 자랑스러운 모습을 찾아 봐야겠다.

찬찬히 공들여 찾아봐야겠다.

따뜻한 시선을 나에게로 돌려 놓아야겠다.

• 21<sup>st</sup> December 2022

🔑 Problem

• python List 를 사용해서 Queue 자료구조를 구현해보라고?

🛰️ Reference Site

• 동기화된 큐 클래스
• 파이썬 자습서 > 5.자료구조

🎽 Learn

• java에서 사용하는 java.util.Queue 나 C++ 에서 제공하는 STL: Standard Template Library 수준으로 Queue 자료 구조를 구현하는 건 매우 복잡하고 어려운 일이다.
• 여기서 필요한 건 enqueue 와 dequeue 를 List 를 사용해서 어떻게 구현 할 것지? 가 관건!
• 기능을 살펴보면,
  • enqueue : 데이터를 넣는다.
  • dequeue : 데이터를 반환하고, 삭제한다.
• 이제 List 를 사용해 기능을 구현해보면,

q = [] # 큐로 사용할 List 생성

def enqueue(item):
    q.append(item)

def dequeue():
    if len(q) > 0
        return q.pop(0)

🎁 Summary

List API

• list.append(x) : 리스트 끝에 항목을 더한다. list[len(list):]=[x] 와 같다.
• list.pop([i]) : 리스트에서 주어진 위치에 있는 항목을 삭제하고, 그 항목을 돌려준다. 인덱스를 지정하지 않으면, list.pop()은 리스트의 마지막 항목을 삭제하고 돌려준다. ( 메서드 시그니처에서 i 를 둘러싼 대괄호는 매개변수가 선택적임을 나타낸다. 그 위치에 대괄호를 입력해야 한다는 뜻이 아니다. )
• list[i] : 인덱스에 있는 값에 접근 할 수 있다.
• del list[i] : 리스트에서 값 대신 인덱스를 사용해서 항목을 삭제하는 방법이다.

  # del example
  a = [-1, 1, 66, 25, 333, 333, 1234.5]
  del a[0] # -1 을 삭제한다.
  # 결과값 [1, 66, 25, 333, 333, 1234.5]
  del a[2:4] # 25, 333 을 삭제한다.
  # 결과값 [1, 66, 333, 1234.5]
  del a # 변수 a 자체를 삭제한다. 이후에 이름을 삭제할 수 없다.

• 20<sup>th</sup> December 2022

🔑 Problem

• python에서 역순으로 10부터 1까지 숫자 출력하려면 Index를 어떻게 해야하지?

🛰️ Reference Site

• Python range() Function
• Stanford Python Guide

🎽 Learn

• JAVA는 for 문의 index를 하나씩 감소하면서 출력하면 된다.

  for(int i=10; i>0; i--) {
    print(i)
  }

• python은 `range(start, stop, step) 함수를 사용한다.

  for i in range(10, 0, -1)
    print(i)

• JAVA의 IntStream.range(int startInclusive, int endExclusive) 와 비슷한데, step 이 파라미터로 추가되어 사용하기 더 편하다.

  🎁 Summary

• range(stop): range(10)은 0, 1, 2, 3, 4, 5, 6, 7, 8, 9
• range(start, stop): range(1,11) 은 1, 2, 3, 4, 5, 6, 7, 8, 9, 10
• range(start, stop, step):
  • start, stop, step은 음수로 지정 가능
  • range(0,20,2)은 0, 2, 4, 6, 8, 10, 12, 14, 16, 18
  • range(10,0,-1)은 10, 9, 8, 7, 6, 5, 4, 3, 2, 1