기술 블로그

[알고리즘] 이진 검색 트리

여러 개의 키 저장INSERT, SEARCH, DELETE여러 개의 키를 저장하고 검색, 삽입, 삭제 작업을 효율적으로 수행하기 위해 다양한 자료구조가 사용됩니다. 아래는 배열과 연결 리스트를 사용할 경우, 정렬 여부에 따른 시간 복잡도를 정리한 표입니다:자료구조정렬여부SearchInsertDelete배열 (Array)정렬됨O(log n)O(n)O(n)배열 (Array)정렬되지 않음O(n)O(1), O(n)O(1)연결 리스트 (Linked List)정렬됨O(n)O(n)O(1)연결 리스트 (Linked List)정렬되지 않음O(n)O(1)O(1)🔍 배열이나 연결 리스트를 사용하는 경우, 정렬 여부와 상관없이 INSERT, SEARCH, DELETE 중 적어도 하나는 O(n)의 시간 복잡도를 가집니다. 이..

트리

트리 루트(Root): 트리 구조에서 가장 위에 있는 노드입니다.부모-자식 관계: 한 노드 아래에 연결된 노드를 ‘자식 노드’라고 하며, 연결 위쪽의 노드를 ‘부모 노드’라고 합니다.형제 노드: 동일한 부모를 가진 노드들을 형제(sibling)라고 합니다.리프(Leaf) 노드: 자식 노드가 없는 노드입니다. 트리의 말단에 위치합니다.조상-자손 관계: 부모-자식 관계를 확장한 개념으로, 조상은 부모의 부모까지 포함하며, 자손은 자식의 자식까지 모두 포함합니다. 이진트리이진트리는 모든 노드가 최대 두 개의 자식 노드를 가지는 트리입니다. 각각의 자식 노드는 왼쪽 자식(left child) 또는 오른쪽 자식(right child)으로 구분됩니다. 자식이 하나뿐인 경우에도 해당 자식이 왼쪽인지 오른쪽인지를 명확..

물론이죠! 전체적으로 프로세스 간 통신(IPC, Inter-Process Communication)과 관련된 내용을 다루고 있는 것 같아요. 흐름을 유지하면서 좀 더 명확하고 자연스럽게 정리해드릴게요:공유 메모리(shared memory) 객체는, 해당 이름을 가진 객체가 존재하지 않을 경우 새로 생성되며, 읽기와 쓰기가 모두 가능한 형태로 생성됩니다. 이때, 공유 메모리 객체의 접근 권한은 0666으로 설정되어, 모든 사용자에게 읽기 및 쓰기 권한을 부여합니다.이러한 공유 메모리는 파일 디스크립터(file descriptor)를 통해 접근하며, 이는 시스템 콜(system call)의 반환값으로 할당됩니다. 사용자 애플리케이션에서는 직접 하드웨어나 커널을 제어할 수 없기 때문에, 시스템 콜을 통해 커널..

트랜잭션(Transaction)이란?트랜잭션은 DBMS에서 데이터를 다루는 논리적 작업 단위입니다.단일 SQL문일 수도 있고, 여러 개의 SQL문이 순차적으로 실행되는 복합적인 작업일 수도 있습니다.트랜잭션은 다음과 같은 역할을 합니다:복구 단위: 오류 발생 시 이전 상태로 되돌릴 수 있음분리 단위: 여러 트랜잭션이 동시에 동일 데이터를 다룰 때 독립성 보장원자성 보장: 전체 작업이 전부 수행되거나 전혀 수행되지 않아야 함BEGIN TRANSACTION A 계좌 10000 인출 (UPDATE) B 계좌 10000 입금 (UPDATE)COMMIT TRANSACTION시작과 끝을 말합니다.  트랙잭션의 성질원자성 : 전부 수행되거나 수행되지 않아야 함일관성 : 수행 전이나 수행 후 일관된 상태 유지해야..

출력 차원을 늘려야 하는 이유이진 분류에서는 예를 들어 강아지 = 1, 고양이 = 0처럼 단일 출력 노드로도 충분합니다. 그러나 이렇게 단일 출력으로 분류하게 되면, 중간값(예: 0.5)처럼 애매한 결과가 나와 오류가 발생할 수 있습니다. 이를 방지하고 더 복잡한 다중 분류 문제를 해결하기 위해 출력 차원을 늘리는 방식, 즉 출력 노드를 클래스 수만큼 구성하는 방식을 사용합니다. 예를 들어, 분류 대상이 3종류라면 다음과 같이 표현합니다:강아지 → [1,0,0]고양이 → [0,1,0]토끼 → [0,0,1]이렇게 하면 각 클래스에 해당하는 확률 분포를 명확히 표현할 수 있습니다. Softmax: 다중 분류에서의 확률 출력다중 분류에서는 출력이 확률 분포의 형태를 띄어야 하므로 다음 조건을 만족해야 합니다:..

