🔎DFS (Depth First Search)

깊이 우선 탐색으로, 스택을 사용해 구현한다.

구현 방법

1. graph를 배열의 형태로 완성한다.
   → 각 index에 해당 index번째 노드와 연결된 간선의 번호를 적는다.
   cf) 양방향인 경우, 양쪽에 적어야한다.
2. 탐색 시작 노드를 스택에 삽입하고 방문처리한다.
3. 스택의 최상단 노드에 방문하지 않은 인접 노드가 있으면 해당 노드를 스택에 넣고 방문 처리한다.
   → 방문하지 않은 인접 노드가 없으면 다시 스택에서 최상단 노드를 꺼낸다.
4. 2번이 불가능 할때까지 반복한다.

# 방문 정보를 리스트 자료형으로 표현
# 노드는 9개지만, index 0번 노드는 사용하지 않는다.
visited =[False] * 10

# 각 노드가 연결된  정보를 리스트 자료형으로 표현 (2차원 리스트)
graph = [
	[],                 # 빈 자리
  [3, 4, 5],          # 1번 노드와 연결된 노드들
  [2, 3, 8],          # 2번 노드와 연결된 노드들
  [1, 7],             # 3번 노드와 연결된 노드들
  [1, 4, 5],          # 4번 노드와 연결된 노드들
  [3, 5],             # 5번 노드와 연결된 노드들
  [3, 4],             # 6번 노드와 연결된 노드들
  [7],                # 7번 노드와 연결된 노드들
  [2, 6, 8],          # 8번 노드와 연결된 노드들
  [1, 7]              # 9번 노드와 연결된 노드들
]

def DFS(graph, visited, start):
  # 현재 노드를 방문 처리
  visited[start] = True
  print(start, end = ' ')

  for i in graph[start]:
    if not visited[i]:
      DFS(graph, visited, i) // 재귀함수!!

# 현재 노드와 연결된 다른 노드를 재귀적으로 방문
DFS(graph, visited, 1)

🔎BFS (Breadth First Search)

너비 우선 탐색으로, deque를 사용하여 구현

구현 방법

1. graph를 배열의 형태로 완성한다.cf) 양방향인 경우, 양쪽에 적어야한다.
   → 각 index에 해당 index번째 노드와 연결된 간선의 번호를 적는다.
2. 탐색 시작 노드를 큐에 삽입하고 방문 처리한다.
3. 큐에서 노드를 꺼내 해당 노드의 인접 노드 중에서 방문하지 않은 노드를 모두 큐에 삽입하고 방문 처리한다.
4. 2번이 불가능 할때까지 반복한다.

from collections import deque

# BFS
def BFS(graph, visited, start):
  queue = deque([start])

  # 첫 노드 방문 처리
  visited[start] = True

  # 큐가 빌 때까지 반복
  while queue:
    # 큐에서 하나의 원소를 뽑아 출력
    v = queue.popleft()
    print(v, end = ' ')

    # 해당 원소와 연결된, 아직 방문하지 않은 원소들을 큐에 삽입
    for i in graph[v]:
      if not visited[i]:
        queue.append(i)
        visited[i] = True

# 노드는 9개지만, index 0번 노드는 사용하지 않는다.
visited =[False] * 10

# 각 노드가 연결된  정보를 리스트 자료형으로 표현 (2차원 리스트)
graph = [
  [],                 # 빈 자리
  [],                 # 1번 노드와 연결된 노드들
  [2, 3, 8],          # 2번 노드와 연결된 노드들
  [1, 7],             # 3번 노드와 연결된 노드들
  [1, 4, 5],          # 4번 노드와 연결된 노드들
  [3, 5],             # 5번 노드와 연결된 노드들
  [3, 4],             # 6번 노드와 연결된 노드들
  [7],                # 7번 노드와 연결된 노드들
  [2, 6, 8],          # 8번 노드와 연결된 노드들
  [1, 7]              # 9번 노드와 연결된 노드들
]

BFS(graph, visited, 1)

✏️팁

• 둘다 O(NlogN)의 시간 복잡도를 지닌다.
• True / False를 적극 활용하기

visited =[False] * (N+1)

• ⭐노드가 1부터 시작하는 경우, graph와 visited도 1부터 시작하기 → 헷갈림 방지
• DFS의 재귀가 이미 visited를 모두 방문했음에도 실행하고 있을 때를 대비하여, 해 호출마다 check_end 함수를 넣을 수 있음.
• 일반적으로, BFS가 DFS보다 빠름.

