본문 바로가기

TIL

 (53)
Algo. quick sort , merge sort 간단 정리 오늘 어쩌다 보니 sort에 대해 생각할 시간을 가지게 되었다. 갑작스럽게 생각을 하려니 또 잊어버린 부분이 많아서 다시 되새기는 김에 정리하려 한다. 먼저 merge sort부터 정리해 보겠다. 병합 정렬은 기본적으로 분할 정복 방식으로 정렬을 진행 한다. 코드의 진행을 먼저 간단히 말하면 재귀적으로 계속 반씩 쪼개나 가면서 길이가 1개일 때까지 내려간다. 그 뒤 다시 올라오면서 값들을 병합하는 단계를 거친다. 여기서 시간 복잡도를 결정하는 부분은 병합하는 부분인데 병합 단계에서 최대 n번만큼 비교할 수 있다. 또한 순환 호출할 때 깊이가 반씩 나누기 때문에 logn이다. 따라서 최종적으로 nlogn이 된다고 한다. 자세한 부분은 밑에 블로그를 참고 하자. 여기서 또 내가 생각해야 될 부분은 이 병합 ..
PS. 슬라이딩 윈도우 그리고 투포인터 오늘은 투 포인터 관련 문제를 풀다가, 이전부터 정리하고 싶었던 두 가지 기법을 정리하려고 한다. 간단히 개념만 정리하고 끝내겠다. 먼저 슬라이딩 윈도우란 고정 사이즈의 윈도우가 이동하면서 윈도우 내에 있는 데이터를 이용해 문제를 풀이하는 알고리즘이다. 네트워크에서 사용되던 알고리즘을 문제 풀이에 응용한 경우라고 한다. 투 포인터랑 다른 점은 고정 사이즈의 윈도우를 사용해서 순회를 하는 방식이다. 그리고 투포인터는 보통 정렬 배열을 대상으로 하는데 슬라이딩 윈도우는 정렬 여부에 관계없이 활용된다는 차이가 있다. 그리고 투포인터는 꼭 뭐 앞에서 순차적으로 찾을 필요 없이 양쪽에서 다가와도 되고 문제마다 다르다. 물론 슬라이딩 윈도우도 다르긴 하다. 근데 일단 슬라이딩 윈도우는 사이즈를 고정한 점이 가장 큰..
TS. Generics 그리고 코드 중복에 관해 오늘은 간단하게 제네릭을 정리하려고 한다. 제너릭을 사용하는 이유는 코드의 중복을 없애는 게 가장 큰 목적이 아닐까 한다. 기본적으로 같은 기능을 하는 함수들이 다른 타입의 인자를 받게 될때, 제너릭을 사용해서 같은 함수로 처리할 수 있게 해 준다. 간단한 예제를 보자. 같은 기능을 하는 함수를 불필요하게 여러 개 만들 필요가 없다. function getNumber(value: number) { return value; } function getArray(value: string[]) { return value; } // 제네릭 기본 문법 - 함수 function getValue(value: T): T { return value; } getValue('hi').toLocaleUpperCase(); ge..
PS. FenwickTree 그전에 SegmentTree 오랜만에 세그먼트 트리 문제를 풀게 되었는데, 예전에 한창 풀다가 오랜만에 풀라고 하니까 기억이 안 나서 다시 정리를 하려고 한다. 보통 세그먼트 트리 문제들은 펜윅트리. 그래서 나도 펜윅트리를 알고 나서는 세그 트리 문제들 펜윅트리로 많이 풀었다. 근데 또 특정 값을 구하거나 그런 문제들에는 안되서 좀 변형하면 되긴한다. 근데 펜윅트리 같진 않다. 아무튼 펜윅트리를 알기 전에 당연히 세그 트리를 알면 좋고 세그 트리는 응용해서 다 풀 수 있다. 그래서 간단하게 세그먼트 트리 특징 정리하고 코드 보고 펜윅트리 비교하고 끝내겠다. 먼저 예제로는 백준 2042번 구간 합 구하기라는 문제를 풀 거다. 간단하게 정리하겠지만 전체 개념은 밑에 블로그를 참고하면 될 거 같다. 정말 디테일하게 정리해주셨다. http..
TS. Type alias과 interface차이 오늘 간단하게 타입스크립트 개념을 공부하다가 비슷한 둘을 만나서 이펙티브 자바스크립트에서 찾아보니 관련 글이 있어서 정리하려 한다. 그전에 간단하게 오늘 공부한 타입스크립트 타입들에 대해 정리하고 가야겠다. 그중 기억에 남는 건 인덱싱이랑 딕셔너리 패턴인데 다음과 같다. //인덱싱 interface StringArray{ [index:number]:string; } var arr: StringArray = ['a','b','c']; arr[0]="new" interface originArray{ [index:number]:number } var arr2:originArray=[] //딕셔너리 패턴 interface StringRegesDictionary{ [key:string] : RegExp } var..
TS. 타입스크립트 시작전에 그 유명한 이펙티브 시리즈의 타입스크립트를 보려고 한다. 예전에 자바 공부를 할 때 자바 하면 이펙티브 자바라고 들었어서 이 책도 같은 이펙티브 시리즈여서 신나서 산거 같다. 아무튼 새 친구를 만났으니 시간 좀 보내야겠다. 사실 이 책이 완전 개념 책은 아닌 걸로 알아서 개념적인 부분은 따로 좀 보면서 재밌었던 파트 있으면 정리하는 식으로 해야겠다. 일단 타입스크립트는 이름처럼 타입을 사용하는 자바스크립트다. 찾아보면 자바스크립트의 슈퍼셋 언어라고 나오는데 왜 써야 하는지 알아보자. 몇 가지가 있는데 간단히 얘기하면 에러를 방지하고 생산성을 향상시킨 다고 한다. 에러를 방지하는 건 자바스크립트의 경우 일단 결과를 콘솔에 찍어봐야 에러를 발견하는 경우가 많아서 타입 스크립트를 쓰면 작성 과정에서 바로 찾을..
DOM. 관련 개념 정리 DOM 관련 강의를 듣고 있는데 어제 쓴 글이랑 관련 있는 게 나와서 생각나는 부분만 정리해 보려고 한다. 강의는 인프런에 'DOM 기본' 이란 강의다. 오늘은 설명할 부분은 ECMAscript Overview부분을 설명한다. 밑에 참고하면 된다. https://tc39.es/ecma262/#sec-ecmascript-overview ECMAScript® 2022 Language Specification The first and subsequent editions of ECMAScript have provided, for certain operators, implicit numeric conversions that could lose precision or truncate. These legacy imp..
JS. this this에 대해 공부하다가 헷갈리는 부분들이 있어서 간단하게 정리하려고 한다. 자바스크립트 this는 다른 객체지향 언어들의 this와 좀 다르게 this에 바인딩되는 객체가 한 가지가 아니라 해당 함수 호출 방식에 따라 this에 바인딩되는 객체가 달라진다. 이게 왜 이런 식으로 설계되었는지는 저번에 프로토타입 글에서 공유한 '자바스크립트는 왜 프로토타입을 선택했을까? '글을 보면 자바스크립트의 철학을 통해 조금은 알 수 있다. 자바스크립트의 경우 함수 호출 방식에 의해 this에 바인딩할 어떤 객체가 동적으로 결정된다. 함수를 선언할 때 this에 바인딩할 객체가 정적으로 결정되는 것이 아니라 함수를 호출할 때 함수가 어떻게 호출되었는지에 따라 this에 바인딩할 객체가 동적으로 결정된다. 여기서 저..

티스토리툴바