leah

Input

Default

1
2
3

import sys
sys.setrecursionlimit(100000)
input = sys.stdin.readline

fibonacci 함수에 인자로 입력할 n이 주어진다. (0 ≤ n ≤ 50)

1

n = int(input())

Output

fibonacci 함수가 호출된 횟수를 출력한다.

출력값이 매우 커질 수 있으므로 정답을 1,000,000,007 로 나눈 나머지를 출력한다.

1
2
3

if n < 2: print(num[n])
else:
  print(num[n] % 1000000007)

DP

• 일단 호출 횟수 를 출력해야 한다는 점!

• 재귀함수를 사용하면 피보나치 수열을 진행하는 동시에 count도 해야하므로 시간 초과 가 발생한다…

• 따라서 배열 을 사용해서 count 횟수만 진행한다! 이러면 for문으로 충분함

  1	num = [1, 1]

1. n < 2 인 경우에는 위에서 바로 출력하면 됨

   1	if n < 2: print(num[n])

2. 그 외의 경우에는 배열을 증가시키고 출력해야 함

   • 횟수는 default로 n < 2 의 경우에는 1번 이고, 그 이후에는 fibonacci(n-2) + fibonacci(n-1) 에 따라 num[본인-1] + num[본인-2] + 본인 호출 횟수 1 을 append 한다.

   1 2 3 4 5 6

   else: for _ in range(n-1): # fibonacci(n-2) + fibonacci(n-1)에 자기 자신 호출 횟수 +1 num.append(num[-1] + num[-2] + 1) print(num[n] % 1000000007)

들어가기에 앞서,

Server Side Rendering을 지원하던 기존 Multi Page Form 방식에서 모바일 사용자가 증가함에 따라 React, Angular, Vue 등 Client Side Rendering이 가능한 SPA가 등장하게 되었다. SPA는 1개의 페이지에서 수정되는 부분만 리렌더링하는 등 여러 동작이 이루어진다. 그렇다면 SSR과 CSR의 차이는 무엇일까?

SSR

서버에서 렌더링 작업을 수행하는 SSR은 사용자가 웹페이지에 접근할 때 서버에서 페이지에 대한 요청을 보내고, 서버에서 html, view 등의 리소스가 어떻게 보여질 지 해석되어 렌더링 후 사용자에게 반환하는 방식으로, 전체적인 프로세스는 다음과 같다.

여기서 첫번째 단계는 다음과 같이 이루어진다.

SSR이어도 Ajax 기능을 위해 클라이언트 렌더링 요소가 포함될 수 밖에 없다.

쉽게 설명하면, 페이지를 구성해서 그에 해당하는 html을 다운받아 화면에 렌더링하는 것으로, CSR에 비해 다운 받는 파일이 많지 않아 초기 로딩 속도가 빠르고, 사용자가 빨리 콘텐츠를 볼 수 있다. 근데 이 과정이 브라우저 👉 프론트 서버 👉 백엔드 서버 👉 데이터 베이스 를 거쳐 데이터를 받고 역순으로 브라우저까지 데이터를 가져와 그려야 하기 때문에, 페이지 이동/ 클릭 등으로 다른 요청이 생길 때마다 이 과정을 반복하면 변경되지 않은 부분도 계속해서 리렌더링되는 문제점이 있다. (서버 부하 등의 문제를 일으킬 수 있음)

CSR

CSR은 최초 1번만 서버에서 전체 페이지를 렌더링하여 보내주면, 이후에는 사용자의 요청이 올 때마다 리소스를 서버에서 제공받아 클라이언트가 해석하고 렌더링하는 방식이다. 전체적인 프로세스는 다음과 같다.

SSR에 클라이언트 렌더링 요소가 포함된다면, CSR는 SSR 없이 일관된 코드를 작성할 수 있다. (물론 아닌 경우도 있음)

