나무의 SW연구소

1. TCP와 IP TCP/IP는 Internet에서 사용되는 protocol이다. 1960년대 미국방성의 연구에서 시작되어 1980년대에 protocol model이 공개되었다. hardware, OS, 매체에 관계없이 동작할 수 있다. 패킷  통신 방식의 인터넷 프로토콜인 IP(Internet Protocol)와 전송 조절 프로토콜인 TCP(Transmission Control Protocol)로 이루어져있다. IP는 패킷 전달 여부를 보증하지 않고, 패킷을 보낸 순서와 받는 순서가 다를 수 있다. TCP는 IP 위에서 동작하는 프로토콜로, 데이터의 전달을 보증하고 보낸 순서대로 받게 해준다. HTTP, FTP, SMTP 등 TCP를 기반으로 한 많은 수의 application protocol들이 IP 위에서 동작하기 때문에 TCP/IP로 부르기도 한다. TCP/IP protocol은 OSI 모형보다 먼저 개발되었다. TCP/IP 프로토콜은 OSI 모형과 정확하게 일치하지는 않지만, OSI 모형을 4계층 혹은 5계층으로 분류하여 적용할 수 있다. 2. 각 Layer별 기능 Layer 1 : 네트워크 연결 계층 (Network Access Layer) - Ethernet, Wi-Fi, Token ring TCP/IP 패킷을 네트워크 매체로 전달하는 것과 네트워크 매체에서 TCP/IP 패킷을 받아들이는 과정을 담당한다. 기본적으로 에러검출 / 패킷의 프레임화를 담당한다. Layer 2 : 인터넷 계층 (Internet Layer) - IP (IPv4, IPv6) 논리적인 주소 IP를 이용한 노드간 전송과 라우팅 기능을 처리하게 된다. 네트워크상 최종 목적지까지 정확하게 연결되도록 연결성을 제공한다. Layer 3 : 전송 계층 (Transport Layer) - TCP, UDP, DCCP, SCTP, IL, RUDP 자료의 송수신을 담당한다. 애플리케이션 계층의 세션과 데이터그램 통신서비스 제공한다. Layer 4 : 응용

1. OSI 모형 (Open Systems Interconnection Reference Model) 국제표준화기구(ISO)에서 개발한 모델로 컴퓨터 네트워크 프로토콜 디자인과 통신을 계층으로 나누어 설명한 것이다. 이 모형을 이용하면 네트워크상에서 발생하는 문제의 원인이 어디에서 발생하는지 보다 쉽게 유추가 가능하다. 2. 각 Layer별 기능  Layer 1 : 물리 계층 (Physical Layer) 네트워크의 하드웨어 전송을 담당하는 계층으로 시스템의 전기적, 물리적 표현을 나타낸다. 케이블 종류, (802.11 무선 시스템에서와 같은) 무선 주파수 링크는 물론 핀 배치, 전압, 물리 요건 등이 포함된다. 네트워킹 문제가 발생하면 많은 네트워크 전문가가 물리 계층으로 바로 가서 모든 케이블이 제대로 연결돼 있는지, 라우터나 스위치 또는 컴퓨터에서 전원 플러그가 빠지지 않았는지 확인한다. Layer 2 : 데이터 링크 계층 (Data Link Layer) - 이더넷 노드 간 데이터 전송을 제공하며, 물리 계층의 오류 검출 및 수정에 필요한 기능적, 절차적 수단을 제공한다. 여기에는 2개의 부계층(매체 접근 제어(MAC), 논리적 연결 제어(LLC))이 존재한다. 주소값은 물리적으로 할당 받는데, 이는 네트워크 카드가 만들어질 때부터 MAC address가 정해져있다는 의미이다. 데이터 링크 계층의 가장 잘 알려진 예는 이더넷이다. 이 외에도 HDLC나 ADDCCP 같은 P2P(point-to-point) 프로토콜이나 패킷 스위칭 네트워크, LLC, ALOHA 같은 근거리 네트워크용 프로토콜이 있다. Layer 3 : 네트워크 계층 (Network Layer) - 라우터 여러 개의 노드를 거칠 때마다 경로를 찾아주는 역할을 하는 계층으로 라우터 기능의 대부분이 이 계층에 해당한다. 다양한 길이의 데이터를 네트워크들을 통해 전달하고, 그 과정에서 전송 계층이 요구하는 서비스 품질을 제공하기 위한 기능적, 절차적 수단을 제공한다. 네트워

