This Week. 24 ~ 29 한 주간 정리

오늘부터 시작하는 일주일을 되돌아보는 시간.  먼저 이번 주에 공부한 내용들을 체크해 보자.

• FenickTree, Segment Tree
• 타입스크립트 제너릭, 코드 중복
• 슬라이딩 윈도우, 투 포인터
• quick sort, merge sort
• 타입스크립트 설정 및 코드 생성

간단하게 펜윅트리랑 merge sort 복습하는 겸

백준 문제에서 1517 버블 소트라는 문제를 풀면서 정리를 해야겠다. 이문제가 마침 두 가지로 풀 수 있다. 먼저 펜윅트리부터 보자. 트리 크기는 세그먼트랑 다르게 입력값만큼 만들어 주면 된다.

#include<bits/stdc++.h>
 
#define fastio ios::sync_with_stdio(0), cin.tie(0), cout.tie(0)
#define endl "\n"
#define pii pair<int,int>
#define ll long long

using namespace std;

const int MAX = 500001;
int tree[MAX];
int arr[MAX];
int n;
vector<pii> edge;


void update(int idx, int val){
	while(idx<=n){
		tree[idx] +=val;
		idx+=(idx & -idx);
	}
}


ll query(int idx){
	ll ret = 0;
	while(idx){
		ret+=tree[idx];
		idx -= (idx & -idx);
	}
	return ret;
}


int main(){
	
	
	cin>>n;
	
	ll ans=0;
	for(int i=0; i<n; i++){
		int v;cin>>v;
		edge.push_back({v,i+1});
	}
	
	
	sort(edge.begin(), edge.end());
	
	for(int i=edge.size()-1; i>=0; i--){
		ans+=query(edge[i].second);
		update(edge[i].second, 1);
	}
	
	
	cout<<ans<<endl;
	
	
	return 0;
}

저번에 정리하면서 말한 인버전 카운팅 문제로 보면 된다. 값과 인덱스 값을 같이 받아서 값을 기준으로 정렬을 한 다음 뒤부터 돌면서 값이 큰 놈부터 체크하고 업데이트해주면 다음 작은 값들은 그 값이 표시되어 있을 테니까 그 값들만큼 순서가 바뀌면 된다. 1615번 문제도 똑같은 문제다. 다음에 이걸로 다시 또 풀어보고 다른 유형 체크하면서 개념 익혀야겠다. 

다음은 merge sort로 같은 문제를 푼 코드이다.

#include<bits/stdc++.h>
 
#define fastio ios::sync_with_stdio(0), cin.tie(0), cout.tie(0)
#define endl "\n"
#define pii pair<int,int>
#define ll long long

using namespace std;

int N, arr[500005], sorted[500005];
ll cnt;
void merge(int left, int mid, int right) {
	int s1 = left, s2 = mid + 1, k = left;
	while (s1 <= mid && s2 <= right) {
		if (arr[s1] <= arr[s2]) {
			sorted[k++] = arr[s1++];
		}
		else {
			cnt += (mid - s1 + 1);
			sorted[k++] = arr[s2++];
		}
	}
	if (s1 <= mid) {
		for (int i = s1; i <= mid; i++) sorted[k++] = arr[i];
	}
	else {
		for (int i = s2; i <= right; i++) sorted[k++] = arr[i];
	}
	for (int i = left; i <= right; i++) arr[i] = sorted[i];
}
void mergeSort(int left, int right) {
	if (left < right) {
		int mid = (left + right) / 2;
		mergeSort(left, mid);
		mergeSort(mid + 1, right);
		merge(left, mid, right);
	}
}
int main() {
	cin >> N;
	for (int i = 1; i <= N; i++) cin >> arr[i];
	mergeSort(1, N);
	cout << cnt;
}

그냥 merge sort를 구현하는데,  여기서 만약 값이 더 크다면 그 길이만큼을 더해준다. swap하는 횟수를 체크하기 때문에 그점을 생각하면 비교적 떠올릴 수 있을 거 같다.

다음으로 타입스크립트를 정리해 보자

먼저 이번주에 나는 제너릭 부분이랑 코드 생성 및 설정 부분을 보았는데, 제네릭이 생각이 잘 안나는 관계로 내가 쓴글 위주로 디시보고 책에서 미처 확인하지 못한 부분을 정리하겠다. 

저번에 Pick이야기를 하면서 태그된 유니온에서도 다른 형태의 중복이 발생할 수 있는경우를 다루지 않았다 다음과 같다.

interface SaveAction{
	type: 'save';
    //...
}

interface LoadAction{
	type: 'load';
    // ...
 }
 
 type Action = SaveAction | LoadAction; 
 type ActionType = 'save' | 'load';

Action유니온을 인덱싱하면 타입 반복 없이 ActionType을 정의할 수 있다.

type ActionType = Action['type'] // 타입은 "save" || "load"

Action 유니온에 타입을 더 추가하면 ActionType은 자동적으로 그 타입을 포함한다. ActionType은 Pick을 사용하여 얻게 되는, type 속성을 가지는 인터페이스와는 다르다.

type ActionRec = Pick<Action, 'type'>; //{type: "save" | "load"}

아 그리고 코드 생성 부분을 정리하다가 런타임 성능 관련해서 적어두면 좋을 거 같아서 정리하겠다.

타입과 타입 연산자는 자바스크립트 변환 시점에 제거되기 때문에, 런타임 성능에 아무런 영향을 주지 않는다. 타입스크립트의 정적 타입은 실제로 비용이 전혀 들지 않는다. 타입스크립트를 쓰는 대신 런타임 오버헤드를 감수하며 타입 체크를 해본다면, 타입스크립트 팀이 다음 사항들을 얼마나 테스트해 왔는지 몸소 느끼게 된다고 한다.

• '런타임' 오버헤드가 없는 대신, 타입스크립트 컴파일러는 '빌드 타임' 오버헤드가 있다고 한다. 타입스크립트 팀은 컴파일 성능을 중요하게 생각한다고 한다. 따라서 컴파일은 일반적으로 상당히 빠른 편이고, 오버헤드가 커지면, 빌드 도구에서 '트랜스파일만'을 설정하여 타입 체크를 건너뛸 수 있다.
• 타입스크립트가 컴파일하는 코드는 오래된 런타임 환경을 지원하기 위해 호환성을 높이고 성능 오버헤드를 감안할지, 호환성을 포기하고 성능 중심의 네이티브 구현체를 선택할지의 문제에 맞닥뜨릴 수도 있다고 한다. 예를 들어 제너레이터 함수가 ES5 타깃으로 컴파일되려면, 타입스크립트 컴파일러는 호환성을 위한 특정 헬퍼 코드를 추가할 것이다. 이런 경우가 제너레이터의 호환성을 위한 오버헤드 또는 성능을 위한 네이티브 구현체 선택의 문제이다. 어떤 경우든지 호환성과 성능 사이의 선택은 컴파일 타깃과 언어 레벨의 문제이며 타입과는 무관하다.

 

복습을 하려고 한 번씩 본 부분들을 따로 정리하지 않았는데, 뭔가 이렇게 했던 부분에 미처 지나간 부분을 다시 정리하면 좋긴 한데, 복습보다는 새로 공부해서 부담이 되지 않을까 생각이 든다. 물론 뭐 많은 내용은 아니고 겹치는 것도 많지만, 일단 좀 더 지켜봐야겠다.

 

 

참고 및 출처: <이펙티브 타입스크립트> (댄 밴더캄 지음, 장원호 옮김, 인사이트 ,2021) , https://salepark.tistory.com/11