즉, 먼저 데이터를 제외하고 화면을 그리는 코드들만 프론트 서버에서 다운받아진다. 이는 js 파일에 한번에 묶이기 때문에 첫 다운에 시간이 오래 걸린다. 따라서 초기 구동 속도가 SSR에 비해 느려지는데, 이는 code splitting 으로 해결할 수 있다. 하지만 아직 데이터를 다운 받은 상태가 아니다. 클라이언트의 요청이 발생하면 필요한 데이터만 백엔드 서버에 요청하여 받아온 후 해당 부분을 갱신하는 방식으로 SPA가 작동하기 때문에 서버 부하가 덜하다.

이와 관련된 문제는 검색 엔진 최적화에 취약할 수 있다는 점이다.

초기에 데이터 없이 html이 다운되기 때문에 검색봇이 해당페이지를 빈 페이지로 착각하여 Search Engine Optimization에 취약할 수 있다.

그래서 차이점은?

• 렌더링 속도
• SEO
• 보안

등의 차이가 있다.

CSR은 사용자의 요청에 맞게 필요한 부분만 다시 읽기 때문에 서버에서 전체 페이지를 다시 읽는 것보다 빠른 반응 속도를 기대할 수 있다. 하지만 초기 로딩 시

1. html 다운: 페이지를 읽고
2. js 다운: js를 읽고
3. js을 실행하고

등등을 모두 마무리해야 사용자에게 콘텐츠가 보이기 때문에 화면을 렌더링하기까지의 초기 로딩 속도가 느리다. 하지만 그 이후에는 빠른 반응을 보인다.

SSR은 서버에서 view를 렌더링하여 가져오기 때문에, 초기 로딩 속도 (초기 화면 렌더링 속도) 가 빠르다.

Next.js란?

그래서 Next는 어떤 SSR과 CSR의 단점을 보완하는 걸까?

SSR은 불필요한 부분까지 리렌더링 되어 서버 부하가 발생할 수 있다는 점, CSR은 초기 로딩 속도가 느리고 SEO에 취약하다는 단점이 있다.

Next.js를 사용하여 첫페이지는 백엔드 서버에서 렌더링하여 빈 html이 아닌 데이터가 채워진 html을 받는다면 SEO 문제를 해결할 수 있다. 이후에는 CSR 방식에 따라 필요한 데이터만 받아 갱신한다면 서버 부하도 줄일 수 있다.

Next.js를 통해…

기존의 문제점인

• webpack과 같은 번들러를 통해 code를 번들하고 Babel과 같은 컴파일러로 변환해야 함
• code splitting과 같은 성능 최적화가 필요함
• 성능과 SEO를 위해 몇몇 페이지를 pre-render 해야할 수 있음
• React app과 데이터 스토어를 연동하기 위해 SSR 코드를 작성해야 할 수 있음
• 그냥, SSR과 CSR를 모두 사용하고 싶음

을 해결할 수 있다.

그러니까 Next.js의 특징은

• 페이지 기반의 라우팅 시스템 (CRA 시 page folder 생성)
• 한 페이지 당 SSG와 SSR을 지원해 pre-rendering 가능
• 자동화된 code splitting을 통해 페이지 로딩을 빠르게 함
• Client Side Routing에 최적화된 prefetching을 지원함
• 빌트인 CSS, Sass이 지원되며, 모든 CSS-in-JS 라이브러리를 지원함
• 빠른 재구동 개발 환경을 지원함
• serverless 함수를 이용해 API를 개발할 수 있게 API 라우터를 지원함
• 확장 가능함

등이 있다.

Reference

https://nextjs.org/learn/basics/create-nextjs-app

Input

첫째 줄에 N (1 ≤ N ≤ 15)이 주어진다.

둘째 줄부터 N개의 줄에 Ti와 Pi가 공백으로 구분되어서 주어지며, 1일부터 N일까지 순서대로 주어진다. (1 ≤ Ti ≤ 5, 1 ≤ Pi ≤ 1,000)

1
2
3
4
5
6
7
8
9
10
11

N = int(input())
T = []
P = []
dp = []

for _ in range(N):
  t, p = map(int, input().split())
  T.append(t)
  P.append(p)
  dp.append(p)
dp.append(0)

Output

첫째 줄에 백준이가 얻을 수 있는 최대 이익을 출력한다.

1

print(dp[0])

DP

역순으로 접근해 무조건 index 0 값에 최대를 담도록 함.