✏️서론

Next.js 공부를 하던중, 여러가지 Rendering 기법이 존재해서 정리해 보았다.

공부를 하기 전에는 "Next.js는 Server Side Rendering 방식을 사용해" 라는 말을 주변에서 굉장히 많이 들어서 Next.js == SSR 이라는 사고방식이 머리에 박혀있었다.

알고보니, Next.js는 SSR만을 (Pre)-Rendering 방식으로 사용하고 있지 않았다.

나와 같은 프린이들은 이글을 읽고 잘못된 지식을 바로잡아야 한다.

⭐CSR > SSG > SSR 순으로 이해해보자.⭐

1. CSR (Client Side Rendering)

→ 하나의 Page에 컴포넌트만 바꿔서 출력하는 SPA기법을 사용하는 React의 대중적인 방식

→ 클라이언트가 Skeleton Html에 Data를 Fetch해서 표시하는 방식 (useEffect + fetch)

→ SEO에 관여할 필요가 없는 페이지 이거나, Pre-Render하지 않아도 되는 페이지인 경우에는 기존처럼 CSR를 사용하면 된다.

친절하게도 NextJS에서 Pre-Fetching 코드를 CustomHook으로 만들어서 제공해주었다. → useSWR Hook

공식문서 읽어보고 사용하기

https://swr.vercel.app/docs/getting-started

User가 페이지를 보고 싶은 Request를 날리면 다음과 같은 과정으로 처리된다.

1. User가 Page Request를 Backend에 날린다.
2. 브라우저는 뼈대 Html을 그린다.
3. Server는 Javascript 코드를 제공한다.
4. JavaScript 코드를 토대로 페이지를 그려나간다.

이때, 4번의 속도가 매우 빨라서, User는 마치 이미 만들어진 페이지를 가져오는 것처럼 보인다.

하지만, 실제로는 뼈대 Html만 받아오는 것이다

→ 이는, SEO (Search Engine Optimization)에 부정적인 영향을 미친다.

(아래 사진) Skeleton HTML만 렌더링된 모습

NextJS는 React와 다른 “Pre-Rendering”을 통해 페이지를 렌더링한다.

공식문서에는 다음과 같이 설명되어 있다.

By default, Next.js pre-renders every page.
This means that Next.js generates HTML for each page in advance, instead of having it all done by client-side JavaScript.
Pre-rendering can result in better performance and SEO.

Each generated HTML is associated with minimal JavaScript code necessary for that page.
When a page is loaded by the browser, its JavaScript code runs and makes the page fully interactive (this process is called hydration in React).

Pre-Render하는 대략적인 과정은 다음과 같다.

1. User의 Page Request
2. Server는 뼈대 Html + Javascript 코드를 바탕으로 완성된 페이지를 제공한다.
   → 이때, 사용한 Javascript 코드를 같이 넘겨준다 (Hydration)
   이는, 첫 렌더링을 제외하면 Client Side Rendering 또한 가능하게 하기 위함이다. (event handling)

⭐여기서부터 중요하다⭐

Next.Js는 Pre-Rendering을 하는 시점을 On Build Time vs On Each Request로 구분한다

Build Time에 Pre-Render하는 방법을 Static Site Generation

Each Request에 Pre-Render하는 방법을 Server Side Rendering이라 한다.

그럼 CSR, SSG, SSR이 각각 어떻게 실행되는지 알아보자

Static Side Generation (Recommended)

→ 페이지들은 빌드할 때 Pre-Render된다.

이후, Hydrate을 통해 Regular React App처럼 Interactive한 Aplication으로 사용가능하다.

공식문서

If a page uses Static Generation, the ✏️page HTML is generated at build time.That means in production, the page HTML is generated when you run ⭐`next build`.
This HTML will then be reused on each request. It can be cached by a CDN.
In Next.js, you can statically generate pages with or without data.

How to User SSG?: `getStaticProps` Function

// 형식 정확히 일치 필요!
export async function getStaticProps(context) { … }

→ Server에서만 실행되는 코드를 작성한다.
(i.e. Client에서 사용하는 코드는 사용 불가능하다.)

→ Not Be included in code bundle that server gives to client

→ return 형식이 정해져 있음

return {
	props: {
	    my_data: data
    },
    revalidate: time_in_sec,
    notFound : Boolean,
    redirect : {
    	destination: URL_String,
    }
}

https://nextjs.org/docs/pages/building-your-application/data-fetching/get-static-props

