burning-carrot/core-javascript

What I learend about the core of the javascript. (Korean) - burning-carrot/core-javascript

github.com

(최신 버전의 글은 위 GitHub 저장소에서 확인하실 수 있습니다. 때때로 업데이트되고있어요~)

Javascript에서 this는 무엇인가?

this가 무엇인지 대답하라고 할 때 보통 상황마다 다른 this를 대답하곤 한다.

"그래서 this가 뭔데요?"

this는 현재 실행 문맥이다. 그런데 이놈은 상황마다 다르다.

실행문맥이란 말은 호출자가 누구인지와 같다.

콘텍스트(context) 객체는 this가 바라보고 있는 어떤 객체이며 역으로 표현하면 this는 context를 가리키고 있는것이다.

 

this가 변하는 상황을 먼저 나열해보자

  • global scope
  • Object's method (암시적 바인딩)
  • call(), apply(), bind() (명시적 바인딩)
  • arrow function
  • new
  • callback

이제부터 정리해보자


상황에 따른 this

global scope

전역공간에서의 this는 전역객체를 가리킨다.

  • 브라우저는 window
  • Node.js는 global

전역변수를 선언하면 자바스크립트 엔진은 이를 전역객체의 프로퍼티로 할당한다.

var a = 1;

this.a; // 1

 

Object's method

함수는 자체로 독립적인 기능을 수행

메서드는 자신을 호출한 대상 객체에 관한 동작 수행 (부모 객체라고 하자)

  • 함수에서의 this : 전역객체
  • 메서드에서의 this : 호출한 객체
var func = function () {
  console.log(this);
};

(function () {
  func();
})(); // 즉시 실행함수로 실행해도, 다른 함수에서 a를 호출해도 a의 this는 Window, global이다.

var obj = {
  method: func,
};

obj.method(); // obj를 가리킨다.

 

call, apply, bind

함수에 명시적으로 this를 바인딩 할 수 있다.

call과 apply의 차이는 바인딩할 함수의 인자가 되며, 인자를 넣어주는 방법이 다르다.

func.call(this, `param1`, `param2`); // argument
func.apply(this, [`param1`, `param2`]); // array

call과 apply의 return값은 undefined이다.

또한 call, apply는 바인딩 하는 순간 실행된다.

bind의 경우는 this 바인딩만 해주고 실행은 직접 해줘야 한다.

func.bind(this, `param1`, `param2`);

 

arrow function

화살표 함수는 자신의 this가 없다.

화살표 함수는 함수를 선언할 때 this에 바인딩할 객체가 정적으로 결정되며, 화살표 함수를 둘러싸는 렉시컬 스코프(lexical scope)의 this가 사용된다.

또한 call, apply, bind를 사용해 명시적으로 this를 bind하더라도 무시한다.

var obj = {
  outer: function () {
    console.log(this); // this1

    var innerFunc = () => {
      console.log(this); // this2
    };
    innerFunc();
  },
};

obj.outer(); // this1과 this2는 동일하다.
var name = "outer";
const arrowObj = {
  name: "object",
  func: () => console.log(`${this.name} function`),
};

const funcObj = {
  name: "object",
  func: function () {
    console.log(`${this.name} function`);
  },
};

arrowObj.func(); // outer function
funcObj.func(); // object function

 

new

생성자 함수에서는 인스턴스 자신이된다. (class와 비슷함)

var Obj = function (name, age) {
  this.name = name;
  this.age = age;
};

var obj = new Obj("나비", 1); // {name:"나비", age:1}

 

callback

콜백함수의 제어권을 가지는 함수(메서드)마다 다르다

제어권을 가지는 함수가 콜백 함수에서 this를 무엇으로 할지 결정하기 때문이다.

// setTimeout의 this는 Window, Global이다.
setTimeout(function () {
  console.log(this); // Window
}, 300);

// Array.prototype.forEach에서 this는 Window, Global이다.
[1, 2, 3, 4, 5].forEach(function (x) {
  console.log(this, x); // Window
});

