[패스트캠퍼스 수강 후기] 올인원 패키지 : 컴퓨터 공학 전공 필수👉C언어인강 100% 환급 챌린지 46회차 미션

 

 

 

환급미션 46일째....

 

 

소프트웨어 베이직 - 자료구조와 알고리즘 - 11. 트리 - 이진 트리 

소프트웨어 베이직 - 자료구조와 알고리즘 - 12. 트리 - 이진 트리의 구현 및 순회

운영체제 - 쓰레드의 이해 - 02. 스레드 장단점

운영체제 - 쓰레드의 이해 - 03. 스레드 동기화 문제

 

 

 

 

소프트웨어 베이직 - 자료구조와 알고리즘 - 11. 트리 - 이진 트리

 

 

 

 

트리(Tree)는 나무를 뒤집은 듯한 형태의 자료구조이다.

 

최상단 노드를 '루트 노드(root node)'라고 하고,

루트 노드에서 가지를 이용해 각각의 노드로 연결된다.

트리에서 끝에 해당하는 노드를 '리프 노드(leaf node)'라고 한다.

 

 

 

각각의 노드는 부모/자식의 관계를 가지기도 하고

37, 50 사이의 관계는 '형제 노드'라고 한다.

 

 

 

 

트리의 길이 = 출발 노드에서 목적지 노드까지 거치는 가지의 수

 

-> 위의 예시에서, root node로부터 leaf node 중 76까지의 길이는 2가 된다.

 

 

 

 

 

 

깊이 = root node에서 특정 node까지의 길이

 

 

 

높이 = root node에서 가장 깊은 노드까지의 길이

 

 

 

 

 

 

 

- 이진 트리 (Binary Tree)

 

 

많은 양의 노드를 낮은 높이에서 관리할 수 있기 때문에 데이터 활용의 효율성이 높아진다.

구현이 쉽기도 하고 데이터 저장, 탐색 등 다양한 목적으로 사용할 수 있다.

 

 

 

* 이진 트리 (Binary Tree) 

: 최대 2개의 자식을 가질 수 있는 트리

 

 

 

 

 

* 포화 이진 트리 (Full Binary Tree) 

: 리프 노드를 제외한 모든 노드가 자식노드를 2개 갖는다.

 

포화이진트리

 

 

 

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

: 모든 노드들이 왼쪽 자식부터 차근차근 채워진 노드

 

완전이진트리

 

 

* 높이 균형 트리 (Height Balanced Tree)

: 왼쪽/오른쪽 자식 트리의 높이가 1 이상 차이나지 않는 트리

 

높이균형트리

 

-> 오른쪽 트리를 보면, 자식 노드가 왼쪽으로 편향되어 있는데,

이러한 트리를 '편향 트리'라고도 한다.

 

 

 

 

 

 

 

 

 

소프트웨어 베이직 - 자료구조와 알고리즘 - 12. 트리 - 이진 트리의 구현 및 순회

 

 

 

- 이진 트리

 

포인터를 이용하여 구현하면, 데이터 관리를 효과적으로 할 수 있다.

 

 

 

c언어로 포인터를 이용하여 구현

 

 

 

 

- 이진 트리의 순회

 

이진 트리에 담긴 데이터를 하나씩 방문하는 방법에는 크게 3가지가 있다.

-> 전위 순회 / 중위 순회 / 후위 순회

 

 

 

* 이진트리의 전위 순회

 

 

전위 순회란 위의 그림과 같은 방식의 순회 알고리즘을 말한다.

 

우선 순위가 본인 > 왼쪽 자식 > 오른쪽 자식 순으로 부여된다고 생각하면 이해가 쉬울 듯 하다.

 

 

c언어를 이용한 전위순회 알고리즘 구현

 

강의에서는 함수이름을 preorder 으로 정의했는데,

다른이름 어쩌구 경고가 떠서 preOrder로 구현했다.

 

 

 

 

* 이진트리의 중위 순회

 

 

 

중위 순회란 위의 그림과 같은 방식의 순회 알고리즘을 말한다.

 

root node에서 왼쪽 자식을 끝까지 방문한 다음 출력하고, 

왼쪽에 있는 모든 자식을 출력한 다음 자기 자신을 출력,