https://nextjs.org/docs/pages/api-reference/functions/get-static-props)

import path from "path";
import fs from "fs/promises";

export async function getStaticProps() {
    // NodeJS Code To get Access to Data Json File
    // Data Json File Location: "/data/dummy-backend.json"
    
	const filePath = path.join(process.cwd(), "data", "dummy-backend.json");
    const jsonData = await fs.readFile(filePath);
    const data = JSON.parse(jsonData);
    
    return {
        props: {
			products: data.products,
		},
	};
}

function HomePage(props) {
/*
의문점!
props를 상위 컴포넌트로부터 전달받는 경우에는 getStaticProps와 상위 컴포넌트 중에 어떤걸 사용하는 거지?
*/
	const { products } = props;
		return ({products.map((product) => (
			{product.title}
		))}
	);
}
export default HomePage;

그러면 실제로 build 했을때 어떻게 나타날까?

npm run build → Build NextJS Project

- Root Folder (Route : “/”) 가 SSG 되었다

데이터가 Pre-Rendering 되었다

→ 이때, props로 넘겨주는 Data는 hydrate에 이용되지 않는다

→ StaticProps는 페이지 검사를 하면 드러나기 때문에 중요한 정보는 표시하지 않아야 한다 (props로 사용하면 안된다는 뜻)

Props (underline : default)

- revalidate : x초 (default : false)

→ ISR을 만들기 위한 값  

- notFound : true | false

→ 404 Page를 리턴할할지 말지를 결정한다.  

- redirect : {destination : String, permanent: true | false}

동적 라우팅을 하는 경우 ([page_name.js]) SSG 사용방법이 다르다.

동적 라우팅 + Static Site Generation

getStaticProps의 context(인자)는 객체이다

key Values
- params : 동적 라우팅에 사용되는 값이다

export async function getStaticProps(context) {
	const { params } = context;
}

Q. `useRouter()의 query` vs `getStaticProps context.params` 같은 코드 아닌가요?

A. No, `useRouter`는 Client Side에서 실행하는 NextJS 코드이다.

즉, Pre-Rendendering에서는 `getStaticProps`의 `context.params`를 사용하고, Client Side에서 사용하고 싶으면 `useRouter`를 사용하자.

이때, NextJs는 동적 라우팅을 Pre-render하기 위해서는 몇개의 페이지를 만들어야 하는지 알려줘야 한다.

(알려주지 않으면 무한개의 동적 라우팅 주소를 만들지도?ㅋㅋ)

By `getStaticPaths`

export async function getStaticPaths ( ) {...}

→ 동적 라우팅의 경로들을 미리 알려주는 역할을 한다

→ 해당 동적 라우트로 가는 Link가 있는 페이지는 Build때 Pre-render한다.

즉, Pre-render 된다는 것은, 이후에는 마치 SPA처럼 행동한다는 것이다

기본형