// eventListener에서 this는 event.target이다.
// <button id="a">클릭</button>
document.body.querySelector("#a").addEventListener("click", function (e) {
  console.log(this); // button
});

 


실전 문제들

 

7 Interview Questions on "this" keyword in JavaScript. Can You Answer Them?

7 interview questions to challenge your knowledge on "this" keyword in JavaScript.

dmitripavlutin.com

해당 문제들은 위 글에서 가져왔으며, 문제 정답 해설은 제가 직접 달았습니다. 틀린 부분은 댓글로 남겨주시면 빠르게 반영하겠습니다.

 

Variable vs property

const object = {
  message: "Hello, World!",

  getMessage() {
    const message = "Hello, Earth!";
    return this.message;
  },
};

console.log(object.getMessage()); // What is logged?

getMessage는 object의 메소드이다. 이 경우 this는 호출한 객체를 나타내므로 Hello, World!가 출력된다.

 

Cat name

function Pet(name) {
  this.name = name;

  this.getName = () => this.name;
}

const cat = new Pet("Fluffy");

console.log(cat.getName()); // What is logged?

const { getName } = cat;
console.log(getName()); // What is logged?

첫번째의 경우 object의 메소드로 호출했다. 따라서 Fluffy가 출력된다.

두번째의 경우 object의 메소드를 함수로 추출해서 실행했다.

이 때 getName은 arrow function이므로 렉시컬 스코프의 this를 기억한다.

따라서 위와 같이 this는 Pet이다. 따라서 Fluffy가 출력된다.

만약 getName이 arrow function이 아닌 일반 함수일 경우에 getName을 추출해서 사용할 경우 this는 전역객체이다.

전역객체에서 name은 선언되지 않았으므로 undefined이다. 따라서 undefined가 출력된다.

 

Delayed greeting

const object = {
  message: "Hello, World!",

  logMessage() {
    console.log(this.message); // What is logged?
  },
};

setTimeout(object.logMessage, 1000);

object의 메소드에서 this는 자기 자신이다.

그러나 우리는 setTimeout의 callback으로 object의 메소드를 인자로 넣었다.

따라서 이 함수는 메소드가 아닌 일반 함수로 동작한다.

이 일반 함수는 arrow function이 아니기 때문에 렉시컬 스코프를 기억하지 못하고 따라서 this는 전역객체가 된다.

따라서 undefined가 출력된다.

만약 arrow function인 경우에는 어떻게될까?

이는 객체에서 프로퍼티에 arrow function 함수를 할당하는 형태가 된다.

var message = "new world";

const object = {
  message: "Hello, World!",

  logMessage() {
    console.log(this.message); // What is logged?
  },

  logMessageArrow: () => {
    console.log(this.message); // What is logged?
  },
};

object.logMessage(); // 'Hello, World!'
object.logMessageArrow(); // 'new world'

setTimeout(object.logMessage, 1000); // 'new world'
setTimeout(object.logMessageArrow, 1000); // 'new world'

이 경우 arrow function는 자신의 this를 가지고 있지 않다. 따라서 이 this는 전역 객체가 된다.

따라서 위 경우는 다음과 같이 출력된다. 객체의 프로퍼티로 arrow function을 할당하는 경우에는 무조건 전역 객체가 this이기 때문이다. 이는 callback으로 사용될 때도 어차피 전역이므로 동일하다.

함수 단위 스코프를 이용하는 경우는 다음과 같다.

var foo = "foo";

function hello() {
  const object = {
    message: "Hello, World!",
    foo: "bar",

    logMessage() {
      console.log("method", this.foo, this.message);
    },

    logMessageArrow: () => {
      console.log("arrow", this.foo, this.message);
    },
  };

  object.logMessage(); // 'method' 'bar' 'Hello, World!'
  object.logMessageArrow(); // 'arrow' 'foo' undefined

  setTimeout(object.logMessage, 1000); // 'method' 'foo' undefined
  setTimeout(object.logMessageArrow, 1000); // 'arrow' 'foo' undefined
}

hello();