그리고 오른쪽 자식을 방문해서 처음의 알고리즘대로 출력하는 것이 특징이다.

 

우선 순위가 왼쪽 자식 > 본인 > 오른쪽 자식 순으로 부여된다고 생각하면 이해가 쉬울 듯 하다.

 

이 알고리즘은 글로 보면 복잡해보이지만

실제로는 

왼쪽부터 차례대로 출력되는 것을 확인할 수 있다.

 

c언어를 이용한 중위순회 알고리즘 구현

 

 

 

 

* 이진 트리의 후위 순회

 

후위 순회란 위의 그림과 같은 방식의 순회 알고리즘을 말한다.

 

우선순위가 왼쪽 자식 > 오른쪽 자식 > 본인 순으로 부여된다고 생각하면 이해가 쉬울 듯 하다.

모든 경우에서 왼쪽 자식이 오른쪽 자식보다 우선순위가 높다.

 

 

c언어로 후위순회 알고리즘 구현

 

 

 

 

* 이진 트리 사용해보기 

 

 

위에서 작성한 것들을 이용해 이진 트리를 실제로 사용해볼 것이다.

 

 

 

강의에서 사용한 코드에 살짝 조미료를 버무려보았다..

 

 

 

 

결과값은 위와 같이 성공적으로 출력되었다.

 

 

 

 

=> 이진트리가 어떤 것인지 알아보고, 출력하는 방식 3가지를 정리해보았다.

 

 

 

 

 

 

 

 

운영체제 - 쓰레드의 이해 - 02. 스레드 장단점

 

 

 

 

- Thread 장점 

 

 

* 사용자에 대한 응답성 향상

 

 

어떤 프로세스의 기능이 2가지라고 가정했을 때,

---------

기능1 : 1~100만 덧셈

기능2 : 지금까지 더한 수를 전달

---------

기능1, 2 각각을 2개의 스레드 안에 만들면

멀티태스킹 / 멀티프로세싱과 같이 병렬처리되어 응답시간이 줄어들 수 있다.

 

웹서버의 경우, 여러 클라이언트가 서버에 어떤 요청을 했을 때

각각의 요청을 받아들이는 스레드를 별도로 여러 개 마련하기도 한다.

 

 

 

* 자원 공유 효율적

 

IPC 기법같은 번거로운 작업이 필요없다.

프로세스 안에 있기 때문에, 프로세스의 모든 데이터에 접근 가능하다.

 

가령, 6개의 프로세스를 만들어서 사용하면 리눅스의 경우 24GB의 공간이 필요하지만

하나의 프로세스에 6개의 스레드를 만들어서 사용할 경우 4GB의 공간만 사용하게 된다.

 

 

 

* 작업이 분리되기 때문에 코드가 간결하다.

 

thread 1

thread 2 등의 함수를 실행하게 될 텐데

무조건 간결하다는 뜻이 아니라,

코드가 분리되기 때문에 간결해보일 수 있다는(?) 장점이 있다고 한다.

(사실 작성하기 나름이라고 한다.)

 

 

 

 

 

- Thread 단점

 

 

* 1개의 스레드만 문제가 있어도, 전체 프로세스가 영향받는다.

 

 

 

위의 그림에서 보는 것처럼

멀티 프로세스로 구성했을 때는 특정 프로세스에 문제가 있어도 나머지 프로세스는 잘 작동하지만,

멀티 스레드의 경우에는 특정 스레드에 문제가 발생할 경우 전체 프로세스에 영향을 주게 된다.

 

 

 

* 많은 스레드를 생성했을 때 성능 저하 문제

 

ex)

리눅스에서는 thread를 process인 것처럼 다룬다.

-> 스레드의 갯수가 많아질 경우, 모든 스레드를 스케쥴링 해야하고

context switching이 많이 일어나기 때문에 성능이 저하될 수 있다.

 

 

 

 

- Process vs Thread

 

독립적 vs 프로세스에 종속(서브셋)

독립적인 자원을 가짐 vs 프로세스 자원을 공유

자신만의 주소영역을 가짐 vs 주소영역 공유

IPC기법으로 통신 vs 그럴 필요 없음

 

 

 

 

* POSIX 스레드 (POSIX Threads, 약어 : PThread)

: Thread 관련 표준 API