1. 아스키 코드(ASCII) American Standard Code for Information Interchange의 약자로, 1960년대 미국 ANSI에서 표준화한 정보교환용 7비트 부호체계이다. 8비트 중에서 7비트만 사용하여 총 128개의 부호를 표기할 수 있다. 나머지 1비트는 통신 에러 검출을 위한 것으로 1의 개수가 홀수이면 1, 짝수이면 0으로 표기하였다. 이를 parity bit라고 한다. 이후 1비트를 더 확장한 ANSI 코드가 나왔으나 이것만으로는 다른 언어를 표현할 수 없었다. 이를 해결하기 위해 국제 표준 코드인 유니코드(Unicode)가 등장하게 되었다. [아스키 코드표] 2. 유니코드(Unicode) 초기 유니코드는 다양한 언어를 지원하기 위해 2바이트(=65536)로 용량을 확장하였다. 그러나 2바이트만으로는 고어(古語), 토속어 등을 담기에는 역부족이었다. 이러한 문제점을 해결하기위해 기본언어판과 보충언어판(BMP + SMP)으로 구성된 유니코드 3.0을 출시하게된다. (2019년 5월 7일 현재, 유니코드 버전 12.1) 유니코드 인코딩은 UTF-8, UTF-16, UTF-32 등이 있으며, 유니코드라 하면 일반적으로 UTF-8이 사용된다. UTF-8로 표현 가능한 길이는 최대 6바이트이나 다른 인코딩과의 호환을 위해 4바이트까지만 사용된다. 1바이트 영역은 아스키 코드와 하위 호환성을 가지며, 아스키 코드의 0~127까지는 UTF-8로 완전히 동일하게 사용된다. 아스키 코드와의 호환은 인터넷에서 가장 많이 사용되는 인코딩이 되는데 큰 이점으로 작용하였다. 유니코드가 쓰이기 전에는 대부분의 인터넷 문서들이 아스키 코드로 작성되었기 때문에 기존 인터넷 문서를 문제없이 호환된다는 것은 큰 장점이었다. UTF-8의 인코딩 규칙은 바이트가 추가될 때마다 1번째 바이트에 '1'로 표기해주는 방식이다. 1개의 바이트가 추가되었다면 '110'을, 2개의 바이트가 추가되었다면 

1. 커맨드 패턴 (command pattern) 각종 기능을 캡슐화하여 여러 기능을 실행/관리할 수 있다. 커맨드 패턴을 이용하면 요구 사항을 객체로 캡슐화 할 수 있으며, 매개변수를 써서 여러가지 다른 요구 사항을 집어 넣을 수도 있다. 또한 요청 내역을 큐에 저장하거나 로그로 기록할 수도 있으며, 작업 취소 기능도 지원할 수 있다. 커맨드 패턴은 (1)명령, (2)수신자, (3)발동자, (4)클라이언트로 이루어진다. - 명령(command) : 수행 동작을 담고 있는 클래스 - 수신자(receiver) : 명령 수행하는 클래스 (ex. TV, 오디오 등 각종 기기) - 발동자(invoker) : 명령 수행을 요청하는 클래스 (ex. 리모컨) - 클라이언트(client) : 어떤 명령을 수행할지 결정하는 클래스 (1) 명령 LightOnCommand 클래스는 Command 인터페이스를 구현하여, Light 객체의 On/Off를 실행할 수 있다. (2) 수신자 Light 클래스는 장소(mPlace)의 점/소등을 할 수 있다. Command 클래스의 execute() 메소드에서 호출한다. (3) 발동자 RemoteControl 클래스는 입력된 Command를 실행한다. 총 7개의 slot이 존재하고, 미리 Command를 입력한 뒤, slot 번호를 통해 명령을 실행할 수 있다. onButtonWasPushed()와 함께 slot 번호를 입력하면 slot에 해당하는 기기의 정의된 동작을 수행하게 된다. (4) 클라이언트 각 Command 객체와 RemoteControl 객체 생성한다. 명령의 실행과 시점을 결정한다. 하기에서는 main 클래스가 해당 역할을 담당한다. LivingRoom과 Kitchen의 점등과 소등 명령을 정의하였으며, onButtonWasPushed(), offButtonWasPushed()를 통해 실행할 수 있다. 2. 결과 수행 결과는 하기와 같다. 각 slot에 해당하는 사

