728x90
반응형

TypeScript는 JavaScript의 기능들을 제공하면서 그 위에 자체 레이어를 추가한다.

JavScript는 string, number, object, undefined 같은 타입을 가지고 있지만, 할당되었는지 미리 확인해 주지 않는다.

타입 정의하기(Defining Types)

객체의 형태를 명시적으로 나타내기 위해서는 interface로 선언한다.

const user = {
  name: "Hayes",
  id: 0,
};
interface User {
  name: string;
  id: number;
}

const user:User = {
	name: "Hayes",
	id: 0,
}

해당 interface에 맞지 않는 객체를 생성하면 TypeScript는 경고를 준다.

TypeScript는 JavaScript와 마찬가지로 객체 지향 프로그래밍을 지원한다.

interface User{
	name:string;
	id:number;
}

class UserAccount {
	name:string;
	id:number;

	constructor(name:string,id:number){
		this.name=name;
		this.id=id;
	}
}

const user:User = new UserAccount("Murphy",1);

인터페이스는 함수에서 매개변수와 리턴 값을 명시하는데 사용되기도 한다.

interface User {
  name: string;
  id: number;
}

function getAdminUser(): User {
  //...
}

function deleteUser(user: User) {
  // ...
}

JavaScript에서 사용했던 boolean, bigint, null, number, string, symbol, object, undefined는 당연히 사용할 수 있고, 여기에 더하여

any (무엇이든 허용)

unknown (타입이 무엇인지 확인)

never (이 타입은 발생될 수 없다)

void (undefined를 리턴하거나 리턴 값이 없음)

interface를 우선적으로 사용하고, 특정 기능이 필요할 때 type을 사용해야 한다.

타입 구성 (Composing Types)

여러가지 타입을 이용하여 새 타입을 작성하기 위해 Union과 Generic을 사용한다.

유니언(Unions)

타입이 여러 타입 중 하나일 수 있음을 선언하는 방법이다.

예를 들어 boolean 타입을 true 또는 false로 설명할 수 있다.

type MyBool = true | false;

유니언 타입이 가장 많이 사용된 사례 중 하나는 값이 string 또는 number의 리터럴 집합을 설명하는 것이다

type WindowStates = "open" | "closed" | "minimized";
type LockStates = "locked" | "unlocked";
type OddNumbersUnderTen = 1 | 3 | 5 | 7 | 9;
function getLength(obj: string | string[]) {
  return obj.length;
}
// 이건 array 또는 string을 받는 함수라는 뜻이다.

제네릭(Generics)

제네릭은 이전 글에서 공부했었는데, 타입에 변수를 제공하는 방법이다.

제네릭이 없는 배열은 어떤 것이든 포함할 수 있다.

제네릭이 있는 배열은 배열 안의 값을 설명할 수 있다.

type StringArray = Array<string>;
type NumberArray = Array<number>;
type ObjectWithNameArray = Array<{ name: string }>;

구조적 타입 시스템 (Structural Type System)

타입 검사가 값이 있는 형태에 집중한다.

구조적 타입 시스템에서 두 객체가 같은 형태를 가지면 같은 것으로 간주된다.

interface Point {
  x: number;
  y: number;
}

function printPoint(p: Point) {
  console.log(`${p.x}, ${p.y}`);
}

// "12, 26"를 출력합니다
const point = { x: 12, y: 26 };
printPoint(point);

여기서 point 변수는 Point 타입으로 선언된 적이 없지만, TypeScript는 타입 검사에서 point의 형태와 Point의 형태를 비교하여 같은 형태이기 때문에, 통과한다.

TypeScript 설치

2가지 방법으로 설치할 수 있다.

  1. npm을 이용 (Node.js 패키지 매니저)
  2. TypeScript의 Visual Studio 플러그인 설치
npm install -g typescript

코드 컴파일

tsc temp.ts
728x90
반응형

'프론트엔드 > TypeScript' 카테고리의 다른 글

Generic  (0) 2022.07.12
728x90
반응형

알고리즘 문제를 풀다가 출력 부분을 해결할 때, 문자열을 join 함수로 사용하는 방법을 많이 보아서 알아볼려고 하였다.

join 함수

형태 : 구분자.join(리스트)

