1. 문제의 발단

• 요즘 보고 있는 알고리즘 문제들에 '부분집합'을 구하는 문제들이 많다. 매번 찾아보고 생각해서 쓰는 것보다 아예 외워버리듯이 적어버리면 편하지 않을까?라는 생각과 일단은 어떻게 모든 부분집합을 구할 수 있을까?라는 관점에서 포스팅을 하려고 한다.

2. 부분집합?

• 파란색 원은 밖의 원에 안에 있다. 이것이 바로 완전한 부분집합이 되는 것이다.
• 그러므로, 배열에서 '부분집합'을 말하면, 아래의 예시에서, arr안에 arrPartOne은 부분집합으로 모두 들어 있지만, arrPartTwo의 경우, 5가 없어서 부분집합이라고 할 수 없다.

let arr = [0, 1, 2, 3, 4]
let arrPartOne = [1, 0]
let arrPartTwo = [4, 5]

3. 그래서 어떻게 구할까?

• 재귀 함수를 이용한다.

let arr = [1, 2, 3]

let result = []

function everyComb(string, begin) {
	result.push(string);
	for(let i = begin; i < arr.length; i++) { // 반복문으로 시작점부터 arr의 요소 하나하나를 선택하고
		everyComb(string + arr[i], i + 1); // 재귀함수의 인자로 하나씩 넣어서 시작점을 1씩늘린다.
	}
}
everyComb('', 0);

console.log(result) // '', '1', '12', '123', '13', '2', '23', '3'

1. useEffect?

• 첫 번째 인자로 받은 함수가 두 번째 인자로 받은 Array안의 값이 바뀔 때마다 실행된다.
• 두 번째 인자에 빈 배열을 넣으면?
  
  • 처음 컴포넌트 생성 시에만 effect가 실행된다. 한번 외부의 API를 받아 오려고 할 때 사용할 수 있다.

import { useEffect, useState } from "react";

export default function App() {
	const [count, setCount] = useState(); // state로 count를 준다.

	const handleCountClick = () => { // 카운트를 1씩 버튼이 눌릴때 올린다.
		setCount(count + 1);
	};

	useEffect(() => {
		console.log("카운트가 1 올랐습니다.") // count값이 바뀔때 마다 console에 메시지가 찍힌다.
    }, [count]);
    
	return (
		<div className="App">
			<button onClick={handleCountClick}>카운터 : {count}</button>
    		</div>
	)
}

2. AJAX 요청을 통한 서버에서 데이터를 가져와 사용하기.

• 위에서 한 것처럼, fetch를 통해서 서버에서 데이터를 가져와 사용할 수 있다.
• AJAX는 JSON 형식으로 돌아온다는 것을 잊지 말자.

const [data, setData] = useState();