1. 정의 소프트웨어 혹은 하드웨어의 제작자의 권리를 지키면서 원시 코드를 누구나 열람할 수 있도록 한 소프트웨어 혹은 오픈 소스 라이선스에 준하는 모든 통칭을 일컫는다. 2. 특징 - 소스 코드가 공개되어 있어 원하는대로 사용/복사/재배포 가능하다. - 공개된 소스의 무료 사용 권리가 있으나, 그에 따른 법적 책임이 뒤따른다. - 권한 및 책임의 종류에 따라 약 1,000가지의 다양한 open source license가 존재한다. - OSI(Open Source Initiative)에서 인증한 라이선스는 약 70여개가 있다. * 법적 위험을 피하기 위해 open source에 대해 잘 이해하고 대응해야 한다. 3. 소프트웨어 지적재산권 - 저작권(copyright) : 등록과 같은 절차 없이, 창작과 동시에 권리가 발생한다. 저작권자의 허가없이 저작물의 사용/복제/배포/수정이 불가능하다. - 특허권(patent) : 발명에 관하여 발생하는 권리로 출원의 절차가 필요하다. 특허 기술을 사용하기 위해서 특허권자의 허락이 필요하다. - 사용허가권(license) : 소프트웨어를 사용할 수 있는 권리를 의미한다. 4. 오픈 소스 라이선스 비교 - GPL : 미국 자유소프트웨어 재단이 만들었으며, open source의 53%를 차지하고, 공개범위가 넓다. Sourceforge의 60%이상을 차지하고 있는 대표적인 lisence. 대표적인 사례로는 Linux kernel, GNU tools(gcc, gdb 등), Samba등이 있다. - LGPL : 자유소프트웨어 재단이 open source 활성화를 위해 GPL의 소스 공개 의무를 완화한 lisence이다. 독점 library가 표준이 되는 것을 방지하기 위해 만들어졌다. 대표 소프트웨어는 GNU C library (glibc, uclibc)가 있다. - MPL : open source의 상용 제품 적용을 용이하게 하기 위해 모질라 재단에서 만들었다. 상용 소

1. 컴포지트 패턴 (composite pattern) 객체들의 관계를 트리 구조로 구성하여 부분-전체를 나타내는 계층 구조로 만들 수 있다. 이 패턴을 이용하면 클라이언트에서 단일 객체와 여러 객체들로 구성된 복합 객체 모두 동일하게 다루도록 한다. 쉽게 표현하자면 담는 그릇과 내용물을 동일하게 다루는 것으로 디렉토리 트리 구조가 이에 해당한다. 파일 관리자와 같은 디렉토리 트리 구조는 디렉토리와 파일을 동일한 개념으로 다룬다. 사용자가 디렉토리의 depth를 변경하며 이동할 수 있고, 특정 디렉토리에 속한 디렉토리와 파일 목록을 보여준다. 디렉토리와 파일을 담고 있는 디렉토리도 같은 레벨의 파일과 동일하게 취급하게 된다.(이해가 어려우면 당장 핸드폰의 파일관리자를 실행해보라.) 파일관리자와 클래스 다이어그램을 비교하자면 Composite 클래스는 디렉토리를, Leaf를 파일을 의미한다. Composite 클래스와 Leaf 클래스는 Component 추상 클래스를 상속받았기 때문에 동일하게 취급할 수 있다. 이러한 composite 패턴의 특징을 이용해 디렉토리 트리 구조를 만들고, 다룰 수 있다. Component는 추상 클래스로 Directory의 reference를 가지고 있다. add(), getChildren()은 필요 시 하위 클래스에서 override하여 구현한다. mParentDirectory는 부모 디렉토리 참조이며, getAbsolutePath() 호출 시 재귀호출을 통해 절대 경로를 완성한다. 클래스 다이어그램에 나타난 것과 같이 Directory 클래스는 하위 클래스를 가질 수 있고, 이를 지원하기 위한 메소드를 override하여 정의한다. File 클래스는 Leaf에 해당하는 클래스로 트리 구조의 마지막에 위치한다.