class와 new 키워드를 사용하는 경우는 callback으로 메소드를 사용할 때 다음과 같다.

여기서 arrow function의 경우 렉시컬 스코프를 기억하기 때문이다.

class Object {
  constructor(message) {
    this.message = message;
    this.logMessage = function () {
      console.log("method", this.message);
    };
    this.logMessageArrow = () => {
      console.log("arrow", this.message);
    };
  }
}

const object = new Object("Hello, World!");

setTimeout(object.logMessage, 1000); // 'method' undefined
setTimeout(object.logMessageArrow, 1000); // 'arrow' 'Hello, World!'

 

Artificial method

const object = {
  message: "Hello, World!",
};

function logMessage() {
  console.log(this.message); // "Hello, World!"
}

// Write your code here...

this를 강제로 바인딩 하는 문제이다.

bind, apply, call 등을 이용해 강제로 바인딩을 할 수 있다.

혹은 object의 메소드로 지정한 후 호출해 사용할 수 있다.

object.logMessage = logMessage;
object.logMessage();

// Using func.call() method
logMessage.call(object);

// Using func.apply() method
logMessage.apply(object);

// Creating a bound function
const boundLogMessage = logMessage.bind(object);
boundLogMessage();

 

Greeting and farewell

const object = {
  who: "World",

  greet() {
    return `Hello, ${this.who}!`;
  },

  farewell: () => {
    return `Goodbye, ${this.who}!`;
  },
};

console.log(object.greet()); // What is logged?
console.log(object.farewell()); // What is logged?

이 경우에 arrow function의 this는 전역객체이다.

따라서 greet의 경우에는 Hello, World!가, farewell의 경우에는 Goodbye, undefined!가 출력된다.

 

Tricky length

var length = 4;
function callback() {
  console.log(this.length); // What is logged?
}

const object = {
  length: 5,
  method(callback) {
    callback();
  },
};

object.method(callback, 1, 2);

object.method에 인자로 넣은 callback을 실행했다.

callback이 인자로 실행되므로 여기서 this는 전역객체이다. 따라서 4가 출력된다.

 

Calling arguments

var length = 4;
function callback() {
  console.log(this.length); // What is logged?
}

const object = {
  length: 5,
  method() {
    arguments[0]();
  },
};

object.method(callback, 1, 2);

이 경우 method에서 argument는 특수한 변수이며 다음과 같다.

{
  0: callback,
  1: 1,
  2: 2,
  length: 3
}

여기서 arguments[0]의 callback을 호출할 경우 이 callback은 arguments의 메소드처럼 동작한다.

따라서 이 경우 this는 arguments를 나타내므로 arguments의 길이인 3이 출력된다.

(object.method에 인자로 값을 3개 넣었으므로)

들어가며

소프트웨어 마에스트로 11기 활동이 끝난지 대략 3개월 정도 지난것 같다.

매 기수별로 전형에 차이가 있기도 하고, 특히 작년같은 경우는 코로나19 때문에 일정 자체도 예전보다 많이 밀렷었다.

소마 11기 활동을 준비하면서 자료를 얻기 좀 힘들었었는데 후배 기수들을 위해서 공부했던것들을 정리해보려 한다.

 

2021년 12기를 모집하고 있다.

코딩 테스트

코딩 테스트는 10기 때와 11기 때 많이 달랐다고 들었다.

10기 때는 알고리즘 문제로만 시험을 본것으로 알고 있으며, 여러 문제들이 주어진 것으로 알고있다. (제한시간 내에 다풀기 어려운)

11기때는 이와 반대로 알고리즘 3문제, SQL 문제, web 문제 이렇게 총 5문제를 풀었다.

 

알고리즘 시험 대비하기

소마 합격생들의 후기 및 블로그들을 살펴보면 대충 어떤 문제들을 공부했는 지 알 수 있다.

출제 문제들의 공통 특징들을 요약한다면, 문제들이 대부분 O(N logN) 이내에 풀어야 시간초과가 나지 않는 문제들로 이루어졌었다는 점이다.