export default function App() {
  useEffect(() => {
      fetch('http://어떤 데이터를 주는 서버의 주소')
      .then(response => response.json())
      .then(data => {
          data(newData);
      }, [data])
  }
}

return (
  <div className='App'>
      <div>서버에서 받아온 내용 : {data}</div>
  </div>
)

3. AJAX 요청의 속도

• 분명 외부의 API에서 데이터를 받아 올 때, 전송속도가 느릴 수 도 있다. 그래서 로딩 화면과 같은 것을 구연해서 유저들이 조금 더 나은 경험을 할 수 있도록 해야 한다.

const [data, setData] = useState();
const [isLoading, setIsLoading] = useState(true);

  return {isLoading ? <LoadingIndicator /> : <div>로딩 완료 화면</div>}
  // 만약 로딩이 되지않은 상태인 false라면 LoadingIndicator를 보여주고 다 되면 완료 화면을 보여줌.
  
  useEffect(() => {
    setIsLoading(true);
    fetch('http://어떤 데이터를 주는 서버의 주소')
      .then(response => response.json())
      .then(data => {
          data(newData);
      }, [data])
  }

이것만 보고도 이해한다면 당신은 천재.
아니면 기본적인 사용의 형태를 템플릿처럼 외워도 일단 사용하는데 문제는 없다.
리액트는 1000번 보는 것보다 1번 해보는 게 낫다.
이렇게 내용도 없는 데이터를 주고받는 것부터 해보는 것이 이해에 도움이 훨씬 잘 될 것이다.
그래도 막막하다면, 다시 리액트 기초로 돌아가 큰 구조를 보는 것부터 연습하자!

1. 사건의 발단

        자료구조를 배운 뒤로 많은 사람들이 알고리즘을 늪에서 허우적거리고 있었다. 물론, 나도 같이 물 먹고 있었다. 그래서 이대로 뒤 쳐질 수 없기 때문에 모든 것을 완벽히 하는 '안내서'를 만들어 내기에 이르렀다.

2. Tree의 구조와 특징

• 트리구조의 특이점은 우리가 이때까지 보아왔던 Array, Stack, Queue와 다르게  '부모와 자식이 있는 구조'가 트리구조라고 할 수 있다. 물론 형제도 있다.
• 이때 각각의 요소들은 'Node'라고 부른다.
• 가장 마지막에 있는 node 즉, 자식이 없는 node를 'Leaf'라고 부른다.
• 각 층에 따라 '레벨'로 구분할 수 있다.

3. 이진트리 (Binary Tree)

• 자식을 2개만 가지는 트리.
• 물론, 3개 이상도 붙을 수 있지만 우리가 보는 알고리즘은 이진트리를 이용해서 해결할 수 있다.

4. 이진 탐색 트리 (Binary Search Tree)

• 부모 노드의 기준으로 자식이 작은것은 왼쪽, 큰 것은 오른쪽에 위치하게 되는 트리의 한 구조이다.
• 위의 그림에서 보듯이, 크다 작다만 비교해서 원하는 타깃을 찾을 수 있도록 할 수 있다.
• 이 경우, 시간복잡도는 O(log N)이 된다.
• 배열로 이진 탐색트리를 만들 수 있다. 배열을 하나 만들어서 중간 값을 찾아서, 루트로 지정하고 그것을 기준으로 작은 수를 왼쪽의 자식으로 쓰고 그 왼쪽 자식을 다시 루트 즉, 중간값이라고 크기를 다시 비교해서 작으면 왼쪽, 크면 오른쪽에 넣는 것을 반복하면 배열들을 이진 탐색 트리로 만들 수 있다.
• 즉, 중간값을 찾고, 절반으로 나눈 것에 다시 중간값을 찾고, 또 절반 나눈 것에 다시 중간값을 찾고... 이거 어디서 많이 보던 행동이다. 시작하는 인덱스와 끝나는 인덱스를 받아서 그 중간값을 찾아 반환하는 '재귀 함수'를 만들면 간단하게 해결할 수 있다.

5. 이진트리의 순회방법

1. Inorder
   • Left -> Root -> Right의 순서로 탐색함.
   • 자식이 없으면 다시 위로 올라가 자기 자신(Root)을 출력함.
   • 위의 예시에서 보면, 1, 5, 7, 8, 10, 15. 20, 17, 25의 결과가 나온다.
2. Preorder
   • Root -> Left -> Right의 순서로 탐색함.
   • 일단 자기 자신(Root)을 출력하고, 왼쪽으로 먼저 가서 다시 자신을 출력, 자식이 없을 때까지 반복한 후, 자식이 없다면 다시 위로 올라간다. 하지만, 먼저 자기 자신을 출력했기 때문에 바로 오른쪽으로 가서 출력하게 된다.
   • 위의 예시에서 보면, 15, 10, 5, 1, 7, 8, 20, 17, 25의 결과가 나온다.
3. Postorder
   • Left -> Right -> Root의 순서로 탐색함.
   • 왼쪽으로 자식이 없을 때까지 간 후, 자식이 없는 노드를 출력, 그리고 바로 오른쪽으로 넘어가서 출력, 그 후 자기 자신으로 넘어가게 된다.
   • 위의 예시에서 보면, 1, 7, 8, 5, 10, 17, 25, 20, 15의 결과가 나온다.

• 위의 방법으로 트리들을 순회해서 답을 찾게 된다. 왼쪽부터 오른쪽으로 가는 것은 같지만 찾는 방법에 따라 답을 도출하는 시간이 차이가 난다.

6. Graph 검색

① DFS (Depth-First Search)

• 깊이 우선 탐색 방법이라고도 말한다.
• 앞에 적혀 있던 이진트리의 순회 방법 3가지가 DFS에 속한다.
• 하나의 자식을 방문하여, 그다음 자식, 그다음 자식으로 자식이 없는 경우까지 들어가서 방문한 후에, 그다음 가장 가까운 줄기를 방문하는 것을 반복하는 것이다.
• 즉, Stack을 이용하면 된다.
  1. 처음 Stack으로 사용할 Array를 만들고, Root(0)를 넣는다.
  2. 그리고 바로 Root(0)가 Stack에서 나오게 되고, 그에 자식(1)을 모두 Stack에 넣는다.
  3. 나왔던 Root(0)를 출력하고, Stack에 들어 있던 자식(1)은 Stack에서 나오게 되고, 그에 자식을 모두(2, 3) Stack에 넣는다.
  4. 들어있던 Stack의 가장 상위의 노드(1)를 출력하고, Stack의 가장 위에 있는 노드(3)를 꺼내고, 이미 들어간 노드(2)를 제외하고 남은 자식들(4, 5)을 스택에 넣고 꺼내진 노드(3)를 출력한다.
  5. Stack에서 다시 가장 위에 있는 노드(5)를 꺼내고, 꺼낸 노드의 자식들(6, 7)을 Stack에 넣고 꺼내진 노드(5)를 출력한다.
  6. Stack의 가장 위에 있는 노드(7)를 꺼내고, 자식 노드가 없으므로, 바로 출력한다.
  7. Stack에서 다시 가장 위에 있는 노드(6)를 꺼내고, 꺼낸 노드의 자식(8)을 Stack에 넣고 꺼내진 노드(6)를 출력한다.
  8. Stack에 남은 노드(8, 4 ,2)는 자식이 없으므로 순서대로 꺼내지고 출력된다.
  9. 결국 출력 결과는 0, 1, 3, 5, 7, 6, 8, 4, 2 순이다.
• 위의 내용을 재귀 함수로 구연할 수도 있다. (노드에 방문하면 방문한 노드를 출력하고, 자식들을 Queue에 순서대로 넣고, 그 자식을 재귀 호출한다. 이것을 반복한다.)
  1. 시작 노드(0)를 재귀 함수로 호출한다. 호출되었을 때 자신(0)을 출력한다.
  2. 자식 노드(1)를 재귀 함수로 호출한다. 호출되었을 때 자신(1)을 출력한다.
  3. 첫 번째 자식 노드(2)를 재귀 함수로 호출한다. 호출되었을 때 자신(2)을 출력한다.
  4. 연결관계를 입력할 때 왼쪽을 먼저 출력하게 지정하였다. 그래서 왼쪽의 노드(4)를 재귀 함수로 호출한다. 호출되었을 때 자신(4)을 출력한다.
  5. 그 전 단계에서 오른쪽 노드(3)에 해당하는 부분을 이미 만났으므로 아까의 오른쪽 노드(3)를 재귀 함수로 호출한다. 호출되었을 때 자신(3)을 출력한다.
  6. 마지막 남은 자식 노드(5)를 재귀 함수로 호출한다. 호출되었을 때 자신(5)을 출력한다.
  7. 연결관계를 입력할 때 왼쪽을 먼저 출력하게 지정하였기 때문에 왼쪽의 노드(6)를 재귀 함수로 호출한다. 호출되었을 때 자신(6)을 출력한다.
  8. 자식 노드(8)를 재귀 함수로 호출한다. 호출되었을 때 자신(8)을 출력한다.
  9. 자식이 더 이상 없으므로 앞 단계로 나와서 호출되지 않은 노드(7)를 재귀 함수로 호출한다. 호출되었을 때 자신(7)을 출력한다.
  10. 결국 출력 결과는 0, 1, 2, 4, 3, 5, 6, 8, 7 순이다.
• 일상생활에서 페이지 뒤로, 앞으로 가기 등을 생각한다.

② BFS (Breadth-First Search)

• 넓이 우선 탐색 방법이라고도 말한다.
• 하나의 자식을 방문하면, 일단 같은 레벨의 모든 형제들을 다 방문하고, 자식의 자식 노드를 방문하여 같은 레벨의 모든 형제들을 방문하는 것을 반복하는 것이다.
• 즉, Queue를 이용하면 된다.
  1. 처음 Queue로 사용할 Array를 만들고. Root(0)를 넣는다. Queue는 기준이 필요해서 처음 만들 때 넣어놓고 시작한다.
  2. 그리고 바로  Root(0)가 Queue에서 나오게 되고, 그에 자식(1)을 모두 Queue에 넣는다. 꺼냈던 노드(0)는 출력한다.
  3. Queue에서 순서대로 노드(1)를 하나 꺼내고, 자식 노드들(2, 3)을 모두 Queue에 추가한다. 꺼냈던 노드(1)는 출력한다.
  4. Queue에서 순서대로 노드(2)를 하나 꺼내고, 이미 들어가 있는 자식 노드들(2, 3)을 제외하고 자식 노드(4)를 Queue에 넣는다. 그리고 꺼냈던 노드(2)는 출력한다.
  5. Queue에서 순서대로 노드(3)를 하나 꺼내고, 이미 들어가 있는 자식 노드들(2, 4)을 제외하고 자식 노드(5)를 Queue에 넣는다. 그리고 꺼냈던 노드(3)는 출력한다.
  6. Queue에서 순서대로 노드(4)를 하나 꺼내고, 이미 모든 자식 노드들(2, 3)은 Queue에서 들어왔다 나갔기 때문에 꺼냈던 노드(4)는 바로 출력된다.
  7. Queue에서 순서대로 노드(5)를 하나 꺼내고, 자식 노드들(6, 7)을 모두 Queue에 추가한다. 꺼냈던 노드(5)는 출력한다.
  8. Queue에서 순서대로 노드(6)를 하나 꺼내고, 자식 노드(8)를 Queue에 추가한다. 꺼냈던 노드(6)는 출력한다.
  9. Queue에서 순서대로 노드(7)를 하나 꺼내고, 자식 노드들이 없기 때문에 꺼냈던 노드(7)는 바로 출력된다.
  10. Queue에서 순서대로 노드(8)를 하나 꺼내고, 자식 노드들이 없기 때문에 꺼냈던 노드(8)는 바로 출력된다.
  11. 결국 출력 결과는 0, 1, 2, 3, 4, 5, 6, 7, 8 순이다.
• 일상생활에서 프린터기의 작동 원리 등을 생각한다.

기본적인 방법은 이렇다. 하지만 코드로 표현하려고 하면 잘 안될 것이다. 하지만 의미를 이해하고 간단한 문제부터 접근한다면 각각의 순회 방법을 이용하는 방법이 보이기 시작한다. 그 이후 반복해서 문제를 해결하게 되면 익숙해 질 수 있다. 이후, 시간이 나면 위의 내용을 코드로 직접 구현해 포스팅 할 예정이다.

1. 문제의 발단.

• 시간 복잡도를 생각해서 거듭제곱(x^nxn)을 구할 예정이다.
• 아주 큰 수가 제곱수 안에 있을 경우 94,906,249를 나눠 나머지를 다시 제곱해 줘서 컴퓨터가 표현할 수 있는 수 안에서 결과를 구해야 한다.
• Math.pow()는 사용 금지한다.

2. 시도 1

function efficientPow(baseNum, exponent) {
  let result = 1;
  for(let i = 0; i < exponent; i++) {
    result = result * baseNum;
    if(result > 94906249) {
      result = result % 94906249;
    }
  }
  return result;
}

• 답은 맞았다.
• 하지만 효율적이지 못했다. 시간 복잡도를 통화하지 못했다.
• 반복문이 아닌 재귀 함수 등을 이용하는 것도 또 다른 방법이 될 수 있지만, 똑같은 방식으로 반복문을 재귀 함수로 고친다고 해도, 시간 복잡도를 줄이지 못할 것이라고 생각했다.
• 그래서 거듭제곱의 특징을 알아보고 시간 복잡도를 줄일 수  있지 않을까?라고 생각했다.

3. 지수법칙

• 위의 식을 이용하면 내가 곱해야 할 지수를 절반으로 줄일 수 있다고 생각했다. 즉 2의 5승 곱하기 2의 5승은 2의 10승과 같다면, 2의 5승까지만 알게 되면 더 이상 2의 6승 등을 알 필요가 없어진다.

4. 시도 2

function efficientPow(baseNum, exponent) {
  if(exponent === 0){
    return 1;
  }
  // 재귀의 탈출 조건이 된다.
  let halfExponent = efficientPow(baseNum, Math.floor(exponent/2));
  // 제곱의 지수의 절반인경우를 구한다.
  let result = (halfExponent * halfExponent) % 94906249;
  // 만약, 표현할 수 있는 최대 수를 넘기면 나눠서 나머지에 다시 절반인 제곱수를 곱한다.
  if(exponent % 2 === 0){
    return result;
  }else{
    return (result * baseNum) % 94906249;
  }
  // 이후, 지수가 짝수이면 그대로 리턴, 아니라면 다시 곱해서 최대수가 넘으면 사눠서 나머지를 리턴한다.
}

• 성공!
• 정말 절반만 계산해서 시간 복잡도를 크게 떨어뜨릴 수 있었다.

나는 중1 시절 수학을 놨다.
사실 저 지수법칙과도 초면이었다...
역시 또 수학공식을 모르니 생각이 넓게 미치지 못하는 것 같다. 코드를 쓰는 문법에 익숙해지면 알고리듬 공부를 할 때는 수학에 대해 공부하는 것도 나쁘지 않은 전략이 될 것 같다.