join 함수는 매개변수로 들어온 리스트에 있는 요소 하나하나를 합쳐서 하나의 문자열로 바꾸어 반환하는 함수이다.

  • ''.join(리스트) ''.join(리스트)를 이용하면 매개변수로 들어온 ['a', 'b', 'c'] 이런 식의 리스트를 'abc'의 문자열로 합쳐서 반환해주는 함수인 것이다.
  • '구분자'.join(리스트) '구분자'.join(리스트)를 이용하면 리스트의 값과 값 사이에 '구분자'에 들어온 구분자를 넣어서 하나의 문자열로 합쳐줍니다.

ex>

a = ['a', 'b', 'c', 'd', '1', '2', '3']
print(a)
print("".join(a))
# 'a', 'b', 'c', 'd', '1', '2', '3'
# abcd123

그래서 임의의 구분자를 리스트 요소 사이사이에 넣어줄 수도 있다.

# 원본 리스트
a = ['BlockDMask', 'python', 'join', 'example']
print(a)
print()
 
# 리스트를 문자열로 합치기
result1 = "_".join(a)
print(result1)
 
# 리스트를 문자열로 합치기
result2 = ".".join(a)
print(result2)

# ['BlockDMask', 'python', 'join', 'example']
# BlockDMask_python_join_example
# BlockDMask.python.join.example
728x90
반응형
728x90
반응형

제네릭은 어떠한 클래스 혹은 함수에서 사용할 타입을 그 함수나 클래스를 사용할 때 결정하는 프로그래밍 기법을 말한다.

Java나 C++등의 정적 타입 언어에서는 함수 및 클래스를 선언하는 시점에서 매개변수 혹은 리턴 타입을 정의해야하기 때문에 기본적으로 특정 타입을 위해 만들어진 클래스나 함수를 다른 타입을 위해 재사용할 수 없다.

 

그래서 제네릭을 통해 함수와 클래스의 범용적인 사용을 가능하게 한다.

JavaScript는 타입 에러를 런타임에서 일으킨다. 코드를 실행시키기 전까지는 함수와 클래스가 모든 타입에 대응하기 때문에 JavaScript에서는 필요가 없다.

 

제네릭은 꺽쇠를 넣고 그 안에 타입으로 사용되는 식별자를 집어넣는다. 클래스에서 제네릭을 사용하겠다고 선언한 경우 T는 해당 클래스에서 사용할 수 있는 특정한 타입이 된다.

 

배열을 입력으로 받아 그 배열의 첫번째 요소를 출력하고 싶은 경우, 제네릭을 쓰는 것과 안 쓰는 경우를 비교해보자.

 

function first(arr:any[]):any {
	return arr[0];
}

위의 코드는 어떤 타입의 배열이라도 받을 수 있기 때문에 리턴하게 되는 타입이 무엇인지 알 수 없다.

 

function first<T>(arr: T[]):T {
	return arr[0];
}
first<number>([1,2,3]); // 1

사용할 때는 함수를 호출할 때 제네릭 문법으로 타입을 정해주기만 하면 된다.

 

다음과 같은 배열이 주어졌을 때, age가 가장 높은 요소를 반환하는 함수를 구현한다고 해보자.

const ages = [
	{ age: 10 },
	{ age: 12 },
	{ age: 19 },
	{ age: 22 },
]

typescript를 사용하지 않는다면 이런 식으로 작성한다.

  • code
  • function getOldest(ages) { return ages.sort((a, b) => b.age - a.age)[0]; /* const sortedAges = ages.sort((a, b) => b.age - a.age); return sortedAges[0]; */ }

하지만 typescript로는 이렇게 작성해야 한다.

  • code
  • type ageObj = { age: number } function getOldest(ages: ageObj[]): ageObj { return ages.sort((a, b) => b.age - a.age)[0]; }

자 하지만 만약 객체가 더 복잡한 형태면 어떻게 해야 할까?

예를 들어 ages가 아닌 persons 배열이 주어졌다고 해보자.

const persons = [
	{ name: "jinho", age: 22, gender: "male", address: "A"},
	{ name: "jinho2", age: 18, gender: "male", address: "B"},
	{ name: "jinho3", age: 28, gender: "male", address: "C"},
]

const oldestPerson = getOldest(persons);

이렇게 되면 우리의 oldestPerson 변수는 { name: string, age: number, gender: string, address: string } 의 타입이 아닌 ageObj 타입을 가지게 된다. 따라서 아래의 동작은 오류를 발생시킨다.