1. 싱글턴 패턴 (singleton pattern) 생성자가 여러 차례 호출되더라도 실제로 생성되는 객체는 하나이고, 최초 생성 이후에 호출된 생성자는 최초의 생성자가 생성한 객체를 return한다. 즉 해당 클래스의 인스턴스가 하나만 만들어지고, 어디서든지 그 인스턴스에 접근할 수 있다. 보통 getInstance()로 불리오는 정적 메소드를 호출하는 형식으로 구현된다. 클래스 다이어그램을 살펴보면 클래스 내부의 singleton 객체와 생성자는 private로 외부에서 접근이 불가하나, getInstance()를 통해 객체를 생성하고 얻을 수 있도록 접근제어자가 public으로 설정되어 있다. 코드를 살펴보면 위에 언급한대로 구현되어 있는 상태이다. getInstance() 메소드를 살펴보면 동기화(syncronized)처리가 되어 있는 것을 확인할 수 있는데, 다중 thread 상황에서 mSingleton 객체가 만들어지기 전에 2개 이상의 thread가 접근해 객체를 여러 개 만드는 경우가 발생할 수 있다. 이를 위해 syncronized 처리를 한 것인데, 동기화 처리를 하면 속도가 많이 저하된다. 객체가 2개 이상 만들어 질 수 있는 때는 최초 생성하는 경우인데, 동기화에 따르는 비용이 크기 때문에 큰 문제가 아니라면 그냥 두는 것도 방법일 수 있다.

1. 데코레이터 패턴 (decorator pattern) 데코레이터 패턴에서는 객체에 추가적인 요건을 동적으로 첨가한다. 데코레이터는 서브클래스를 만드는 것을 통해서 기능을 유연하게 확장할 수 있는 방법을 제공한다. 쉽게 말해 샌드위치와 같이 본래의 재료에 무언가를 추가할 때 사용된다. 클래스 다이어그램을 살펴보면 Component는 기본적인 재료를 의미한다. 샌드위치로 예를 들자면 Component는 "빵"이라고 할 수 있다. 기본 재료인 "빵"에 Decorator 를 상속받은 ConcreteDecoratorA, ConcreteDecoratorB를 사용하여 각종 햄, 야채, 소스를 추가하면 된다. Decorator 객체는 Component의 reference를 가지고 있고, 이 곳에 꾸며야 할 객체(ConcreteComponent)를 전달받아 여러 가지 동작/정보를 추가하게 된다. Beverage 클래스는 Component에 해당하는 객체로 기본적인 음료를 나타내는 추상 클래스이다. CondimentDecorator 클래스는 Decorator의 역할을 하는 클래스로 첨가물을 나타내는 추상클래스이다. 전달받은 Beverage 클래스를 저장하여, 꾸며 주게(첨가물 추가) 된다. DarkRoast 객체는 Beverage를 상속받은 클래스로 ConcreteComponent의 역할을 한다. 명칭과 가격을 정의했다.  마지막으로 Moca 클래스는 ConcreteDecorateA의 역할을 하며, 넘겨받는 DarkRoast 클래스에 Moca를 추가하고, 명칭과 가격을 꾸며주게 된다. 사용하는 코드는 다음과 같다. 자바 I/O 패키지에 데코레이터 패턴이 다수 적용되어 있다. FileInputStream → BufferedInputStream → LineNumberInputStream으로 이어지는 확장 구조를 가지고 있다. FileInputSream은 파일을 읽어들이는 기본 동작을 정의하며