// [pid].js 파일에서 가능한 pid값들을 설정해주기
export async function getStaticPaths() {
	return {
		paths: [ // 객체 배열
		{params: {pid: "p1"}, // params가 key인 객체
		{params: {pid: "p2"},
		{params: {pid: "p3"},
	],
	fallback: true | false | "blocking"
	}
}

주의사항 및 사용법

동적 중첩 라우트

- If the page name is `pages/posts/[postId]/[commentId]`, then `params` should contain `postId` and `commentId`.

동적 라우트

- If the page name uses [catch-all routes](https://nextjs.org/docs/pages/building-your-application/routing/dynamic-routes#catch-all-segments))like `pages/[...slug]`, then `params` should contain `slug` (which is an array). If this array is `['hello', 'world']`, then Next.js will statically generate the page at `/hello/world`.
- If the page uses an [optional catch-all route](https://nextjs.org/docs/pages/building-your-application/routing/dynamic-routes#optional-catch-all-segments),,) use `null`, `[]`, `undefined` or `false` to render the root-most route. For example, if you supply `slug: false` for `pages/[[...slug]]`, Next.js will statically generate the page `/`.

example

// [pid].js
export async function getStaticPaths() {
	const data = await getData();
	const ids = data.products.map((product) => product.id);
	const paths = ids.map((id) => ({
		params: { pid: id },
	}));
	return {
		paths,
		fallback: true,
	};
}

What is fallback key?

fallback : true | false | “blocking”

Error Handling을 하면서 사용하기

fallback : false

→ route에 포함되지 않는 경우 404Error 발생.

→ `404.js` 에서 Error Handling

fallback : true

→ route에 포함되지 않는 경우 404Error가 발생하지 않음. 단, getStaticProps에서 데이터를 찾는 과정에서 코드Error가 발생함

→ `getStaticProps`에서 ErrorHandling해야함

export async function getStaticProps(context) {
	const { params } = context;

	const productId = params.pid;
	const data = await getData();
	const product = data.products.find((product) => product.id === productId);
	// Error Handling
	if (!product) {
		return {
			notFound: true,
		};
	}
	return {
		props: {
			loadedProduct: product,
		},
	};
}

ISR (Incremental Static Regeneration)

만약에 빌드 → 배포를 통해 프로젝트를 배포하고,😱 코드가 변경되면 NextJS는 빌드를 새로하고 배포를 다시하지 않는한, 변경된 코드가 적용되지 않는다.

cf) npm run dev 는 build를 다시하게끔 되어있어서 값이 바뀐다

따라서, NextJS에서는 이러한 수고를 덜기 위해 Build를 일정시간마다 해주는 방법을 제공한다. → revalidate key

export async function getStaticProps() {
	const filePath = path.join(process.cwd(), "data", "dummy-backend.json");
	const jsonData = await fs.readFile(filePath);
	const data = JSON.parse(jsonData);
	console.log("Regenerated");
	return {
		props: {
			products: data.products,
		},
		revalidate: 5,
	};
}
// 5초마다 build를 재진행한다
// 없으면 false로 간주하여, 재빌드를 하지 않는다

이제, On Each Request에 Pre-Render하는 SSR에 대해 알아보자.

Server-Side Rendering

→ Pre-Render할때 즉, Build Time때 알 수 없는 데이터를 가져올 때.

즉, request를 날릴때 데이터를 가져올 수 있는 경우 ex) Authorization headers or geolocation

getServerSideProps

export async function getServerSideProps (context)

→ page 폴더 내에서 사용

→ request 날릴때에만 fetch data

cf) build타임때 알 수 있는 데이터이면, 그냥 `getStaticProps` 로 Pre-Fetching해도된다.

→ getServerSideProps는 build할때 pre-Render하지 않으므로, 동적 라우트를 사용하는 경우 getStaticPaths처럼 Route를 지정해줄 필요가 없다.

→ 사용법은 revalidation을 제외하고 `getStaticProps` 와 동일하다

// pages/user-profile.js
export async function getServerSideProps() {
	return {
		props: {
			username: "Jiho",
		},
	};
}

context : getStaticProps와는 다르게 매번 request, response가 다르므로, res res를 포함한다.

export async function getServerSideProps(context) {
	const { params, req, res } = context;
	return {
		props: {
			username: "Jiho",
		},
	};
}

https://nextjs.org/docs/pages/api-reference/functions/get-server-side-props)

Client Side Rendering + Static Site Rendering 도 가능하다

→ Static Site로 Pre-Fetch하고(no - revalidating), CSR로 바뀐 값들을 가져오는 방법

참고 문헌

https://optinmonster.com/seo-ranking-factors/)

https://marketbrew.ai/server-side-rendering-and-seo-the-ultimate-guide)

방법1 : O(nlogn)

• 직관적, 현실적
• 각 k에 대하여 2로 나눠가면서 bitwise 1의 개수를 더하는 방식
• Max n = 10^5이므로, 충분히 가능한 방식

class Solution:
    def countBits(self, n: int) -> List[int]:
        ans = []
        # O(logN)
        for elmt in range(n+1):          
          tmp = 0 
          # O(logN)         
          while(elmt != 0):            
            if(elmt % 2 != 0):
              tmp += 1
            elmt //= 2
          ans.append(tmp)        
        return ans

⭐방법2 :  O(n)

• DP
• Bitwise 표현의 성질을 이용한다.
• 각 숫자를 2의 거듭제곱을 기준으로 분류했을때, 이전 구간의 형태가 다음 구간에서 나타나는 성질을 이용한다.
• 따라서, rightShift한 값에 없어진 rightmost bit의 값을 더해주면 해당 elmt의 값이 나온다.

rightShift 했을때 값 : ans[i >> 1]

없어진 bit : i & 1

→ BottomUp 방식

class Solution:
    def countBits(self, n: int) -> List[int]:
        ans = [0] * (n + 1)
        for i in range(1, n + 1):
            ans[i] = ans[i >> 1] + (i & 1)
        return ans