console.log(oldestPerson.name) 
// type error: Property 'name' does not exist on type 'ageObj'.

여기서 우리는 getOldest 함수가 조금 더 타입에 자유롭도록 하기 위해 generic을 사용해야 한다.

function getOldest<T extends ageObj>(ages: T[]): T {
	return ages.sort((a, b) => b.age - a.age)[0];
}

const persons = [
	{ name: "jinho", age: 22, gender: "male", address: "A"},
	{ name: "jinho2", age: 18, gender: "male", address: "B"},
	{ name: "jinho3", age: 28, gender: "male", address: "C"},
]

interface IPerson {
	name: string;
	age: number;
	gender: string;
	address: string;
}

const oldestPerson = getOldest<IPerson>(persons);

 

 

import React from 'react'

const App = (): JSX.Element => {
	const [count, setCount] = React.useState(0);

	const addCount = () => setCount(count + 1);
	const minusCount = () => setCount(count - 1);

	return <div>{count}</div>
}

 

import React from 'react'

interface IPerson {
	name: string;
	age: number;
	gender: string;
	address: string;
}

const App = (): JSX.Element => {
	const [person, setPerson] = React.useState<IPerson>({
		name: "",
		age: 0,
		gender: "",
		address: "",
	});

	React.useEffect(() => {
		// data fetching -> setPerson(불러온 데이터)
	}, [])

	return <div>{person.name}</div>
}
728x90
반응형

'프론트엔드 > TypeScript' 카테고리의 다른 글

TypeScript 설치와 사용  (0) 2022.07.13
728x90
반응형

오늘 WIT 동아리에서 프로젝트 발표를 진행할 때, 프로젝트 기간이 남을 경우 AWS S3로 배포한다는 이야기가 나와서, 매번 배포할 때 사용한다는 것만 알고 자세히 어떤 건지 알기 위해서 찾아보았다.

Amazon S3란?

Amazon Simple Storage Service의 약자로 파일 서버의 역할을 하는 서비스라고 생각하면 된다.

(어떠한 정보(파일)를 저장하는 서비스)

정보를 서버를 구축해서 저장할 수도 있겠지만 S3를 쓰면 많은 것을 신경쓰지 않고 할 수 있다. 

일반적인 파일 서버는 트래픽이 증가함에 따라서 장비를 증설하는 작업을 해야 하는데, S3는 이걸 대신해 준다.

또한 파일에 대한 접근 권한을 지정할 수 있어서 서비스를 호스팅 용도로 사용하는 것을 방지할 수 있다.

호스팅 : 서버 컴퓨터의 전체 또는 일정 공간을 이용할 수 있도록 임대해 주는 서비스. 사용자가 직접 서버를 구입하고 운영할 필요 없이 호스팅 업체가 미리 준비해 놓은 서버를 빌려 사용하는 형식이다. 웹 호스팅, 서버 호스팅, 메일 호스팅 등 다양하다.

는 특정 비즈니스, 조직 및 규정 준수 요구 사항에 맞게 데이터에 대한 엑세스를 최적화, 구조화 및 구성할 수 있는 관리 기능을 제공하는 것으로 온라인 스토리지 서비스이다.

사용하는 이유

  • 일단 이것을 사용하는 이유는 저장 용량이 무한대이고 파일 저장에 최적화되어있고, 용량을 추가하거나 성능을 높이는 작업이 필요없다.
  • Auto Scaling이나 Load Balancing에 신경쓰지 않아도 된다.
  • 정적 웹페이지는 S3를 이용하면 성능도 높이고 비용도 절감된다. 동적 웹페이지는 EC2라는 것을 사용하면 성능도 높이고 비용도 절감한다.
  • S3 자체로 정적 웹서비스가 가능하다.
  • 예를 들어 웹사이트를 만들 때 사용자들이 파일을 전송하면 그 파일을 S3에 저장하고 S3에서 다운받아서 다른 사용자에게 제공한다.