즉 브루트 포스 방법으로 모든 경우를 시도해 보기 보다는 시간복잡도를 줄여야 하는 문제들이 존재했다.

N log N 이내로 문제를 풀기 위한 기법들은 다음과 같았다.

  • 자료구조
  • 정렬
  • 동적 계획법

이 외에도 그래프 관련 기법들은 알아놓는 편을 추천한다.

기본적인 다익스트라, 플로이드 와샬, 플로이드에서 유니온 파인드(서로소 집합) 정도는 알아놓는것을 추천한다.

특히 문제에서 요구하는 기법 자체를 모를 경우 절대로 시간 복잡도를 줄이기 불가능한 경우가 있었다.

 

개인적으로 추천하는 커리큘럼은 삼성 SDS에서 2주동안 진행하는 알고리즘 특강의 커리큘럼이다.

알고리즘 문제풀이를 진행하며 공부한 알고리즘들을 따로 정리했었는데 도움이 되었으면 좋겠다.

 

changicho/algorithm-training

The repository of problem solving (especially algorithm problems of computer science) - changicho/algorithm-training

github.com

 

여기까지는 정석대로 알고리즘 시험을 준비하는 방법이고,

이 방법대로 준비할 경우 대충 백준 플래티넘 이상 등급정도의 실력을 가지고 있을 것이다.

 

그러나 실제로 코딩테스트 합격자들의 문제 풀이수를 보면, 알고리즘 문제에서 제대로 푼 문제가 1~2 문제 정도였다.

즉 다들 알고리즘 문제의 정답률이 생각보다 낮았으며, 꼭 다 맞출 필요는 없다는 말이 된다.

 

따라서 알고리즘 문제풀이에 자신이 없는 경우는 출제 경향만 훑고 가는것도 크게 도움이 될 것이다.

추천하는 백준 문제들은 다음과 같다.

 

1939번: 중량제한

첫째 줄에 N, M(1≤M≤100,000)이 주어진다. 다음 M개의 줄에는 다리에 대한 정보를 나타내는 세 정수 A, B(1≤A, B≤N), C(1≤C≤1,000,000,000)가 주어진다. 이는 A번 섬과 B번 섬 사이에 중량제한이 C인 다리

www.acmicpc.net

 

1092번: 배

첫째 줄에 N이 주어진다. N은 50보다 작거나 같은 자연수이다. 둘째 줄에는 각 크레인의 무게 제한이 주어진다. 이 값은 1,000,000보다 작거나 같다. 셋째 줄에는 박스의 수 M이 주어진다. M은 10,000보

www.acmicpc.net

 

2493번: 탑

첫째 줄에 탑의 수를 나타내는 정수 N이 주어진다. N은 1 이상 500,000 이하이다. 둘째 줄에는 N개의 탑들의 높이가 직선상에 놓인 순서대로 하나의 빈칸을 사이에 두고 주어진다. 탑들의 높이는 1

www.acmicpc.net

 

SQL 문제

사실 매번 전형이 다르다 보니 SQL 문제는 이번에 나올지 확실할 수 없다.

프로그래머스와 Leetcode에서 SQL 문제를 풀었었고 대부분 SQL 테스트의 경우에는 쉽게 통과할 수 있었다.

LEFT_JOIN, RIGHT_JOIN 정도까지 알고 가면 좋을것 같고, ORDER_BY 정도는 알아야 한다.

 

Web 문제

다양한 분야의 연수생들을 뽑는것을 원칙으로 알고있는데, Javascript + HTML 을 주로 하는 front-end 포지션에 유리한 문제이다.

11기는 시험을 구름 IDE에서 진행했었고, 클라우드 서버에 html, js를 띄워 javascript로 API fetching 을 하는 문제를 냈었다.

보통 이런 경우에 문제는 API서버에 요청을 보낼 수 있는지와 응답받은 데이터를 이용해 DOM을 갱신하는것을 물어보는것이 대부분이고,

CORS 문제를 해결하는 것 정도만 알면 될것이다.

 