• 현재 일자 i 에 기간 T[i] 를 더했을 때 N+1 보다 작아야 하므로, 예외의 경우 이전 값 dp[p+1] 을 유지한다.

  1 2	if i+T[i] > N: dp[i] = dp[i+1]

• 범위 내에 드는 경우 최대 이익을 구하는 조합 을 구해야 하므로, 이전 값 dp[i+1] 과 현재 비용 P[i] 에 T[i] 이후의 비용을 더한 값 중 max 값을 취한다.

  1 2	else: dp[i] = max(dp[i+1], P[i]+dp[i+T[i]])

문제 조건

1. bfs()

• 같은 색 뿌요가 4개 이상 상하좌우로 연결되어 있으면 한꺼번에 없어질 것, 1연쇄에 해당
• 터질 수 있는 뿌요가 여러 그룹이 있다면 동시에 터지고, 여러 그룹이더라도 1연쇄에 해당

2. check_fall()

• 아래에 바닥이나 다른 뿌요가 나올 때까지 아래로 떨어질 것

3. while

• 뿌요가 없어지고 난 후 bfs부터 다시 반복

Code

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
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85

from collections import deque
import sys

input = sys.stdin.readline
dir = [[-1,0],[1,0],[0,-1],[0,1]]

# string to string(char) array
board = [list(map(str, input().strip())) for _ in range(12)]

# 뿌요 터뜨리기
def bfs(dx, dy, flag):
  q = deque()
  c = [[0]*6 for _ in range(12)]
  q.append([dx, dy])
  cnt = 1
  c[dx][dy] = cnt

  # 한 점씩 상하좌우 체크
  # 같은 색의 뿌요 체크
  while q:
    dx, dy = q.popleft()

    for i in range(4):
      x = dx + dir[i][0]
      y = dy + dir[i][1]

      if 0 <= x < 12 and 0 <= y < 6:
        if board[x][y] == board[dx][dy] and c[x][y] == 0:
          cnt += 1
          c[x][y] = 1
          q.append([x, y])

  # 연쇄되는 경우
  if cnt >= 4:
    flag += 1
    for i in range(12):
      for j in range(6):
        # pop 시키기
        if c[i][j] == 1:
          board[i][j] = "."

  return flag

def check_fall():
  # 마지막 줄 제외하고 역순으로 체크 (아래로 떨어지므로)
  for i in range(10, -1, -1):
    for j in range(6):
      # 아래로 떨어져야 하는 경우
      if board[i][j] != "." and board[i+1][j] == ".":
        for k in range(i+1, 12):
          # 뿌요가 없는 & 가장 밑으로 현재의 뿌요를 떨어트려야 함
          # break point
          if k == 11 and board[k][j] == ".":
            board[k][j] = board[i][j]
          # k < 11인데 뿌요가 있는 경우
          elif board[k][j] != ".":
            board[k-1][j] = board[i][j]
            break
        
        board[i][j] = "."

answer = 0

# case 반복
while True:
  # 이 때 cnt는 0인지 아닌지만 체크하는 변수로,
  # 다른 색의 뿌요 그룹이 터져도 동시에 터지는 것으로 간주하여 한번의 연쇄로 취급함
  cnt = 0

  # 한 board 케이스 연쇄되는 경우의 수 체크
  for i in range(12):
    for j in range(6):
      if board[i][j] != ".":
        cnt += bfs(i, j, cnt)

  # break point: board 전체 검사 했는데 cnt == 0
  if cnt == 0:
    print(answer)
    break

  # 연쇄된 경우 -> 다시 처음부터 board 체크해야 함
  else:
    answer += 1
  
  check_fall()

Python

• string to string(char) array

  1	[list(map(str, input().strip())) for _ in range(12)]

Input

첫째 줄에 거스름돈 액수 n(1 ≤ n ≤ 100,000)이 주어진다.

1

n = int(input())

Output

거스름돈 동전의 최소 개수를 출력한다.

만약 거슬러 줄 수 없으면 -1을 출력한다.

DP

최소 거스름돈 개수를 구해야 하기 때문에, 큰 수인 5로 거스름돈을 나누기 시작해야 한다.