인공신경망(Artificial Neural Network, ANN)은 결국 하나의 함수로 볼 수 있습니다. 이 함수 fff는 다양한 weight와 bias, 즉 파라미터들로 구성된 함수이며, 입력 x가 주어졌을 때 출력은 f(x)가 됩니다. 즉, 신경망은 파라미터화된(parameterized) 함수로서, 주어진 입력에 대해 적절한 출력을 내는 함수 f_w(x)를 학습합니다. 예를 들어 수학에서 x→f→x2처럼, 어떤 입력 x가 함수 f를 통해 f(x)로 변환되는 것처럼, 신경망도 입력 x를 받아 출력합니다. 이때 출력된 fw​(x)는 정답 레이블 y에 대한 확률 분포, 즉 조건부 확률 분포 p(y∣fw(x))을 따르게 됩니다. 이 확률 분포를 어떻게 모델링하느냐에 따라 신경망의 출력 해석이 달라집니다. ..

확률 곱셈의 수치적 불안정성과 로그 변환의 필요성if 강아지사진 q를 최대화해야else if 고양이사진 q를 최소화해야확률 q를 최소화하는 것은, 수학적으로 1 - q를 최대화하는 것과 같습니다.이 개념은 베르누이 분포의 확률 표현인q^p * (1 - q)^(1 - p)을 최대화하는 것과도 같습니다. 이 수식은 p가 1일 때는 q, p가 0일 때는 1 - q를 취하는 구조로, 주어진 정답에 따라 올바른 확률을 선택하여 곱하는 방식입니다. 이는 독립시행에서 전체 확률을 계산하기 위해 각 시행의 확률을 곱하는 방식과 같습니다. 예를 들어, 어떤 모델이 하나의 데이터에서 정답을 0.9 확률로 맞춘다고 하면, 이를 100번 반복하면 전체 확률은 0.9^100 ≈ 0.000026이 됩니다. 이처럼 0과 1 사이의..

프로세스의 상태운영체제에서 프로세스(Process) 는 실행 중 여러 가지 상태(state) 를 가집니다. 대표적인 상태는 다음과 같습니다.1. 프로세스의 주요 상태상태설명생성 상태 (New)프로세스가 생성되어 PCB가 할당 된 상태준비 상태 (Ready)실행 가능한 상태이지만 CPU를 할당받지 못한 상태실행 상태 (Running)CPU를 할당받아 실행 중 인 상태대기 상태 (Waiting, Blocked)입출력 작업 등 특정 이벤트를 기다리는 상태종료 상태 (Terminated)실행이 끝나 PCB가 폐기되고 자원이 반환된 상태2. 프로세스 상태 전이 (State Transition)준비 → 실행: CPU를 할당받으면 실행 상태로 전환실행 → 준비: 타이머 인터럽트 발생 시 다시 준비 상태로 이동실행 →..

프로세스의 상태운영체제에서 프로세스(Process) 는 실행 중 여러 가지 상태(state) 를 가집니다. 대표적인 상태는 다음과 같습니다.1. 프로세스의 주요 상태상태설명생성 상태 (New)프로세스가 생성되어 PCB가 할당 된 상태준비 상태 (Ready)실행 가능한 상태이지만 CPU를 할당받지 못한 상태실행 상태 (Running)CPU를 할당받아 실행 중 인 상태대기 상태 (Waiting, Blocked)입출력 작업 등 특정 이벤트를 기다리는 상태종료 상태 (Terminated)실행이 끝나 PCB가 폐기되고 자원이 반환된 상태2. 프로세스 상태 전이 (State Transition)준비 → 실행: CPU를 할당받으면 실행 상태로 전환실행 → 준비: 타이머 인터럽트 발생 시 다시 준비 상태로 이동실행 →..

실행 중인 프로그램을 프로세스(Process) 라고 합니다. 메모리는 커널 영역(Kernel Space) 과 사용자 영역(User Space) 으로 나뉘며, 프로세스는 사용자 영역에서 실행됩니다. 같은 프로그램이라도 여러 개의 프로세스로 실행될 수 있습니다. 즉, 동일한 프로그램을 여러 번 실행하면 각각 독립적인 프로세스로 동작합니다. 하지만 같은 프로그램이 여러 번 실행된다고 해서 반드시 메모리에 중복 적재될 필요는 없습니다.프로세스 제어 블록모든 프로세스는 프로세스 제어 블록(PCB, Process Control Block) 이라는 데이터 구조를 갖습니다. 운영체제는 PCB를 통해 각 프로세스를 식별하고 관리합니다. PCB는 운영체제의 커널 영역 에 위치하며, 실행 중인 모든 프로세스의 PCB가 저장..