code-l.log

client에서 ESM Scripts 활용하기

Wed, 30 Aug 2023 12:54:13 GMT

우선, html에 js파일을 넣을때 type="module" 로 해야한다.

client.js

function click(element) {
    alert("click");
};

이렇게 작성될 경우

Uncaught ReferenceError: click is not defined
    at DIVElement.onclick

이런 오류를 마주치게 된다.

이 문제는 ES6 모듈의 스코프와 HTML 인라인 onclick 속성이 서로 다르게 동작하기 때문에 발생한다.

HTML의 onclick은 전역 스코프에서 함수를 찾으려고 하지만, ES6 모듈은 자체 스코프를 가지고 있습니다.

그래서, onclick 속성은 click 함수를 찾을 수 없어서 Uncaught ReferenceError 오류가 발생합니다.

방법 : 전역 객체에 함수 추가

client.js 내에서 다음과 같이 작성하여 전역 객체에 함수를 추가하기.

window.click = function(element) {
    alert("click");
};

TypeScript에서의 해결

(window as any).click = function(element: Element) {
    alert("click");
}

하지만, 이렇게 해결함에도 여러개의 함수를 추가할때 타입스크립트 에러가 발생한다.

TS2339: Property 'click' does not exist on type 'void'.

이 문제를 해결하기 위해 먼저 window 객체에 대한 타입 확장을 할 수 있다.

