분류 전체보기110 Union-Find의 최적화 과정 Union-Find는 말 그대로 임의의 그룹과 그룹을 묶고(Union) 두 노드가 같은 그룹인지 확인(Find) 하는 알고리즘이다. 하나씩 따라 해 보면서 어떻게 구현하고, 최적화시키는지 확인해보자. Union Find는 그룹을 하나의 트리로 표현한다. 이렇게 하면 두 노드가 같은 그룹인지 확인할 때 단순히 root 노드가 같은지만 확인하면 되기 때문에 간단해진다. void unionGroup(int x, int y) { int rootX = findRoot(x); int rootY = findRoot(y); parent[rootX] = rootY; } bool isSameGroup(int x, int y) { return findRoot(x) == findRoot(y); } 첫 번째 함수는 x와 y를 .. 2019. 10. 16. ES8의 async와 await 이전 글(Promise)에서 비동기 작업을 구현하는 방법으로 콜백과 Promise에 대해서 알아봤다. javascript에서 피할 수 없는 비동기 작업을 구현하는데 초기에 콜백을 이용했고, 이를 개선하기 위해 ES6에 Promise가 등장했다. Promise가 chaining을 통해 콜백의 많은 부족한 부분을 해결했지만, 역시 동기적인 코드가 갖는 직관적인 인상은 줄 수 없었다. 이처럼 아직 비동기 작업의 구현에는 갈증을 해소하지 못했고, 이를 채워줄 새로운 스펙이 ES8(ECMA2017)의 async와 await이다. async - await 요청 시점과 응답 시점이 달라서 구현하기 힘들었던 비동기 작업을 콜백, Promise로 제어했지만 역시 이상적으로는 아래처럼 동기적인 작업처럼 코딩하고 싶다. f.. 2019. 10. 16. ES6의 Promise Javascript에서는 실행 결과를 받을 때까지 기다리지 않고 다음 작업을 이어서 하는 비동기 요청을 자주 쓴다. 요청과 완료 시점이 다르기 때문에 코딩은 더 어렵게 느껴지지만 javascript가 실행되는 single-thread 환경을 생각해보면 자주 사용할 수밖에 없다. 예를 들어 browser에서 동기적으로 작업을 한다면 그 작업이 진행되는 동안에 사용자의 액션은 freezing 될 것이고, 이런 browser는 아무도 사용하지 않을 것이다. 비동기를 자주 사용하는 환경인 만큼 이를 구현하는 방법도 시간에 따라 진화하고 있다. 최신 표준에서는 어떻게 구현을 하는지 알아보기 앞서서 진화해온 과정을 익히기 위해 옛날 방법부터 시작해서 ES6에 등장하는 Promise까지 알아보자. Callback j.. 2019. 10. 16. ES6의 Iterator와 Generator 이번 글에는 Iterator와 Generator의 스펙과, 왜 등장했는지, 어떻게 사용하는지에 대해서 정리해본다. Iterator Iterator는 ES6에 추가되었다. 다시 해석하면 그 전에도 어찌어찌 구현하던 것을 Iterator로 바꿀 수 있단 뜻이다. Iterator는 정의된 인터페이스를 구현하면 그 구현체를 순회할 수 있는 객체이다. 순회라고 하면 Array가 떠오르고, Array를 순회하려면 forEach나 for-in으로도 가능하다. 하지만 forEach 는 순회 중간에 중단할 수 없는 단점이 있고, for-in은 이름부터 원하는 순회를 하는 듯 하지만 역시 아래와 같은 여러 단점이 있다. for (const i in arr) 에서 i의 type이 string으로 뭔가 이상하다. 왜 stri.. 2019. 10. 16. npm에서 package.json의 module version관리 최근 연습 삼아 npm모듈을 만들어서 배포하고 있었는데 그 과정에서 API가 달라지는 경우가 있었다. 혼자 사용하는 거라면 늘 그랬듯이 후딱 고쳐서 사용했겠지만, npm에 배포를 하는 모듈이다 보니 신경 써야 할 것이 있었다. 내 모듈의 API가 바뀌었는데 정작 사용하는 곳에서 수정 없이 사용한다면 오류가 날 것이기 때문이다. 이런 API가 변경하는 경우를 대비해서 어떻게 모듈의 버전을 잡아야 하는지, npm에서 참조하는 모듈들은 어떻게 가져다 쓰는 건지 정리해봤다. 버전 변경을 하기 전에 먼저 사용하고 있는 버전의 규칙과, package.json에서 버전을 해석하는 방법에 대해서 알아보자. 버전 규칙 npm에서는 {MAJOR}.{MINOR}.{PATCH}를 따르는 Semantic Versioning을 .. 2019. 10. 15. 가산기(Carry-lookahead Adder) 구조 가산기 CPU의 연산처리과정을 익혀보던 중 그 흔한 덧셈을 과연 어떻게 최적화를 시켰을까 궁금해서 찾아보게 되었다. 가산기는 간단히 말하면 두 수의 덧셈을 연산하는 논리회로이다. 반가산기(half adder), 전가산기(full adder), RCA(ripple carry adder)는 익숙하지 않은 사람이 회로만 봐도 이해가 가능할 정도로 상당히 간결하다. 반가산기 전가산기 RCA 출처 : wikipedia 간단히 정리하면 반가산기는 입력으로 두 개의 bit가 주어질 때 S(sum)과 C(carry) bit를 구한다. 전가산기는 반가산기에 carry bit까지 입력으로 들어올 때를 구현했고, RCA는 이런 전가산기를 여러 bit에서 연산 가능하도록 조합한 형태이다. Ripple carry adder로 .. 2019. 10. 15. 이전 1 ··· 15 16 17 18 19 다음