1. 옵저버 패턴 (observer pattern) 옵저버 패턴(observer pattern)은 한 객체의 상태가 바뀌면 그 객체에 의존하는 다른 객체들한테 연락이 가고 자동으로 내용이 갱신되는 방식으로 일대다(one-to-many) 의존성을 가지는 구조를 의미한다. 쉽게 말해 여행 준비를 할 때 '준비가 완료되었는지 매 순간 확인하지 않고, 준비가 완료되면 연락받는 것'과 같다. 옵저버 패턴은 느슨한 결합(loose coupling)으로 두 객체가 연결되는데, 이는 상호작용을 하긴 하지만 서로에 대해 잘 모른다는 것을 의미한다. 옵저버(연락을 받는 객체)가 연락을 받고 싶다면 주체(연락을 하는 객체)에서 정의한 interface를 구현한 뒤 주체에게 등록만 하면 된다. 주체는 옵저버가 무엇을하는지 어떤 클래스를 상속받고 있는지 등에 대해 전혀 알지 않아도 되며, 주체 또는 옵저버가 바뀌더라도 서로에게 영향을 미치지 않는다. 각각의 코드를 살펴보면 ConcretePublischer 객체는 연락을하는 주체로 Observer가 등록되면 ArrayList로 Observer관리하고 이벤트 발생 시 loop를 돌며 등록된 observer에 연락을 준다. registerObserver()를 통해 옵저버를 등록할 수 있으며, unregisterObserver()를 통해 등록된 옵저버를 제거할 수 있다. 연락을 받는 옵저버는 옵저버 interface를 구현한 뒤 Publisher에게 연락을 받기 위해 등록하면 연락받을 준비가 완료되며, 이 후 Publisher에서 Callback이 오면 해당 동작을 처리하면된다. 옵저버 패턴을 사용하면 어떤 정보가 필요한 경우 매 번 확인을 하지 않고, 이벤트가 발생하는 순간에 주체로부터 연락을 받을 수 있다. 옵저버 패턴의 일반적인 사례는 사용자 입력에 대한 이벤트(OnClickListener) 처리가 있으며, MVC(Model-View-Controller) 패턴과 자주

1. 스트래티지 패턴 (strategy pattern) 스트래티지 패턴(strategy pattern)에서는 알고리즘군을 정의하고 각각을 캡슐화하여 교환해서 사용할 수 있도록 만든다. 스트래티지를 활용하면 알고리즘을 사용하는 클라이언트와는 독립적으로 알고리즘을 변경할 수 있다. 쉽게 이야기하자면 지정된 알고리즘의 세부 구현을 변경할 필요없이 쉽게 교환할 수 있게 해주는 디자인 패턴이다. 클래스 다이어그램을 살펴보면 오리의 행동을 정의한 2가지 interface가 존재하고, Duck 클래스를 상속받은 오리(MallardDuck, RedheadDuck, RubberDuck)은 각자에게 맞는 행동 객체를 할당하여 사용할 수 있다. 만일 행위가 변경된다면 원하는 행동 객체를 할당하여 쉽게 교체하여 사용할 수 있다. 하기의 RubberDuck을 구현한 코드를 살펴보면 RubberDuck에 맞게 FlyBehavior와 QuackBehavior에 객체를 할당하여 사용하면 되며, 행위에 변경이 발생하더라도 해당 행위에 맞는 객체로 교체해주면 쉽게 동작을 변경할 수 있다. 위의 방식처럼 클래스를 합치는 것을 구성(composition) 관계라 한다. 구성(composition)이란 클래스를 상속하는 대신 기존 클래스(super class)의 인스턴스를 참조하는 private 필드를 서브 클래스로 만들고자 했던 클래스에 만드는 것이다. 즉 RubberDuck 클래스는 Duck 클래스를 상속하는 대신에 Duck 클래스에 추가된 FlyBehavior와 QuackBehavior를 RubberDuck 클래스에서 행동에 맞는 객체를 할당하여 사용하였다. 이와같이 구조를 잡을 때에는 각 클래스의 관계가 'is-a'인지, 'has-a'인지를 이해하고, 관계에 맞는 구조를 잡아주는 것이 좋다. 만일 두 클래스 간의 관계에 대해 자신있게 'is-a'가 맞다고 이야기할 수 없다면 상속(inheritance)은 피해야 하며,