```ts interface MyWindow extends Window { click1?: (element: Element) => void; click2?: (element: Element) => void; click3?: (element: Element) => void; }

declare var window: MyWindow;

window.click1 = function(element: Element) { alert("click1"); }

window.click2 = function(element: Element) { alert("click2"); }

window.click3 = function(element: Element) { alert("click3"); }

TCP / IP header format

Wed, 02 Aug 2023 19:37:43 GMT

TCP/IP

TCP/IP 3분 개념이해 (현업에 적용하는 CS 6탄)

이해하면 인생이 바뀌는 TCP 송/수신 원리

TCP는 데이터를 세그먼트(Segment)라는 블록 단위로 분할해 전송한다.

전송되는 블록의 크기는 네트워크 부하 정도, 윈도우 크기 등의 영향을 받으며, 가변크기를 지원한다. TCP는 세그먼트를 하나의 단위로 간주하여 순서 번호를 관리하지않는다. 대신 세그먼트에 실려 전송되는 데이터의 바이트 개수를 순서번호에 반영한다.

TCP헤더구조

TCP의 세그먼트는 헤더 구조로 시작하고, 전송 데이터가 뒤따른다. http://www.ktword.co.kr/test/view/view.php?m_temp1=1889

IP헤더 구조

null 병합 연산자 (??)

Sun, 30 Jul 2023 14:59:44 GMT

null 병합 연산자(Nullish coalescing operator)

null 병합 연산자는 논리연산자로 좌측 표현식이 null 또는 undefined 일때 우측 표현식을 반환하고, 그렇지 않으면 좌측 표현식을 반환하는 연산자이다.

문법

좌측표현식 ?? 우측표현식

예제

const nullValue = null;
const emptyText = ""; // falsy
const someNumber = 42;

const valA = nullValue ?? "default for A";
const valB = emptyText ?? "default for B";
const valC = someNumber ?? 0;

console.log(valA); // "default for A"
console.log(valB); // "" (as the empty string is not null or undefined)
console.log(valC); // 42

위 예제의 emptyText처럼 falsy한 값을 논리적으로 처리하기 좋다.

Optional chaining 연산자(?.)와의 관계

널 병합 연산자는 명확한 값으로 undefined과 null을 처리하고, optional chaining 연산자 (?.)는 null or undefined일 수 있는 객체의 속성에 접근할 때 유용하다.

예제

const foo = { someFooProp: "hi" };

console.log(foo.someFooProp?.toUpperCase() ?? "not available"); // "HI"
console.log(foo.someBarProp?.toUpperCase() ?? "not available"); // "not available"

정의될지 안될지 모르는 값을 처리해주기 유용하다

학습정리 06

Tue, 18 Jul 2023 17:34:17 GMT

영속 자료 구조

영속 자료 구조 — Pesistent Data Structures 는 불변 자료구조의 특성(데이터의 값이 변하지 않는다)을 유지하면서 추가시에 시공간 복잡도를 줄일 수 있는 방법이다.

함수형 프로그래밍

공부할것,

순수함수 외부 상태 참조 x, 입력과 출력 같게

불변성 유지 인자를 변경 x 새로운 버전의 새로운 오브젝트를 만들어서 반환

Object.freeze로 불변성으로 만들기

Expressions Only if. for x

First-class, higher-order finctions

모나드..?

pipe, go, curry

go, pipe, curry

함수형 프로그래밍 강의

일급

값으로 다룰 수 있다.
변수에 담을 수 있다.
함수의 인자로 사용될 수 있다.
함수의 결과로 사용될 수 있다.

일급 함수

함수를 값으로 다룰 수 있다.
코드를 값으로 다룰 수 있다.
조합성과 추상화의 도구

// 변수에 담을 수 있다.
const add = a => a+2

// 함수의 인자로 사용될 수 있다.
log(add2);

//함수의 결과로 사용될 수 있다.
const f = () => () => 1;

map

const map = (f: Function, iter) => {
    let res = [];
    for (const i of iter) {
        res.push(f(i));
    }
    return res;
};

reduce

const reduce = (f, acc, iter) => {
  if (liter) {
      iter = acc[Symbol.iterator]();
      acc = iter.next().value;
  }
  for (const a of iter) {
  acc = f(acc, a);
  }
  return acc;
}

go

const go = (...args) => reduce((a, f) => f(a), args);

go(
        0,
        a => a + 1,
        a => a + 10,
        a => a + 100,
        console.log    // 111
);

pipe

const pipe = (f, ...fs) => (...as) => go(f(...as), ...fs);

const f = pipe(
  (a, b) => a + b,
  a => a + 10,
  a => a + 100
);

console.log(f(0, 1));    // 111

curry

const curry = f => (a, ..._) => (_.length ? f(a, ..._) : (..._) => f(a, ..._));

const mult = curry((a, b) => a * b);
console.log(mult(3)(2));    // 6

const mult3 = mult(3);
console.log(mult3(3));    // 9
console.log(mult3(4));    // 12

조건문을 안쓴다

명령형 아니라 선언형 프로그래밍

명령형 동작을 일일이 기술
선언형 명령형으로 작성된걸 순수함수로 구현해서

따라서, 선언적으로 프로그램 분기를 가지기보다

if 대신 필터걸로

부작용 없이,

Monad

3분 Monad

완전요약

제네릭 T

특정 파라미터의 타입을 추상화한거다.

모나드란

제네릭이 타입을 추상화했다면

모나드는 연산을 추상화

합성이 가능한 연산

우리가 함수형에서 함수들을 체이닝

선언적으로 프로그래밍을 하기 위해서는 특정 함수의 호출로 함수안에 추상화해서

이 과정에서... 여러가지 연산이 필요

A -> B 과정에 서브 프로그램들로 하지만 결국은

여러개의 수많은 연산들로 이어져있다.

A -> B B -> C + A -> C

연산을 합칠 수 있다.

List

A class가 있는데 객체에 대해서 a.map(x => new Tuple(x.num)) 타입이 바뀐다 왜? 타입이 바꼈는데 모나드?

즉 맵이랑 플랫맵은

언제든 데이터를 다른타입로 바꿀 수 있다.

a.map(람다 다음 타입을 결정).map(람다).map(람다) ...

연산을 나타내는 타입 M

이게 모나드이려면 퓨어와 컴포즈가 존재해야한다.

int toString toCharArray

Compose(toString, toCahrArray): 새로운 연산

퓨어와 컴포즈를 가지고 있어야 모나드

모나드라는 인터페이스라면

퓨어와 컴포즈를 상속

연산을 합쳐서 하나의 연산을 만든다

프로그램은 하나의 큰 모나드이다

프로그램은 모나드들의 연결해놓은것이다.

함수는 state를 가지면 안된다.

TypeScript 개발 환경 설정하기(Debugging)

Tue, 18 Jul 2023 04:33:41 GMT

VSCode

빈 디렉터리 열기

npm init 하기

npm init -y

tsc init 하기 이때 반드시 sourceMap을 만들어줘야 js파일을 ts로 디버깅 할 수 있다.

tsc --init --sourceMap

타입스크립트 파일 만들고 중단점 걸기

타입스크립트 파일 sourceMap을 만들며 자바스크립트로 컴파일 하기

tsc *ts --sourceMap

또는 타입스크립트 파일 변경을 관측하면서 자동으로 자바스크립트로 컴파일하게 할 수 있다. 새로운 터미널을 열어서 아래 명령을 입력한다.

tsc --watch

보이는것처럼 관측하며 자동으로 컴파일한다.

생성된 자바스크립트 파일이랑, map 파일 확인하기

디버깅 탭 가서 launch.json 파일 만들기

이때, node로 만들면 된다.

생성된 launch.json 파일의 program이 생성된 자바스크립트 파일인지 확인한다.

디버깅하기(F5)

타입스크립트 중단점에 맞춰 디버깅이 되는것을 볼 수 있다!!

WebStrom

똑같이 터미널을 열어서 아래와 같은 설정들을 한다.

npm init -y
tsc --init --sourceMap

파일을 만들고 중단점을 만든다.

타입스크립트를 컨파일한다. 하나씩 컴파일해도되고, 자동으로 관측하면 컴파일하게 해도 된다. 아래 두가지 중 하나를 한다.

tsc *ts --sourceMap

tsc --watch

난 새로운 터미널을 만들어서 watch를 했다.

자바스크립트 파일이 생성됨을 확인한다.

디버깅 옵션을 만들자. 우측 상단에 Edit Configurations에 들어간다.

좌측 상당에 새로 만들기를 눌러서 node.js를 선택한다.

컴파일된 자바스크립트 파일을 선택한다.

저장하고 디버깅하기를 누르면 타입스크립트 중단점에서 잘 디버깅 되는 모습을 볼 수 있다.

콘솔 입출력은 Process Console탭을 활용하자.

멀티스레드에서 힙과 스레드 공간

Mon, 17 Jul 2023 17:56:03 GMT

통상적으로 알고 있는 스택과 힙 공간

이 그림은 단일 스레드 프로세스일때만 해당한다.

자바만 생각해도 아무 설정을 안해도 gc같은것들이 데몬 쓰레드로 동작한다.

논리적인 멀티스레드 프로그램의 메모리 영역이다.

직렬적인 메모리 구조에 저렇게 병렬적으로 생길 일 없다.

그나마 직렬적으로 표현된 여러 스레드에 각각 할당된 스택공간이다.

스택 공간은 컴파일시 결정된다? NO 상황에 따라 여러 스레드가 각각의 스택을 생성해 가변적으로 변한다.

하지만, 힙 공간은 컴파일시 결정된다? YES(?)

자바같은 경우는 jvm 위에서 동작하기 때문에(뇌피셜) 동적으로 런타임에 힙의 최대 공간을 늘려줄 수 있다.

// 현재 힙의 최대 크기 확인
long maxHeapSize = Runtime.getRuntime().maxMemory();
System.out.println("Max Heap Size: " + maxHeapSize);

// 힙 크기 동적으로 변경
long newMaxHeapSize = ...; // 새로운 최대 힙 크기 설정
try {
    // 새로운 최대 힙 크기로 변경
    Runtime.getRuntime().exec("java -Xmx" + newMaxHeapSize + " YourProgram");
} catch (IOException e) {
    // 변경 실패 시 처리
    e.printStackTrace();
}

하지만, C나 JavaScript 는 그러한 기능을 제공하지 않는다.

사진 출처 : 황기태 교수님 운영체제 강의안 일부

JavaScript랑 친해지기

Sat, 15 Jul 2023 16:16:34 GMT

1 자바 스크립트 공부하기

1) 모던 자바스크립트 Deep Dive

모던 자바스크립트 Deep Dive는 무려 956페이지에 달하는 자바스크립트 정석같은 책이다. 깊이있게 공부하고 싶다면 읽어 보는게 좋을 것 같다.

2) MDN

MDN Your blueprint for a better internet은 모질라 재단 및 다른 IT기업들이 사용하는 웹 개발을 위한 문서 저장소이자 수많은 프로그래밍 입문자들을 위한 학습 장소이다.

웹 개발에 필요한 html, css, javascript, http 등 전반적인 내용이 상세하게 문서화 되어있다.

일부 페이지는 한국어로도 번역되어있으니 대략적으로 읽어보고, 필요할때 기억안나면 찾아서 활용하기 좋다.

3) 드림코딩의 자바스크립트 강의

드림코딩의 자바스크립트 강의 20-30분씩 13개의 강의로 되어있다. 분야별로 예제와 그림을 통해 실습 코드로 보여주어 공부하기 좋다. 특히, 자바스크립트 9. 유용한 10가지 배열 함수들. Array APIs 총정리 강의는 꼭 들어보자. 자바스크립트가 지원하는 배열 매서드들을 더 쉽게 활용할 수 있게 될것이다.

4) Poiemaweb

poiemaweb는 한국형 MDN이 아닐까 싶다. 영어에 낯선 사람이라면 이 사이트를 적극 활용해보는것도 좋겠다.

2 TypeScript

typescript는 동적타입 언어인 javascript를 정적타입 언어처럼 사용할 수 있게해주는 오픈소스이다. 컴파일 할 경우 javascript 파일로 되어 100% 호환 가능하고, 여러 es버전에 맞게 컴파일 할 수 있다는게 강점이다.

프로그래밍 도구로서의 타입 또한, typeScript는 우리가 코드 상에서 실수를 저질렀을 때 버그를 잡아준다. 그런데 TypeScript는 여기서 더 나아가서 우리가 실수를 저지르는 바로 그 순간 이를 막아준다.

타입 검사기는 우리가 변수 또는 다른 프로퍼티 상의 올바른 프로퍼티에 접근하고 있는지 여부를 검사할 수 있도록 관련 정보들을 가지고 있다. 이 정보를 활용하면 타입 검사기는 우리가 사용할 수 있는 프로퍼티를 제안할 수 있게 된다.

즉, 자동완성이 가능하고 개발 생산성과 버그를 막아준다.

TypeScript for Java/C# Programmers 문서는 정적타입 객체지향 언어가 익숙한 프로그래머에게 좋은 선택이라 알려주며 타입 스크립트에 적을할 수 있게 차이점을 설명해주며 도와준다.

참고로 C#의 리드 아키텍트이자 델파이가 개발에 참여하였다.

3 TypeScript 디버깅

THIS is EASY TypeScript Setup in VSCode - Alex Ziskind의 영상을 보면 sourceMap파일을 생성해서 javascript파일을 typescript로 디버깅 할 수 있는 방법을 알려준다.

디버깅은 프로그램을 작성하는데 강력한 도구이다. 더이상 설명이 필요할까 싶다!

영상을 따라하면, typescript의 변화를 감지해서 실시간으로 javascript으로 디버깅하는 방법까지 나와있으니, typescript를 채택한다면 반드시 따라해보자!

TypeScript for Java Programmers

Sat, 15 Jul 2023 03:32:51 GMT

서론

TypeScript는 C#, Java와 같이 정적 타이핑을 사용하는 언어에 익숙한 프로그래머들에게 인기 있는 선택이다.

TypeScript의 타입 시스템은 정적 타이핑이 가지는 많은 이점을 제공합한다.

TypeScript는 이러한 개발자에게 친숙한 기능을 많이 제공하지만, JavaScript(또한 TypeScript도 마찬가지로)가 기존의 객체 지향 프로그래밍(OOP) 언어와 어떤 차이가 있는지 다시 살펴볼 필요가 있다.

이러한 차이점을 이해하는 것은 더 나은 JavaScript 코드를 작성하는데 도움을 줄 것이고, C#/Java에서 TypeScript로 바로 입문한 프로그래머가 겪는 흔한 함정을 피할 수 있을 것이다.

JavaScript 함께 배우기 (Co-learning JavaScript)

만약 JavaScript를 처음 접하는 Java 프로그래머라면, JavaScript의 런타임 동작을 이해하기 위해 우선적으로 타입을 제외한 JavaScript의 일부분을 배우는 것이 좋다.

TypeScript는 코드를 실행하는 방식을 바꾸지 않기 때문에, 실제로 무언가 동작하는 코드를 작성하기 위해서는 여전히 JavaScript가 어떻게 작동하는지 배워야 한다!

TypeScript가 JavaScript와 동일한 런타임을 사용하므로, 특정한 런타임 동작(문자열을 숫자로 변환하기, 경고 표시, 디스크에 파일 쓰기 등)을 구현하려는 리소스는 항상 TypeScript 프로그램에 똑같이 잘 적용된다는 점을 기억하는 것은 매우 중요하다. TypeScript에 특정된 리소스에만 제한을 두지 말자!

클래스 다시 생각하기 (Rethinking the Class)

Java는 의무적 OOP 언어라고 부른다. 이러한 언어에서 클래스는 코드 구성의 기본 단위일 뿐만 아니라 런타임 시 모든 데이터 그리고 동작의 기본적인 컨테이너이다. 기능과 데이터를 전부 클래스에 담도록 강제하는 것은 일부 문제에 대해선 좋은 도메인 모델이 될 수 있지만, 모든 도메인이 이러한 방식으로 표현될 필요는 없다.

자유로운 함수와 데이터 (Free Functions and Data)

JavaScript에서 함수는 어디에나 있을 수 있고, 데이터를 미리 정의된 ‘class’나 ‘struct’에 속하지 않고 자유롭게 전달할 수 있다. 이러한 유연성은 매우 강력하다. OOP 계층과 상관 없이 데이터를 처리하는 “자유로운” (클래스와 연관되지 않은) 함수는 프로그램을 JavaScript로 작성하는 모델로 선호된다.

정적 클래스 (Static Classes)

추가적으로, Java의 싱글턴과 정적 클래스 같은 특정 구조는 TypeScript에서 필요하지 않습니다.

TypeScript의 OOP (OOP in TypeScript)

즉, 원한다면 계속 클래스를 사용해도 된다! 일부 문제는 기존의 OOP 계층으로 해결하기 적합하며, TypeScript가 JavaScript의 클래스를 지원하므로 이러한 모델을 더 효과적으로 만든다. TypeScript는 인터페이스, 상속, 정적 메서드 구현과 같은 많은 일반적인 패턴을 지원한다.

이 가이드의 뒷부분에서 클래스를 다룰 것이다.

타입 다시 생각하기 (Rethinking Types)

TypeScript의 타입에 대한 이해는 사실 C#이나 Java와 상당히 다르다. 몇 가지 차이점을 살펴보자.

이름으로 구체화된 타입 시스템 (Nominal Reified Type Systems)

C#과 Java에서 주어진 값과 객체는 ‘null’, 원시 타입, 또는 정의된 클래스 타입 중 정확하게 하나의 타입을 가진다. 런타임 시점에서 정확한 타입을 묻기 위해 value.GetType() 또는 value.getClass()와 같은 메서드를 호출할 수 있다. 이러한 타입의 정의는 특정한 이름을 갖고 클래스의 어딘가 존재하며, 명시적인 상속관계나 공통적으로 구현된 인터페이스가 없는 이상 두 클래스가 유사한 형태를 가졌다 해도 서로 대체하여 사용할 수 없다.

이러한 양상은 reified, nominal 타입 시스템을 설명한다. 코드에서 사용한 타입은 런타임 시점에 존재하며, 타입은 구조가 아닌 선언을 통해 연관 지어진다.

집합으로서의 타입 (Types as Sets)

Java에서 런타임 타입과 해당 컴파일 타임 선언 사이의 일대일 대응관계는 중요합니다.

TypeScript에서 타입은 공통의 무언가를 공유하는 값의 집합으로 생각하는 것이 좋다. 타입은 집합에 불과하기 때문에, 특정한 값은 동시에 수많은 집합에 속할 수 있습니다.

일단 타입을 집합으로 생각하기 시작하면, 특정 연산이 매우 자연스러워진다. 예를 들어, Java에서는 ‘String’과 ‘int’ 둘 다 가능한 타입이 존재하지 않기 때문에 이 값을 인자로 전달하는 것은 이상합니다.

TypeScript에서 모든 타입이 단순히 집합이라는 것을 깨닫는 순간 이는 매우 자연스러워진다. ‘string’ 집합 또는 ‘number’ 집합에 속할 수 있는 값을 어떻게 설명하시겠습니까? 이 값은 단순히 그 집합들의 유니언: ‘string | number’에 속한다.

TypeScript는 집합론에 의거해 타입을 이용하는 여러 방법을 제공하며, 타입을 집합으로 생각하는 것이 더 직관적이다.

삭제된 구조적 타입 (Erased Structural Types)

TypeScript에서, 객체는 정확히 단일 타입이 아니다. 예를 들어 인터페이스를 만족하는 객체를 생성할 때, 둘 사이의 선언적인 관계가 없더라도 해당 인터페이스가 예상되는 곳에 해당 객체를 사용할 수 있습니다.

interface Pointlike {
  x: number;
  y: number;
}
interface Named {
  name: string;
}

function printPoint(point: Pointlike) {
  console.log("x = " + point.x + ", y = " + point.y);
}

function printName(x: Named) {
  console.log("Hello, " + x.name);
}

const obj = {
  x: 0,
  y: 0,
  name: "Origin",
};

printPoint(obj);
printName(obj);

TypeScript의 타입 시스템은 명목이 아닌 구조적이다.

obj는 숫자인 x와 y 프로퍼티를 가지고 있으므로, Pointlike로써 사용될 수 있다. 타입 간의 관계는 특정 관계로 선언되었는지가 아닌, 포함된 프로퍼티에 의해 결정된다.

TypeScript의 타입 시스템은 또한 구체화되지 않았다.

런타임에 obj가 Pointlike임을 알려주지 않는다. 사실, Pointlike 타입은 런타임에 어떤 형태로도 존재하지 않는다.

집합으로서의 타입 개념으로 보면, obj를 Pointlike 값 집합이나 Named 값 집합의 멤버로 간주할 수 있다.

빈 타입 (Empty Types)

첫 번째로 빈 타입은 예상을 무시하는 것처럼 보인다.

class Empty {}

function fn(arg: Empty) {
  // 무엇인가를 하나요?
}

// 오류는 없지만, '빈' 타입은 아니지 않나요?
fn({ k: 10 });

TypeScript는 주어진 인수가 유효한 Empty인지 확인하여 fn의 호출이 유효한지를 검사한다 { k: 10 }과 class Empty { }의 _구조를 확인하여 유효성을 검사합니다. Empty에 프로퍼티가 없으므로 Empty가 수행하는 모든 프로퍼티가 { k: 10 }에 속해있다. 그러므로, 유효한 호출이다.

놀랍지만, 최종적으로 명목적인 객체지향프로그래밍 언어와 매우 비슷하게 사용된다. 파생 클래스와 파생 클래스의 기본 사이의 자연스러운 하위 타입 관계가 파괴되기 때문에, 하위 클래스는 삭제할 수 없다. 구조적 타입 시스템은 호환 가능한 유형의 속성을 갖는 측면에서 하위 타입을 설명하므로 위의 관계를 암시적으로 구별한다.

동일한 타입 (Identical Types)

또 다른 빈번한 놀라움의 원인은 동일한 타입에 기인합니다.

class Car {
  drive() {
    // hit the gas
  }
}
class Golfer {
  drive() {
    // hit the ball far
  }
}
// No error?
let w: Car = new Golfer();

다시 말하지만, 오류가 아닌 이유는 클래스의 구조가 동일하기 때문이다. 잠재적인 혼란의 이유가 될 수도 있겠지만, 사실 상관없는 클래스가 동일한 경우는 일반적이지 않다.

차후에 클래스 챕터에서 클래스가 서로 어떻게 관련되는지에 대해 자세히 알아볼 것이다.

반영 (Reflection)

객체지향 프로그래머는 제네릭을 포함하여 어떤 값의 유형이라도 다룰(query)수 있음에 익숙하다.

static void PrintType() {
    System.out.println(typeof(T).Name);
}

TypeScript의 타입 시스템이 완벽히 지워졌으므로, 제네릭 타입 인자의 인스턴스화와 같은 정보는 런타임에 사용할 수 없다.

JavaScript에는 typeof와 instanceof와 같은 제한된 원시요소가 있지만, 이런 연산자는 타입이 지워진 코드의 출력에 존재하므로 여전히 작동함을 알아야 한다. 예를 들어, typeof (new Car())는 Car나 "Car"가 아닌 "object"이다.

출처 : TypeScript for Java/C# Programmers

정리4

Thu, 13 Jul 2023 17:22:49 GMT

난제 javascript에는 4바이트를 기준으로 동작하는 타입이 없다...! number은 8바이트로 부동소수점까지 표시 가능한 자료형이고 string은 가변적이다.

DataView DataView 뷰는 플랫폼의 자체 엔디언(바이트 정렬 방법)에 신경 쓰지 않으면서 ArrayBuffer에서 다양한 숫자 자료형의 데이터를 읽고 쓰기 위한 저수준 인터페이스를 제공한다.

이를 이용해서 32비트 정수형을 표현해볼 수 있겠지만,

Int32Array Int32Array 형식화 배열(TypedArray)은 플랫폼의 바이트 순서를 따르는 2의 보수 32비트의 부호있는 정수 배열이다. 바이트 순서를 제어해야 하는 경우 대신 DataView를 사용한다. 배열의 내용은 0으로 초기화된다. 배열이 생성되면 객체의 메서드를 사용하거나 표준 배열 인덱스 구문(즉, 대괄호 표기법 사용)을 사용하여 배열의 요소를 참조할 수 있다.

이를 이용해서 구현해보자.

학습 정리 - Day 03

Wed, 12 Jul 2023 09:45:26 GMT

학습 정리 - Day 03

학습 정리 - Day 02

Tue, 11 Jul 2023 09:24:22 GMT

가상머신

vmware fusion

우분투 다운받기

64-bit ARM (ARMv8/AArch64) desktop image

VS code 설치

Download Visual Studio Code

에서 우분투 버전의 Arm64로 선택

ip 확인하기

맥북

ifconfig | grep inet
ipconfig getifaddr en0

우분투

ip addr

유저 새로 생성하기

sudo adduser luizyformac

ssh 설정하기

$ sudo -s // root 전환
$ apt-get install ssh // ssh 설치
$ service ssh start // 서버 시작
$ service ssh status // 현재 상태 확인 가능

ssh 접속하기

로컬에서

$ ssh [username]@[host ip] -p [호스트 포트 번호]

파일 권한

자리수	1	3	3	3
의미	디렉터리 파일	소유자	그룹	그 외 사용자

ex) drwsrw-r--

d : 디렉터리 r : 읽기 w : 쓰기 x : 실행

8진수 모드로 파일 권한 수정하기

rwx 3개를 한자리수 8진수로 표현 가능하다 0o111 = 8 : rwx 0o110 = 7 : rw- 0o101 = 6 : r-x . . . 0o000 = 0 : ---

chmod 764 file

위 명령은 file을 rw-r-xr-- 접근권한으로 설정한다는 뜻

NTP

Network Time Protocol 이란 네트워크에서 시간 동기화를 위해 사용되는 프로토콜

설치

sudo apt-get install ntp

요것은 ntp서버에 있는 시간으로 동기화해주는 과정이다.

rotate

$ apt-get install rdate # rdate설치

$ rdate -s [ntp서버url] # rdate 명령어수행

$ date # 변경된 시간 확인

curl 설치하기

CURL은 서버와 통신할 수 있는 커맨드 명령어 툴이자 웹개발에 매우 많이 사용되고 있는 무료 오픈소스이다.

sudo apt-get install -y curl

노드 설치하기

nvm(Node Version Manager) https://github.com/nvm-sh/nvm

깃헙 가이드에 따라서 명령어들로 node 20을 설치했다.

luizyformac@luizy-virtual-machine:~$ curl -o- https://raw.githubusercontent.com/nvm-sh/nvm/v0.39.3/install.sh | bash

luizyformac@luizy-virtual-machine:~$ export NVM_DIR="$([ -z "${XDG_CONFIG_HOME-}" ] && printf %s "${HOME}/.nvm" || printf %s "${XDG_CONFIG_HOME}/nvm")"
[ -s "$NVM_DIR/nvm.sh" ] && \. "$NVM_DIR/nvm.sh" # This loads nvm

luizyformac@luizy-virtual-machine:~$ nvm install 20

luizyformac@luizy-virtual-machine:~$ nvm -v
0.39.3
luizyformac@luizy-virtual-machine:~$ node -v
v20.4.0
luizyformac@luizy-virtual-machine:~$ npm -v
9.7.2

모두 다 설치되었다.

vi편집기로 파일 만들기

vi main.js

코드 복사 붙여넣기

^c :wq

파일 확인하기

알림보내기

curl -X POST -H 'Content-type: application/json' --data [데이터] [목적지]

Axios

Axios란?

Axios는 node.js와 브라우저를 위한 Promise 기반 HTTP 클라이언트 입니다. 그것은 동형 입니다(동일한 코드베이스로 브라우저와 node.js에서 실행할 수 있습니다). 서버 사이드에서는 네이티브 node.js의 http 모듈을 사용하고, 클라이언트(브라우저)에서는 XMLHttpRequests를 사용합니다.

기능

브라우저를 위해 XMLHttpRequests 생성
node.js를 위해 http 요청 생성
Promise API를 지원
요청 및 응답 인터셉트
요청 및 응답 데이터 변환
요청 취소
JSON 데이터 자동 변환
XSRF를 막기위한 클라이언트 사이드 지원

기사 제목을 가져오기위해 Axios로 뉴스 링크에 get요청을 보내자!

const axios = require('axios').default;
const link = 'https://news.naver.com/main/main.naver?mode=LSD&mid=shm&sid1=105';
const data = axios.get(link);

Axois는 Promise 객체를 활용하기때문에 실행문을 따로 작성해줘야한다.

Promise

Promise객체는 비동기 작업이 맞이할 미래의 완료 또는 실패와 그 결과 값을 나타낸다.

기본 예제

let myFirstPromise = new Promise((resolve, reject) => {
  // 우리가 수행한 비동기 작업이 성공한 경우 resolve(...)를 호출하고, 실패한 경우 reject(...)를 호출합니다.
  // 이 예제에서는 setTimeout()을 사용해 비동기 코드를 흉내냅니다.
  // 실제로는 여기서 XHR이나 HTML5 API를 사용할 것입니다.
  setTimeout( function() {
    resolve("성공!")  // 와! 문제 없음!
  }, 250)
})

myFirstPromise
    .then((successMessage) => {
    // successMessage는 위에서 resolve(...) 호출에 제공한 값입니다.
    // 문자열이어야 하는 법은 없지만, 위에서 문자열을 줬으니 아마 문자열일 것입니다.
    console.log("와! " + successMessage)
    })
    .catch((error) => {
    console.log("에러!" + successMessage)
    })
    .finally((error) => {
    console.log("무조건 실행!" + successMessage)
    });

const axios = require('axios').default;
const link = 'https://news.naver.com/main/main.naver?mode=LSD&mid=shm&sid1=105';
const data = axios.get(link);

cheerio

DOM 객체를 반환해주기 때문에 변수면 $으로 명명

const cheerio = require('cheerio');
const $ = cheerio.load(data);

한글깨짐 방지

decoder 사용하기

const decoder = new TextDecoder('euc-kr');
const content = decoder.decode(response.data);

쉘 스크립트

[Linux] 쉘 스크립트(Shell script) 기초

쉘 스크립트란 간단히 말하자면 Unix커맨드등을 나열해서 실행하는 것이다. 언제 어떤 조건으로 어떠한 명령을 실행시킬 것인가, 파일을 컨텐츠를 읽어 들일 것인가, 로그 파일을 작성하는 것 등을 할 수 있다.

예시

test.sh

#!/bin/sh

echo "Hello, World!"

zsh

> sehll test.sh
> Hello, World!

입력

#!/bin/sh

read NAME
echo "Hello, $NAME!"

request

axios처럼 http 요청을 날리는 npm모듈이지만, 2020 부터 Deprecated 예정으로 사라질 예정이라고 한다. request 를 이용한 성공적인 크롤링 예제를 봤었지만, axios를 활용하는 방법을 고민해봐야겠다.

text encoding

디코딩하고싶은 디코더 객체를 만든다.

const decoder = new TextDecoder('euc-kr');

인코딩하고싶은 내용을 binary형태로 가져와 인코딩한다.

axios.get(url, { responseType: 'arraybuffer', responseEncoding: 'binary' })
  .then(response => {
    if (response.status === 200) {
      const html = decoder.decode(response.data);
      const $ = cheerio.load(html);
    });

크롤링에 성공장면

const decoder = new TextDecoder('euc-kr');

const axios = require('axios').default;
const cheerio = require('cheerio');
const { Script } = require('domelementtype');

const url = 'https://news.naver.com/main/main.naver?mode=LSD&mid=shm&sid1=105';

//버퍼를 주고, 바이너리로 받아와야 원하는 형태로 인코딩 할 수 있다.
axios.get(url, { responseType: 'arraybuffer', responseEncoding: 'binary' })
  .then(response => {
    if (response.status === 200) {
      const html = decoder.decode(response.data);
      const $ = cheerio.load(html);

      // 기사 제목을 선택하는 CSS 선택자를 사용하여 크롤링합니다.
      const newsTitles = $('.sh_text_headline');

      // 각 기사 제목을 출력합니다.
      newsTitles.each((index, element) => {
        console.log($(element).text());
      });
    }
  })
  .catch(error => {
    console.log(error);
  })
  .finally(response => {
    console.log("axois end");
  });

출력

정부, 5G 신규 사업자에 26.5~27.3㎓ 800㎒폭 할당
넥슨 '데이브 더 다이버' 누적 판매량 100만장 돌파
포스코DX, 佛 물류자동화 기업 엑소텍과 맞손
지하갱도 통신망 구축…작업자 안전 ‘실시간 관리’
카카오엔터, 반년간 웹툰·웹소설 불법물 1420만건 차단
 "주머니에 들어가는 양자 컴퓨터 시대 올 것" 꿈의 컴퓨터 만드는 김정상 아이온큐 공동 창업자[스타트업 리포트]
axois end

학습정리 - day1

Mon, 10 Jul 2023 09:21:14 GMT

정리

기록에 필요성과 방법 중간중간 기록하는것은 흘러가는 생각의 변화의 발자취를 남겨준다. 가볍게라도 기록을 남기는것과 그렇지 않는것은 생각을 복기하는것은, 그 과정에서도 성장을 가져온다. 같은 과정에서도 더 많은 성장을 이끌어내는 방법인것 같다.
프로그래밍 언어 나에게 Java가 제일 익숙한 언어지만, JavaScript를 공부하고 활용해보았다. 문법의 유사성은 보이지만, 원시타입 변수, 리터럴 표현법, 객체지향언어인지, 절차지향언어인지, 컴파일 언어인지, 스크립트 언어인지, 정적타입 언어인지, 동적타입 언어인지 등에서 많은 차이를 보였다. 이러한 차이가 만드는 특성을 이해했기때문에 나머지 문법을 몰라도 위 내용처럼 금방 찾아서 쓸 수 있었다.
JavaScript 원시타입으로 undefined 라는 값을 가지고있다. 이는 동적타입 변수이기 때문에 변수에 값이 할당될때 항상 재할당 되며, 선언되지 않았거나 한번도 할당되지 않았을때 가지는 값이다.

배열을 3차원 배열까지 확장시키면서 undefined라는 특성을 잘 활용해서 가변길이 배열을 적절히 만들어 활용할 수 있었다.

객체지향 언어이므로 Java와 유사하게 활용할 수 있었다.

유연한 언어인 만큼 배열을 다루면서 확장성이 뛰어나다는것을 알 수 있었고, 그에 따라 개발자가 철저히 관리할 줄 알아야한다는점도 알 수 있었다.
함수 분리기준 함수는 행위를 이름붙여 쪼갤 수 있는 단위로 하였다. 함수를 분리하지 않았다면, 주석의 증가와 가독성이 떨어지는 코드가 되었을것이다. 이를 이름붙여 나눌 수 있는 단위 즉, 함수명만 보고 행위를 예측할 수 있는 단위로 분리하게 되었을때 코드에대한 설명이 주석이 아니라 함수 명으로 표현이 가능하게 되어 과정을 이해하기 훨신 수월한 코드를 만들 수 있었다.

마크다운

마크다운 코드블록 만들기

영어로 바꾸고 1 왼쪽에 있는 backtick 세번에 가두고 쓰기

자바스크립트 문법

함수 선언

function sum(num1, num2){
    return num1 + num2;
}

배열 선언

let arr1 = [];
let arr2 = new Array();

2차원 배열 만들고 출력해보기

let arr = new Array();

arr[3] = [3, 2, 1, 0];
arr[2] = [2, 1, 0];
arr[1] = [1, 0];
arr[0] = [0];

arr.forEach((item) => {
    console.log(item);
});

js에서 char to int

var test = 'a';
test.charCodeAt(0); // 97

js switch문

switch(x) {
  case 'value1':  // if (x === 'value1')
    ...
    [break]

  case 'value2':  // if (x === 'value2')
    ...
    [break]

  default:
    ...
    [break]
}

입력값 언어 확인하기

자바스크립트에서 정규식으로 입력값을 검사해보자.

function checkEng(str){
    const regExp = /[a-zA-Z]/g; // 영어
    if(regExp.test(str)){
        return true;
    }else{
        return false;
    }
}

VSCode

폰트 설정

목표 : 고정폭 폰트로 출력하자.

vscode를 통해 실행하면 OUTPUT에 출력되며 가변폭 폰트로 출력된다
terminal의 node 명령어로 하면 고정폭으로 출력된다.

Oracle DBMS - Data Types

Fri, 14 Apr 2023 08:12:56 GMT

참조 : Database SQL Language Reference

1. character_datatypes (문자열)

{ CHAR [ (size [ BYTE | CHAR ]) ]
| VARCHAR2 (size [ BYTE | CHAR ])
| NCHAR [ (size) ]
| NVARCHAR2 (size)
}

2. number_datatypes (숫자형)

{ NUMBER [ (precision [, scale ]) ]
| FLOAT [ (precision) ]
| BINARY_FLOAT
| BINARY_DOUBLE
}

1) NUMBER Data Type

NUMBER(p,s)
NUMBER(p) -> NUMBER(p,0)
NUMBER  -> NUMBER(38,0)

정밀도 p 1부터 38값을 가지고, 기본 38이다. 숫자의 자릿수를 의미한다.

스케일 s -84 부터 127의 값을 가지고 기본 0이다. 소수점 아래 자릿수를 의미한다.

사용 예시)

Actual Data	Specified As	Stored As
123.89	`NUMBER`	123.89
123.89	`NUMBER(3)`	124
123.89	`NUMBER(3,2)`	exceeds precision
123.89	`NUMBER(4,2)`	exceeds precision
123.89	`NUMBER(5,2)`	123.89
123.89	`NUMBER(6,1)`	123.9
123.89	`NUMBER(6,-2)`	100
.01234	`NUMBER(4,5)`	.01234
.00012	`NUMBER(4,5)`	.00012
.000127	`NUMBER(4,5)`	.00013
.0000012	`NUMBER(2,7)`	.0000012
.00000123	`NUMBER(2,7)`	.0000012
1.2e-4	`NUMBER(2,5)`	0.00012
1.2e-5	`NUMBER(2,5)`	0.00001

2) FLOAT Data Type

CREATE TABLE test (col1 NUMBER(5,2), col2 FLOAT(5));

INSERT INTO test VALUES (1.23, 1.23);
INSERT INTO test VALUES (7.89, 7.89);
INSERT INTO test VALUES (12.79, 12.79);
INSERT INTO test VALUES (123.45, 123.45);

SELECT * FROM test;

      COL1       COL2
---------- ----------
      1.23        1.2
      7.89        7.9
     12.79         13
    123.45        120

3. datetime_datatypes (날짜형)

Datetime Field	Valid Values for Datetime	Valid Values for INTERVAL
YEAR	-4712 to 9999 (excluding year 0)	Any positive or negative integer
MONTH	01 to 12	0 to 11
DAY	01 to 31 (limited by the values of MONTH and YEAR, according to the rules of the current NLS calendar parameter)	Any positive or negative integer
HOUR	00 to 23	0 to 23
MINUTE	00 to 59	0 to 59
SECOND	00 to 59.9(n), where 9(n) is the precision of time fractional seconds. The 9(n) portion is not applicable for DATE.	0 to 59.9(n), where 9(n) is the precision of interval fractional seconds
TIMEZONE_HOUR	-12 to 14 (This range accommodates daylight saving time changes.) Not applicable for DATE or TIMESTAMP.	Not applicable
TIMEZONE_MINUTE (See note at end of table)	00 to 59. Not applicable for DATE or TIMESTAMP.	Not applicable
TIMEZONE_REGION	Query the TZNAME column of the V$TIMEZONE_NAMES data dictionary view. Not applicable for DATE or TIMESTAMP. For a complete listing of all time zone region names, refer to Oracle Database Globalization Support Guide.	Not applicable
TIMEZONE_ABBR	Query the TZABBREV column of the V$TIMEZONE_NAMES data dictionary view. Not applicable for DATE or TIMESTAMP.	Not applicable

전체 표

Code	Data Type	Description	설명
1	VARCHAR2(size [BYTE \| CHAR])	Variable-length character string having maximum length size bytes or characters. You must specify size for VARCHAR2. Minimum size is 1 byte or 1 character. Maximum size is: 32767 bytes or characters if MAX_STRING_SIZE = EXTENDED 4000 bytes or characters if MAX_STRING_SIZE = STANDARD Refer to "Extended Data Types" for more information on the MAX_STRING_SIZE initialization parameter. BYTE indicates that the column will have byte length semantics. CHAR indicates that the column will have character semantics.	가변길이 문자열 byte 기준 사이즈
1	NVARCHAR2(size)	Variable-length Unicode character string having maximum length size characters. You must specify size for NVARCHAR2. The number of bytes can be up to two times size for AL16UTF16 encoding and three times size for UTF8 encoding. Maximum size is determined by the national character set definition, with an upper limit of: 32767 bytes if MAX_STRING_SIZE = EXTENDED 4000 bytes if MAX_STRING_SIZE = STANDARD Refer to "Extended Data Types" for more information on the MAX_STRING_SIZE initialization parameter.	가변길이 문자열 Unicode 기준 사이즈
2	NUMBER [ (p [, s]) ]	Number having precision p and scale s. The precision p can range from 1 to 38. The scale s can range from -84 to 127. Both precision and scale are in decimal digits. A NUMBER value requires from 1 to 22 bytes.	숫자형 데이터 p는 정밀도로 기본 38다. 최소 1 한자리수 부터, 최대 38 자리수까지 s는 스케일값으로 기본 0이다, 소숫점 아래 표현 수 이다. 데이터 사이즈는 1 부터 22 bytes이다.
2	FLOAT [(p)]	A subtype of the NUMBER data type having precision p. A FLOAT value is represented internally as NUMBER. The precision p can range from 1 to 126 binary digits. A FLOAT value requires from 1 to 22 bytes.	실수형 데이터 타입 p는 NUMBER와 같은 스케일 값이다. 데이터 사이즈는 1부터 22bytes이다,
8	LONG	Character data of variable length up to 2 gigabytes, or 2^31 -1 bytes. Provided for backward compatibility.	문자형 데이터로 길이는 최대 2gb거나 2^31 - 1 btres이다.
12	DATE	Valid date range from January 1, 4712 BC, to December 31, 9999 AD. The default format is determined explicitly by the NLS_DATE_FORMAT parameter or implicitly by the NLS_TERRITORY parameter. The size is fixed at 7 bytes. This data type contains the datetime fields YEAR, MONTH, DAY, HOUR, MINUTE, and SECOND. It does not have fractional seconds or a time zone.	날짜형 데이터
100	BINARY_FLOAT	32-bit floating point number. This data type requires 4 bytes.	32bit 이진수 데이터
101	BINARY_DOUBLE	64-bit floating point number. This data type requires 8 bytes.	64bit 이진수 데이터
180	TIMESTAMP [(fractional_seconds_precision)]	Year, month, and day values of date, as well as hour, minute, and second values of time, where fractional_seconds_precision is the number of digits in the fractional part of the SECOND datetime field. Accepted values of fractional_seconds_precision are 0 to 9. The default is 6. The default format is determined explicitly by the NLS_TIMESTAMP_FORMAT parameter or implicitly by the NLS_TERRITORY parameter. The size is 7 or 11 bytes, depending on the precision. This data type contains the datetime fields YEAR, MONTH, DAY, HOUR, MINUTE, and SECOND. It contains fractional seconds but does not have a time zone.
181	TIMESTAMP [(fractional_seconds_precision)] WITH TIME ZONE	All values of TIMESTAMP as well as time zone displacement value, where fractional_seconds_precision is the number of digits in the fractional part of the SECOND datetime field. Accepted values are 0 to 9. The default is 6. The default format is determined explicitly by the NLS_TIMESTAMP_FORMAT parameter or implicitly by the NLS_TERRITORY parameter. The size is fixed at 13 bytes. This data type contains the datetime fields YEAR, MONTH, DAY, HOUR, MINUTE, SECOND, TIMEZONE_HOUR, and TIMEZONE_MINUTE. It has fractional seconds and an explicit time zone.
231	TIMESTAMP [(fractional_seconds_precision)] WITH LOCAL TIME ZONE	All values of TIMESTAMP WITH TIME ZONE, with the following exceptions: Data is normalized to the database time zone when it is stored in the database. When the data is retrieved, users see the data in the session time zone. The default format is determined explicitly by the NLS_TIMESTAMP_FORMAT parameter or implicitly by the NLS_TERRITORY parameter. The size is 7 or 11 bytes, depending on the precision.
182	INTERVAL YEAR [(year_precision)] TO MONTH	Stores a period of time in years and months, where year_precision is the number of digits in the YEAR datetime field. Accepted values are 0 to 9. The default is 2. The size is fixed at 5 bytes.
183	INTERVAL DAY [(day_precision)] TO SECOND [(fractional_seconds_precision)]	Stores a period of time in days, hours, minutes, and seconds, where day_precision is the maximum number of digits in the DAY datetime field. Accepted values are 0 to 9. The default is 2. fractional_seconds_precision is the number of digits in the fractional part of the SECOND field. Accepted values are 0 to 9. The default is 6. The size is fixed at 11 bytes.
23	RAW(size)	Raw binary data of length size bytes. You must specify size for a RAW value. Maximum size is: 32767 bytes if MAX_STRING_SIZE = EXTENDED 2000 bytes if MAX_STRING_SIZE = STANDARD Refer to "Extended Data Types" for more information on the MAX_STRING_SIZE initialization parameter.
24	LONG RAW	Raw binary data of variable length up to 2 gigabytes.
69	ROWID	Base 64 string representing the unique address of a row in its table. This data type is primarily for values returned by the ROWID pseudocolumn.
208	UROWID [(size)]	Base 64 string representing the logical address of a row of an index-organized table. The optional size is the size of a column of type UROWID. The maximum size and default is 4000 bytes.
96	CHAR [(size [BYTE \| CHAR])]	Fixed-length character data of length size bytes or characters. Maximum size is 2000 bytes or characters. Default and minimum size is 1 byte. BYTE and CHAR have the same semantics as for VARCHAR2.	고정길이 문자열 byte 기준 사이즈
96	NCHAR[(size)]	Fixed-length character data of length size characters. The number of bytes can be up to two times size for AL16UTF16 encoding and three times size for UTF8 encoding. Maximum size is determined by the national character set definition, with an upper limit of 2000 bytes. Default and minimum size is 1 character.	고정길이 문자열 unicode 기준 문자열
112	CLOB	A character large object containing single-byte or multibyte characters. Both fixed-width and variable-width character sets are supported, both using the database character set. Maximum size is (4 gigabytes - 1) * (database block size).
112	NCLOB	A character large object containing Unicode characters. Both fixed-width and variable-width character sets are supported, both using the database national character set. Maximum size is (4 gigabytes - 1) * (database block size). Stores national character set data.
113	BLOB	A binary large object. Maximum size is (4 gigabytes - 1) * (database block size).
114	BFILE	Contains a locator to a large binary file stored outside the database. Enables byte stream I/O access to external LOBs residing on the database server. Maximum size is 4 gigabytes.

[백준] 1981: 배열에서 이동 - BFS, 우선순위 큐

Thu, 06 Apr 2023 03:30:58 GMT

[백준] 12850 : 본대 산책2 - 분할정복, 행렬, 행렬제곱

출처 : 배열에서 이동 acmicpc.net/problem/1981

시간 제한	메모리 제한
1초	256 MB

문제

n×n짜리의 배열이 하나 있다. 이 배열의 (1, 1)에서 (n, n)까지 이동하려고 한다. 이동할 때는 상, 하, 좌, 우의 네 인접한 칸으로만 이동할 수 있다.

이와 같이 이동하다 보면, 배열에서 몇 개의 수를 거쳐서 이동하게 된다. 이동하기 위해 거쳐 간 수들 중 최댓값과 최솟값의 차이가 가장 작아지는 경우를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 n(2 ≤ n ≤ 100)이 주어진다. 다음 n개의 줄에는 배열이 주어진다. 배열의 각 수는 0보다 크거나 같고, 200보다 작거나 같은 정수이다.

출력

첫째 줄에 (최대 - 최소)가 가장 작아질 때의 그 값을 출력한다.

예제

입력 :

1	1	3	6	8
1	2	2	5	5
4	4	0	3	3
8	0	2	3	4
4	3	0	2	1

출력: 2

해설

아이디어

출발점(1,1) 부터 도착점 (n,n) 까지 이동하면서, 거쳐간 수의 최대 최소 차가 최소가 되게해야한다.

최솟값을 구해야하므로 나올 수 있는 경우의 수 중에 최대최소 차가 가장 작은것부터 탐색한다.

우선, 출발점과 도착점은 반드시 지나야하므로, 초기 최대최소로 설정해준다. M(max) : 1, m(min) : 1

출발점부터 현재 최대 최소로 탐색 가능한만큼 완전 탐색한다. M : 1, m : 1

현재 최대 최소로는 도착점까지 도달하지 못했다.

다음으로 생기는 경우의수는 다음과 같다 M : 3, m : 1, dif(difference) : 2 (new) M : 2, m : 1, dif : 1 (new) M : 4, m : 1, dif : 3 (new)

이 중 최대최소 차가 가장 적은 두번쨰 경우로 탐색을 시작한다. M : 2, m : 1

다음 가능한 경우의 수를 탐색한다 M : 3, m : 1, dif : 2 M : 4, m : 1, dif : 3 M : 5, m : 1, dif : 4 (new) M : 2, m : 0, dif : 2 (new)

차가 제일 적은 첫번째 경우 탐색 M : 3, m : 1, dif : 2

다음 경우의 수 M : 4, m : 1, dif : 3 M : 5, m : 1, dif : 4 M : 2, m : 0, dif : 2 M : 6, m : 1, dif : 5 (new)

차가 제일 적은 세번째 경우 탐색 M : 2, m : 0, dif : 2

이때,도착지까지 도달했으므로 답은 2가 된다.

좌표와, 최대최소는 쌍으로 되어있으므로 두 정수의 쌍을 표현할 P 클래스를 구현한다. 추후 HashSet으로 방문 체크를 할거라 싱글턴 기법으로 구현해 같은 점에대한 해쉬코드를 같게 해준다.

private static class P{
        public final int x, y;

        private P(int x, int y) {
            this.x = x;
            this.y = y;
        }

        private static P[][] ps;

        static {
            ps = new P[201][201];
        }

        public static P get(int x, int y){
            if (ps[x][y] == null){
                return ps[x][y] = new P(x, y);
            }
            return ps[x][y];
        }
    }

경우의수들은 항상 최대최소 차가 가장 적은값을 뽑아야하므로 우선순위 큐로 구현한다.

PriorityQueue queue = new PriorityQueue<>((o1, o2) -> Integer.compare(o1.y - o1.x, o2.y - o2.x));

중복된 최대최소를 경우의수로 생각 할 필요 없으므로 중복체크를 할 HashSet을 구현한다.

HashSet visit = new HashSet<>();

최대 최소 쌍을 골랐을때 출발점으로부터 탐색 할 메소드를 구현한다. 이때 탐색하며 새로 가능한 점을 Set 자료구조로 반환하고, 도착지까지 도착할 경우 null을 반환한다.

private static HashSet find(P minmax){
        int min = minmax.x;
        int max = minmax.y;

        HashSet set = new HashSet<>();
        boolean[][] visit = new boolean[N][N];
        ArrayDeque deque = new ArrayDeque<>();
        deque.addLast(P.get(0,0));
        visit[0][0] = true;

        while (!deque.isEmpty()){
            P p = deque.pollFirst();
            if (p.x == N-1 && p.y == N-1)
                return null;

            for (int i = 0; i < 4; i++) {
                int x = p.x + dx[i];
                int y = p.y + dy[i];
                if (x < 0 || y < 0 || x >= N || y >= N) continue;
                if (visit[x][y]) continue;
                if (min <= map[x][y] && map[x][y] <= max){
                    visit[x][y] = true;
                    deque.addLast(P.get(x,y));
                }
                else {
                    set.add(map[x][y]);
                }
            }
        }
        return set;
    }

출발점과 도착점으로 초기 최대 최소쌍을 설정해준다.

P init = P.get(Math.min(map[0][0], map[N-1][N-1]), Math.max(map[0][0], map[N-1][N-1]));

순차적으로 너비 우선 탐색을 할 코드를 구현한다.

HashSet visit = new HashSet<>();
queue.add(init);
visit.add(init);

while (!queue.isEmpty()){
    P p = queue.poll();

    HashSet next = find(p);

    if (next == null){
        System.out.println(p.y - p.x);
        break;
    }

    for (Integer i : next) {
        if (i > p.y){
            P nextp = P.get(p.x, i);
            if (visit.contains(nextp)) continue;
            queue.add(nextp);
            visit.add(nextp);
        }
        else if (i < p.x){
            P nextp = P.get(i, p.y);
            if (visit.contains(nextp)) continue;
            queue.add(nextp);
            visit.add(nextp);
        }
    }
}

최악의 경우 100x100개의 쌍이 만들어지고 그래프의 정점이 최대 100x100이므로 O(N^4logN) 100,000,000 x log100(=6.x) 으로 표현되지만, 모든 쌍이 그래프의 모든 점을 탐색하지 않으니 시간안에 들어 올 것 같다. 공간 복잡도는 가능한 쌍의 수와 같아 최대 100x100의 두개의 int쌍이 생겨 공간복잡도는 넉넉하다.

시간 복잡도	공간 복잡도
O(N^4logN)	100x100x8Byte + a

---

코드

github에서 코드 보기 : https://github.com/LuizyHub/CodingTestStudy/blob/master/src/Baek1981.java

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.HashSet;
import java.util.PriorityQueue;
import java.util.StringTokenizer;

public class Main {
    public static final int[] dx = {-1, 0, 0, 1};
    public static final int[] dy = {0, 1, -1, 0};
    private static class P{
        public final int x, y;
        private P(int x, int y) {
            this.x = x;
            this.y = y;
        }
        private static P[][] ps;
        static {
            ps = new P[201][201];
        }
        public static P get(int x, int y){
            if (ps[x][y] == null){
                return ps[x][y] = new P(x, y);
            }
            return ps[x][y];
        }
    }
    private static int N;
    private static int[][] map;
    private static HashSet find(P minmax){
        int min = minmax.x;
        int max = minmax.y;
        HashSet set = new HashSet<>();
        boolean[][] visit = new boolean[N][N];
        ArrayDeque deque = new ArrayDeque<>();
        deque.addLast(P.get(0,0));
        visit[0][0] = true;
        while (!deque.isEmpty()){
            P p = deque.pollFirst();
            if (p.x == N-1 && p.y == N-1)
                return null;

            for (int i = 0; i < 4; i++) {
                int x = p.x + dx[i];
                int y = p.y + dy[i];
                if (x < 0 || y < 0 || x >= N || y >= N) continue;
                if (visit[x][y]) continue;
                if (min <= map[x][y] && map[x][y] <= max){
                    visit[x][y] = true;
                    deque.addLast(P.get(x,y));
                }
                else {
                    set.add(map[x][y]);
                }
            }
        }
        return set;
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());
        map = new int[N][N];
        StringTokenizer st;
        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 0; j < N; j++) {
                map[i][j] = Integer.parseInt(st.nextToken());
            }
        }

        P init = P.get(Math.min(map[0][0], map[N-1][N-1]), Math.max(map[0][0], map[N-1][N-1]));
        PriorityQueue
 queue = new PriorityQueue<>((o1, o2) -> Integer.compare(o1.y - o1.x, o2.y - o2.x));
        HashSet visit = new HashSet<>();
        queue.add(init);
        visit.add(init);

        while (!queue.isEmpty()){
            P p = queue.poll();

            HashSet next = find(p);

            if (next == null){
                System.out.println(p.y - p.x);
                break;
            }

            for (Integer i : next) {
                if (i > p.y){
                    P nextp = P.get(p.x, i);
                    if (visit.contains(nextp)) continue;
                    queue.add(nextp);
                    visit.add(nextp);
                }
                else if (i < p.x){
                    P nextp = P.get(i, p.y);
                    if (visit.contains(nextp)) continue;
                    queue.add(nextp);
                    visit.add(nextp);
                }
            }
        }
    }
}

결론

지난번 아기상어 문제처럼 우선순위 큐를 이용한 너비우선 탐색을 진행하였다. 개선할 점으로는 매번 새로운 탐색을 진행하므로 이전 상황을 메모해두면 이전 상황부터 탐색을 진행해, 탐색 부분에서 속도를 줄일 수 있을 것 같다. 맵 사이즈가 최대 100x100이기 때문에 이 문제에서는 문제가 되지는 않았다. 대부분 사람들은 주어지는 숫자가 200이하 자연수인점을 이용해서 이분탐색(투 포인터)를 이용해 최소 해를 찾았다. 주어지는 수의 범위가 컸다면 내가 풀었던 방식으로 풀어야 할 것같다.

컴퓨터 시스템과 운영체제

Tue, 21 Mar 2023 16:31:29 GMT

사용자 공간과 커널 공간

32비트 Windows 운영체제 전체 4GB의 메모리 영역에서 하위 2GB는 사용자 공간, 상위 2GB는 커널 공간으로 나뉜다.

사용자 공간 응용 프로그램이 적재되고, 응용프로그램 변수가 만들어지고 동적 할당 받는 공간으로 활용하는 공간
커널 공간 커널 코드와 커널 데이터, 그리고 커널 함수들이 실행될 떄 필요한 스택 공간, 디바이스 드라이버 등이 탑재되는 공간

사용자 공간과 커널 공간으로 나누는 이유

응용 프로그램으로부터 커널 코드와 데이터를 지키기 위해서이다. 커널이 개방되어 있으면 시스템 훼손, 시스템 중단 등 심각한 문제가 발생할 수 있다. 만일, 응용 프로그램에서 cli(clear interrupt flag)과 같은 특권 명령을 실행할 수 있도록 허용한다면 cli를 실행하고 sti(set interrupt flag) 명령을 실행하지 않은 채 중단되거나 종료되어 버린다면, 더이상의 인터럽트를 인지할 수 없게된다. 따라서, 메모리 공간을 분리해서 커널공간을 보호해야 한다.

사용자 모드와 커널 모드

	사용자 모드	커널 모드
CPU의 메모리 엑세스 범위	사용자 공간에 국한. 커널 공간 엑세스 불가	커널 공간을 포함한 모든 메모리 공간
CPU의 하드웨어 엑세스 여부	불가(X)	모든 하드웨어 엑세스 가능(O)
CPU가 처리 가능한 명령	특권 명령을 제외한 모든 CPU 명령	특권 명령을 포함한 모든 CPU 명령
오류 발생 시 처리	사용자 프로그램만 실행 종료. 시스템이 종료되지 않으므로 안전	시스템에 심각한 오류가 발생한 것으로 시스템 종료

사용자 모드와 커널 모드로 나눈 이유

커널 코드와 데이터에 대한 보안과 보호를 위해서이다. 응용프로그램에 오류가 있을 수 있으므로 사용자 모드에서만 실행시키고, 특권 명령은 실행시키지 못하게 하여 하드웨어 접근을 막고 커널 공간에 접근하지 못하게 한다.

용자 모드에서 커널 모드로 바뀌는 경우

시스템 호출 응용프로그램이 시스템 호출 라이브러리에 작성된 시스템 호출 함수를 통해 간접적으로 커널 함수를 호출한다. 시스템 호출 라이브러리에 있는 시스템 호출 함수는 고유 번호( 커널 함수의 고유 ID, 시스템 호출 번호)로 커널 함수를 구분한다. '시스템 호출'은 CPU 모드를 커널 모드로 바꾸고 커널 공간 내에 미리 정해진 주소에 있는 '시스템 호출 핸들러(system call handler)' 코드를 실행하는 과정이다.
인터럽트 발생 입출력 장치나 저장장치가 CPU에게 인터럽트를 거는 경우 CPU는 자동으로 커널모드로 전환되고, CPU는 ISR(Interrupt Service Routine)로 점프하여 실행한다. ISR이 끝나면 CPU는 다시 사용자 모드로 돌아간다.

32비트 Windows 운영체제에서 응용프로그램과 라이브러리

응용프로그램의 크기

응용프로그램 크기는 최대 2GB로 제한되며, 코드, 전역변수, 힙, 스택을 모두 합친 크기를 의미한다. 운영체제가 설정한 2GB를 넘을 수 없다. 너머에 커널 공간이 있기 때문이다.

응용프로그램의 라이브러리

응용프로그램은 사용자가 작성한 함수들과 이들에 의해 호출되는 라이브러리 함수들이 링크 과정(linking)을 거쳐 하나의 실행 파일 내에 결합되어 저장된다. 응용프로그램이 실행될 때 실행 파일이 사용자 공간에 적재된다. 그러므로 사용자가 작성한 코드들과 전역 변수들, 그리고 라이브러리 함수들과 라이브러리에 선언된 전역 변수들이 응용프로그램에게 할당된 사용자 공 간에 함께 있으며, 사용자가 작성한 함수와 라이브러리 함수 모두 사용자 모드에서 실행된다.

특권 명령

특권 명령은 CPU 제조업체에 의해 특별히 설계된 CPU 명령들이다.

• I0 명령 I/0 명령은 컴퓨터 본체 내 하드웨어들을 제어하거나 입출력 장치나 저장장치를 제어하고 읽기 쓰기에 사용되는 CPU 기계 명령이다. 그래픽 카드나 네트워크 카드 등 입출력 장치들은 CPU 가 액세스할 수 있는 여러 개의 레지스터를 내장하고 있는데 이들을 I/0 포트(port)라고 부르 며, I/0 포트마다 I/0 주소가 할당된다. CPU는 I/0 포트에 값을 읽거나 쓰는 방식으로 입출력 장치를 제어하거나 입출력 장치에 값을 쓰거나 값을 읽는다.

• Halt 명령 커널은 현재 처리할 작업이 없을 때, Halt 명령을 실행하여 CPU의 작동을 중지시키고 CPU를 유휴(idle) 상태로 만든다.

• 인터럽트 플래그 켜고 끄기 대부분의 CPU는 인터럽트가 발생할 때 처리할 지 아니면 무시할 지를 나타내는 비트를 가지 고 있는데 이를 인터럽트 플래그(interrupt flag)라고 부른다.

• 타이머 설정 타이머를 설정하는 명령은 특권 명령이다.

• 컨텍스트 스위칭 현재 CPU의 레지스터들을 커널 영역에 저장하고, 저장된 컨텍스트 정보를 CPU 레지스터에 복귀시키는 컨텍스트 스위칭 명령은 커널 모드에서 실행되는 특권 명령이다.

시스템 유휴 프로세스(system idle process)

Windows10에서 작업관리자를 사용하여 CPU 실 행한 전체 실행 시간과 커널 모드로 작동한 시간을 비교하여 보여준다. 그래프에서 약간 진하 게 표시된 부분이 커널 모드로 작동하는 시간이다. 커널 모드의 시간 비율이 높은 경우는, 현재 windows에서 아무 작업도 이루어지고 있지 않을 때 커널 모드에서 실행되는 시스템 유휴 프로 세스(system idle process) 때문이다.

커널

커널은 부팅 시에 커널 공간에 적재되는 함수들과 데이터들의 집합이다, 커널은 컴파일된 바이너리 형태로 운영체제가 설치되는 하드 디스크의 특정 영역에 있다가 부팅 시에 메모리에 적재되며, 커널 모드에서 실행될 함수들과 시스템을 관리하기 위한 여러 종 류의 테이블과 구조체 등으로 구성된다. 커널 코드는 함수들의 집합이다. 컴퓨터에서 실행되는 단위는 프로세스나 스레드이지만, 커널은 프로세스도 스레드도 아니며 실행 단위가 아니고 그저 커널 공간에 적재된 함수들과 자료 구조들이다. 커널 공간은 수백 개의 함수들과 이들이 생성하고 사용하는 많은 자료구조들, 그리고 여러 디바이스 드라이버들로 이루어져 있다. 커널은 실행중이라고 표현할 수 없는 코드일 뿐이고, 프로세스가 아니므로 스택이나 힙도 가지지 않는다.

시스템 호출

시스템 호출은 사용자 공간의 코드에서 커널 공간의 코드를 호출하는 과정으로 커널 콜 (kernel call)이라고도 부른다.시스템 호출은 응용프로그램이 이러한 커널의 기능을 활용하도록 마련된 유일한 기술이다. 운영체제들은 사용자가 응용프로그램 내에서 직접 커널 함수를 호출하는 시스템 호출 코드를 작성하는 수고를 들어주기 위해 시스템 호출 라이브러리를 제공한다. 따라서, 기계명령을 직접 작성하지 않고, 시스템 호출을 일으킬 수 있다. 시스템 호출 라이브러리에 포함된 함수들을 시스템 호출 함수, 혹은 커널 API라고 부른다.

java에서는 직접 활용할 수 없는 경우가 많아, native call을 통해 C로 이루어진 코드를 불러올때가 많다. native 매서드는 운영체제 라이브러리를 활용하기 위해 C코드를 불러와 매서드 내용이 없는것을 볼 수 있다

시스템 호출은 응용프로그램에 서 커널 기능을 활용하는 유일한 경로(interface)이다.

CPU마다 '시스템 호출'을 일으키는 특별한 기계 명령(machine instruction)을 두고 있다. 이 기계 명령을 '시스템 호출 CPU 명령'이라고 하며 다음과 같은 것들이 있다. • int exge/iret - 인텔의 x86계열의 CPU의 명령, 32비트에서 사용 • syscall/sysret - AMD에서 최초 구현. 64비트에서만 작동 • sysenter/sysexit - Intel에서 최초 구현, x86/64 CPU, AMD에서 사용 시스템 호출을 트랩(trap)'이라고도 부르며, 시스템 호출이 진행되는 과정을 '트랩을 실행한다고 한다'고 한다. 시스템 호출을 일으키는 이 CPU 명령들을 '트랩 명령'이라고도 한다.

printf()실행 과정

printf()는 디스플레이에 정수, 실수, 문자열 등을 출력하는 C 표준 라이브러리 함수이다. 디스플레이 등 장치에 접근하는 것은 커널만이 할 수 있기 때문에, printf()가 직접 디스플레이에 쓰는 작업 은 할 수 없다. 대신, printf() 함수는 디스플레이에 출력하기 위해 시스템 호출 라이브러리의 write() 함수를 호출하여, write() 함수가 시스템 호출을 일으켜 커널 함수를 실행시키도록 한다. printf()는 매번 write()를 호출하는 것은 아니다. 표준 라이브러리에는 디스플레이에 출력할 데이터를 임시로 모아두는 '출력 버퍼'를 두고 있는데. printf()는 먼저 이 버퍼에 저장하고 이 버퍼가 차게 되거나 'n'을 만나면 write() 시스템 호출 함수를 호출하여 디스플레이에 출력시킨다. 이렇게 하는 이유는 시스템 호출 횟수를 줄여 시스템 호출로 인한 성능 저하를 막기 위해서이다. 시스템 호출에는 사용자 모드와 커널 모드 사이의 전환, 커널 함수 실행 등 많은 시간이 소요되므로, 시스템 호출 횟수를 줄이는 것이 성능 향상 을 위해 무엇보다도 필요하다.

java에서 System.out.println() 과 System.err.println() 는 서로 다른 버퍼를 가진다.

 System.err.print("err");
 System.out.print("out");

함수 호출과 시스템 호출의 차이

	함수 호출	시스템 호출
메모리 영역	사용자 영역의 코드에서 사용자 영역의 함수 호출	사용자 영역의 코드에서 커널 함수 호출
CPU 실행 모드	사용자 모드	사용자 모드에서 커널 모드로 전환
비용	함수 호출에 따른 비용	커널 모드로 전환하는 등 함수 호출에 비해 큰 비용

인터럽트 발생 및 처리 과정

CPU와 인터럽트 제어기

컴퓨터 시스템에서 인터럽트가 처리되기 위해서는 CPU와 인터럽트 제어기 (Interrupt Controller) 등의 하드웨어가 상호 협력해야 한다. 일반적으로 CPU에는 인터럽트 수신 핀이 1개뿐이기 때문에, 여러 입출력 장치로부터 인 터럽트를 받기 위해, CPU와 입출력 창치 사이에 APIC(Advanced Programmable Interrupt Controller)라는 하드웨어가 사용되며 인터럽트 제어기라고 한다. APIC는 입출력 장치로부 터 직접 인터럽트 신호를 받는 I/0 APIC 장치와 I/0 APIC로부터 인터럽트 정보를 받아 CPU의 INTR 핀에 직접 인터럽트 신호를 발생시키는 Local APIC 장치로 분리 구성된다. 현대의 I0APIC는 24개의 인터럽트 수신 핀을 두고 있어 24개의 장치로부터 인터럽트 신호를 받을 수 있 다. APIC 장치에 있는 각 인터럽트 입력 핀을 IRQ라고 하면, 핀에 고유 번호를 매겨 IRO1, IR03 과 같이 부른다. 여러 CPU가 있는 병렬 시스템에서 각 CPU마다 혹은 멀티 코어 CPU에서 각 코어에, Local APIC 장치가 하나씩 연결되며, I/O APIC는 대체로 컴퓨터당 1개만 사용된다.

인터럽트 벡터 테이블

인터럽트 벡터 테이블은 256개의 인터럽트에 대해 인터럽트 서비스 루틴 (ISR)의 주소를 저장 하고 있는 테이블이다. 인터럽트 벡터 테이블은 커널 영역에 저장되고 커널 코드에 의해서만 수정된다. 인터 럽트 벡터 테이블은 부팅 시에 만들어지고 ISR의 주소들이 저장된다. 인터럽트 벡터 테이블이 저장된 메모리 주소는 CPU 내에 레지스터에 저장되어 CPU가 인터럽트 서비스 루틴의 주소를 알 아낼 때 이용된다. IRC 핀마다 인터럽트 벡터가 결정되어 있으며, 이에 따라 운영체제는 부팅 시 I/0 APIC 내부에 24개의 IRQ마다 인터럽트 벡터(인터럽트 번호)를 저장한다.

처리 과정

장치로부터 인터럽트가 발생하면 I/0 APIC는 해당하는 IRQ의 인터럽트 벡터를 Local APIC에게 전송하고 Local APIC가 CPU에게 이를 알려주고 CPU는 인터럽트 벡터 테이블에 서 현재 발생한 인터럽트를 처리할 서비스 루틴의 주소를 알아내고 서비스 루틴을 실행한다.

고민해보기

자바에서 다음과 같은 코드를 수행하면 붉은 글씨로 "err"과 흰 글씨로 "out"이 출력된다.

public class Main {
    public static void main(String[] args) {
        System.err.print("err");
        System.out.print("out");
    }

System.err.print("err");
System.out.print("out");

위 두개의 함수는 서로 다른 버퍼를 가지고 출력한다. 다음과 같은 코드의 출력을 예측해보자.

public class Main {
    static final int MAX = 1_000_000;
    public static void main(String[] args) {
        for (int i = 0; i < MAX; i++) {
            System.err.println("err");
            System.out.println("out");
        }
    }
}

3. 알 수 없음.

[백준] 12850 : 본대 산책2 - 분할정복, 행렬, 행렬제곱

Wed, 01 Mar 2023 09:04:15 GMT

[백준] 12850 : 본대 산책2 - 분할정복, 행렬, 행렬제곱

출처 : 본대 산책2 acmicpc.net/problem/12850

시간 제한	메모리 제한
1초	512 MB

문제

숭실 대학교 정보 과학관은 유배를 당해서 캠퍼스의 길 건너편에 있다. 그래서 컴퓨터 학부 학생들은 캠퍼스를 ‘본대’ 라고 부르고 정보 과학관을 ‘정보대’ 라고 부른다. 준영이 또한 컴퓨터 학부 소속 학생이라서 정보 과학관에 박혀있으며 항상 꽃 이 활짝 핀 본 대를 선망한다. 어느 날 준영이는 본 대를 산책하기로 결심하였다. 숭실 대학교 캠퍼스 지도는 아래와 같다.

(편의 상 문제에서는 위 건물만 등장한다고 가정하자)

한 건물에서 바로 인접한 다른 건물로 이동 하는 데 1분이 걸린다. 준영이는 산책 도중에 한번도 길이나 건물에 멈춰서 머무르지 않는다. 준영이는 할 일이 많아서 딱 D분만 산책을 할 것이다. (산책을 시작 한 지 D분 일 때, 정보 과학관에 도착해야 한다.) 이때 가능한 경로의 경우의 수를 구해주자.

입력

D 가 주어진다 (1 ≤ D ≤ 1,000,000,000)

출력

가능한 경로의 수를 1,000,000,007로 나눈 나머지를 출력한다.

아이디어

그림을 그래프처럼 생각하며, 건물들을 각각 노드로 만들었다.

/*
js - jb
|  \ |
sa - ml
|  \ |
jl - hk
|    |
hs - hn

0 - 1
| \ |
2 - 3
| \ |
4 - 5
|   |
6 - 7
 */

N번 이동했을때 각 건물에 도착하는 경우의수는, N-1번 건물에 연결된 건물에 도착하는 수의 합이다.

Buildings[N][node.num] = Buildings[N-1][node.connected1] + Buildings[N-1][node.connecter2} ... ;

따라서 내가 만든대로면, N번째의 1번 노드에 도착하는 경우의수를 계산하면된다.

Bottom Up방식
바텀 업 방식으로 차례대로 구하면 총 N번의 반복문을 돌게 될것이다. 공간복잡도는 직전 값과 현재 값만 필요하므로 거의 안들것으로 예상된다. 최대 1억이라는 값이 들어와 O(1억) 을 1초로 계산했을때 시간제한에 걸림을 알 수 있다.

시간 복잡도 공간 복잡도

O(N) 거의 안듦

시간 복잡도	공간 복잡도
O(N)	거의 안듦

행렬곱을 이용한 거듭제곱 분할정복
반복문 방식을 보다싶이 같은 연산이 N번 반복됨을 알 수 있다. 이는, 특정 행렬에 같은 행렬을 N번 곱하는 연산으로 표현 가능다.
```
int[] ansMatrix = {1,0,0,1,0,0,0,0};
int[][] matrix = {
       //0 1 2 3 4 5 6 7
        {0,1,1,1,0,0,0,0},//0
        {1,0,0,1,0,0,0,0},//1
        {1,0,0,1,1,1,0,0},//2
        {1,1,1,0,0,1,0,0},//3
        {0,0,1,0,0,1,1,0},//4
        {0,0,1,1,1,0,0,1},//5
        {0,0,0,0,1,0,0,1},//6
        {0,0,0,0,0,1,1,0},//7
};
```
ansMatrix는 처음 움직임을 표현한 배열이다. 시작점에서 연결된 지점으로 한칸씩 이동한것을 표현했으며, 이 행렬에 matrix를 계속 곱해준다면, 반복문에서 했던 연산이 반복됨을 알 수 있다. 따라서 matrix의 2의n제곱의 제곱값을 미리 구해 거듭제곱을 분할정복하면 O(logN)이라는 시간복잡도로 값을 구할 수 있다. 예를들어보자. matrix의 1,2,4,8,16...2^31제곱값을 구해놓는다. 100제곱값은 64제곱 32제곱 4제곱의 곱으로, 2050은 2048제곱 2제곱의 곱으로 분할해서 미리 계산한 값을 이용해 목표값을 표현 할 수 있다. 공간복잡도 또한 256MB임에 충분함을 알 수 있다.

시간 복잡도 공간 복잡도

O(logN) 4Byte*8*8*31 + a

시간 복잡도	공간 복잡도
O(logN)	4Byte88*31 + a

코드

Bottom Up방식

백준에서 코드 보기 : http://boj.kr/9447a952e18d44878b0e250942f9af39

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {
    private static int N;
    private static final int MOD = 1_000_000_007;
    private static int[][] buidings = new int[2][8];
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());
        int current = 0;
        int pre = 1;
        buidings[current][0] = 1;
        buidings[current][3] = 1;
        for (int i = 1; i < N; i++) {
            current = (current+1)%2;
            pre = (pre+1)%2;

            buidings[current][0] = ((buidings[pre][1] + buidings[pre][2])%MOD + buidings[pre][3])%MOD;
            buidings[current][1] = (buidings[pre][0] + buidings[pre][3])%MOD;
            buidings[current][2] = (((buidings[pre][0] + buidings[pre][3])%MOD + buidings[pre][4])%MOD + buidings[pre][5])%MOD;
            buidings[current][3] = (((buidings[pre][0] + buidings[pre][1])%MOD + buidings[pre][2])%MOD + buidings[pre][5])%MOD;
            buidings[current][4] = ((buidings[pre][2] + buidings[pre][5])%MOD + buidings[pre][6])%MOD;
            buidings[current][5] = (((buidings[pre][2] + buidings[pre][3])%MOD + buidings[pre][4])%MOD + buidings[pre][7])%MOD;
            buidings[current][6] = (buidings[pre][4] + buidings[pre][7])%MOD;
            buidings[current][7] = (buidings[pre][5] + buidings[pre][6])%MOD;

        }

        System.out.println(buidings[current][1]);

    }
}
/*
js - jb
|  \ |
sa - ml
|  \ |
jl - hk
|    |
hs - hn

0 - 1
| \ |
2 - 3
| \ |
4 - 5
|   |
6 - 7


 */

행렬곱을 이용한 거듭제곱 분할정복

백준에서 코드 보기 : http://boj.kr/c4d99cd262bb4b9584ce5d3e5b2bd36d

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {
    private static int N;
    private static final int MOD = 1_000_000_007;
    private static int[] ansMatrix = {1,0,0,1,0,0,0,0};
    private static long[][][] binaryMatrix = new long[32][8][8];
    private static int[][] matrix = {
//           0 1 2 3 4 5 6 7
            {0,1,1,1,0,0,0,0},//0
            {1,0,0,1,0,0,0,0},//1
            {1,0,0,1,1,1,0,0},//2
            {1,1,1,0,0,1,0,0},//3
            {0,0,1,0,0,1,1,0},//4
            {0,0,1,1,1,0,0,1},//5
            {0,0,0,0,1,0,0,1},//6
            {0,0,0,0,0,1,1,0},//7
    };

기본 값 세팅

      private static void initMatrix(){
        for (int i = 0; i < 8; i++) {
            for (int j = 0; j < 8; j++) {
                binaryMatrix[0][i][j] = matrix[i][j];
            }
        }
        for (int i = 1; i < 32; i++) {
            binaryMatrix[i] = mutiplyMatrix(binaryMatrix[i-1], binaryMatrix[i-1]);
        }
    }
    private static long[][] mutiplyMatrix(long[][] a, long[][] b){
        long[][] ans = new long[8][8];
        for (int i = 0; i < 8; i++) {
            for (int j = 0; j < 8; j++) {
                for (int k = 0; k < 8; k++) {
                    ans[i][j] += a[i][k]*b[k][j];
                    ans[i][j]%=MOD;
                }
            }
        }
        return ans;
    }

    private static int[] mutiplyMatrix(int[] a, long[][] b){
        int[] ans = new int[a.length];
        for (int i = 0; i < a.length; i++) {
            for (int j = 0; j < b[i].length; j++) {
                ans[i] += a[j]*b[i][j];
                ans[i] %= MOD;
            }
        }
        return ans;
    }

행렬곱 연산을 위한 매소드 정의와, matrix 2의n제곱꼴의 값을 미리 구해주는 함수

     private static void solution(int count){
        String s = Integer.toBinaryString(count);
        int size = s.length();
        long[][] toMultiply = new long[8][8];
        for (int i = 0; i < 8; i++) {
            toMultiply[i][i] = 1;
        }
        for (int i = 0; i < s.length(); i++) {
            if (s.charAt(i) == '1'){
                toMultiply = mutiplyMatrix(toMultiply,binaryMatrix[size-i-1]);
            }
        }
        ansMatrix = mutiplyMatrix(ansMatrix, toMultiply);

        System.out.println(ansMatrix[1]);

    }
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());
        initMatrix();

        solution(N-1);

    }
}

결론

처음에는 Bottom Up방식 말고는 가장 빠른 방법이 없다고 생각했다. 직접 구현해보며 규칙성을 찾으려고도 해봤으나, 찾기는 힘들었고 그러다 떠오른방식은 선형대수학에서 배웠던 행렬식의 제곱을 쉽게 구하는 방법이 떠올랐다.

출처 : STEM CookBook, 기초 선형대수학(2판)

책의 일부분을 발췌해왔다. 이와같이 직교 대각화 행렬을 구할 수 있다면 이 문제는 O(1)만에 문제를 해결할 수 있었겠지만, 실제 풀이를 보았듯이 이 행렬은 이러한 연산이 불가능 했다. 행렬이 대각화가 되지 않아서, 결국에는 거듭제곱의 분할정복으로 문제를 풀게 되었다.

또, 자연스럽게 사용하고있었지만 이진수를 다루기에는 비트연산도 훌륭한 방법이지만, Integer.toBinaryString이라는 매소드로 문자열로 다루는것도 좋은 방법인거같다. 시험장이라면 이 방법이 편하기때문에 이 방법을 선택할것이다.

이 문제는 행렬 거듭제곱에 관한 문제였지만, 큰 거듭제곱을 연습하기 좋은 문제가 있어 첨부해본다.

곱셈 : https://www.acmicpc.net/problem/1629

[백준] 9527: 1의 개수 세기 - 2진수, 분할정복, 재귀

Sat, 25 Feb 2023 15:44:57 GMT

2진수와 분할정복

출처 : 1의 개수 세기 https://www.acmicpc.net/problem/9527

시간 제한	메모리 제한
1초	128 MB

문제

두 자연수 A, B가 주어졌을 때, A ≤ x ≤ B를 만족하는 모든 x에 대해 x를 이진수로 표현했을 때 1의 개수의 합을 구하는 프로그램을 작성하시오.

즉, f(x) = x를 이진수로 표현 했을 때 1의 개수라고 정의하고, 아래 식의 결과를 구하자.

입력

첫 줄에 두 자연수 A, B가 주어진다. (1 ≤ A ≤ B ≤ 10^16)

출력

1의 개수를 세어 출력한다.

아이디어

2진법 문제의 경우 직관적인 10진법으로 바꿔 생각해보는게 도움이 된다. 나같은 경우는 N자리수 자연수 까지 1의 개수를 세는것으로 생각했다.

예를들어 99 까지의 1의 개수를 세면
01
10
11
12
13
.
.
.
21
.
.
.
31
.
.
.
91

10의자리수에 1이 10번, 1의 자리수에 1이 10번 총 20번 나오게 된다.

2진법으로 7까지의 1의 개수를 세어보면
421(자릿수)
001 = 1
010 = 2
011 = 3
100 = 4
101 = 5
110 = 6
111 = 7

1의 자리수에 1 4번, 2의 자리수에 1 4번, 4의 자리수에 1 4번 총 12번 나오게 된다.

좀 더 일반화해서 2진법의 2^10 - 1 = 1111111111(2) 길이가 10인 수 까지의 1의 개수를 세어보면
1의 자리수에 0 2^8개, 1 2^8개 총 2^9 수가 오며,
1의 자리수에 1 2^8개, 2의 자리수에 1 2^8개, ... 2^9의 자리수에 1 2^8개의 1
1은 총 (2^8) * 9개가 존재한다.

완전 일반화해보면, 2^N - 1 까지의 1의 합은 (2^(N-2)) * (N-1)이다.

이러한 부분 일반화는 문제를 재귀적으로 해결함에 도움이 될것이다.

또 다음 예시로 111000000111(2) 이러한 12자리 2진수가 있다고 하자.
111000000111(2) 까지 1의 개수를 더할 것 이다.
제일 앞에있는, 즉 가장 높은 자리수의 1은 몇번 존재하는지 세는 방법은
100000000001(2) ~ 111000000111(2)
즉, 가장 높은 자리수 1은 111000000111(2) - 2^11 = 11000000111(2)번 존재한다.

의사코드를 써보면 다음과 같다.

function sumAllBinaryOne(number)
    if number = 1 or number = 0
        return number
    length = number.BinaryLength
    return (2^(length-2)) * (length-1)
    + num - 2^(length-1) + 1
    + sumAllBinaryOne(number - 2^(length-1))

코드

분할정복(?)과 재귀를 이용

백준에서 코드 보기 : http://boj.kr/31279aee4f8f4314942262ce82ef9cc8

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
    private static long A,B;
    private static int getBinaryLength(long num){
        int length = 0;
        while (num != 0){
            length++;
            num >>= 1;
        }
        return length;
    }
    private static long count(long num){
        if (num < 2)
            return num;
        int numlen = getBinaryLength(num);
        return (1L <<(numlen-2))*(numlen-1) + num - (1L <<(numlen-1)) + 1 + count(num - (1L <<(numlen-1)));
    }
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        A = Long.parseLong(st.nextToken());
        B = Long.parseLong(st.nextToken());
        System.out.println(count(B) - count(A-1));
    }
}

결론

O(1)로 한번에 구할 수 있는 일반항을 구할 수 있으면 좋지만, 부분적인 일반항이라도 세울 수 있다면, 재귀, 반복문, 점화식 등을 이용하면 원하는 값을 구할 수 있다는 것을 알았다.

[백준] 1922: 네트워크 연결 - MST, Prim, BST, TreeSet

Wed, 22 Feb 2023 19:01:41 GMT

대표적인 최소 스패닝트리 프림 알고리즘 우선순위 큐 대신 이진탐색 트리 이용

출처 : 네트워크 연결 acmicpc.net/problem/1922

시간 제한	메모리 제한
2초	256 MB

문제

도현이는 컴퓨터와 컴퓨터를 모두 연결하는 네트워크를 구축하려 한다. 하지만 아쉽게도 허브가 있지 않아 컴퓨터와 컴퓨터를 직접 연결하여야 한다. 그런데 모두가 자료를 공유하기 위해서는 모든 컴퓨터가 연결이 되어 있어야 한다. (a와 b가 연결이 되어 있다는 말은 a에서 b로의 경로가 존재한다는 것을 의미한다. a에서 b를 연결하는 선이 있고, b와 c를 연결하는 선이 있으면 a와 c는 연결이 되어 있다.)

그런데 이왕이면 컴퓨터를 연결하는 비용을 최소로 하여야 컴퓨터를 연결하는 비용 외에 다른 곳에 돈을 더 쓸 수 있을 것이다. 이제 각 컴퓨터를 연결하는데 필요한 비용이 주어졌을 때 모든 컴퓨터를 연결하는데 필요한 최소비용을 출력하라. 모든 컴퓨터를 연결할 수 없는 경우는 없다.

입력

첫째 줄에 컴퓨터의 수 N (1 ≤ N ≤ 1000)가 주어진다.

둘째 줄에는 연결할 수 있는 선의 수 M (1 ≤ M ≤ 100,000)가 주어진다.

셋째 줄부터 M+2번째 줄까지 총 M개의 줄에 각 컴퓨터를 연결하는데 드는 비용이 주어진다. 이 비용의 정보는 세 개의 정수로 주어지는데, 만약에 a b c 가 주어져 있다고 하면 a컴퓨터와 b컴퓨터를 연결하는데 비용이 c (1 ≤ c ≤ 10,000) 만큼 든다는 것을 의미한다. a와 b는 같을 수도 있다.

출력

모든 컴퓨터를 연결하는데 필요한 최소비용을 첫째 줄에 출력한다.

아이디어

우선순위 큐를 이용한 프림 알고리즘 구현
힙 이라는 자료구조를 이용해, 반정도 정렬된 구조에서 항상 최대 또는 최소를 찾을 수 있다는 장점이 있다. 삽입, 삭제 모두 O(logN)이라는 시간 복잡도를 가지며, 완전한 정렬상태를 가지지 않아 시간복잡도에서 이점을 가진다. 다만, 탐색은 O(N)이라는 시간복잡도를 가진다.

시간 복잡도 공간 복잡도

O(ElogE) (E + V) * (sizeof)int + ɑ
BST(Binary Search Tree)를 이용하여 프림 알고리즘 구현
힙과 같은 2진트리이며, 이진트리는 삽입, 삭제, 탐색이 최소 O(logN)에서 O(N)의 시간복잡도를 가진다. 다만, 자바 콜렉션 프레임워크에서는 TreeMap, TreeSet은 O(logN)의 시잔복잡도를 삽입, 삭제, 탐색에 모두 보장한다.
```
TreeSet.java
A NavigableSet implementation based on a TreeMap. The elements are ordered using their natural ordering, or by a Comparator provided at set creation time, depending on which constructor is used.
This implementation provides guaranteed log(n) time cost for the basic operations (add, remove and contains).
```
출처 : 자바 공식 문서 삽입, 삭제, 탐색 과정에서 AVL트리처럼 균형 이진트리를 유지하는것으로 추정된다. 따라서, 힙 자료구조보다는 균형을 유지하기 위해 추가적인 삽입, 삭제에 조금 더 오래걸릴 것으로 추정되지만, 탐색 또한 O(logN)이라는 시간복잡도를 가진다는 장점이 있다.

시간 복잡도 공간 복잡도

O(ElogV) (E + V) * (sizeof)int + ɑ

시간 복잡도	공간 복잡도
O(ElogE)	(E + V) * (sizeof)int + ɑ

시간 복잡도	공간 복잡도
O(ElogV)	(E + V) * (sizeof)int + ɑ

코드

우선순위 큐를 이용한 프림 알고리즘

백준에서 코드 보기 : http://boj.kr/578f96de5024454282bcb510e297c6d7

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Main {
    private static class Node implements Comparable{
        public int to;
        public int weight;

        public Node(int to, int weight) {
            this.to = to;
            this.weight = weight;
        }

        @Override
        public int compareTo(Node o) {
            return Integer.compare(this.weight,o.weight);
        }
    }

우선순위 큐에 넣어 줄 노드의 우선순위를 재정의

    private static ArrayList[] weights;
    private static boolean[] visit;
    private static int V,E;
    private static int primPQ(int start){
        PriorityQueue pq = new PriorityQueue<>();
        int total = 0;
        pq.offer(new Node(start,0));
        while (!pq.isEmpty()){
            Node node = pq.poll();
            if (visit[node.to])
                continue;
            total += node.weight;
            visit[node.to] = true;
            for (int i = 0; i < weights[node.to].size(); i++) {
                Node next = weights[node.to].get(i);
                if (!visit[next.to])
                    pq.add(next);
            }
        }
        return total;
    }

방문하지 않았던 모든 노드 까지의 가중치를 우선순위큐에 삽입해, 이후 방문 후 큐에서 뽑으면 continue를 통해 다시 뽑음. 필요하지 않은 노드들이 우선순위 큐에 들어있어 깊이를 깊게하여 삽입삭제 시간을 높힘.

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        V = Integer.parseInt(br.readLine());
        E = Integer.parseInt(br.readLine());

        visit = new boolean[V];
        weights = new ArrayList[V];

        for (int i = 0; i < V; i++) {
            weights[i] = new ArrayList<>();
        }

        for (int i = 0; i < E; i++) {
            st = new StringTokenizer(br.readLine());
            int from = Integer.parseInt(st.nextToken())-1;
            int to = Integer.parseInt(st.nextToken())-1;
            int weight = Integer.parseInt(st.nextToken());
            if (from == to)
                continue;
            weights[from].add(new Node(to,weight));
            weights[to].add(new Node(from,weight));
        }

        System.out.println(primPQ(0));
    }
}

이진 탐색 트리를 이용한 프림 알고리즘

백준에서 코드 보기 : http://boj.kr/467b9ee3110e4fbf8c24e5cc8a4f7cb5

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Main {
    private static class Node implements Comparable{
        public int to;
        public int weight;

        public Node(int to, int weight) {
            this.to = to;
            this.weight = weight;
        }
        @Override
        public boolean equals(Object obj) {
            Node node = (Node)obj;
            if (this.weight == node.weight && this.to == node.to)
                return true;
            else
                return false;
        }
        @Override
        public int compareTo(Node o) {
            if (this.weight == o.weight)
                return Integer.compare(this.to,o.to);
            else
                return Integer.compare(this.weight,o.weight);
        }
    }

TreeSet은 중복값을 허용하지 않는다. HashSet은 해시코드를 이용해서 해싱을해서 같은 값을 가지더라도, 다른 해시코드값을 가지면 다르게 구분되지만, TreeSet은 값만 비교해서 같은값이면 다른 해시코드라도 같은곳에 저장된다. 따라서, 가중치값이 같더라도 다르게 구분하기 위해 노드값 또한 compareTo 매소드에 비교하게 해줬다. TreeSet은 내부적으로 같은지 비교하기위해 equals 매소드도 많이 호출한다. 따라서, equals매소드도 필요에따라 Override해줬다.

    private static ArrayList[] weights;
    private static int[] distance;
    private static boolean[] visit;
    private static int V,E;
    private static int primBST(int start){
        TreeSet treeSet = new TreeSet<>(); // Node(to, weight)
        int total = 0;
        distance[start] = 0;
        treeSet.add(new Node(start,0));
        while (!treeSet.isEmpty()){
            start = treeSet.pollFirst().to;
            total += distance[start];
            visit[start] = true;
            for (int i = 0; i < weights[start].size(); i++) {
                Node node = weights[start].get(i);
                if (!visit[node.to] && distance[node.to] > node.weight){
                    if (distance[node.to] == Integer.MAX_VALUE) { // never was in tree;
                        distance[node.to] = node.weight;
                        treeSet.add(node);
                    }
                    else { // is in tree;
                        treeSet.remove(new Node(node.to, distance[node.to]));
                        distance[node.to] = node.weight;
                        treeSet.add(node);
                    }
                }
            }
        }
        return total;
    }

TreeSet에는 방문하지 않았던 노드들만 저장되어있어 최대 깊이는 logV이며, 탐색이 가능해 가중치를 갱신하기 위해 remove와 add를 적절히 활용해 낮은 깊이를 유지함에 시간복잡도에 이점이 생기고, 메모리 또한 이점생기지만, distance배열을 추가해 비슷할거 같다.

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        V = Integer.parseInt(br.readLine());
        E = Integer.parseInt(br.readLine());


        distance = new int[V];
        Arrays.fill(distance,Integer.MAX_VALUE);
        visit = new boolean[V];
        weights = new ArrayList[V];

        for (int i = 0; i < V; i++) {
            weights[i] = new ArrayList<>();
        }

        for (int i = 0; i < E; i++) {
            st = new StringTokenizer(br.readLine());
            int from = Integer.parseInt(st.nextToken())-1;
            int to = Integer.parseInt(st.nextToken())-1;
            int weight = Integer.parseInt(st.nextToken());
            if (from == to)
                continue;
            weights[from].add(new Node(to,weight));
            weights[to].add(new Node(from,weight));
        }

        System.out.println(primBST(0));
    }
}

결론

우선순위 큐와 TreeSet은 각각 힙과 균형이진트리라는 자료구조형태로 구현되어있어, 둘 다 이진트리라는 공통점이 있다.

힙은 반정도만 정렬되어 삽입 삭제가 빠르고 최대 또는 최소를 항상 알 수 있는 장점이 있다. 단점으로는 탐색을 하기위해서는 모든 값을 다 비교해야하므로 O(N)이라는 시간 복잡도를 가지는 단점이 있고, 완전히 정렬된 상태가 아니다.

균형 이진 트리는 완전 정렬되어 삽입 삭제 탐색까지 모두 O(logN)이라는 시간 복잡도를 가진다는 장점이 있다. 단점으로는 균형을 유지하기 위해 삽입 삭제 과정에 추가적인 연산이 필요 할 수 있다는 장점이 있다.

해당 문제에서 힙은 빠른 삽입 삭제로 문제를 풀 수 있었지만, 탐색을 못해 깊이 조절이나, 필요없는 값 까지 들어가게 되었다. 하지만, 균형 이진트리는 빠른 삽입 삭제와 탐색을 통해 필요한 값만 트리에 담아 깊이를 조절하고 필요없는 값을 넣지 않을 수 있었으나 추가적으로 distance라는 배열을 활용하게 된다는 점에서 메모리가 더 사용되었다.

힙과 균형이진트리의 장단점을 잘 비교 할 수 있었고, 앞으로 상황에 따라 더 최적화된 자료구조를 선택 할 수 있게 되었다.

[백준] 16236 : 아기 상어 - JAVA

Thu, 16 Feb 2023 05:18:53 GMT

출처 : 아기 상어 acmicpc.net/problem/16236

시간 제한	메모리 제한
2초	512 MB

문제

N×N 크기의 공간에 물고기 M마리와 아기 상어 1마리가 있다. 공간은 1×1 크기의 정사각형 칸으로 나누어져 있다. 한 칸에는 물고기가 최대 1마리 존재한다.

아기 상어와 물고기는 모두 크기를 가지고 있고, 이 크기는 자연수이다. 가장 처음에 아기 상어의 크기는 2이고, 아기 상어는 1초에 상하좌우로 인접한 한 칸씩 이동한다.

아기 상어는 자신의 크기보다 큰 물고기가 있는 칸은 지나갈 수 없고, 나머지 칸은 모두 지나갈 수 있다. 아기 상어는 자신의 크기보다 작은 물고기만 먹을 수 있다. 따라서, 크기가 같은 물고기는 먹을 수 없지만, 그 물고기가 있는 칸은 지나갈 수 있다.

아기 상어가 어디로 이동할지 결정하는 방법은 아래와 같다.

더 이상 먹을 수 있는 물고기가 공간에 없다면 아기 상어는 엄마 상어에게 도움을 요청한다.
먹을 수 있는 물고기가 1마리라면, 그 물고기를 먹으러 간다.
먹을 수 있는 물고기가 1마리보다 많다면, 거리가 가장 가까운 물고기를 먹으러 간다.

거리는 아기 상어가 있는 칸에서 물고기가 있는 칸으로 이동할 때, 지나야하는 칸의 개수의 최솟값이다. 거리가 가까운 물고기가 많다면, 가장 위에 있는 물고기, 그러한 물고기가 여러마리라면, 가장 왼쪽에 있는 물고기를 먹는다.

아기 상어의 이동은 1초 걸리고, 물고기를 먹는데 걸리는 시간은 없다고 가정한다. 즉, 아기 상어가 먹을 수 있는 물고기가 있는 칸으로 이동했다면, 이동과 동시에 물고기를 먹는다. 물고기를 먹으면, 그 칸은 빈 칸이 된다.

아기 상어는 자신의 크기와 같은 수의 물고기를 먹을 때 마다 크기가 1 증가한다. 예를 들어, 크기가 2인 아기 상어는 물고기를 2마리 먹으면 크기가 3이 된다.

공간의 상태가 주어졌을 때, 아기 상어가 몇 초 동안 엄마 상어에게 도움을 요청하지 않고 물고기를 잡아먹을 수 있는지 구하는 프로그램을 작성하시오.

입력

첫째 줄에 공간의 크기 N(2 ≤ N ≤ 20)이 주어진다.

둘째 줄부터 N개의 줄에 공간의 상태가 주어진다. 공간의 상태는 0, 1, 2, 3, 4, 5, 6, 9로 이루어져 있고, 아래와 같은 의미를 가진다.

0: 빈 칸
1, 2, 3, 4, 5, 6: 칸에 있는 물고기의 크기
9: 아기 상어의 위치

아기 상어는 공간에 한 마리 있다.

출력

첫째 줄에 아기 상어가 엄마 상어에게 도움을 요청하지 않고 물고기를 잡아먹을 수 있는 시간을 출력한다.

시간분석도

시간제한 : 2초 (1억 - 1초)

최대 20*20 사이즈의 공간 입력 상어의 최대 이동 횟수 400

이동할 때 마다 O(N^2)일 경우, 이동을 최대 N번 400 * 400 * 400 = 64_000_000
6천4백만번으로 연산 가능
이동할 때 마다 O(N^3)일 경우, 이동을 최대 N번 400 * 400 * 400 * 400 = 25_600_000_000
25억번으로 불가능

N^2 이내로 이동가능한 알고리즘 구현해야함

아이디어

bfs를 이용한 너비 우선탐색으로 가까운 먹이를 찾는 코드를 구현. 다만, 같은 거리내에서는 y값이 작을수록, x값이 작을수록 우선순위가 높아진다.

첫번째 생각, 다음 노드를 저장하는 배열을 만들어 매번 우선순위에 맞게 정렬을 해준다. 정렬 : O(NlogN) -> 전체 시간복잡도 O(N^3logN) 약 553_206_796 가능.

두번째 생각 다음 노드를 우선순위 큐를 이용하여 삽입 삭제를 logN에 연산. -> 전체 시간복잡도 O(N^2logN) 약 1_383_016 가능.

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Main {
    private static class Node implements Comparable {
        public int distance;
        public int x;
        public int y;

        public Node(int distance, int x, int y) {
            this.distance = distance;
            this.x = x;
            this.y = y;
        }

        @Override
        public int compareTo(Node o) {
            if (o.distance != distance){
                return distance - o.distance; //smaller
            } else if (o.x != x) { //distance is same
                return x - o.x; //bigger
            }
            else {// distance same, x same
                return y - o.y; //bigger
            }
        }
    }

우선순위 큐에 삽입할 Node class 구현, Comparable 인터페이스 구현으로 우선순위 설정

    private static int[] dy = {0, -1, 1, 0};
    private static int[] dx = {-1, 0, 0, 1};

상하좌우 탐색을 위한 배열, 문제 우선순위에 맞춰 상, 좌, 우, 하 순서로 탐색해서 우선순위 큐 삽입 속도를 높혀줌.

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int N = Integer.parseInt(br.readLine()); // Max = 20
        int[][] space;
        int insideShark = 0;
        int sharkSize = 2;
        int distance = 0;
        int sharkX=-1, sharkY=-1;

space : 물고기 위치 배열 insideShark : 상어가 먹은 물고기 수 sharkSize : 현재 상어 크기 distance : 총 이동거리, 총 소요시간 sharkX, sharkY : 현재 상어 위치

        space = new int[N][N]; // Max 20*20 400
        StringTokenizer st;

        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 0; j < N; j++) {
                int n = Integer.parseInt(st.nextToken());
                if (n==9) {
                    sharkX = i;
                    sharkY = j;
                    n=0;
                }
                space[i][j] = n;
            }
        }

입력 종료

        PriorityQueue que = new PriorityQueue<>();

        boolean ischanged = true;
        while (ischanged){ // if changed nothing -> break
            int[][] visited = new int[N][N];
            que.add(new Node(1,sharkX,sharkY));
            visited[sharkX][sharkY] = 1;
            ischanged = false;

            while (!que.isEmpty()){
                Node cur = que.poll();
                int curX = cur.x;
                int curY = cur.y;

                if (space[curX][curY] > 0 && space[curX][curY] < sharkSize){
                    distance += (visited[curX][curY] -1);
                    insideShark++;
                    if (sharkSize == insideShark){
                        sharkSize++;
                        insideShark = 0;
                    }
                    space[curX][curY] = 0; // fish is gone
                    sharkX = curX;
                    sharkY = curY;
                    ischanged = true; // shark position changed
                    que.clear();
                    break;
                }

                for (int i = 0; i < 4; i++) {
                    int nextX = curX + dx[i];
                    int nextY = curY + dy[i];

                    if (0 <= nextX && nextX < N && 0 <= nextY && nextY < N
                    && visited[nextX][nextY] ==0 && space[nextX][nextY] <= sharkSize){
                        visited[nextX][nextY] = visited[curX][curY] + 1;
                        que.add(new Node(visited[nextX][nextY], nextX, nextY));
                    }
                }
            }
        }
        System.out.println(distance);
    }
}

전체 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Main {
    private static class Node implements Comparable {
        public int distance;
        public int x;
        public int y;
        public Node(int distance, int x, int y) {
            this.distance = distance;
            this.x = x;
            this.y = y;
        }

        @Override
        public int compareTo(Node o) {
            if (o.distance != distance){
                return distance - o.distance; //smaller
            } else if (o.x != x) { //distance is same
                return x - o.x; //bigger
            }
            else {// distance same, x same
                return y - o.y; //bigger
            }
        }
    }

    private static int[] dy = {0, -1, 1, 0};
    private static int[] dx = {-1, 0, 0, 1};

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine()); // Max = 20
        int[][] space;
        int insideShark = 0;
        int sharkSize = 2;
        int distance = 0;
        int sharkX=-1, sharkY=-1;
        space = new int[N][N]; // Max 20*20 400

        StringTokenizer st;
        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 0; j < N; j++) {
                int n = Integer.parseInt(st.nextToken());
                if (n==9) {
                    sharkX = i;
                    sharkY = j;
                    n=0;
                }
                space[i][j] = n;
            }
        }

        PriorityQueue que = new PriorityQueue<>();
        boolean ischanged = true;

        while (ischanged){ // if changed nothing -> break
            int[][] visited = new int[N][N];
            que.add(new Node(1,sharkX,sharkY));
            visited[sharkX][sharkY] = 1;
            ischanged = false;

            while (!que.isEmpty()){
                Node cur = que.poll();
                int curX = cur.x;
                int curY = cur.y;

                if (space[curX][curY] > 0 && space[curX][curY] < sharkSize){
                    distance += (visited[curX][curY] -1);
                    insideShark++;

                    if (sharkSize == insideShark){
                        sharkSize++;
                        insideShark = 0;
                    }

                    space[curX][curY] = 0; // fish is eaten
                    sharkX = curX;
                    sharkY = curY;
                    ischanged = true; // shark position changed
                    que.clear();
                    break;
                }

                for (int i = 0; i < 4; i++) {
                    int nextX = curX + dx[i];
                    int nextY = curY + dy[i];

                    if (0 <= nextX && nextX < N && 0 <= nextY && nextY < N
                    && visited[nextX][nextY] ==0 && space[nextX][nextY] <= sharkSize){
                        visited[nextX][nextY] = visited[curX][curY] + 1;
                        que.add(new Node(visited[nextX][nextY], nextX, nextY));
                    }
                }
            }
        }

        System.out.println(distance);
    }
}

Java 변수의 초기화

Mon, 22 Aug 2022 09:33:49 GMT

변수의 초기화

지역변수의 초기화는 필수적이지만, 멤버변수(클래스변수, 인스턴스변수)와 배열은 다음과같이 자동 초기화된다.

자료형	기본값
boolean	false
char	'\u0000'
byte	0
short	0
int	0
long	0L
float	0.0f
double	0.0d or 0.0
참조형 변수	null

멤버변수의 초기화 방법

기본값
명시적 초기화
초기화 블럭
- 인스턴스 초기화 블럭, 클래스 초기화 블럭
생성자(인스턴스 변수만 해당)

0,1,2,3순으로 변수가 초기화된다.

class InitTest{
    static int cv = 1;
    int iv = 1;

    static{
        cv = 2;
    }

    {
        iv = 2;
    }

    InitTest() {
        iv = 3;
    }
}

	클래스 초기화	-	-	인스턴스 초기화	-	-	-
	기본값	명시적 초기화	클래스 초기화블럭	기본값	명시적 초기화	인스턴스 초기화블럭	생성자
cv	0	1	2	2	2	2	2
iv				0	1	2	3
order	1	2	3	4	5	6	7