면접

11기 면접

2번 정도의 코딩 테스트를 통과하면 이제 면접이다.

최근에는 150명 정도를 선발하기 때문에 (11기 기준) 여기서 부터 경쟁률은 3:1 이하 정도로 떨어진다고 보면 된다.

이는 매 기수마다 경쟁률을 보면 알 수 있는데, 서류 전형부터 경쟁률이 약 10:1 정도였으므로 코딩 테스트에서 절반 이상 떨어뜨린다고 가정했다.

 

면접은 조별로 느낌이 많이 다른것으로 알고있다. 어떤 조는 프로젝트 중심으로, 어떤 조는 CS 지식 중심으로 진행되는 것으로 알고 있다.

종합적으로는 CS지식은 많이 물어보지 않는것 같다. 대신에 프로젝트 경험이 가장 중요하게 작용한다고 생각한다.

특히 대기업 인턴 경험의 경우가 유리했던것 같은데, 이는 어느정도 이미 증명되었다고 볼 수 있는 계기를 마련했기 때문이라고 생각한다.

 

그리고 소마 면접에서 유리한 가장 좋은 경험으로는 다음과 같다.

프로젝트 도중 팀원이 탈주한 경험

 

11기도 약 10% 정도가 도중에 그만둔 것으로 알고있다. 따라서 이런 위기를 극복한 경험이 있다면 다른 지원자들과 차별화 할 수 있을것이다.

 

이 외에도 소프트웨어 마에스트로의 특성에 맞춰서 유리한 경험이 있다면 면접은 크게 준비하지 않아도 될것같다.

 

12849번: 본대 산책

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

www.acmicpc.net

난이도 정답률 (%) 시간 제한 (초)
Silver I 63.764 1

설계

시간 복잡도

D는 다음과 같다. (1 ≤ D ≤ 100,000)

D분 일 때, 정보 과학관에 도착해야 한다.

모든 경우를 탐색할 경우 제한 시간 내에 불가능하다. (1,000,000,007 이상이 소요되기 때문)

따라서 이전 연산 결과를 활용한 동적 계획법을 사용한다.

이 경우 시간 복잡도는 O(N) 이므로 제한 시간 1초 내에 충분하다.

 

공간 복잡도

정답은 1,000,000,007로 나눈 수 이기 때문에, 1,000,000,007 이하의 정수이다.

경우의 수를 계산할 때 이 범위를 초과할 수 있으므로 연산 과정들은 long long형으로 선언한다.

 

동적 계획법

현재 위치로 오는 경우는, 현재 위치와 연결된 위치들의 이전에 방문한 횟수들을 더한 값이다.

따라서 일반식은 다음과 같이 설정할 수 있다.

// a, b는 i와 연결되어 있는 위치
dp[n][i] = dp[n-1][a] + dp[n-1][b] ...

dp를 다음과 같이 설정한다.

dp[n][index]  // n초 후 해당 건물 위치 index로 가는 경우의 수

여기서 n이 매우 크고, n을 계산할 때는 n-1번째 값만 필요하므로 dp 배열을 1차원으로 설정한다.

여기서 정보과학관에서 출발해야 하는데, index를 다음과 같이 설정한다.

  • 0 : 정보과학관
  • 1 : 전산관
  • 2 : 신앙관
  • 3 : 미래관
  • 4 : 진리관
  • 5 : 환경직기념관
  • 6 : 학생회관
  • 7 : 형남공학관

정보 과학관에서 출발하므로 dp의 0번째는 = 1이 된다.

dp[8] = {1, 0, 0, 0, 0, 0, 0, 0}; // n = 0 일 때

탐색을 진행하면서 dp의 값들을 이전 값들을 이용해 갱신한다.

이 때 이동할 수 있는 위치는 정해져 있으므로 연결된 점들을 이용한다.