사용되는 용어들

  • 객체 : 데이터 하나하나를 의미한다.
  • 버킷 : 객체가 파일이라면 연관된 객체들을 그룹핑한 최상위 디렉토리를 버킷이라고 한다. 버킷에 포함된 모든 객체에 대해서 일괄적으로 인증과 접속 제한을 걸 수 있다.
  • 객체 스토리지 : S3의 가장 큰 특성으로 높은 내구성과 가용성을 제공한다. 하나의 단위 객체가 업로드되면 자동으로 내부의 여러 위치에 복제본을 생성한다. S3객체 스토리지도 동일 Region내에 여러 AZ에 걸쳐 복제본을 생성한다. (한 객체에 손상이 발생해도 손상되지 않은 복제본이 있어서 내구성 상승)
  • 버전관리 : 객체들의 변화를 저장한다. (Git 생각하면 된다.)
  • RRS : Reduced Redundancy Storage. 일반 S3객체에 비해서 데이터가 손실될 확률이 높은 형태의 저장 방식이다.
  • Glacier : 매우 저렴한 가격으로 데이터를 저장할 수 있는 아마존의 스토리지 서비스
  • 장기적으로 데이터 보관을 위한 용도면 Glacier가 적합하고, 장기 스토리지나 백업 및 복구 파일용은 Standard-IA가 적합하다.

특성

  • 객체 생성 및 삭제만 지원한다.
  • 사용자가 인터넷을 통해 단위 객체에 접근하므로 주소값은 고유하다.
  • HTTP 프로토콜을 사용하여 업로드/다운로드를 수행할 수 있다.
728x90
반응형
728x90
반응형

https://www.acmicpc.net/problem/2193

 

2193번: 이친수

0과 1로만 이루어진 수를 이진수라 한다. 이러한 이진수 중 특별한 성질을 갖는 것들이 있는데, 이들을 이친수(pinary number)라 한다. 이친수는 다음의 성질을 만족한다. 이친수는 0으로 시작하지 않

www.acmicpc.net

[풀이]

먼저 조건을 생각해보면 처음 숫자는 무조건 1이 나와야 하고, 1은 연속해서 나올 수가 없고, 0에는 아무런 제약이 없다. 끝에 숫자가 1이면 그 다음은 무조건 0이라는 사실과 끝에 숫자가 0이면 0 또는 1 두가지가 나올 수 있다.

(처음에는 헷갈려서 그림을 그리면서 해보았다..)

끝에 숫자가 0인것과 1인것을 구분해서 구해보면

각각의 숫자는 피보나치 수열을 따른 다는 것을 알 수 있다(0,1,1,2,3,5,…)

따라서 Dynamic Programming으로 각각 구해서 해결할 수 있었다.

 

n은 1부터 가능하므로 배열을 만들때 주의해서 index 오류를 범하지 않도록 해야 한다.

 

[해결]

n=int(input())
zero=[0]*n
one=[0]*n
if n>1:
    zero[1]=1
    one[0]=1
    for i in range(2,n):
        one[i] = one[i-1]+one[i-2]
        zero[i] = zero[i-1]+zero[i-2]
    print(one[n-1]+zero[n-1])
elif n==1:
    print(1)

 

728x90
반응형
728x90
반응형

https://www.acmicpc.net/problem/13413

 

13413번: 오셀로 재배치

로봇을 좋아하는 세희는 로봇동아리에서 카메라와 센서, 라즈베리 파이, 집게발을 이용해 로봇을 완성하였다. 이 로봇을 통해서 오셀로 재배치라는 작업을 하려고 한다. 오셀로 말은 앞면이 검

www.acmicpc.net

[풀이]

이 문제는 두 개의 배열을 입력받아서 첫번째 것을 두번째 배열과 똑같이 만들려고 하는 것이다. 방법은 2가지인데, W,B가 있으면 두개를 바꾸던가 W->B(혹은 B->W) 이런식으로 바꿀 수 있다. W,B 2개를 바꾸면 한번에 2자리가 해결되는 것이므로 위치 바꿀 수 있으면 이 방법이 최소 횟수일 것이다.

n = int(input())
    first = input()
    second = input()

    for i in range(n):
        if first[i]!=second[i]:
            arr.append(first[i])

내가 어려웠던 곳은 일단 서로 배열이 다르면 arr 배열에 저장해두었는데, 이걸 어떻게 해야 뒤집고 바꾸는 갯수를 다 알 수 있을까였다. 다른 곳이 짝수이면 나누기 2를 해주어서 몫을 더해줄까.. 이런 생각도 해보았는데