그리고 5로 나눈 나머지를 2로 나누었을 때 0이 되면 그게 정답이 되고, 0이 아니면 5를 줄이고 2를 늘려봐야 한다.

그래도 답이 안 나오면 거슬러 줄 수 없는 경우(e.g. 1)이므로 -1을 출력하면 됨.

1
2
3
4
5
6
7
8
9

for five in range(int(n/5), -1, -1):
  coin = five
  money = n - (5 * five)
  if money % 2 == 0:
    coin += int(money / 2)
    print(coin)
    exit()
    
print(-1)

Better Solution

DP 문제인 만큼, 형식에 맞게 풀어보자.

0. Default

   • 매번 sys.stdin.readline 을 치기보다, 기본처럼 input() 으로 간단하게 처리하기 위해 아래와 같이 세팅한다.

   1 2	import sys input = sys.stdin.readline

   1 2 3 4 5 6 7

   n = int(input()) # 나머지 num = n % 5 # 동전 개수 count = 0

1. Exception : 5보다 작은 수 중 2로 나눌 수 없는 1이나 3 일 경우, 2나 5로 나눌 수 없기 때문에 -1을 출력한다.

   1 2 3

   if n == 1 or n == 3: print(-1) exit(0)

2. 5로 먼저 나눈 후, 나머지가 2로 나눠지면 5로 나눈 몫과 2로 나눈 몫을 더하여 출력한다.

   몫을 int(n / 5) 와 같이 처리하지 말고, python의 // 를 활용하자!

   1 2 3

   elif num % 2 == 0: print(n // 5 + num // 2) exit(0)

3. 나머지가 2로 나눠떨어지지 않는 경우, 5의 몫을 -1하고 (나머지에 5를 더하여) 다시 2로 나눈 몫과 5로 나눈 몫을 더하여 출력한다.

   1 2 3

   else: print((n // 5 - 1) + (num + 5) // 2) exit(0)

Input

첫째 줄에 M과 N, 그리고 K가 빈칸을 사이에 두고 차례로 주어진다. M, N, K는 모두 100 이하의 자연수이다.

둘째 줄부터 K개의 줄에는 한 줄에 하나씩 직사각형의 왼쪽 아래 꼭짓점의 x, y좌표값과 오른쪽 위 꼭짓점의 x, y좌표값이 빈칸을 사이에 두고 차례로 주어진다. 모눈종이의 왼쪽 아래 꼭짓점의 좌표는 (0,0)이고, 오른쪽 위 꼭짓점의 좌표는(N,M)이다. 입력되는 K개의 직사각형들이 모눈종이 전체를 채우는 경우는 없다.

• 좌표로 주어지는 직사각형 외의 공간을 구하는 문제이므로, 주어지는 직사각형의 영역은 1 로 표기해둔다.
• 이 때, 좌표로 직사각형이 주어지므로 한 칸에 해당하는 좌표와 이를 구분해야 한다.
• 즉, 한 칸의 영역은 끝 좌표-1 에 해당한다.

1
2
3
4
5
6
7
8
9

m, n, k = map(int, sys.stdin.readline().split())
board = [[0]*(n) for _ in range(m)]
for _ in range(k):
  x1, y1, x2, y2 = map(int, sys.stdin.readline().split())
  x2 -= 1
  y2 -= 1
  for x_idx in range(x1, x2+1):
    for y_idx in range(y1, y2+1):
      board[y_idx][x_idx] = 1

Default

1
2

import sys
sys.setrecursionlimit(1000000)

DFS

• 연속되는 공간을 찾을 때, 위/아래/양 옆을 체크하므로 dir 을 미리 세팅한다.

• 출력해야 하는 값이 count 와 영역 이므로 이 둘에 해당하는 변수를 생성한다.

• 모든 보드의 칸을 돌면서 0 인 경우 해당 영역의 넓이를 구하고 count+1 을 해야 하므로 가장 바깥쪽이자 전체를 도는 for문을 생성한다.

  • 0임을 체크하면, 다시 이 영역을 count하면 안 되므로 1로 세팅하고, 해당 영역부터 넓이를 체크해야 하므로 area는 1로 초기화, 그리고 dfs를 돈다.
  • area를 global 로 설정하여 해당 변수를 result에 append 하여 이후 출력값을 sort 한다.
  • 또한, 연속된 0 값을 체크하여 영역을 세는 것이므로 count++ 을 수행한다.

  1 2 3 4 5 6 7 8

  for y in range(m): for x in range(n): if board[y][x] == 0: board[y][x] = 1 area = 1 dfs(y, x) result.append(area) count += 1

• 연속된 영역을 파악하기 위해 dfs를 돈다.

  • 미리 생성해 둔 dir에 따라 연속된 넓이를 체크하고,
  • 이 때 범위 내의 값일 경우, 위와 동일하게 칸을 1로 세팅, 넓이를 +1하고 dfs를 이어서 수행한다.

  1 2 3 4 5 6 7 8 9 10 11 12

  def dfs(dy, dx): global area for dd in dir: x = dd[0] + dx y = dd[1] + dy if 0 <= x < n and 0 <= y < m: if board[y][x] == 0: board[y][x] = 1 area += 1 dfs(y, x)

Output

첫째 줄에 분리되어 나누어지는 영역의 개수를 출력한다.

둘째 줄에는 각 영역의 넓이를 오름차순으로 정렬하여 빈칸을 사이에 두고 출력한다.

int 배열 값을 str으로 하나씩 출력하는 법

' '.join(map(str, arr)) 를 통해 1 7 13 과 같이

int 값을 str로 mapping하고 한 칸 띄어쓰기를 join 한다.

런타임 에러가 뜰까봐 sys를 이용하는데, 알고리즘은 다 맞아놓고 자꾸 출력 형식에서 틀린다… 바보야…!!!!!!

1
2
3
4

result.sort()
sys.stdout.write(str(count))
print()
sys.stdout.write(' '.join(map(str, result)))

Input

첫째 줄에 유저의 수 N (2 ≤ N ≤ 100)과 친구 관계의 수 M (1 ≤ M ≤ 5,000)이 주어진다.

둘째 줄부터 M개의 줄에는 친구 관계가 주어진다. 친구 관계는 A와 B로 이루어져 있으며, A와 B가 친구라는 뜻이다. A와 B가 친구이면, B와 A도 친구이며, A와 B가 같은 경우는 없다. 친구 관계는 중복되어 들어올 수도 있으며, 친구가 한 명도 없는 사람은 없다. 또, 모든 사람은 친구 관계로 연결되어져 있다. 사람의 번호는 1부터 N까지이며, 두 사람이 같은 번호를 갖는 경우는 없다.

1

n, m = map(int, input().split())

먼저 친구 관계 👉 트리 구조 이므로 adj 를 생성하고, bfs를 위해 visited 도 생성한다.

그리고, 답을 저장한 뒤 min 을 출력해야 하므로 answer 도 생성한다.

1
2
3
4

adj = [[] for _ in range(n+1)]
visited = [0]*(n+1)
answer = [0]*(n+1)
answer[0] = sys.maxsize

친구 관계를 저장할 adj에 입력값 저장!

1
2
3
4

for _ in range(m):
  a, b = map(int, input().split())
  adj[a].append(b)
  adj[b].append(a)

Default

1
2
3

import sys
from collections import deque
sys.setrecursionlimit(100000)

BFS

연속적으로 이어진 값을 더해나가는 문제이기 때문에, 어제 배운 새로운 접근 방식에 따라 bfs 를 적용하여 queue 를 이용해 답을 구해봤다.

1
2
3

def bfs(start):
  queue = deque()
  queue.appendleft(start)

queue에 값이 존재하는 동안

• start 자신이 아니며, 아직 방문하지 않은 노드에 대해서
• queue에 append 하고 +1 을 수행한다.

이 때, pop 이 아니라 popleft 임!!!

1
2
3
4
5
6
7

while queue:
  now = queue.popleft() # pop()이 아니라 popleft()!!!

  for friend in adj[now]:
    if visited[friend] == 0 and friend != start:
      queue.append(friend)
      visited[friend] = visited[now] + 1

Output

첫째 줄에 BOJ의 유저 중에서 케빈 베이컨의 수가 가장 작은 사람을 출력한다. 그런 사람이 여러 명일 경우에는 번호가 가장 작은 사람을 출력한다.

• 모든 n 사람에 대해서 bfs를 시행해야 하므로 for문을 돌리고,
• visited 값을 모두 더한 값이 케빈 베이컨의 값이므로 sum을 이용한다.
• 이후 visited를 다시 초기화시켜야 한다.

index 함수는 찾는 값의 index가 여러개일 경우 가장 첫번째 index를 반환하므로, 자동적으로 조건을 만족시킨다.

1
2
3
4
5
6

for i in range(1, n+1):
  bfs(i)
  answer[i] = sum(visited)
  visited = [0]*(n+1)

print(answer.index(min(answer)))

Input

일단 기본으로

1
2

import sys
sys.setrecursionlimit(100000)

recursion limit 설정 값을 잘 파악하자

입력 파일의 첫째 줄에는 전체 사람의 수 n이 주어지고,

둘째 줄에는 촌수를 계산해야 하는 서로 다른 두 사람의 번호가 주어진다.

그리고 셋째 줄에는 부모 자식들 간의 관계의 개수 m이 주어진다.

넷째 줄부터는 부모 자식간의 관계를 나타내는 두 번호 x,y가 각 줄에 나온다. 이때 앞에 나오는 번호 x는 뒤에 나오는 정수 y의 부모 번호를 나타낸다.

1
2

n = int(input())
x, y = map(int, input().split())

DFS

일단 촌수를 세는 규칙을 파악해야 하는데, 굉장히 간단하다.

트리 구조를 토대로, 위아래로만 count를 더해나가면 된다. 즉, 부모/ 형제 만을 기준으로 트리를 순회하면 됨.

• 연속적으로 adj 을 체크하므로 배열을 만들고

• 기본적으로 DFS라면, visited 를 생성하자.

  1 2	adj = [[] for _ in range(n+1)] visited = [False] * (n+1)

  1 2 3 4

  for _ in range(int(input())): a, b = map(int, input().split()) adj[a].append(b) adj[b].append(a)

• 관련이 없을 때는 -1을 출력해야 하므로, 이를 체크할 boolean 변수를 생성하자.

  1	check = False

break point : 현재 체크하고 있는 값과 target 값이 같다면, 지금까지의 count 값을 출력하고 끝낸다.

1
2
3
4

if now == target:
  print(count)
  check = True
  return

이제 adj 배열에서 방문하지 않은 child에 대해 bfs를 진행한다.

1
2
3
4
5
6
7

def dfs(now, target, count):
  visited[now] = True
  global check

	  for child in adj[now]:
    if not visited[child]:
      dfs(child, target, count+1)

Another Solution

BFS로 queue 를 이용하는데, 모든 경우를 체크하는 경우이므로 이어서 값을 확인하기 좋다.

특히 깊이가 깊어질 때마다 count+1 을 수행하기에 큐가 적합하다.

1
2
3
4
5
6
7

while q:
        d = q.popleft()
        for i in s[d]:
            if visit[i] == 0:
                visit[i] = 1
                result[i] = result[d] + 1
                q.append(i)

이렇게 count를 배열로 설정하여 하나씩 더해가고, 정답을 출력하기 위해

1

print(result[b] if result[b] != 0 else -1)

해당 index로 바로 접근해서 출력하고 아닌 경우도 쉽게 예외 처리할 수 있다.

Output

입력에서 요구한 두 사람의 촌수를 나타내는 정수를 출력한다.

어떤 경우에는 두 사람의 친척 관계가 전혀 없어 촌수를 계산할 수 없을 때가 있다. 이때에는 -1을 출력해야 한다.

• 여기서 위에서 생성한 check 변수를 활용하면 된다. global 로 선언하였기 때문에, 비동기 처리되어 dfs가 모두 끝난 뒤 if문을 체크하게 된다.

1
2
3
4

dfs(x, y, 0)

if not check:
  print(-1)

FirstEvent

ToTimeZone

DayName

TimeSinceLastFalse

TimeSinceLastTrue