dp[0] = 1;
while (D--) {
  long long temp[8] = {
      0,
  };

  for (int i = 0; i < 8; i++) {
    temp[0] = dp[1] + dp[3];
    temp[1] = dp[0] + dp[2] + dp[3];
    temp[2] = dp[1] + dp[3] + dp[4] + dp[5];
    temp[3] = dp[0] + dp[1] + dp[2] + dp[5];
    temp[4] = dp[2] + dp[5] + dp[6];
    temp[5] = dp[3] + dp[2] + dp[4] + dp[7];
    temp[6] = dp[4] + dp[7];
    temp[7] = dp[5] + dp[6];
  }

  for (int i = 0; i < 8; i++) {
    dp[i] = temp[i] % 1000000007;
  }
}

 

테스트케이스

종류 input output
예제 10 9857

 

코드

 

changicho/algorithm-training

The repository of problem solving (especially algorithm problems of computer science) - changicho/algorithm-training

github.com

 

정리

내 코드 (ms) 빠른 코드 (ms)
0 0

 

 

12852번: 1로 만들기 2

첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 자연수 N이 주어진다.

www.acmicpc.net

난이도 정답률 (%) 시간 제한 (초)
Silver I 52.488 0.5

 

설계

시간 복잡도

X는 최대 10^6인 자연수이다.

 

X부터 1까지 탐색을 진행할 때 다음 두가지 방법을 이용할 수 있다.

  • BFS
  • 동적 계획법

BFS의 경우 최악의 경우 시간 복잡도는 O(N) 이하이다.

동적 계획법의 경우 최악의 경우 시간 복잡도는 O(N) 이다.

두 방법 모두 제한시간 0.5초 내에 충분하다.

 

공간 복잡도

X는 최대 10^6인 자연수이다.

 

저장해야 되는 정보는 다음과 같다.

 

  • 현재 노드 (index)
  • 부모 노드
  • 1까지 도달하는데 거치는 노드의 수

이 값 모두 int형으로 충분하다.

 

테스트케이스

종류 input output
예제 1 2 1
2 1
예제 2 10 3
10 9 3 1
임계값 (최소) 1 0
1
임계값 (최대) 1000000 19
1000000 500000 250000 125000 62500 31250 15625 15624 7812 3906 1953 651 217 216 108 54 27 9 3 1 

 

풀이

BFS

 

changicho/algorithm-training

The repository of problem solving (especially algorithm problems of computer science) - changicho/algorithm-training

github.com

BFS를 이용해 X에서 1까지 탐색할 수 있다.

 

이 때 저장해야 할 정보는 다음과 같다.

  • 현재까지 거쳐온 노드의 정보

노드의 정보에서 가장 마지막에 저장되어있는 것이 현재 방문한 노드이므로 vector로만 나타낼 수 있다.

이 때 이전에 방문한 정점을 다시 방문하지 않도록 주의한다.

struct Status {
  vector<int> history;
};

queue<Status> q;
vector<int> answer;
q.push({{N}});

while (!q.empty()) {
  Status cur = q.front();
  q.pop();

  int node = cur.history.back();
  if (node == 1) {
    answer = cur.history;
    break;
  }
  if (visited[node]) continue;
  visited[node] = true;

  vector<int> new_history = cur.history;

  if (node % 3 == 0) {
    new_history.push_back(node / 3);
    q.push({new_history});
    new_history.pop_back();
  }
  if (node % 2 == 0) {
    new_history.push_back(node / 2);
    q.push({new_history});
    new_history.pop_back();
  }
  if (node - 1 > 0) {
    new_history.push_back(node - 1);
    q.push({new_history});
    new_history.pop_back();
  }
}

 

동적 계획법

 

changicho/algorithm-training

The repository of problem solving (especially algorithm problems of computer science) - changicho/algorithm-training

github.com

동적 계획법을 이용하고, 각 상황별로 어느 노드에서 현재 노드로 왔는지를 기록한다.

이 떄의 시간 복잡도는 O(N)이다.

 

다음 자료구조에서 나타내는 정보는 다음과 같다.

  • 현재 노드 (index)
  • 부모 노드
  • 1까지 도달하는데 거치는 노드의 수