결국은 W랑 B가 있으면 더 큰 수를 출력하면 된다. arr에 입력받은 것이 만약 WBB라면 W랑 B는 서로 위치 바꾸어서 한 번이고, B하나 남은건 W로 바꾸어 줄테니까 총 개수가 2이다.

 

이건 결국 W랑 B중에 더 큰 수의 개수를 정답으로 하면 된다.

t = int(input())
arr=[]
ans=0
answer=[]
for i in range(t):
    n = int(input())
    first = input()
    second = input()

    for i in range(n):
        if first[i]!=second[i]:
            arr.append(first[i])
    if arr.count('B')>=arr.count('W'):
        ans=arr.count('B')
    else:
        ans = arr.count('W')
    answer.append(ans)
    arr=[]
for a in answer:
    print(a)

 

728x90
반응형
728x90
반응형

주의깊게 봐야할 부분은 buffer를 활용하는 부분인데, 이 코드에서 buffer n개를 모두 사용하지 못한다. cell의 n-1개만 사용한다는 뜻인데, cell 하나는 채울 수가 없다. 이유는 index의 in과 out이 같은 것을 empty로 간주하기 때문에 마지막까지 사용하면 full인지 empty인지 구분할 수가 없게 된다.

→ in +1== out 일 때 full이라고 생각하기 때문에

( 컴파일할 때, n을 작게 하면 한 cell이 채워지지 않는다는 것을 알 수 있다. )

 

n개의 cell을 다 채울려면 어떻게 해야할까? in이나 out으로 full이나 empty를 판단하는 것이 아니라, 버퍼 안의 데이터의 개수를 셈으로써 full이냐 empty이냐를 알도록 하면 된다. 그렇게 하기 위해서는 변수가 필요하다. (아래에서는 공유변수 counter를 사용한다.)

 

개수를 다루는 변수로 counter를 사용하는데, counter는 전역변수이면서 공유변수 이여야 하는데 쓰레드의 counter 공유 변수 동시 접근 시 문제가 생긴다.

그 문제가 바로 Race Condition이다. 

 

Race Condition

우리가 생각할 때, counter=counter+1이라는 코드가 실행되면 한 번에 딱 실행될거원라고 생각하지만 실제로는 아니다.

이 코드가 기계어로 실행될 때는, 3가지 과정을 거치는데 register에 저장하고 register에서 값을 증가하고 counter에 다시 register에 넣는 단계를 거친다. 

counter=counter-1의 경우도 마찬가지이다. 따라서, 공유변수 counter를 두고, 2개의 thread에서 counter값에 접근하면, counter값이 이상하게 변할 수 있다. 위에서 보면 실행 상은 counter가 5여야 하는데, 실제로 기계어로 실행되면 4또는 6이 될 수도 있는 것이다.

이 문제가 Race condtition이다.Race 즉, 서로 다른 쓰레드가 같은 자원을 두고 경쟁하는 상태를 의미한다. 

 

그렇다면 이런 Race condition은 어떠한 방법으로 해결할까? 지금 문제가 되는 것이 기계어가 3줄이니까 3줄이 한번에 돌지 않고 문맥 교환이 일어나서 상대 쓰레드가 들어와서 공유변수의 값을 수정해서 벌어지는 일들이다. 그럼 문맥교환이 일어나더라도 간섭이 없도록 코드가 실행되게 만들면 어떨까?

이 방법이 바로 Atomic한 실행이라고 한다. 예를 들어 counter부분을 임계구역으로 만들어놓으면 생산자에서 코드 2줄까지 실행하고 문맥교환이 일어나서 소비자에서 진입하려고 할 때, 진입하지 못하도록 하고 대기하도록 한다. 

 

원소적(Atomic) 실행

: 공유변수를 통해 상호작용하는 프로세스 혹은 쓰레드 간에 문맥교환이 언제 일어나도 간섭이 없는 실행이 보장되는 것.

-> 공유변수를 사용하는 코드 영역에 임계 구역을 설정한다. 아까 코드에서는 register와 counter를 사용하여서 counter의 값을 증가시키거나 감소시키는 부분을 임계 구역으로 설정하는 것이다. 