-> 시스템 프로그래밍에서 다룰 예정

 

 

 

 

 

 

 

 

운영체제 - 쓰레드의 이해 - 03. 스레드 동기화 문제

 

 

 

- 동기화 (Synchronization) 이슈

 

동기화 : 작업 사이의 실행 시기를 맞추는 것

여러 스레드가 동일한 자원(data) 접근 시 동기화 이슈 발생

또한

실행 순서가 정해져있지 않기 때문에 비정상 동작을 하는 경우가 있다.

 

-> 여러 스레드가 동시에 동일한 자원을 수정할 때, 각 스레드 결과에 영향을 줄 수 있다.

이런 상황이 발생할 경우 디버깅이 쉽지 않다.

 

 

 

ex) python 으로 확인해보기 - 컴공 전공필수 패키지에는 파이썬이 없는데 복습용으로 가져왔다고 한다..

 

 

-------------

import threading //파이썬의 기본 라이브러리의 하나로, threading이라는 라이브러리를 제공

 

g_count = 0 //전역변수 선언

 

def thread_main(): //함수

 global g_count //전역변수를 사용하겠다고 선언

 for i in range(10000) :

  g_count = g_count + 1

 

threads = [ ] //리스트 변수, c언어의 배열과 유사

 

for i in range(50) : //50번동안 반복, threading의 라이브러리를 이용해 스레드 생성

 th = threading.Thread(target = thread_main) //생성된 스레드의 주소값을 th에 넣음

 threads.append(th) //주소값을 리스트에 계속 넣음

//결국, 스레드에 접근할 수 있는 50개의 주소값이 threads 리스트에 들어가게 된다.

 

for th in threads : // threads 리스트에서 변수의 주소값을 하나씩 가져와서 start함수 실행 (스레드 실행)

 th.start()

 

for th in threads : // 다른 스레드가 끝날 때까지 기다림 -> 스레드 간의 동기화

 th.join()

 

print ('g_count = ', g_count) 

// 결국 50 * 10000의 값인 '500000'이 출력된다.

-------------

 

 

->

만약,

함수의 for in range (10000) 부분에서 10000 대신 더 큰 값인 100000 등을 입력한다면

이상한 결과값이 출력될 것이다.

이런 오류들이 바로 동기화 이슈 때문에 발생하는 것이다.

 

 

 

* 이러한 동기화 이슈를 해결하기 위해

thread_main() 함수 내에 있는

 

for i in range(1000000):

 g_count = g_count + 1

 

이 부분에 대해

한 번에 한 스레드만 이 코드를 실행하도록 수정한다면

이슈가 해결될 수 있을 것이다.

 

--------------------------------

import threading

 

g_count = 0

 

def thread_main():

 global g_count

 lock acquire() // #2,  실행하는 스레드에게 열쇠(?)를 준 것과 같은 상황. 현재 스레드에서 for문이 끝나기 전까지 컨텍스트 스위칭이 일어난다 하더라도 스위칭된 스레드에서 아래 for문을 수행할 수 없게 된다. 

 for i in range(100000):

  g_count = g_count + 1

 lock.realease() // #3, lock을 부여받은 스레드에서 for문이 종료되면 lock이 해제 되는 것이다. (열쇠를 반납한다고 생각)

 

lock = threading.Lock() // #1, threading 라이브러리에서 제공하는 함수 lock 

아랫부분은 동일

----------------------------

 

 

 

 

 

- 동기화 이슈 해결 방안

 

 

•Mutual exclusion (상호 배제)

•여러 스레드가 변경하는 공유 변수에 대해 Exclusive Access

•한 스레드가 공유 변수를 갱신하는 동안 다른 스레드가 동시에 접근하지 못하도록 막을 것

 

 

 

 

정리

 

Thread 개념 정리 

•프로세스와 달리 스레드간 자원 공유

 

Thread 장점

•cpu 활용도를 높임

•성능 개선 가능

•응답성 향상

•효율적인 자원 공유 (IPC 불필요)

 

Thread 단점

•하나의 스레드 문제가 프로세스 전반에 영향을 줌

•여러 스레드 생성 시 성능 저하 가능성

 

동기화 이슈 및 해결 방안

 

 

 

 

올인원 패키지 : 컴퓨터 공학 전공 필수👉https://bit.ly/3i4sCVE