struct Edge {
  int length; // 1까지 도달하는데 거치는 노드의 수
  int from;   // 부모 노드
};
Edge dp[1000001]; // 현재 노드 index

일반 식은 다음과 같다.

dp[i] = min({dp[i - 1].length + 1, i - 1}, {dp[i / 2].length + 1, i / 2}, {dp[i / 3].length + 1, i / 3})

현재 index에서의 dp값은 현재 index로 도달할 수 있는 3가지 경우 중에서 가장 length가 짧은 경우이다.

 

초기 값은 다음과 같다.

dp[1] = {0, 0};

이 방법으로 bottom-up 방식으로 풀이한다.

 

X가 1인 경우는 보장되므로 2부터 탐색을 진행한다.

 

이 때 i번째를 구할 때 i-1번쨰를 이용해 먼저 구해 초기값을 할당하지 않도록 구성한다.

for (int i = 2; i <= N; i++) {
  dp[i] = {dp[i - 1].length + 1, i - 1};
  if (i % 2 == 0 && dp[i].length > dp[i / 2].length + 1) {
    dp[i] = {dp[i / 2].length + 1, i / 2};
  }
  if (i % 3 == 0 && dp[i].length > dp[i / 3].length + 1) {
    dp[i] = {dp[i / 3].length + 1, i / 3};
  }
}

 

정리

내 코드 (ms) 빠른 코드 (ms)
0 0

 

'공부 > 알고리즘 문제풀이' 카테고리의 다른 글

백준.12849.본대 산책  (0) 2021.01.26
백준.1197.최소 스패닝 트리  (0) 2021.01.24
큰 수 연산 (Big Integer)  (0) 2021.01.04
삼성 7699. 수지의 수지 맞는 여행  (0) 2019.12.31
삼성 9088. 다이아몬드  (0) 2019.12.27
 

1197번: 최소 스패닝 트리

첫째 줄에 정점의 개수 V(1 ≤ V ≤ 10,000)와 간선의 개수 E(1 ≤ E ≤ 100,000)가 주어진다. 다음 E개의 줄에는 각 간선에 대한 정보를 나타내는 세 정수 A, B, C가 주어진다. 이는 A번 정점과 B번 정점이

www.acmicpc.net

난이도 정답률 (%) 시간 제한 (초)
Gold IV 39.708 2

설계

유사한 문제

시간 복잡도

정점의 개수 V(1 ≤ V ≤ 10,000)와 간선의 개수 E(1 ≤ E ≤ 100,000)

 

최소 신장 트리를 구하기 위해선 크루스칼 알고리즘과, 프림 알고리즘이 존재한다.

 

각 경우 시간 복잡도는 다음과 같다.

 

  • 크루스칼 : O(E*log_2(E))
  • 프림 : O(E*log_2(V))

두 경우 모두 제한시간 2초 내에 충분하다.

공간 복잡도

가중치 C는 음수일 수도 있으며, 절댓값이 1,000,000을 넘지 않는다.

 

최소 스패닝 트리의 가중치가 -2,147,483,648보다 크거나 같고, 2,147,483,647보다 작거나 같은 데이터만 입력으로 주어지며

이는 int형으로 충분하다.

최소 스패닝 트리 (Minimum Spanning Tree, MST)

최소 스패닝 트리의 정의는 그래프에서 그래프의 모든 정점을 연결하는 트리이다.

이 때 사이클이 존재하지 않도록 모든 정점을 간선으로 연결한다.

또한 모든 간선의 가중치는 최소값이 되어야 한다.

프림의 알고리즘

시간 복잡도 O(E*log_2(V))

우선 순위 큐를 이용해 간선의 가중치가 낮은 간선부터 순회한다.

 

이때 해당 간선의 목적지를 이미 방문한 경우 이를 건너 뛴다.

이전에 목적지를 이미 방문했다는 것은 현재 간선보다 가중치가 낮다는 것을 의미하기 때문이다.

즉 가중치가 낮은 간선들부터 순회해 MST를 생성한다.

 