한 쓰레드가 먼저 임계구역 내에 진입하여 실행 중 문맥 교환이 발생하여 상대 쓰레드에 선점되더라도 그 쓰레드가 임계 구역에 진입하는 것을 허락하지 않고, 대기하도록 한다. 즉, 다른 쓰레드가 실행되더라도 임계구역에는 못들어간다는 의미이다. 

 

임계구역(Critical Section) 설정

임계구역이란 Atomic 실행을 위하여 각 프로세스 혹은 쓰래드가 공유변수, 자료구조, 파일 등을 배타적으로 읽고 쓸 수 있도록 설정한 코드 세그먼트이다. 

 

임계구역 설정하는 것이 비간섭으로 돌게 하는 수단이 된다. (임계 구역의 정의 중요)

→ 공유 변수가 임계 구역처럼 느껴질 수 있겠지만 변수는 수행되는 부분이 아니다. 수행은 코드가 하기 때문에 임계구역은 코드에 만들어 놓는다. 배타적으로 돌도록 코드에 설정해준다. 

 

entry, exit을 설정해 놓음으로써 이 부분은 배타적으로 돌아야한다고 명시한다. enter, exit으로 임계구역을 만들어 놓아야 한다. 화장실을 예시로 든다면, 화장실에 들어갈 때 문을 잠그로, 나갈 때 여는 것과 유사하다. 

 

 임계구역을 하면 한쪽이 먼저 들어가게 되겠고, 그렇게 하면 경쟁하는 다른쪽들은 못 들어가고 있다가 먼저 들어간 쪽이 빠져나가면 그제서야 다른 쪽들 중에 하나가 들어가게 됨으로써 진입과 진출이 순서화된다. (Serialize)

 이런 것을 동기화라고 한다. 즉, 코드 상으로는 독립적이지만 실행 상황에서 선행제약을 만드는 것이다. 

 

임계 구역 설정은 mutex가 기본이다. lock을 mutex 변수로 선언한다. 

위의 코드에서 보면 pthread_mutex_lock으로 잠금을 걸고, 만약 버퍼 크기가 꽉찼으면 pthread_cond_wait으로 대기한다. 그리고 그게 아니라면 in으로 넣고 count값을 증가시켜준 뒤, pthread_cond_signal 함수를 호출한다. 이 함수는 대기 중인 쓰레드에게 signal을 보내 pthread_cond_wait으로 대기중인 쓰레드를 깨우게 되어 다른 쓰레드가 이후의 작업을 진행할 수 있도록 해준다. 

 

728x90
반응형

'CS > 운영체제' 카테고리의 다른 글

[5] 프로세스  (0) 2022.03.24
[4] 컴퓨터 구조와 OS 연계  (0) 2022.03.21
[3] 컴퓨터 구조와 OS 연계  (0) 2022.03.14
[2] 시분할 시스템, 실시간 시스템  (0) 2022.03.09
[1] 운영체제의 발전  (0) 2022.03.07
728x90
반응형

Search, Insert, Delete

- 자료구조의 가장 중요한 연산들

Array : 메모리의 연속된 공간

 

How to Store Items in an Array?

- Packed vs. Unpacked

: 배열이 항상 가득 찬 것은 아님

: 빈 자리를 한 쪽으로 모은다

- Sorted vs. Unsorted

: Item들이 정렬된 상태를 유지하느냐 아니냐

 

Packed, UnSorted : 아마도 가장 간단한 방법

 Packed, UnSorted 성능

: Search : O(n) // 전부 다 보는 수밖에 없다 되게느리다.

: Insert : [Search, O(n)], O(1) // Worst Case를 따진다 -> Search해야되기 떄문에 느리다(작업자체는 빠름)

: Delete : [Search, O(n)], O(1) // Sorting이 안되어있으니까 뒤에서 들고오면 된다.

-> Insert와 Delete는 보통 Search를 먼저 수행함.

Pack, Sorted-> 제일 성능이 나오는 케이스

: Binary Search가 가능해진다.

packing이 되어서 저장이 되어 있는데 Sorting만 되어있으니까. Search가 달라진다. 

: Item의 개수를 표시하는 변수가 따로 필요

근데 Insert, Delete는 packing이 되어 있고, insert할려니까 binary search를 사용하니까 사이에 들어가야 한다. 

실패로 끝날때 index를 보면 사이에 들어가야한다는 것이 나온다. 

