퀵 정렬 (Quick Sort) 기본적으로 배열 요소 갯수가 0이나 1개가 될 때까지 쪼개는 합병정렬과 유사하다. 여기서 피벗포인트라 부르는 단일 요소를 선택하여 수행하는 것이 차이점이다. 중앙점이 아닌, 이 피벗포인트를 기준으로 배열을 한 번 순회하여 기준보다 작은 수를 왼쪽 그룹으로, 큰 수를 오른쪽 그룹으로 이동시킨다. 로직을 이해하고 구현하는 데에 난이도가 좀 있는.. 알고리즘이다. 1. 피벗 헬퍼 앞선 합병정렬에서 합병로직을 먼저 구현했던 것처럼, 퀵정렬에서도 피벗 헬퍼를 통해 퀵정렬에 사용할 메서드를 모듈화해준다. 피벗 헬퍼는 주어진 배열 요소를 피벗 포인트로 지정하여 배열 속 요소를 재배치한다. 좌/우 배열 내의 정렬 여부는 당장 중요하지 않다. 피벗의 선택 기준 배열의 모든 요소 값들을 알..
앞서 배운 정렬 알고리즘들은.. (버블, 삽입, 선택) 작은 규모의 배열에서는 잘 작동하지만, 규모가 커질수록 잘 적용되지 않는다. 합병정렬 (Merge Sort) 0. 개요 배열을 더 작은 배열로 나누는 방식 (분할정복 알고리즘), 요소 배열이 0개나 1개가 될 때까지 반복 0개나 1개가 된 요소 배열 모음을 다시 병합함. 이 과정에서 정렬이 이루어짐. 예를 들어 8개의 원소를 가진 배열을 합병정렬하고자 한다면, 4 -> 2 -> 1개의 원소 그룹으로 나누고 1 -> 2 -> 4 -> 8개로 합치는 과정에서 정렬 1. 로직 구현 의사코드 정렬된 두 배열의 합병을 담당할 함수 구현. 입력 배열 두 개에 있는 모든 요소를 포함 초기값이 0인 I와 J 카운터를 두 배열에 각각 배치하여 While문을 통해 구..
File Allocation 파일에서는 블록 단위로 데이터를 저장한다. 블록 하나의 크기는 4,096Byte이다. 파일 내부에 여러 개의 블록이 존재할 때, 이들을 연결해주는 것을 File Allocation이라 한다. Allocation에는 아래와 같은 방법이 존재한다. Contiguous Allocation 디스크 내부에 존재하는 연속된 블록들을 할당해 파일을 저장하는 방법. 파일 구성 테이블이 존재하는데, 이 테이블에 파일명 - 시작 블록 인덱스 - 블록 길이가 들어있다. 장점 Read/Write 처리하는 데에 시간이 적게 걸린다 단점 External Fragmentation이 발생. 먼저 Fragmatation이란 메모리에 생기는 작은 빈 공간을 말하는데, 빈 공간이 덩어리로 이루어져 있지 않고,..
선택정렬 큰 값을 배열 마지막 인덱스에 위치시키는 버블정렬과 달리, 작은 값을 한 번에 하나씩 위치시킨다. 기준 값과 나머지 원소들을 전부 순회하며 비교하여, 가장 작은 값과 자리를 바꾼다. 의사코드 최솟값 인덱스를 저장할 변수 필요. 초기값은 시작하는 기준 값과 동일하게 설정해주면 될 듯. 기준값부터 나머지 원소를 순회하며 최소값 인덱스를 갱신, 저장 기준값과 최소값 교환 원래 기준값 다음 인덱스부터 1,2,3 과정 반복 구현 function selectSort(arr) { for (var i = 0; i arr[minIdx]) { let tmp = arr[i]; arr[i] = arr[minIdx]; arr[minIdx] = tmp; } } return arr; } const arr = [4, 24,..
데이터를 정렬할 수 있는 방법은 무수히 많고, 각 알고리즘은 장단점을 갖고 있다. 같은 결과값을 갖더라도 결과를 내기까지의 과정이 제각기 다르다. 특정 상황에 유난히 잘 작동하는 정렬 방법이 존재하고, 이를 잘 활용하게 하기 위함 버블 정렬 자바스크립트 내장 정렬 메서드 array.sort() : num1 - num2 가 양수를 반환하면 num2가 앞에, 음수를 반환하면 num1이 앞에 온다. 숫자 뿐 아니라 문자열으 길이를 음수/양수로 구분하여 정렬할수도 있다. function numberCompare(num1,num2){ return num1 - num2; } [ 6, 4, 16,10 ].sort(numberCompare); 개념 현재 항목과 다음 항목을 한 번씩 비교하여 교환. 제일 끝에서부터 차례..
0. 검색 (Search) IndexOf 메서드 같은 배열 인덱싱, 문자열 파싱과 관련된 파트 내장함수의 처리 과정을 이해하고, 직접 구현하여 활용할 수 있게 하기 위함 1. 선형 검색 (Linear Search) 모든 개별 항목을 한 번씩 확인하는 방법 첫부분부터 끝부분으로 이동하며 탐색할수도, 역순으로 탐색할수도 있음 indexOf, includes, find, findIndex 메서드를 통해 선형 검색을 구현 기본적인 선형 검색 구현 function linearSearch(arr,value){ for (var i=0; i
What, exactly, is the DOM?과 해당 원문의 번역본을 학습한 후 정리한 글입니다. 웹 페이지가 만들어지는 방법 원본 HTML 문서를 읽어들인 후, 스타일을 입혀 뷰 포트에 표시하는 과정을 Critical Rendering Path라고 한다. 이 과정은 크게 두 단계로 나뉘어 진다. 첫 번째로 읽어들인 문자를 파싱하여 어떤 내용을 렌더링할지 결정하며, 두 번째로 브라우저에서 렌더링을 수행한다. 첫 번째 단계를 통해 렌더 트리가 생성되는데, 이는 HTML 요소(DOM)와 관련 스타일 요소(CSSOM)로 구성된다. DOM이란 DOM(Document Object Model)은 웹 페이지에 대한 인터페이스로, HTML 문서의 구조와 내용을 다양한 프로그램에서 사용할 수 있게 한 객체 기반 표현이..
이번 주 - (알고리즘) 재귀 알고리즘 + 응용문제 - (리액트) 라우터와 라이프사이클, Ajax 통신 다음 주 - 딥러닝, OS 중간고사 - (알고리즘) 검색과 정렬 알고리즘 + 응용문제 - (리액트) Redux와 성능개선, CAReact 마무리
1. 데드락 (Deadlock) 프로세스나 쓰레드가 사용하고자 하는 컴퓨터 자원을 다른 프로세스가 갖고 종료 조건이 서로 맞물려 있는 상태로 무한정 대기하는 상황을 데드락(Deadlock)이라고 한다. 프로그램 설계 시 데드락이 발생하지 않도록 유의하여야 한다. 각자 설계한 프로그램이 단독적으로 실행될 때는 문제가 없을 수 있지만, 여러 개의 프로그램이 함께 실행되는 과정에서 발생할 수도 있기 때문에 문제점을 발견하거나 예방하기 쉽지 않다. 컴퓨터 자원의 분류 재사용 가능한 자원(Reusable Resources)과 소비성 자원 (Comsumable Resources)으로 나뉘어진다. CPU나 입출력 장치, 메모리 등 대부분의 하드웨어 자원은 사용 후 소멸되지 않으므로 재사용 가능한 자원에 속한다. 이러..
0. 재귀 자기자신을 호출하는 절차 (함수) JSON()의 파싱이나, DOM getElementById 등의 내부 코드가 재귀로 구성되어 있음 물론 반복문만으로도 구현이 가능하지만, 재귀를 사용함으로써 직관적이고 간결하게 구현할 수 있음 1. 필수 요소 중단점 (Base Case) 재귀가 중단되는 시점, 즉 종료 조건과 마지막으로 반환할 Return을 지정해주어야 한다. 다른 입력값 (Different Input) 매번 같은 함수를 호출하면서 다른 출력을 반환할 수 있게 하기 위해선 입력값 또한 달라져야 한다. 2. 예시 예시 반복문을 이용한 팩토리얼 구현 function loopFactorial(num){ let total = 1; for(let i = num;i>0;i--){ total *= i } ..
