본문 바로가기

CS23

백준 - [BOJ 22856] 트리 순회 문제노드가 N개인 이진 트리가 있다. 트리를 중위 순회와 유사하게 순회하려고 한다. 이를 유사 중위 순회라고 하자.순회의 시작은 트리의 루트이고 순회의 끝은 중위 순회할 때 마지막 노드이다. 이때 루트 노드는 항상 1번 노드이다.유사 중위 순회는 루트 노드에서 시작하며, 다음과 같이 진행된다.현재 위치한 노드의 왼쪽 자식 노드가 존재하고 아직 방문하지 않았다면, 왼쪽 자식 노드로 이동한다.그렇지 않고 현재 위치한 노드의 오른쪽 자식 노드가 존재하고 아직 방문하지 않았다면, 오른쪽 자식 노드로 이동한다.그렇지 않고 현재 노드가 유사 중위 순회의 끝이라면, 유사 중위 순회를 종료한다.그렇지 않고 부모 노드가 존재한다면, 부모 노드로 이동한다.유사 중위 순회를 종료할 때까지 1 ~ 4를 반복한다.위 그림에 있.. 2024. 7. 8.
[Java] Binary Tree Binary Tree는 트리를 통해 데이터를 비선형적으로 관리하는 자료구조이다.앞서 포스팅에서 BST(Binary Search Tree)에 대해서 설명했는데 BST도 이진 트리를 기반한 자료구조이다. 왜 Binary Tree를 사용할까?Tree Post에서도 설명했는데 일반 DAG와 같은 Tree는 효율성 측면에서 너무 부족하다. 그저 Graph와 다름이 없다.그래서 실제 데이터 처리를 하기 위해 Binary Tree로 효율성을 극대화하는 방법을 채택한 것이다. 크게 Binary Tree의 두 종류를 알아보자. 1. 완전 이진 트리2. 편향 트리 이 외에도 많지만 Binary Tree의 핵심을 설명하기에 두 가지가 최고인 것 같다. 위 두가지 개념을 언급한 이유는 BST의 문제점 때문이다.앞서 작성한 B.. 2024. 7. 8.
18. 상호배제 구현 방법 먼저, 해당 포스팅은 단일 프로세서 상호배제 구현 방법인 것을 알고 있어야 한다.인터럽트 서비스 금지 방법 진입 코드(Entry Code)에서 cli(clear interrupt flag) 명령으로 인터럽트 서비스를 중지하고임계 구역(Critical Code)에서 인터럽트가 발생하면 무시한다.진출 코드(Exit Code)에서 sti(set interrupt flag) 명령으로 인터럽트 서비스를 재실행한다.  인터럽트 서비스를 중지하지 않을 경우, 그림2와 같이 T1이 임계구역을 접근했을 때, T1에게서 인터럽트 서비스가 발생하면 스레드는 대기 상태가 되고 T2를 스케줄한다. 이 때, T2가 임계 구역에 접근하게 된다면 공유 자원에 T1과 T2가 공존하는 현상이 발생한다. 즉 T1이 변수의 값을 읽고 인터.. 2024. 6. 16.
17. 상호 배제 (Mutual Exclusion) 상호배제란? 앞서 스레드 동기화에서 언급된 임계구역과 상호배제는 스레드 동기화를 위한 중요한 개념이다.먼저, 임계 구역(Critical Section)은 각 스레드들이 동시에 접근할 수 있는 공유 데이터를 관리하는 구역이다.상호 배제는 먼저 임계 구역에 접근한 스레드가 임계 구역을 독점적으로 사용하여 스레드 간의 순서를 보장할 수 있는 개념이다. 임계 구역과 상호 배제도 조금 더 쉽게 생각해보자. 스레드 A는 횟집, 스레드 B는 매운탕 집이다. 스레드 A와 B는 수산도매에서 싱싱한 생선을 가져와야한다. 스레드 A와 B는 서로 경매가를 부르고 있는데 도매상이 "마지막으로 현재 경매가 보다 높은 가격을 먼저 제시한 사람에게 판매하겠습니다."라고 했다. 스레드 A와 B는 동시에 "100만 원!"을 외쳤다. 이.. 2024. 6. 15.
16. 스레드 동기화 (Thread Synchronization) 스레드 동기화란 뭘까? 스레드 동기화란 다수의 스레드가 하나의 자원에 동시에 접근할 때 발생할 수 있는 문제점을 해결할 수 있는 방법이다.다수의 스레드가 하나의 자원에 동시에 접근한다는게 무슨 말일까?스레드 동기화 이해하기  먼저, 컴퓨터의 구조를 잘 알고 있어야한다.논리회로, 컴퓨터 구조, 운영체제 앞 단원을 열심히 공부했다면 쉽게 이해할 수 있는 부분이다. 이해를 해보자.컴퓨터는 클럭 단위로 동작한다.클럭 단위로 동작한다는 것은 하나의 작업을 수행할 때, 일정 시간이 소요된다는 의미이다. TEMP = 10 이 있을 때, 하나의 클럭이 소요되는데 0.001초라고 해보자.  스레드 A와 B가 TEMP에 입력한 값을 더하려고 한다. 1. 0초에 스레드 A는 TEMP의 값을 확인한다. 값은 10이다. 5를 .. 2024. 6. 15.
4. Physical Layer - Digital Signals 디지털 신호는 0과 1로 표현할 수 있는 실제 전기 신호이다. 물리 계층에서는 실제 전기를 통해 bit 정보를 전송하기 때문에 디지털 신호에 대해 알고 있어야 한다. Bit Rate (비트 전송률) 1초 당 비트 전송률이고 Bit Per Second로 bps라고도 한다. 물리적인 장치로 디지털 데이터를 전달할 때 디지털 신호로 전달하게 되는데 그림 A와 같이 bit rate가 몇 bit냐에 따라서 디지털 신호의 레벨을 나누게 된다. 한 줄당 80글자가 있는 문장이 총 24줄 있다고 가정하자. 이를 한 페이지라고 했을 때 총 100페이지가 있다면 이 정보를 채널을 통해 전송하는 Bit Rate는 어떻게 될까? 한 글자는 1Byte = 8bit 이므로 8 * 80 * 24 * 100 으로 1,536,000b.. 2024. 4. 24.
3. Physical Layer - Data와 Signals 그리고 Bandwidth 물리 계층에 대해 들어가기 전에 데이터와 신호에 대한 개념이 필요한가보다. 데이터 통신에서 데이터는 두 가지 종류가 있다. 1. 아날로그 데이터 - 연속적인 정보를 가지고 있는 데이터 2. 디지털 데이터 - 불연속적인 정보를 가지고 있는 데이터 아날로그 데이터와 디지털 데이터를 각 각 신호로 나타내면 그림 A처럼 표현할 수 있다. 각 신호는 주기적인 신호(Periodic)와 비주기적인 신호(Non-Periodic)로 구분할 수 있다. 주기적인 신호는 일정한 패턴이 동일한 시간 내 반복되는 것을 말하고 사이클을 형성한다고 한다. 비주기적인 신호는 시간이 지남에 따라 반복되는 패턴 없이 신호가 바뀌는 것을 말한다. 대표적으로 그림 B와 같은 정형파가 주기적인 신호에 속한다. 그 외, 그림 A와 같은 신호들은.. 2024. 4. 23.
2. Protocol Model Seven layers of the OSI Model OSI는 응용 프로그램 계층, 표현 계층, 세션 계층, 전송 계층, 네트워크 계층, 데이터 링크 계층, 물리 계층으로 7개의 레이어를 가진다. 흔히, 자격증 공부에서는 '물데네 전세표응'으로 외우는 유명한 녀석이다. OSI의 7계층을 살펴보면 프로토콜의 원칙을 잘 지키고 있음을 알 수 있다. 각 레이어는 양방향으로 통신이 되며, 같은 계층을 가지고 있다. 참고로 네트워크, 데이터 링크, 물리 계층의 경우 통신 상 존재하는 중간 라우터, 스위치 등에 의해 추가적인 통신이 발생 각 계층은 어떤 일을 하는지 보자. Physical Layer 물리 계층은 그림 A와 같이 구성되어있다. 프로토콜 원칙에서 설명했지만, 각 계층은 두가지 역할을 수행해야 한다고 했.. 2024. 4. 22.
1. Protocol Layering 프로토콜이 뭘까? 프로토콜(Protocol)은 통신에서 상대방과 통신하는 방법에 대한 규약이다. 어떻게 통신할 것인지를 미리 사전에 정의해놓고 그 방식에 맞게 통신하는 것이다. 만약, 프로토콜이 없다고 가정해보자. A 회사에서 B 회사로 데이터를 전달하는데 그냥 원본 그대로 전송한다. A 회사는 전용 우편함이 존재하고 B 회사는 우편함이 따로 없다. B 회사에서 데이터를 전달 받을 때, 우편함이 없어서 사용자에게 직접 가져다 줘야하는데 우편 기사가 존재한다면 한 명, 한 명에 대해 일일이 물어보고 갖다줘야한다. 만약, B 회사에도 우편함이 존재했고 이 우편을 관리해주는 사람이 존재한다면? 알아서 다 해줄 것이다. 컴퓨터 입장에서 본다면 컴퓨터 시스템이 사용자를 찾기 위해 다른 작업을 처리하지 못하고 시간.. 2024. 4. 22.

티스토리툴바