merge sort

카테고리 Algorithm

merge sort

mergeSort

정렬되지 않는 배열을 각각 하나의 원소만 포함하는 n개의 부분 배열로 분할한다. n개의 부분 배열이 1개가 될 때까지 반복해서 병합할 때 정렬한다. 최종적으로 남은 부분 배열이 정렬된 배열이 된다.

두가지 역할을 하는 함수로 나누어 설명할 수 있다.

  1. mergeSort(arr): 배열을 절반으로 나누는 함수
  2. merge(left, right): 반으로 나뉜 두 배열을 정렬하여 새로운 배열로 병합하는 함수

merge 함수 구현

left[0]과 right[0]를 비교하여 더 작은 수를 새로운 배열에 순서대로 담는다.

만약 left[0]이 right[0]보다 작다면 새로운 배열에 left[0]을 담고 이후에 left[1]과 right[0]을 비교한다.

이렇게 비교하면서 새로운 배열을 생성하기를 left, right 배열의 요소가 하나도 남지 않을 때 까지 반복한다.

이게 가능하기 위해서는 left와 right는 정렬된 상태의 배열이여야만 합니다. left, right를 정렬된 배열로 만들어 주기 위해서 mergeSort 함수를 이용합니다.

mergeSort 함수 구현

mergeSort 함수는 인수로 주어진 배열을 요소가 1개일 때까지 절반으로 나누고 정렬하며 merge 해주는 함수이다.

즉, 요소가 1개인 서로 다른 두 배열을 정렬하면서 하나의 배열로 만들어간다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
const arr = [33,2,51,1,10,3];

// 1단계 - 나누기
[33,2,51], [1,10,3]

// 2단계 - 나누기
[33,2],[51],[1,10],[3]

// 3단계 - 나누기
[33],[2],[51],[1],[10],[3]

// 4단계 - 병합
[2,33], [1,51], [3,10]

// 5단계 - 병합
[1,2,33,51], [3, 10]

// 6단계 - 최종 병합
[1,2,3,10,33,51]

코드 구현

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
const merge = (left, right) => {
  const sorted = [];
  
  // left, right 비교하여 정렬된 배열에 담는다.
  while (left.length && right.length) {
    if (left[0] <= right[0]) {
      sorted.push(left.shift());
    } else {
      sorted.push(right.shift());
    }
  }

  // left 또는 right 배열 중 하나는 아직 남아있으므로 남은 배열은 정렬되어 있으므로 복사하여 뒤에 붙혀준다.
  return [...sorted, ...left, ...right];
}

const mergeSort = arr => {
  if (arr.length === 1) return arr;
  const mid = Math.ceil(arr.length / 2);
  const left = arr.slice(0, mid);
  const right = arr.slice(mid);

  return merge(mergeSort(left), mergeSort(right));
}

const arr = [33,2,51,1,10,3];
const sorted = mergeSort(arr);
console.log(arr); // [33,2,51,1,10,3]
console.log(sorted); // [1,2,3,10,33,51]

정리

  • mergeSort는 O(n log n) 시간 복잡도를 가진다. 왜냐하면 절반씩 나눠서 비교하기 때문이다.
  • 안정 정렬에 속한다.

참고자료

댓글 공유

🏰 useCallback과 useMemo

카테고리 React, Hooks

📌 useCallback과 useMemo 사용 이유

함수 컴포넌트는 렌더링 될 때 마다 몸체가 다시 실행되므로 컨텍스트를 기억하기 위해 Hook을 사용한다. 그리고 상위 컴포넌트는 기억된 상태 또는 업데이트 함수를 하위 컴포넌트에게 전달한다.

이 때 상위 컴포넌트가 다시 실행되면 이벤트 핸들러 함수들도 새로 그려지므로 동일참조를 벗어난다.

🐸 useCallback

