힙 정렬(heap sort)
힙 정렬(Heap Sort) 완전 이진 트리를 기본으로 하는 힙 자료구조를 기반으로 한 정렬 방식이다. 불안정 정렬에 속한다. [완전 이진 트리?] 삽입할 때, 왼쪽부터 차례대로 추가하는 이진 트리 시간 복잡도 평균 : O(N logN) 최선 : O(N logN) 최악 : O(N logN) 로직 최대 힙을 구성...
힙 정렬(Heap Sort) 완전 이진 트리를 기본으로 하는 힙 자료구조를 기반으로 한 정렬 방식이다. 불안정 정렬에 속한다. [완전 이진 트리?] 삽입할 때, 왼쪽부터 차례대로 추가하는 이진 트리 시간 복잡도 평균 : O(N logN) 최선 : O(N logN) 최악 : O(N logN) 로직 최대 힙을 구성...
프로세스 vs 스레드 프로그램이란? 어떤 작업을 위해 실행할 수 있는 파일을 의미한다. 프로세스(Process) 실행 중인 프로그램으로 디스크로부터 메모리에 적재되어 CPU의 할당을 받은 작업의 단위다. 운영체제로부터 시스템 자원을 할당받는다. 할당받는 시스템 자원 CPU 시간 운영되기 위...
투포인터 알고리즘 투포인터 알고리즘(Two Pointers Algorithm) 또는 슬라이딩 윈도우(Sliding Window)라고 부른다. 이번에 20년도 상반기 라인 공채 코딩 테스트에서 이를 활용할 만한 문제가 나왔다. 그래서 예전에 정리했던 내용을 떠올리며, 다시 정리하려 글을 쓴다. 알고리즘 문제를 풀다 완전탐색으로 해결하면 시간 초과가 ...
퀵 정렬(Quick Sort) 개념 퀵 정렬은 분할 정복 방법을 통해 주어진 배열을 정렬한다. 분할 정복(Divide and Conquer) : 문제를 작은 2개의 문제로 분리하고 각각을 해결한 다음, 결과를 모아서 원래의 문제를 해결하는 전략이다. 불안정 정렬에 속하며, 다른 원소와의 비교만으로 정렬을 ...
들어가기에 앞서 class Test{ // 생성자가 없는 기본 클래스의 형태. } class Test(){ // 인자가 없는 생성자가 있는 클래스의 형태. } 생성자 자바와 조금 다르다 init 블록을 사용해 기본 생성자를 대체할 수 있다. 생성자에 인자가 필요한 경우 인자처럼 받을 수 있다. → 이를 주 생성자라 부른다. ...
Kotlin의 특징을 정말 간단하고 보기 쉽게 정리하는 공간입니다. 람다 표현식을 지원한다. 스트림 API를 지원한다. 자바와 완벽하게 호환된다. 간결한 문법 세미 콜론을 사용하지 않는다. new를 사용하지 않고 객체를 생성. 타입 추론을 지원한다. var : 수정 가능한 변수 val : 수정 불가능한 값 반복문은 fo...
컴퓨터 시스템의 동작 원리 컴퓨터 내부 장치 : CPU, 메모리 컴퓨터 외부 장치 : 키보드, 모니터, 마우스 등등 컴퓨터 내의 각 하드웨어 장치에는 컨트롤러가 존재한다. 컨트롤러는 일종의 작은 CPU로서, 컴퓨터 전체에 CPU라는 중앙 처리 장치가 있듯이 컨트롤러는 각 하드웨어 장치마다 존재하면서 이들을 제어하는 작은 CPU라 할 수 있다. ...
주소창에 naver.com을 치면 일어나는 일 면접 질문에서도 종종 나오는 방식이다. 이해하기 전에 IP 주소와 도메인에 대한 사전 지식이 필요하다. IP 주소 IP 주소란 많은 컴퓨터들이 인터넷 상에서 서로를 인식하기 위해 지정받은 식별용 번호라고 생각하면 된다. 현재는 IPv4 버전(32비트)로 구성되어 있으며, 한번씩은 들어봤을 법...
인터럽트의 원리 인터럽트란? CPU가 어떤 프로그램을 실행하고 있을 때, 입출력 하드웨어 혹은 소프트웨어에 의해 예외상황이 발생하여 처리가 필요한 경우, CPU에게 이를 알려주는 것을 말한다. 예를 들어, A라는 프로그램이 CPU를 할당받고 명령을 수행하고 있는데, 인터럽트가 발생하면 A는 현재 수행 중인 명령의 위치를 저장해 놓는다. 그...
인터럽트(Interrupt) 하드웨어 장치가 CPU에게 어떤 사실을 알려주거나 CPU의 서비스를 요청해야 할 경우, CPU 내에 있는 인터럽트 라인을 세팅하여 인터럽트를 발생시킨다. (프로그램이 명령을 수행하기 위해서는 CPU를 할당받아야 함) CPU는 매번 프로그램 카운터가 가리고 있는 곳의 명령을 수행한 뒤, 다음 명령을 수행하기 직전에...