따라서 처음에는 임의의 점에 속해있는 간선들을 전부 우선순위 큐에 넣고 탐색해야 한다.

struct Edge {
  int vertex, cost;
};

struct Status {
  Edge edge;

  bool operator<(const Status &b) const {
    return edge.cost > b.edge.cost;
  }
};
priority_queue<Status> pq;
vector<bool> visited(V + 1, false);

// 한 정점에서 시작하는 모든 간선을 우선순위 큐에 집어넣음
visited[1] = true;
for (Edge cur : graph[1]) {
  pq.push({cur});
}

long long answer = 0;

while (!pq.empty()) {
  Status cur = pq.top();
  pq.pop();
  Edge edge = cur.edge;

  if (visited[edge.vertex]) continue;
  visited[edge.vertex] = true;

  answer += edge.cost;

  for (Edge next : graph[edge.vertex]) {
    pq.push({next});
  }
}

크루스칼 알고리즘

시간 복잡도 O(E*log_2(E))

무향 연결 가중 그래프에서 간선의 가중치의 합이 최소인 트리를 구하는 것이다.

MST에는 사이클이 없음에 유의한다.

  1. 모든 간선의 연결 상태를, 가중치에 따라 오름차순으로 정렬한다.
  2. 모든 간선들을 순회하며 탐색한다.
  3. MST에 현재 간선을 포함했을 때 사이클이 생기는지 확인한다.
  4. 사이클이 생기는 경우 포함하지 않는다.
  5. 사이클이 생기지 않는 경우 MST에 해당 간선을 추가한다.

이 경우 자동적으로 cost가 낮은 간선들로만 이루어진 MST를 생성할 수 있다.

 

여기서 사이클이 생기는지의 여부는 union find (disjoint set)을 이용해 판단할 수 있다.

트리의 정점이 낮은 쪽을 부모로 한다고 했을 때, 두 정점에서 찾은 부모가 같은 경우 사이클이 있다고 판단한다.

struct UnionFind {
  vector<int> cycleTable;

  UnionFind(int size) {
    cycleTable.resize(size + 1);

    for (int i = 1; i <= size; i++) {
      cycleTable[i] = i;
    }
  }

  int findParent(int index) {
    if (cycleTable[index] == index) {
      return index;
    } else {
      int p = findParent(cycleTable[index]);
      cycleTable[index] = p;

      return cycleTable[index];
    }
  }

  void merge(int a, int b) {
    int aRoot = findParent(a);
    int bRoot = findParent(b);

    if (a < b) swap(aRoot, bRoot);
    cycleTable[aRoot] = bRoot;
  }
};

간선은 자동으로 오름차순으로 정렬되어야 하며, 다음과 같은 형태이다.

struct Edge {
  int from, to, weight;

  bool const operator<(const Edge &b) const {
    return weight < b.weight;
  }
};

sort(edges.begin(), edges.end());

for (Edge l : edges) {
  if (unionfind.findParent(l.from) == unionfind.findParent(l.to)) continue;

  unionfind.merge(l.from, l.to);
  sum += l.weight;
}

정리

프림의 알고리즘 풀이

 

changicho/algorithm-training

The repository of problem solving (especially algorithm problems of computer science) - changicho/algorithm-training

github.com

크루스칼 알고리즘 풀이

 

changicho/algorithm-training

The repository of problem solving (especially algorithm problems of computer science) - changicho/algorithm-training

github.com

내 코드 (ms) 빠른 코드 (ms)
68 12

고생한 점

V와 E를 입력받고, 간선들을 입력 받을 때 V의 크기만큼 입력받도록 잘못 로직을 구성했었음

'공부 > 알고리즘 문제풀이' 카테고리의 다른 글

백준.12849.본대 산책  (0) 2021.01.26
백준.12852.1로 만들기 2  (0) 2021.01.25
큰 수 연산 (Big Integer)  (0) 2021.01.04
삼성 7699. 수지의 수지 맞는 여행  (0) 2019.12.31
삼성 9088. 다이아몬드  (0) 2019.12.27

+ Recent posts