useCallback()은 하위 컴포넌트에 전달되는 함수를 기억해두고 이를 이용하여 컴포넌트 업데이트 시 리렌더링이 발생할 때, 기억된 함수를 사용해 불필요한 리렌더링을 줄여 성능을 높이기 위해 사용한다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
export function Counter({ count: initialCount, step }) {
	const [count, setCount] = useState(initialCount);

	// 1
	const handleIncrement = useCallback(() => {
		setCount((count) => count + step);
		}, [step]);

	// 2
	const handleDecrement = useCallback(() => {
		setCount(count - step);
		}, [count, step]);

	return (
		<div>
			<Counter.Button onClick={handleDecrement}>-</Counter.Button>
			<Counter.Display>{count}</Counter.Display>
			<Counter.Button onClick={handleIncrement}>+</Counter.Button>
        </div>
    )
  • 기억해야할 데이터 타입이 함수인 경우 사용한다.
  • useEffect()처럼 종속성 배열을 통해 조건에 따라 기억 여부를 재설정할 수 있다.
  • 1번처럼 콜백함수로 전달해주는 경우는 reduce처럼 함수를 기억하고 있는다. 기억되어있는 정보를 가지고 값을 변경하는 것이다.
  • 2번처럼 값을 전달해주면 newState로 받아들여져서 종속성 배열이 바뀌면 렌더링이 발생하게된다. 기억하지 않고 새로운 값을 전달해주고 그 값으로 렌더링해준다.

🐍 useMemo

1
useCallback(fn, deps) === useMemo(() => fn, deps);

useMemo()는 JavaScript 데이터 타입을 기억해야 할 때 사용합니다. 만약 기억해야할 타입이 함수라면 useCallback을 사용한다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
export function Counter({ count: initialCount, step }) {
  const [count, setCount] = useState(initialCount);

  // useMemo(() => fn, deps)
  const handleIncrement = useMemo(
    () => () => setCount((prevCount) => prevCount + step),
    [step]
  );

  // useCallback(fn, deps)
  const handleDecrement = useCallback(() => {
    setCount((prevCount) => prevCount - step);
  }, [step]);

  // memoized Components
  const DecButton = useMemo(
    () => <Counter.Button onClick={handleDecrement}>-</Counter.Button>,
    [handleDecrement]
  );

  const IncButton = useMemo(
    () => <Counter.Button onClick={handleIncrement}>+</Counter.Button>,
    [handleIncrement]
  );

  return (
    <div>
      {DecButton}
      <Counter.Display>{count}</Counter.Display>
      {IncButton}
    </div>
  );
}
  • useMemo()는 해당 컴포넌트를 기억한다.
  • 종속성 배열 [count, onDecrement, onIncrement, restProps]이 변경되면 useMemo가 반환하는 값을 기억하고 실행한다.
  • setCount()를 기억하고 있어 동일참조를 하므로 count 값을 기억하고 있다.

🏓 소감

값을 기억하는 목적으로 좋지만… 굳이 이것을 사용하려고 복잡하게 또 많은 시간을 할애할 필요가 있을까 ?

댓글 공유

⛱ useRef

카테고리 React, Hooks

🐶 useRef()

리액트에서 ref는 주로 DOM 노드 참조 목적으로 사용된다. 컴포넌트 렌더링에 영향을 주지 않는 값 참조 목적으로 사용된다.

useRef()는 함수 컴포넌트 내부에서 특정 값을 지속적으로 참조할 때 사용한다. useState()와 달리 useRef()는 현재 값이 변경되어도 컴포넌트가 다시 렌더링되지 않아 애플리케이션 성능을 최적화 할 수 있다.

1
2
3
4
5
// useRef() 훅을 사용해 카운트 참조 생성
const countRef = useRef(0);

// 카운트 참조의 현재 값이 변경되어도 컴포넌트는 다시 렌더링 되지 않음
countRef.current = countRef.current + 1;

클래스는 자신의 인스턴스 멤버를 사용해 렌더링 상관없이 특정 값을 기억할 수 있는데 반해, 함수는 다시 렌더링 되면 매번 함수 몸체가 초기화 되므로 특정 값을 기억할 때 useRef()를 사용하면 유용하다.

🐥 useRef() 사용목적

1. DOM 요소 접근 및 조작

리액트 render() 단계에서는 DOM이 그려지기 전 단계이므로 DOM에 직접 접근할 수 없다.

하지만 useRef()를 사용하여 컴포넌트가 mount된 시점 이후 DOM 요소에 접근하여 조작할 수 있도록 도와준다.

1
2
3
4
5
6
7
8
9
10
11
12
13
function TextInputWithFocusButton() {
  const inputEl = useRef(null);
  const onButtonClick = () => {
    // `current` points to the mounted text input element
    inputEl.current.focus();
  };
  return (
    <>
      <input ref={inputEl} type="text" />
      <button onClick={onButtonClick}>Focus the input</button>
    </>
  );
}
  • 아직 DOM이 그려지기 전이라 DOM 요소에 접근하여 focus()를 활성화 시킬 수 없지만, useRef()를 사용하여 클래스 컴포넌트 생명주기를 고려하여 DOM 요소에 접근할 수 있도록 도와준다.

2. 함수 컴포넌트 내부에서 특정 값을 기억

함수 컴포넌트 내부에서 특정 값을 기억하면서 값을 변경해도 컴포넌트 렌더링에 영향을 주지 않아야한다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
import { useEffect, useRef, useState } from "react";
import randomcolor from "randomcolor";

function DoNotReRender() {
  const colorRef = useRef(0);
  const [stateValue, setStateValue] = useState(0);
  const [stateHex, setStateHex] = useState(randomcolor());
  const [refHex, setRefHex] = useState(randomcolor());

  useEffect(() => {
    setStateHex(randomcolor());
  }, [stateValue]);

  useEffect(() => {
    setRefHex(randomcolor());
  }, [colorRef]);

  return (
    <Grid lang="en">
      <GridItem
        css={`
          background: ${stateHex};
        `}
      >
        <h2>State</h2>
        <ChangeColorButton
          aria-label="state 컬러 변경"
          onClick={() => setStateValue(stateValue + 1)}
        />
        <p>컬러 변경 버튼을 누르면 컴포넌트가 다시 렌더링 됩니다.</p>
      </GridItem>
      <GridItem
        css={`
          background: ${refHex};
        `}
        onClick={() => {
          colorRef.current += 10;
          console.log(`colorRef.current = ${colorRef.current}`);
        }}
      >
        <h2>Ref</h2>
        <ChangeColorButton aria-label="ref 컬러 변경" />
        <p>컬러 변경 버튼을 누르면 컴포넌트가 다시 렌더링 될까요?</p>
      </GridItem>
    </Grid>
  );
}
  • useState()의 setStateValue()메서드를 사용하여 값을 변경한 경우 재렌더링이 발생하지만, useRef()의 current 값을 갱신하면 재렌더링이 발생하지 않는다.

댓글 공유

🚧 Literal type과 as const

카테고리 TypeScript

📌 Literal Type

타입 지정시 string, number 같은 원시타입만 할당할 수 있는 것이 아니다.

개발자가 지정한 글자나 숫자 들을 타입으로 지정할 수 있다.

1
2
let john: "Texas";
let kim: 33;
  • 이제 john에는 ‘Texas’라는 글자만 할당될 수 있고 kim에는 33이라는 숫자만 할당될 수 있다.
계속 읽기

type alias(타입별칭)와 타입 합치기

카테고리 TypeScript

📌 type alias(타입별칭)

1
type Animal = string | number;
  • type 타입변수명 = 타입종류
  • 이런 식으로 타입 별칭으로 변수처럼 담아서 재사용할 수 있다.
  • 관습적으로 대문자 사용

🏓 function type 지정하기

1
2
3
4
5
6
7
8
9
type NumOut = (x: number, y: number) => number;

let ABC: NumOut = function (x, y) {
  return x + y;
};
function removeDash(x: string): number {
  let result = x.replace(/-/g, "");
  return parseFloat(result);
}
계속 읽기

🐒 useEffect

카테고리 React, Hooks

📌 useEffect

1
useEffect(effectCallback);

함수 컴포넌트에서 발생 가능한 side-effect(부수효과)를 관리하기 위해 사용한다.

  • 비동기 통신 요청 및 응답
  • DOM 조작
  • 구독/취소 등

리액트가 할 수 없는 작업을 할 때, useEffect()를 사용한다.

🌈 React Hook 실행 흐름

Hook 실행 흐름

리액트 Hook의 실행흐름은 위 사진과 같다.

함수 컴포넌트에서 클래스 컴포넌트의 생명주기를 구현하기 위해 useEffect()가 componentDidMount(), componentDidUpdate(), componentWillUnmount() 메서드가 발생되는 주기를 대체할 수 있어야한다.

useEffect()가 이들을 100% 대체할 순 없지만 문제없을 정도로 흉내내어 사용하고 있다.

🐥 이펙트 조건 처리

1. componentDidMount() 대체 방법

1
2
3
useEffect(() => {
  // componentDidMount
}, []);
  • useEffect 2번째 인자로 빈 배열을 주게되면 컴포넌트가 처음 mount 되는 때에 한번만 호출된다.

2. componentDidUpdate() 대체 방법

1
2
3
4
5
6
7
useEffect(
	() => {
		// componentDidMount
		// componentDidUpdate
	}.
	[...dependencies]
);
  • useEffect 2번째 인자로 빈 배열 대신 관리할 상태가 추가되면 해당 상태가 변경될 때에만 이펙트 함수가 실행된다. 즉, mount될 때는 1번 실행되고, update 될 때 마다 실행된다.

3. componentWillUnmount() 대체 방법

이벤트 구독/취소처럼 컴포넌트가 제거될 때 실행되어야 하는 함수의 경우 다음과 같이 사용한다.

1
2
3
4
5
6
7
8
9
function Tester() {
  useEffect(() => {
    let clearId = setInterval(() => console.count(), 500);
    // 정리 함수(cleanup)
    return () => {
      clearInterval(clearId);
    };
  }, []);
}
  • cleanUp 함수는 메모리 누수 방지를 위해 UI에서 컴포넌트를 제거하기 직전에 수행된다.
  • Effect 함수가 실행될 때마다 cleanUp 함수가 먼저 실행되어 정리한다.

이는 componentWillUnmount()처럼 동작하는 것 같지만, 리액트 팀은 클래스 컴포넌트 생명주기대로 로직을 구현했을 때, 대규모 프로젝트에서 버그를 많이 발견하였다.

그리하여 리액트 팀에서는 구독취소 후 다시 구독하는 과정을 통해 이를 구현하였다.

1
2
3
4
5
6
7
8
9
10
useEffect(() => {
  function handleStatusChange(status) {
    setIsOnline(status.isOnline);
  }

  ChatAPI.subscribeToFriendStatus(props.friend.id, handleStatusChange);
  return () => {
    ChatAPI.unsubscribeFromFriendStatus(props.friend.id, handleStatusChange);
  };
}, [props.friend.id]); // props.friend.id가 바뀔 때만 재구독합니다.

댓글 공유

💭 useState

카테고리 React, Hooks

📌 useState

1
const [stateValue, stateUpdater] = useState(initState);

함수 컴포넌트에서 상태를 관리할 때 사용하는 API이다.

  • stateUpdater는 보통 setStateValue 이런식으로 set을 붙혀서 사용한다.

🐸 지연된 초기화

initState값은 초기 렌더링 시에만 사용되는 값으로, 이후 렌더링 시에는 무시된다. 만약 초깃값을 계산하는데 많은 시간이 필요한 경우 콜백함수를 통해 지연된 초기화 처리가 가능하다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
const [stateValue, stateUpdater] = useState(() => {
  // 계산에 적지 않은 시간이 소요될 경우
  // 약 790.62890625 ms
  const initialState = fibonacci(39);

  // 계산 이후: 지연된 초기화의 처리 값을 반환
  return initialState;
});

// 또는 localStorage에서 값을 읽어오는 경우
const [stateValue, setUpdater] = useState(() => {
  const persnalization = localStorage.getItem("persnalization");
  return JSON.parse(persnalization);
});

⛳️ 객체 타입 상태 관리

updateState 함수는 setState 함수처럼 객체 상태를 관리하기 합성된 객체를 반환해야 한다.

1
2
3
4
5
6
7
8
9
const [state, updateState] = useState({
  key1: false,
  key2: true,
});

updateState({
  ...state,
  key2: true,
});
  • updateState 함수는 상태 병합이 아닌 대체를 하므로 변경되지 않는 객체 값을 유지하기 위해서 위와 같이 해야한다.

댓글 공유

✈️ 리액트 Hooks

카테고리 React, Hooks

📌 Hooks

리액트 Hook은 클래스로 컴포넌트를 만들 때 발생하는 문제점을 해결하기 위해 등장하였다.

  • 리액트 Hook을 사용하면 함수 컴포넌트 중심으로 개발이 가능하다.
  • 함수 컴포넌트에서도 상태, 로직을 추출하여 다른 컴포넌트에서 재사용 할 수 있다.
계속 읽기

🐥 타마스 러버덕 1일차

카테고리 TypeScript

📌 TypeScript와 JavaScript 관계

모든 JavaScript는 TypeScript이지만, 모든 TypeScript가 JavaScript는 아니다.

1
2
3
4
5
6
7
8
9
10
interface State {
  name: string;
  capital: string;
}
const states: State[] = [
  { name: "yiju", capital: "경기도" },
  { name: "kim", capitol: "서울" },
]; // Error
// Type '{ name: string; capitol: string; }' is not assignable to type 'State'.
//   Object literal may only specify known properties, but 'capitol' does not exist in type 'State'. Did you mean to write 'capital'?

위 예시를 설명하면, 앞서 말한 모든 타입스크립트가 자바스크립트다 라고 하는 말은 틀렸다.

계속 읽기

loco9939

author.bio


author.job