본문 바로가기

CS

 (39)
정적 팩토리 메서드(Static Factory Method) 패스트 캠퍼스의 강의를 듣던 중 정적 팩토리 메서드를 사용하는 상황을 보았다. 처음 보는 객체 생성 방식이길래 찾아보던 중 이것이 정적 팩토리 메서드라는 것을 알게 되었고, 관련 내용을 찾아보던 중 이펙티브 자바라는 책을 알게 되었다. 조슈아 블로크의 Effective Java에서 첫 번째 아이템으로 '생성자 대신 정적 팩토리 메서드를 고려하라'는 주제를 내놓았다. 정적 팩토리 메서드가 과연 무엇이고, 왜 써야 할까? Static Factory Method에 관해 다양한 블로그와 강의 영상이 있지만, 인프런에서 백기선 강사님의 를 참고하였습니다. Static Factory Method 정적 팩토리 메서드는 객체 생성 역할을 하는 클래스 메서드로 생성자(Contstructor)를 통해서가 아닌 Static..
[Sorting] 퀵 정렬 저번 포스팅에서는 분할 정복 알고리즘을 사용한 Merge Sort에 대해 알아보았다. 최악과 최선 모두 O(nlogn)의 시간 복잡도를 가지고 있어 데이터의 양이 많아도 항상 일정한 속도를 유지할 수 있다. Quick Sort 역시 분할 정복 알고리즘을 활용한 정렬방법이다. 나누는 기준점에 따라 최악의 경우 O(n^2)이 걸리기도 하지만 보통 O(nlogn)의 시간이 걸린다. 그럼에도 불구하고 퀵 정렬은 높은 효율을 보인다. 더 깊이 알아보도록 하자. Quick Sort 데이터 집합에서 하나의 Pivot(기준점 데이터)을 잡는다. 왼쪽에는 Pivot보다 작은 값을, 오른쪽에는 Pivot보다 큰 값들로 나누어 분리한다. 분리가 되었다면 Pivot의 데이터는 자신의 위치를 찾게 된다. 이후 다시 정렬이 안된..
[Sorting] 병합정렬 지난 포스팅(버블, 선택, 삽입 정렬)에 이어 오늘은 Merge Sort에 대해 알아보려고 한다. Merge Sort는 분할정복 알고리즘 중 하나로 최소 단위로 쪼개고 병합하는 과정에서 정렬이 이루어진다. Merge Sort의 시간복잡도의 경우 최악, 평균, 최선 모두 O(nlogn)의 시간복잡도를 가진다. Merge Sort 병합정렬로 최소단위까지 나눈 후 다시 결합시키면서 정렬해 가는 알고리즘으로 Merge Sort는 분할정복 알고리즘을 사용한 정렬방법이다. Not In Place Sorting : 추가적인 메모리 공간이 필요하므로 제자리 정렬이 아니다. Stable Sorting : 중복된 데이터를 순서대로 정렬 정렬 과정 데이터 집합을 N/2씩 최소 단위가 될 때까지 나눈다.(마지막 2개에서 1개..
JVM 구조 JAVA는 OS와 상관없이 Window, Linux, MacOS 등 어디에서든 실행할 수 있다. C언어와 다르게 자바는 JVM위에서 실행되므로 OS를 가리지 않는 것이다. 다만 OS에 맞는 JVM을 별도로 설치해줘야 한다. 따라서 우리는 플랫폼에 상관없이 하나의 자바 소스와 자바 컴파일러를 통해 코드를 실행할 수 있게 되었다. JVM(Java Virtual Machine) 자바 가상머신이라고 불리며 자바와 운영체제 사이에서 중개해주는 역할을 하며, 자바 언어가 CPU나 운영체제에 구애받지 않고 실행될 수 있도록 도움을 준다. Java source : 사용자가 작성한 자바 코드 Java Compiler : 기계가 읽을 수 있도록 해석하여 Byte Code로 변환 Class File : 자바 컴파일러에 의해..
[Sorting] 버블정렬, 선택정렬, 삽입정렬 정렬은 데이터의 집합을 특정 기준을 두고 우선 순위에 맞게 데이터를 저장하는 것이다. 대표적인 예로 오름차순과 내림차순이 있다. 정렬에도 다양한 알고리즘이 있지만 오늘은 정렬하는데 O(n^2)의 시간이 필요한 Bubble, Selection, Insertion Sorting에 알아보려고 한다. Bubble Sorting 버블 정렬은 서로 인접한 두 데이터를 비교하고 조건에 맞지 않으면 두 데이터의 위치를 바꾼다. 그러면서 모든 데이터들이 조건에 맞는 위치에 찾아가게 된다. In-place Sorting(제자리 정렬) - 추가적인 메모리 공간을 필요로 하지 않음 Stable Sorting(안정 정렬) 정렬과정 화살표는 현재 비교하려는 데이터이고 항상 자신의 오른쪽 데이터와 비교를 한다. 따라서 화살표가 가..
우선순위 큐 Priority Queue 큐(Queue)는 우선순위와 상관없이 먼저 들어간 데이터가 먼저 나오는 FIFO 방식의 자료구조이다. 우선순위 큐는 들어간 순서에 상관없이 우선순위가 높은 데이터가 우선적으로 나오는 자료구조이다. 그렇다면 우선순위 큐는 어떻게 구현할 수 있을까? 1. 배열로 우선순위 큐 구현하기 우선순위대로 데이터들이 들어온다고 가정했을 때, 우선순위대로 앞의 인덱스부터 채워나가면 되기 때문에 문제가 되지 않는다.(데이터가 모두 들어오고 난 뒤에는 정렬된 상태) 하지만 연속적인 우선 순위 데이터의 입력이 보장되지 않을 경우에는 우선 순위에 맞춰 데이터를 이동시켜야 한다. 이렇게 할 경우 처음 인덱스부터 우선순위를 비교해야 하기 때문에 데이터 삽입의 최악의 시간 복잡도는 O(n)이 걸리게 된다. Enqueue : O(n)..
Process란 OS에서 프로세스는 하나의 작업 단위를 말한다. 사용자가 프로그램을 실행하면 HDD 또는 SDD 저장장치에서 프로그램 코드를 메모리로 가져오게 되면서(Fetch) 하나의 작업이 생성된다. 이러한 작업들은 CPU를 할당받아 처리되어진다. 프로그램은 명령어, 코드 및 정적 데이터들의 묶음이라 보면 된다. Process 실행 중인 프로그램을 말하며, 원초적으로는 하나의 쓰레드만을 가지고 있는 단일 스레드 프로세스를 의미한다. 프로세스가 생성되는 과정 1. 사용자에 의해 프로그램이 실행되어진다. 2. 프로그램 실행에 필요한 코드와 자원들을 메모리로 옮긴다(Fetch). 3. 해당 프로세스의 정보를 가지고 있는 PCB(Process Control Block)가 같이 생성된다. 4. 해당 프로세스는 준비 큐에 들어..
스택과 큐 스택과 큐는 선형의 자료구조로 순서를 가지고 있고, 메모리에 연속적으로 저장된다. 스택과 큐 모두 배열과 연결리스트로 구현 가능하다. 배열로 구현할 경우 확실한 메모리의 사용크기를 알 수 없어 연결리스트로 구현하는 편이 좀 더 쉽다. STACK 스택의 사전적 의미 "쌓이다" 처럼 데이터들이 차곡차곡 쌓이는 자료구조의 모습이다. LIFO(Last In First Out, 후입선출) 구조로 가장 마지막에 저장된 데이터가 가장 먼저 출력된다. 스택은 한 곳으로만 접근할 수 있으며 이 곳을 탑(또는 SP, 스택포인터)이라고 부른다. 스택의 주요 연산으로는 push(삽입)와 pop(삭제)이 있다.위의 그림에서 최초의 탑은 0번 인덱스를 가리키고 있고 데이터가 들어갈 때마다 탑이 가리키는 포인터는 다음 인덱스의 위..

티스토리툴바