Lowest Common Ancestor 트리 자료구조에서 두 노드의 가장 가까운 공통 조상을 찾는 알고리즘으로, 일반적으로 이진 트리나 이진 탐색 트리에서 사용됩니다. 재귀적인 방법과 반복문을 사용한 방법으로 구현할 수 있는데 이 포스팅에서는 재귀를 바탕으로 설명하겠습니다. 동작 순서 루트(root)부터 시작하여 두 대상 노드의 값을 비교합니다. 현재 노드의 값이 두 대상 노드의 값보다 크면, LCA는 현재 노드의 왼쪽 서브트리에 있을 것입니다. 따라서 왼쪽 자식 노드로 재귀 호출합니다. 현재 노드의 값이 두 대상 노드의 값보다 작으면, LCA는 현재 노드의 오른쪽 서브트리에 있을 것입니다. 따라서 오른쪽 자식 노드로 재귀 호출합니다. 두 대상 노드의 값이 현재 노드의 값과 같거나, 현재 노드의 값이 ..
Morris Traversal for Preorder 트리를 순회하는 데 사용되는 다양한 알고리즘이 있습니다. 그 중에서 Morris Traversal 알고리즘은 공간 복잡도를 O(1)로 유지하면서 순회할 수 있는 효율적인 방법으로 스택을 사용하지 않고도 Preorder Traversal를 수행할 수 있습니다. 따라서 메모리 사용에 제약이 있는 환경이거나 공간 복잡도를 최소화해야 하는 상황에서 유용하게 사용될 수 있습니다. 또한 추가 데이터 구조 없이 순회해야 하는 경우에도 유용하게 사용할 수 있습니다. 동작 순서 현재 노드를 기준으로, 왼쪽 서브트리를 순회합니다. 왼쪽 서브트리에서 현재 노드의 바로 이전 노드를 찾습니다. 이전 노드의 오른쪽 자식을 현재 노드로 설정합니다. 현재 노드를 방문합니다. 현재..
프로세스 (Process) 컴퓨터에서 실행되고 있는 프로그램 HDD/SDD에 있던 프로그램이 인스턴스화되어 메모리(RAM)에 올라가면 프로세스가 된다. 프로세스 상태 (Process State) New(=Create) : 생성 상태 프로세스가 생성된 상태 (이지만 아직 메인 메모리에 올라가지는 않았다.) fork() 또는 exec() 함수를 통해 생성되며, 이때, PCB가 할당된다. fork() : 부모 프로세스의 주소 공간을 그대로 복사하여, 새로운 자식 프로세스를 생성한다. exec() : 새롭게 프로세스를 생성한다. Ready : 대기 상태 메인 메모리 공간에 로드되어 CPU에서 실행을 기다리고 있는 상태 Dispatcher 또는 Short-term scheduler에 의해 CPU로 컨텍스트 스위칭..
스트레티지 패턴(Strategy Pattern) 객체의 동작을 런타임에 선택할 수 있게 하는 행동 디자인 패턴 여러 알고리즘을 공통 인터페이스를 구현하는 별도의 클래스로 캡슐화하는 아이디어에 기반한 패턴 구성 요소 컨텍스트(Context) : 동적으ㅡ로 동작을 변경해야 하는 객체를 포함하는 클래스 전략(Strategy) : 모든 알고리즘에 대한 공통 메서드를 정의하는 인터페이스나 추상 클래스 구체적인 전략(Concrete Strategy) : 전략 인터페이스를 구현하고 알고리즘의 실제 구현을 제공하는 클래스 장점 런타임에서 전략을 변경할 수 있다. 개방-폐쇄 원칙(OCP) 준수 : 알고리즘 구현을 변경해도 컨텍스트 클래스에 영향을 미치지 않는다. 단점 여러 클래스를 사용하므로 코드 복잡성이 증가 알고리즘..
옵저버 패턴(Observer Pattern) 어떤 대상의 상태가 변경되었을 때 이 상태 변경에 연관이 있는 관찰자들에게 알려주는 패턴 장점 느슨한 결합(Loose Coupling) : 주체(Subject)와 옵저버는 서로에 대한 최소한의 정보만 알고 있어야 한다. 이로써 시스템의 유연성이 향상되며 요구사항 변경에 대응하기 쉬워진다. 단점 메모리 누수(Lapsed Listener Problem) : 주체 객체가 명시적으로 옵저버를 등록하고 해제하지 않으면 메모리 누수가 발생할 수 있다. 즉, 더 이상 필요하지 않은 옵저버가 주체에 대한 참조를 유지하는 문제가 있을 수 있다. 사용 사례 1:1, 1:N 모두 가능하고 대부분 여러 객체가 한 객체의 상태 변화를 관찰하고 이에 반응해야 할 때 사용한다. GUI ..
컴포지트 패턴(Composite Pattern) 객체들을 트리 구조로 구성하여 전체-부분 계층 구조를 나타내는 데 사용되는 패턴 즉, 객체들을 트리 구조로 구성한 다음 이것을 개별 객체인 것처럼 사용할 수 있다. 구성 요소 Component : 구성에 포함된 객체들의 인터페이스를 선언하고 이러한 자식 구성 요소에 대한 액세스 및 관리를 위한 메서드를 구현한다. 즉, 모든 클래스에 해당하는 공통의 행동을 구현한다. Leaf : 자식이 없는 가장 끝 객체로 실제 작업을 수행한다. Composite(Container) : 자식 구성 요소를 저장하고 구성 요소 인터페이스에서 자식 관련 작업을 구현한다. 즉, 복합체는 자식 구성 요소를 포함하는 컨테이너 역할을 한다. Client : 구성 수조의 객체들과 상호 작..
팩토리 메소드 패턴(Factory Method Pattern) 객체 생성을 클라이언트 코드로부터 분리하고, 객체의 생성 방식을 하위 클래스에 위임하는 패턴 사용 방법 인터페이스나 추상 클래스를 사용하여 팩토리를 정의 인터페이스/추상 클래스를 상속하는 하위 클래스에서 팩토리 메소드 구현 클라이언트 코드에서는 인터페이스/추상 클래스를 통해 객체를 생성하며, 구체적인 팩토리 클래스는 런타임에 선택되거나 주입 장점 확장성 : 팩토리 클래스를 확장하여 객체 생성 로직을 쉽게 변경하거나 다양한 조건에 따라 객체 생성을 커스터마이징 할 수 있다. → 개방-폐쇄 원칙(OCP) 단점 복잡성 : 클래스 계층 구조가 더 복잡해 질 수 있다. 구현 코드 // Step 1: 팩토리 인터페이스 interface ShapeFact..
템플릿 메소드 패턴(Template Method Pattern) 슈퍼클래스에서 템플릿를 정의하고 구체적인 단계는 서브클래스에게 위임하는 패턴 사용 방법 슈퍼클래스에서 템플릿을 정의하고, 필요한 메소드를 추상 메소드나 구현된 메소드로 선언 서브클래스에서 추상 메소드를 구현하거나, 구체적인 메소드를 오버라이딩하여 알고리즘의 일부를 정의 슈퍼클래스에서 정의한 템플릿 메소드를 호출하여 알고리즘을 실행 장점 코드 중복 최소화 : 공통된 부분을 슈퍼클래스에서 구현하여 코드 중복을 방지할 수 있다. 확장성 : 서브클래스를 추가하거나 기존 클래스를 수정하지 않고 알고리즘을 확장할 수 있다. → 개방-폐쇄원칙 (OCP) 보장 단점 너무 많은 서브클래스가 생성되면 클래스 계층 구조가 복잡해질 수 있다. 상위 클래스의 로직..
싱글톤 패턴(Singleton Pattern) 어떤 클래스가 단 하나의 인스턴스만을 가지도록 하는 디자인 패턴 용도 리소스 공유 : 여러 부분에서 하나의 인스턴스를 공유해야 하는 경우 ex) 데이터베이스 연결, 네트워크 연결, 로깅 등 전역 객체 : 전역적으로 접근해야 하는 설정 정보나 상태 정보 관리 객체 생성 제어 : 객체 생성을 제한하고 특정 클래스의 인스턴스가 항상 하나만 생성되도록 보장 사용 방법 생성자 비공개 : 해당 클래스의 생성자를 private으로 선언하여 외부에서 객체를 직접 생성하는 것을 막는다. 정적 메서드로 인스턴스 제공 : 클래스 내부에 정적(static) 메서드(getInstance())를 생성하여 해당 메서드를 통해서만 객체 인스턴스를 얻을 수 있도록 한다. 장점 자원 공유와..
어댑터 패턴(Adapter Pattern) 호환되지 않는 인터페이스들을 연결하는 디자인 패턴 주요 구성 요소 타겟(Target) : 클라이언트가 사용하려는 새로운 인터페이스 어댑티(Adaptee) : 아직 호환되지 않은 기존 클래스/인터페이스 어댑터(Adapter) : 타켓 인터페이스를 구현하여 클라이언트 요청을 어댑티로 전달하는 클래스 클라이언트(Client) : 특정 작업을 요청하는 클래스 용도 및 필요성 기존 코드나 라이브러리를 수정하지 않고 새로운 인터페이스를 사용해야 할 때 다른 곳에서 개발한 클래스를 현재 시스템에 통합해야 할 때 이미 존재하는 클래스를 새로운 인터페이스로 감싸서 사용자가 편리하게 이용할 수 있도록 할 때 사용 방법 상속(extends)을 이용한 클래스 어댑터 패턴 객체(com..