1. 디자인 패턴 (design pattern) 디자인 패턴은 개발 과정에서 겪게되는 공통된 문제들에 대해 전문가들의 경험을 모아 표준적인 해법을 구조화한 것으로, 디자인 패턴을 숙지하면 개발자간의 원활한 커뮤니케이션이 가능해진다. 디자인 패턴은 GoF(Gang of Four)에 의한 고안된 것으로 보는 것이 일반적이다. GoF는 에릭 감마(Erich Gamma), 리처드 헬름(Richard Helm), 랄프 존슨(Ralph Johnson), 존 블리스데스(John Vlissides)에 의해 고안된 것으로 알려져있다. 2. SOLID 원칙 좋은 객체지향 설계를 위해서는 기본적으로 5가지 원칙을 따르는 것이 좋다. 5가지 원칙은 각각의 앞글자를 따서 SOLID라고 부른다. 좋은 설계란 응집도는 높게, 결합도는 낮게 설계된 것을 이야기한다. - SRP (Single Responsibility Principle, 단일 책임 원칙) 객체는 단 하나의 책임만 가져야한다. 즉 어떤 변화에 의해 클래스를 변경해야 하는 이유는 오직 하나뿐이어야 함을 의미한다. - OCP (Open-Closed Principle, 개방-폐쇄 원칙) 변경에는 닫혀있고, 확장에는 열려있어야한다. 요구사항의 변경이나 추가가 발생하더라도, 기존 코드에는 수정이 일어나지 않고, 쉽게 확장할 수 있어야 한다는 의미이다. - LSP (Liskov Substitution Principle, 리스코프 치환 원칙) 자식 클래스는 부모 클래스의 역할을 대체할 수 있어야한다. 자식 클래스는 부모 클래스의 책임을 무시하거나 재정의하지 않고, 확장만 수행해야한다. - ISP (Interface Segregation Principle, 인터페이스 분리 원칙) 사용하지 않는 인터페이스는 구현하지 말아야한다. 하나의 일반적인 interface보다는 여러 개의 구체적인 interface가 낫다. - DIP (Dependency Inversion Principle, 의존 역전 원칙)