Search가 빠른 대신, Insert, Delete가 느리다. 모두를 좋게 하는 방법은 없다. Search가 자주 일어나는 경우 좋음.

 

Unpacked, UnSorted

이전에는 빈자리들이 몰려있기 때문에 몇 개다 라는것만 표현하면 어디까지 쓰고, 어디까지 안쓰는지 알 수 있었는데, 다 흩어져 있기 때문에 쓴다 표시 필요하다. 변수 여러개를 한 단위로 생각하자. 

Insert : 값을 넣는데 앞에서부터 쭉 찾으면서 안쓰는 칸 찾아서 저장하고 쓴다고 표시하면 된다. -> O(n)인거 같은데 기술을 추가하면 O(1)으로 줄일 수 있다. Unpacked, UnSorted 별로 좋은게 없다.

기술은 안쓴는칸은 빈자린데 의미없는 값을 Value에 넣어둔다. 3을 넣어주려고 한다. 3번 index라 하고 7번도 안쓴다.

3에서 index 3번 안쓰고 7번 안쓰고 거기서 또 가면 2번도 안쓰고 그 다음은 value -1이라서 끝난다. 이게 없으면 죽 훑으면서 빈자리를 찾아야 하는데 3번 안쓴다는걸 바로 알 수 있고, 7을 insert할 때 3을 지우고 7로 바꾼다.

거기 있던 7을 가지고 온다. 여전히 7번통해서 2번까지 갈 수 있다. 이 기술을 쓰면 빈자리를 바로 찾을 수 있다. 그 다음에 delete 20을 한다라고 하면 20을 지워야 하는데 어떻게 지우냐. 5번 자리가 날라가는거니까 5번을 Free List Head로 가져오고, 안쓴다고 바꾼다. 20대신 3을 가져다 놓는다

여전히 안쓰는 자리 전부 찾을 수 있고, 주어진 자리를 활용할 수 있다. 그래서 insert를 O(1)으로 할 수 있다. Search가 느린데 Insert, Delete는 빠르다. Byte수가 많으면 복사하는데 오래 걸린다. 

실제로 디스크의 파일 폴더 디렉토리에 들어가면 파일 지우는 거 packed로 packing해서 유지하려면 뒤에서 갖다 옮겨야 되는데 안 쓴다고 마킹만 한다. 마킹만 하기때문에 delete는 빠르다. (현재는 모름)

Free List를 쓰는 다른 하드디스크. 

 

Unpacked, Sorted

Sorting 해두는 부담을 갖는 것은, search가 빠르기 때문에 sorting하는 부담을 가지는데, binary search가 되나..?

쓰는 자리와 안쓰는 자리가 섞여있다. 중간을 찍었는데 안쓰는 자리이면..? -> 비교 불가.

기술 둘!

우선 처음에는 packed처럼 packing이 되어서 돌아간다. delete하기전에 처음에 insert할때는 중간에 빈자리를 두고 insert할 이유는 없다. Packed한것처럼 돌아간다. 첫 delete를 하기 전까지 중간에 빈자리가 안생긴다. delete를 하면 중간에 빈자리가 생기는데 중간에 있는 빈자리는 첫 delete를 할 때 생긴다. 그럼 이 자리는 delete된 자리라는 것을 알 수 있다. 변수가 하나더 필요하다. 사용한 제일 오른쪽 자리에 대한 자료가 필요하다. delete된 자리들은 거기 값을 그대로 나두는 것이다. 지워졌더라도 값은 그대로 살려둔다. 그러면 살아있는 값들과 죽어있는 값들을 다봤을때 sorting이 된걸로 유지를 할 수 있다. delete할때는 binary search로 하고 그냥 지워주면 아무것도 안바뀌니까 살아있는 값 죽어있는 값 다봐도 sorting이 되어 있다. 안쓴다고 marking만 하면 sorting 상태는 유지된다.

delete는 marking만 하면 되니까 O(1). Sorting된 order를 유지하기 위해서 예를 들어서 insert 16을 하려면 6,7사이에 들어가야한다고 나올텐데 약간 빠른 O(n)임. 예를 들어서 insert 4를 한다고 생각할 때, 빈자리까지만 밀면 된다. 

실제 내가 다루는 데이터가 어떤건지에 대해서 많은 영향을 받는다. 

728x90
반응형

+ Recent posts