1. 알고리즘 (algorithm) 알고리즘이란 어떠한 문제를 해결하기 위해 정해진 일련의 절차나 방법을 공식화한 형태로 표현한 것을 의미한다. 알고리즘(algorithm)의 어원은 9세기 페르시아의 수학자인 무하마드 알콰리즈미(Muhammad al-Kwarizmi)의 이름을 라틴어화한 algorismus에서 따온 말이다. - 성능(시간복잡도)과 빅-오 표기법(Big-O Notation) 복잡한 알고리즘일수록 성능을 정확하게 계산하기란 매우 어려운 일이다. 따라서 알고리즘이 복잡할 때 전체 수행 시간에 큰 영향을 미치는 부분만을 고려하여 보다 직관적으로 성능을 추정하고, 표현할 필요가 있다. 이런 경우에 일반적으로 빅-오 표기법(Big-O Notation)을 많이 사용한다. 빅-오 표기법(Big-O Notation)이란 주어진 함수에서 가장 빨리 증가하는 항만을 남긴 채 나머지를 생략하는 표기법이다. 입으로 소리내어 읽을 때 O는 order라고 읽는다. O(n²)은 order and 제곱이라고 읽는다. 빅-오 표기법에 따라 주요 알고리즘의 속도는 하기와 같이 표현된다. O(1)       : 상수적 (배열의 원소 접근, 단순 명령문) O(lg(n))   : 대수적 (이진 검색) [lg(n)은 log₂(n)의 줄인 표현] O(n)       : 선형적 (순차 검색) O(nlg(n)) : 선형적보다는 좋지 않음. (퀵 정렬과 힙 정렬의 평균 수행 시간) O(n²)      : 제곱적 (선택 정렬과 삽입 정렬) O(n³)      : 세제곱적 (두 n x n 행렬의 곱) O(Cⁿ)      : 지수적 (여행하는 판매원 문제, 집합 분할) * n → 입력의 크기 반복문의 수행 횟수는 알고리즘의 성능과 직결된다.빅-오 표기법에 나타나는 알고리즘 성능 추정도 반복문의 수행 횟수를 기반으로 한다. 뛰어난 성능을 자랑하는 이진 탐색은 정렬되어 있는 특징을 이용하여, 약 43억개의 원소가 있는 리스트에서 특정 값을 찾아낼 때 최악의 경우에

1. 퀵 정렬(quick sort) 다른 원소와의 비교만으로 정렬을 수행하는 비교 정렬에 속한다. 분할 정복 알고리즘의 하나로 평균적으로 매우 빠른 수행 속도를 자랑하는 정렬 방법이다. - 시간 복잡성 best-case : O(n lg n) [lg(n)은 log₂(n)의 줄인 표현] average-case : O(n lg n) worst-case:  O(n²) - Java 코드 2. 병합 정렬(merge sort) 분할 정복 알고리즘의 하나로, 나뉘어지지 않을 때까지 리스트를 분할한 뒤 하위 리스트를 정렬한 후 각가을 하나로 합친다. - 시작 복잡성 best-case : O(n lg n) [lg(n)은 log₂(n)의 줄인 표현] average-case : O(n lg n) worst-case:  O( n lg n ) - Java 코드 3. 이진 탐색(binary search) 리스트가 정렬되어 있지 않으면 검색 시 주어진 값에 맞는 원소를 찾기 위해 리스트를 모두 찾아봐야 한다. 하지만 정렬된 리스트가 있거나 검색하기 전에 정렬을 수행한 상황이라면 리스트에서 값을 찾을 때 이진 검색을 사용하는 것이 매우 효율적인 방법이다. 43억개의 원소가 있는 리스트에서 특정 값을 찾아낼 때 최악의 탐색 깊이는 32회이다. - 시간 복잡성 best-case : O(lg n) [lg(n)은 log₂(n)의 줄인 표현] average-case : O(lg n) worst-case : O(lg n) - Java 코드

1. 버블 정렬 (bubble sort) 버블 정렬은 인접한 2개의 원소를 비교하여 정렬을 완성하는 알고리즘이다. 거품이 수면 위로 올라오는 듯한 모습을 보여 버블 정렬이라 불린다. - 시간 복잡성 best-case :  이미 정렬되어 있는 경우 →  O(n) average-case :  O(n²) worst-case : 역순으로 정렬되어 있는 경우  →  O(n²) - Java 코드 2. 삽입 정렬 (insertion sort) 자료 배열의 모든 요소를 앞에서부터 차례대로 이미 정렬된 배열 부분과 비교하여, 자신의 위치를 찾아 삽입하여 정렬을 완성하는 알고리즘이다. 정렬할 리스트가 완성되면 작업을 멈추고 즉시 반환할 수 있다. 다만 버블 정렬은 교환을 위한 임시변수만 필요한 것에 비하여, 삽입 정렬의 경우 정렬하려는 리스트의 2배 정도되는 저장 공간이 필요하다. - 시간 복잡성 best-case : 역순으로 정렬되어 있는 경우  →  O(n) average-case :  O(n²) worst-case : 이미 정렬되어 있는 경우  →  O(n²) - Java 코드

1. Method Area (= Static Area = Class Area = Code Area) Java Compiler가 일차적으로 컴파일한 바이트코드(.class)을 Class Loader를 통해 읽어 저장하는 영역. 클래스/인터페이스에 대한 상수 풀, 멤버변수, static 변수, 생성자와 메소드를 저장하는 영역 * Class Loader : Runtime 시 바이트코드를 로딩한다. * Excution Engine : Runtime Data Area에 배치된 바이트 코드를 명령어 단위로 실행한다. * Garbage Collector : heap을 사용 가능한 만큼 자유롭게 사용하고, 더 이상 사용되지 않는 object들은 GC 프로세스가 메모리에서 제거한다. Heap영역의 object 중 stack에서 도달불가능한(unreachable) object는 garbage collection의 대상이 된다. * Runtime Data Area : JVM이 OS에서 할당받은 메모리 영역이다. 2. Stack Area 기본 타입(primitive type) 변수가 저장되는 영역. Heap Area에 생성된 객체의 주소가 참조 타입 변수에 할당된다. 각 Thread는 자신만의 Stack Area를 가진다. CPU에서 LIFO(Last In, First Out) 형식으로 관리된다. 함수가 종료되면 모든 변수가 스택에서 팝아웃된다. 3. Heap Area JVM이 관리하는 프로그램에서 데이터를 저장하기 위하여 동적으로 할당하여 사용하는 메모리 영역이다. 모든 Object 타입은 Heap Area에 저장되며, 하나의 Heap Area만 존재한다. Garbage Collector를 통해 메모리가 반환된다. 1) Permanent : 생성된 객체들의 주소 값이 저장된 공간 2) New Area - Eden : 객체들이 최초로 생성되는 공간 - Survivor : Eden에서 참조되는 객체들이 저장되는 공간 3) Old Ar

1. Java Compiler 소스코드(.java)를 바이트코드(.class)로 번역한다. 2. android apk build 과정 .java → .class → .dex → .apk → 서명 및 최적화 → release - java compiler에 의해 .class 파일로 컴파일 - 생성된 .class 파일을 android DX tool을 통해 .dex로 변환 - .dex과 resource를 합쳐 .apk로 압축 3. JIT Compiler (Just In Time) → Dalvik 실행 시점에 바이트코드(.dex)를 기계어로 번역한다. 인터프리터 방식의 언어들이 성능 향상을 목적으로 도입하는 경우가 많으며, 자주 사용되는 코드는 매 번 번역하지 않고, 캐싱하여 성능을 개선한다. 메소드 단위로 JIT 컴파일하는 방식과 실행 흐름을 실시간으로 추적하며 컴파일하는 Tracing JIT 방식으로 분류된다. 용량↓, 설치속도↑, 실행속도↓, 배터리 사용↑, CPU 사용↑ 4. AOT Compiler (Ahead Of Time) → Android RunTime 설치 시점에 기계어로 번역한다. 용량↑, 설치 속도↓, 실행 속도↑, 배터리 사용↓, CPU 사용↓ Dalvik은 dexopt를 통해 dex 파일을 최적화한 odex(optimized dex)를 만든다. odex는 특정 시스템에 최적화된 코드로 다른 시스템(기기)에서는 사용할 수 없다. DVM은 odex 파일을 앱 실행시 기계어로 번역한다. ART는 AOT 컴파일 시 dex2oat를 통해 dex → odex → oat로 변경한다. oat 파일은 elf 파일 형식의 기계어를 포함하는 파일이다. oat 파일은 기계어로 완전히 번역된 파일이기 때문에 VM없이도 바로 실행가능하나, Dalvik과의 호환성을 위하여 VM 위에서 돌아가는 것처럼 실행된다. L-OS(5.0, API 21)부터 ART(AOT)가 적용되었으며, N-OS(7.0, AP