• n명이 입국심사를 위해 줄을 서서 기다리고 있습니다. 각 입국심사대에 있는 심사관마다 심사하는데 걸리는 시간은 다릅니다.

• 처음에 모든 심사대는 비어있습니다. 한 심사대에서는 동시에 한 명만 심사를 할 수 있습니다. 가장 앞에 서 있는 사람은 비어 있는 심사대로 가서 심사를 받을 수 있습니다. 하지만 더 빨리 끝나는 심사대가 있으면 기다렸다가 그곳으로 가서 심사를 받을 수도 있습니다.

• 모든 사람이 심사를 받는데 걸리는 시간을 최소로 하고 싶습니다.

• 입국심사를 기다리는 사람 수 n, 각 심사관이 한 명을 심사하는데 걸리는 시간이 담긴 배열 times가 매개변수로 주어질 때, 모든 사람이 심사를 받는데 걸리는 시간의 최솟값을 return 하도록 solution 함수를 작성해주세요.

🍗 제한 사항

• 노드의 개수 n은 2 이상 20,000 이하입니다.
• 간선은 양방향이며 총 1개 이상 50,000개 이하의 간선이 있습니다.
• vertex 배열 각 행 [a, b]는 a번 노드와 b번 노드 사이에 간선이 있다는 의미입니다.

🎁 입출력 예시

• 예제의 그래프를 표현하면 아래 그림과 같고, 1번 노드에서 가장 멀리 떨어진 노드는 4,5,6번 노드입니다.

😎 나의 풀이

from collections import deque

def solution(n, edge): # 6,[[3, 6], [4, 3], [3, 2], [1, 3], [1, 2], [2, 4], [5, 2]]
    answer = 0 # 답을 저장할 answer
    graph = [[] for _ in range(n)] # 연결된 노드 정보 그래프

    dist = [-1] * n # 각 노드의 최단 거리 리스트

    for e in edge: # 인접 노드 정보 추가
      graph[e[0] - 1].append(e[1] - 1)
      graph[e[1] - 1].append(e[0] - 1)

    visit = [False] * n # 방문 배열 초기화
    queue = deque([0]) # 큐 생성 인덱스 0번으로
    dist[1] = 0 # 자기 자신의 거리는 0으로 설정
    visit[0] = True # 자기 자신 방문 True

    while queue:
      u = queue.popleft() # 현재 노드꺼내기

      for v in graph[u]: # 연결 노드 탐색
        if not visit[v]: # 방문하지 않았다면
          queue.append(v) # 큐에 추가
          visit[v] = True # 방문 표시
          dist[v] = dist[u] + 1 # 최단거리 업데이트 (v까지 가는 거리는 현재 u까지 온 거리 + 1)

    for d in dist: # BFS 결과로 만들어진 각 노드의 거리 값 하나씩 확인
      if d == max(dist): # 가장 멀리 있는 거리값과 같다면 (= 가장 먼 노드라면)
        answer += 1 # 그런 값의 노드를 세서 answer에 더한다.

    return answer

1. bfs를 이용한 풀이다.
2. deque와 인접리스트를 초기화 해준다.
3. queue를 돌면서 연결 노드를 탐색하고 방문 하지 않았다면 큐에 추가 후 visit을 True로 업데이트 해주고 최단거리를 업데이트 시켜준다.
4. 최단거리 리스트인 dist를 순회하여 가장 멀리 있는 거리값과 같으면 그 값의 노드를 세서 answer에 더해주면 된다.

• dist의 거리값을 세서 리턴해주는게 핵심인 것 같다.

• n명이 입국심사를 위해 줄을 서서 기다리고 있습니다. 각 입국심사대에 있는 심사관마다 심사하는데 걸리는 시간은 다릅니다.

• 처음에 모든 심사대는 비어있습니다. 한 심사대에서는 동시에 한 명만 심사를 할 수 있습니다. 가장 앞에 서 있는 사람은 비어 있는 심사대로 가서 심사를 받을 수 있습니다. 하지만 더 빨리 끝나는 심사대가 있으면 기다렸다가 그곳으로 가서 심사를 받을 수도 있습니다.

• 모든 사람이 심사를 받는데 걸리는 시간을 최소로 하고 싶습니다.

• 입국심사를 기다리는 사람 수 n, 각 심사관이 한 명을 심사하는데 걸리는 시간이 담긴 배열 times가 매개변수로 주어질 때, 모든 사람이 심사를 받는데 걸리는 시간의 최솟값을 return 하도록 solution 함수를 작성해주세요.

🍗 제한 사항

• 입국심사를 기다리는 사람은 1명 이상 1,000,000,000명 이하입니다.
• 각 심사관이 한 명을 심사하는데 걸리는 시간은 1분 이상 1,000,000,000분 이하입니다.
• 심사관은 1명 이상 100,000명 이하입니다.

🎁 입출력 예시

• 가장 첫 두 사람은 바로 심사를 받으러 갑니다.

• 7분이 되었을 때, 첫 번째 심사대가 비고 3번째 사람이 심사를 받습니다.

• 10분이 되었을 때, 두 번째 심사대가 비고 4번째 사람이 심사를 받습니다.

• 14분이 되었을 때, 첫 번째 심사대가 비고 5번째 사람이 심사를 받습니다.

• 20분이 되었을 때, 두 번째 심사대가 비지만 6번째 사람이 그곳에서 심사를 받지 않고 1분을 더 기다린 후에 첫 번째 심사대에서 심사를 받으면 28분에 모든 사람의 심사가 끝납니다.

😎 나의 풀이

def solution(n, times):
    start,end = 1, min(times) * n # start = 1, end = 42

    while start <= end:
      mid = (start + end) // 2 # 중간 값

      count = 0 
      for time in times:
        count += mid // time # 주어진 시간을 심사 시간으로 나눈 값을 count에 더해준다.

      if count < n: # 심사할수 있는 사람의 수가 n보다 작으면 = 
        # 심사해야 하는 사람의 수보다 작으면 시간이 더 필요
        start = mid + 1 # mid의 오른쪽 탐색
      else:
        end = mid - 1 # mid의 왼쪽 탐색


    return start

1. 이분탐색을 이용한 풀이다.
2. 이분탐색의 범위를 start는 1로 설정하고, end는 times의 min값으로 정한다.
3. times배열을 돌아 주어진 시간을 심사 시간으로 나눈 값을 count에 더한다.
4. 심사할 수 있는 사람의 수가 N보다 작으면 mid의 범위의 오른쪽을 탐색한다.
5. 반대면 왼쪽 (더 작은 범위)를 탐색한다.

• 2분탐색..

• n개의 음이 아닌 정수들이 있습니다. 이 정수들을 순서를 바꾸지 않고 적절히 더하거나 빼서 타겟 넘버를 만들려고 합니다. 예를 들어 [1, 1, 1, 1, 1]로 숫자 3을 만들려면 다음 다섯 방법을 쓸 수 있습니다.

• 사용할 수 있는 숫자가 담긴 배열 numbers, 타겟 넘버 target이 매개변수로 주어질 때 숫자를 적절히 더하고 빼서 타겟 넘버를 만드는 방법의 수를 return 하도록 solution 함수를 작성해주세요.

🍗 제한 사항

• 주어지는 숫자의 개수는 2개 이상 20개 이하입니다.
• 각 숫자는 1 이상 50 이하인 자연수입니다.
• 타겟 넘버는 1 이상 1000 이하인 자연수입니다.

🎁 입출력 예시

• 예제 #1 문제 예시와 같습니다.

• 예제 #2

😎 나의 풀이

def solution(numbers, target):
    global answer
    answer = 0 # answer에 값 저장

    def dfs(i, total): # dfs 
      global answer
      if i == len(numbers): # i와 numbers의 길이가 같으면 모든 숫자를 다봄
        if total == target: # target 값과 total이 같으면
          answer += 1 # 정답한개 추가
        return

      dfs(i + 1, total + numbers[i]) # 더하는 경우
      dfs(i + 1, total - numbers[i]) # 빼는 경우
      return 

    dfs(0,0) # dfs 시작 (0,0) 부터
    return answer # answer 출력

1. dfs를 이용한 풀이다.
2. dfs를 통해 더하는 경우와 빼는 경우 둘다 dfs를 수행한다.
3. i와 numbers의 길이가 같은 경우면 모든 숫자를 다 본 것이기 때문에 total값과 target의 값이 같으면 answer에 1씩 추가해준다.
4. dfs(0,0)으로 dfs를 시작해준다.
5. answer를 리턴하면 된다.

• dfs를 이용한 더하는 경우와 빼는 경우를 전부 구하는 것이 핵심인거같다.

• 점심시간에 도둑이 들어, 일부 학생이 체육복을 도난당했습니다. 다행히 여벌 체육복이 있는 학생이 이들에게 체육복을 빌려주려 합니다. 학생들의 번호는 체격 순으로 매겨져 있어, 바로 앞번호의 학생이나 바로 뒷번호의 학생에게만 체육복을 빌려줄 수 있습니다. 예를 들어, 4번 학생은 3번 학생이나 5번 학생에게만 체육복을 빌려줄 수 있습니다. 체육복이 없으면 수업을 들을 수 없기 때문에 체육복을 적절히 빌려 최대한 많은 학생이 체육수업을 들어야 합니다.

• 전체 학생의 수 n, 체육복을 도난당한 학생들의 번호가 담긴 배열 lost, 여벌의 체육복을 가져온 학생들의 번호가 담긴 배열 reserve가 매개변수로 주어질 때, 체육수업을 들을 수 있는 학생의 최댓값을 return 하도록 solution 함수를 작성해주세요.

🍗 제한 사항

• 전체 학생의 수는 2명 이상 30명 이하입니다.
• 체육복을 도난당한 학생의 수는 1명 이상 n명 이하이고 중복되는 번호는 없습니다.
• 여벌의 체육복을 가져온 학생의 수는 1명 이상 n명 이하이고 중복되는 번호는 없습니다.
• 여벌 체육복이 있는 학생만 다른 학생에게 체육복을 빌려줄 수 있습니다.
• 여벌 체육복을 가져온 학생이 체육복을 도난당했을 수 있습니다. 이때 이 학생은 체육복을 하나만 도난당했다고 가정하며, 남은 체육복이 하나이기에 다른 학생에게는 체육복을 빌려줄 수 없습니다.

🎁 입출력 예시

• 예제 #1 1번 학생이 2번 학생에게 체육복을 빌려주고, 3번 학생이나 5번 학생이 4번 학생에게 체육복을 빌려주면 학생 5명이 체육수업을 들을 수 있습니다.

• 예제 #2 3번 학생이 2번 학생이나 4번 학생에게 체육복을 빌려주면 학생 4명이 체육수업을 들을 수 있습니다.

😎 나의 풀이

def solution(n, lost, reserve):
    # 중복 제거 , 여벌 체육복이 있는데 도난 안당한 학생들 
    reserve_set = set(reserve) - set(lost) # [1,2,5] - [2,4] = {1,5}
    lost_set = set(lost) - set(reserve) # [2,4] - [1,2,5] = {4}

    # 여벌 체육복이 있는 학생들 중 빌려준다. (정렬해서)
    for student in sorted(reserve_set): # {1,5}
      if student - 1 in lost_set:  
        lost_set.remove(student - 1)
      elif student + 1 in lost_set:
        lost_set.remove(student + 1)

    return n - len(lost_set) # n - 체육복 없는 학생 수 => 수업을 들을 수 있는 학생 수

1. 여벌만 있고 도난 안당한 학생 reserve_set과 진짜 체육복이 없는 학생 lost_set을 만들어준다.
2. 여벌 체육복이 있는 학생reserve_set에서 오름차순 정렬한 결과에서 체육복을 빌려준다.
3. student의 앞,뒤로 lost_set에 있으면 빌려줘서 lost_set에서 제거한다.
4. n = 전체 학생 수에서 아직도 체육복이 없는 사람 수를 빼면 결과가 나온다.

• 아이디어를 떠올리기 어려웠던 것 같다. 다시 풀어봐야겠다.

• N개의 정수로 이루어진 수열이 있을 때, 크기가 양수인 부분수열 중에서 그 수열의 원소를 다 더한 값이 S가 되는 경우의 수를 구하는 프로그램을 작성하시오.

🍗 제한 사항

🎁 입출력 예시

• 첫째 줄에 정수의 개수를 나타내는 N과 정수 S가 주어진다. (1 ≤ N ≤ 20, |S| ≤ 1,000,000) 둘째 줄에 N개의 정수가 빈 칸을 사이에 두고 주어진다. 주어지는 정수의 절댓값은 100,000을 넘지 않는다.

• 첫째 줄에 합이 S가 되는 부분수열의 개수를 출력한다.

😎 나의 풀이

N,S = map(int,input().split())
arr = list(map(int, input().split()))
count = 0

from itertools import combinations

for n in range(1, N+1): # 1부터 N까지 부분집합 탐색
  for s in combinations(arr,n): # 부분집합 탐색
    if sum(s) == S: # 부분집합의 합이 S면 
        count += 1 # count 추가

print(count)

1. 부분수열의 개수는 부분집합을 뽑는 문제라고 생각하면 된다.
2. 파이썬의 조합라이브러리인 combinations를 이용해서 1~N까지 탐색을 하고, 부분집합을 탐색해준다.
3. 부분집합의 합이 S와 같으면 count를 추가해서 개수를 세준다.

• 백트래킹 풀이도 있는데 백트래킹으로도 한번 풀어봐야겠다.

• 상근이는 나무 M미터가 필요하다. 근처에 나무를 구입할 곳이 모두 망해버렸기 때문에, 정부에 벌목 허가를 요청했다. 정부는 상근이네 집 근처의 나무 한 줄에 대한 벌목 허가를 내주었고, 상근이는 새로 구입한 목재절단기를 이용해서 나무를 구할것이다.

• 목재절단기는 다음과 같이 동작한다. 먼저, 상근이는 절단기에 높이 H를 지정해야 한다. 높이를 지정하면 톱날이 땅으로부터 H미터 위로 올라간다. 그 다음, 한 줄에 연속해있는 나무를 모두 절단해버린다. 따라서, 높이가 H보다 큰 나무는 H 위의 부분이 잘릴 것이고, 낮은 나무는 잘리지 않을 것이다. 예를 들어, 한 줄에 연속해있는 나무의 높이가 20, 15, 10, 17이라고 하자. 상근이가 높이를 15로 지정했다면, 나무를 자른 뒤의 높이는 15, 15, 10, 15가 될 것이고, 상근이는 길이가 5인 나무와 2인 나무를 들고 집에 갈 것이다. (총 7미터를 집에 들고 간다) 절단기에 설정할 수 있는 높이는 양의 정수 또는 0이다.

• 상근이는 환경에 매우 관심이 많기 때문에, 나무를 필요한 만큼만 집으로 가져가려고 한다. 이때, 적어도 M미터의 나무를 집에 가져가기 위해서 절단기에 설정할 수 있는 높이의 최댓값을 구하는 프로그램을 작성하시오.

🍗 제한 사항

🎁 입출력 예시

• 첫째 줄에 나무의 수 N과 상근이가 집으로 가져가려고 하는 나무의 길이 M이 주어진다. (1 ≤ N ≤ 1,000,000, 1 ≤ M ≤ 2,000,000,000)

• 둘째 줄에는 나무의 높이가 주어진다. 나무의 높이의 합은 항상 M보다 크거나 같기 때문에, 상근이는 집에 필요한 나무를 항상 가져갈 수 있다. 높이는 1,000,000,000보다 작거나 같은 양의 정수 또는 0이다.

• 적어도 M미터의 나무를 집에 가져가기 위해서 절단기에 설정할 수 있는 높이의 최댓값을 출력한다.

😎 나의 풀이

import sys
input = sys.stdin.readline

N,M = map(int,input().split()) # (N = 4 , M = 7)
H = list(map(int,input().split())) # [20,15,10,17]

low = 0 # [0, max(높이)]
high = max(H)
answer = 0

while low <= high:
  mid = (low + high) // 2 # 절단기 높이 후보

  # 잘린 나무 길이 계산
  total = 0
  for i in range(N): # 각 나무를 확인해서 mid보다 높은 나무만 자른다.
    if H[i] > mid: # 나무의 높이가 mid보다 크면
      total += H[i] - mid # 높이에서 mid를 뺀값만큼 total에 더해준다.(가져갈 수 있는 총량)

    # 절단기의 높이가 mid일 때 가져갈 수 있는 나무의 총 길이를 계산하면

    if total >= M: # total이 M보다 크거나 같은지 확인
      answer = mid # 크거나 같으면 절단기의 높이를 mid로 하고 
      low = mid + 1 # 절단기 높이를 더 높일 수 있는지 탐색
    else: # 아니면 (절단기 높이 낮춰야함)
      high = mid - 1 # high를 mid-1로 감소

print(answer)

1. 이분탐색을 이용한 풀이다. 처음에는 다르게 접근했지만 아예 풀리지가 않아서 답을 검색해보고 풀었다.
2. 주석 확인!

• 이분탐색 아이디어가 바로 안떠올랐고 아직 내가 익숙하지 않은 것 같다.

• 요세푸스 문제는 다음과 같다.

• 1번부터 N번까지 N명의 사람이 원을 이루면서 앉아있고, 양의 정수 K(≤ N)가 주어진다. 이제 순서대로 K번째 사람을 제거한다. 한 사람이 제거되면 남은 사람들로 이루어진 원을 따라 이 과정을 계속해 나간다. 이 과정은 N명의 사람이 모두 제거될 때까지 계속된다. 원에서 사람들이 제거되는 순서를 (N, K)-요세푸스 순열이라고 한다. 예를 들어 (7, 3)-요세푸스 순열은 <3, 6, 2, 7, 5, 1, 4>이다.

• N과 K가 주어지면 (N, K)-요세푸스 순열을 구하는 프로그램을 작성하시오.

🍗 제한 사항

🎁 입출력 예시

• 첫째 줄에 N과 K가 빈 칸을 사이에 두고 순서대로 주어진다. (1 ≤ K ≤ N ≤ 5,000)

• 예제와 같이 요세푸스 순열을 출력한다.

😎 나의 풀이

from collections import deque
n, k = map(int, input().split()) # 7, 3
queue = deque(range(1, n + 1)) # [1,2,3,4,5,6,7]
answer = []

while queue:
    for _ in range(k-1): # k-1번 앞사람을 뒤로 보낸다.
        queue.append(queue.popleft()) 
    answer.append(queue.popleft()) # k번째 사람 제거하고 answer에 추가

print(str(answer).replace('[', '<').replace(']', '>'))

1. 큐에 1~N 까지의 값을 넣는다.
2. k-1번 앞사람을 뒤로 보낸다.
3. K번째 사람을 큐에서 제거하고 answer 배열에 추가하면 된다.

• 요세푸스 문제를 처음 알게되었는데 큐로 풀면 금방 풀리는 것 같다.

• 하루에 한 시간 단위로 일을 하거나 일을 쉬어도 된다. 하루에 한 시간 일하면 피로도는 $A$만큼 쌓이고 일은 $B$만큼 처리할 수 있다.

• 만약에 한 시간을 쉰다면 피로도는 $C$만큼 줄어든다. 단, 피로도가 음수로 내려가면 $0$으로 바뀐다. 당연히 일을 하지 않고 쉬었기 때문에 처리한 일은 없다.

• 피로도를 최대한 $M$을 넘지 않게 일을 하려고 한다. $M$을 넘기면 일하는데 번아웃이 와서 이미 했던 일들도 다 던져버리고 일을 그만두게 된다.

• 번아웃이 되지 않도록 일을 할때 하루에 최대 얼마나 일을 할 수 있는지 구해보자. 하루는 24시간이다.

🍗 제한 사항

🎁 입출력 예시

• 첫 번째 줄에 네 정수 $A$, $B$, $C$, $M$이 공백으로 구분되어 주어진다.
• 맨 처음 피로도는 0이다.

• 하루에 번 아웃이 되지 않도록 일을 할 때 최대 얼마나 많은 일을 할 수 있는지 출력한다.

😎 나의 풀이

A,B,C,M = map(int,input().split())

tired = 0 # 피로도
work = 0 # 일한 시간

for _ in range(24): # 24번
  if tired + A <= M: # 피로도 + A가 M보다 작으면
    tired += A # 피로도에 A 추가
    work += B # B만큼 일한시간 추가
  else: # 보다 크면 휴식
    tired -= C # 피로도 C만큼 차감 (휴식했으니)
    if tired < 0: # 피로도가 음수가 되면
      tired = 0 # 피로도는 0으로 초기환

print(work)

1. 피로도를 누적할 tired와 일한 시간을 카운트할 work 변수 초기화를 한다.
2. 주석 내용의 로직대로 풀이하면 work를 출력할 수 있다.

• 문제 내용대로 코드에 옮기면 됬던 문제였다.

• 배열 arr가 주어집니다. 배열 arr의 각 원소는 숫자 0부터 9까지로 이루어져 있습니다. 이때, 배열 arr에서 연속적으로 나타나는 숫자는 하나만 남기고 전부 제거하려고 합니다. 단, 제거된 후 남은 수들을 반환할 때는 배열 arr의 원소들의 순서를 유지해야 합니다. 예를 들면,

• arr = [1, 1, 3, 3, 0, 1, 1] 이면 [1, 3, 0, 1] 을 return 합니다. arr = [4, 4, 4, 3, 3] 이면 [4, 3] 을 return 합니다. 배열 arr에서 연속적으로 나타나는 숫자는 제거하고 남은 수들을 return 하는 solution 함수를 완성해 주세요.

🍗 제한 사항

• 배열 arr의 크기 : 1,000,000 이하의 자연수
• 배열 arr의 원소의 크기 : 0보다 크거나 같고 9보다 작거나 같은 정수

🎁 입출력 예시

😎 나의 풀이

def solution(arr):
    answer = []

    for i in range(len(arr)):
      if i == 0:
        answer.append(arr[i])
      elif arr[i] != arr[i-1]:
        answer.append(arr[i])

    return answer

1. arr을 순회해서 i가 0이면 첫번째 요소니깐 무조건 추가한다.
2. 현재 값이 이전값과 다를 때만 answer배열에 추가한다.
3. answer 리턴

• 현재 값과 이전 값을 비교하는 것이 핵심이다.

• 수많은 마라톤 선수들이 마라톤에 참여하였습니다. 단 한 명의 선수를 제외하고는 모든 선수가 마라톤을 완주하였습니다.

• 마라톤에 참여한 선수들의 이름이 담긴 배열 participant와 완주한 선수들의 이름이 담긴 배열 completion이 주어질 때, 완주하지 못한 선수의 이름을 return 하도록 solution 함수를 작성해주세요.

🍗 제한 사항

• 마라톤 경기에 참여한 선수의 수는 1명 이상 100,000명 이하입니다.
• completion의 길이는 participant의 길이보다 1 작습니다.
• 참가자의 이름은 1개 이상 20개 이하의 알파벳 소문자로 이루어져 있습니다.
• 참가자 중에는 동명이인이 있을 수 있습니다.

🎁 입출력 예시

• 예제 #1 "leo"는 참여자 명단에는 있지만, 완주자 명단에는 없기 때문에 완주하지 못했습니다.

• 예제 #2 "vinko"는 참여자 명단에는 있지만, 완주자 명단에는 없기 때문에 완주하지 못했습니다.

• 예제 #3 "mislav"는 참여자 명단에는 두 명이 있지만, 완주자 명단에는 한 명밖에 없기 때문에 한명은 완주하지 못했습니다.

😎 나의 풀이

def solution(participant, completion):
   participant.sort() # ['ana', 'mislav', 'mislav', 'stanko']
   completion.sort() # ['ana', 'mislav', 'stanko']
   for i in range(len(completion)):
    if participant[i] != completion[i]:
        return participant[i]
   return participant[-1]

1. participant 배열과 completion 배열을 오름차순 정렬한다.
2. participant 배열의 값과 completion배열의 값이 같지 않을 때 participant의 값을 return 한다.
3. 마지막 참가자가 완주하지 못한 선수일 수 있기 때문에 반복문을 다 돌았을 때 끝값을 리턴한다.

• 반복문을 다 돌았을 때 끝값을 리턴하는게 생각보다 걸렸다.

• 정수가 주어지면, 그 수의 정수 제곱근을 구하는 프로그램을 작성하시오.

🍗 제한 사항

🎁 입출력 예시

• 첫째 줄에 정수 n이 주어진다. (0 ≤ n < 2^63)

• 첫째 줄에 q^2 ≥ n인 가장 작은 음이 아닌 정수 q를 출력한다.

😎 나의 풀이

n = int(input())
s = 0
e = n
while s <= e:
    mid = (s + e) // 2
    if mid**2 < n:
        s = mid + 1
    else:
        e = mid - 1
print(s)

1. 이분탐색을 이용한 풀이다. 처음에는 math함수로 아주 간단하게 풀어보려했지만 당연히 시간초과
2. 탐색 범위를 [1,2^32] 까지로 잡고 (문제의 범위에 따라)
3. start와 end를 선언해준다.
4. mid를 제곱한 값이 n보다 작으면 mid의 값을 증가시키고 s에 할당해서 범위를 좁힌다 , n보다 크면 답 후보이기 때문에 e의 값을 할당한다.
5. s를 출력하면 정답

🧵 다른 풀이

from math import floor, sqrt

n = int(input())
i = floor(sqrt(n))

while i*i < n:
    i += 1

print(i)

1. 제곱근과 i의 값을 이용한 풀이다.

• 내가 처음에 풀었던 방식을 조금 수정하면 풀 수 있었던 문제였다. 이분탐색도 좋은 방법 인 것 같다.

• 춘향이는 편의점 카운터에서 일한다.

• 손님이 2원짜리와 5원짜리로만 거스름돈을 달라고 한다. 2원짜리 동전과 5원짜리 동전은 무한정 많이 가지고 있다. 동전의 개수가 최소가 되도록 거슬러 주어야 한다. 거스름돈이 n인 경우, 최소 동전의 개수가 몇 개인지 알려주는 프로그램을 작성하시오.

• 예를 들어, 거스름돈이 15원이면 5원짜리 3개를, 거스름돈이 14원이면 5원짜리 2개와 2원짜리 2개로 총 4개를, 거스름돈이 13원이면 5원짜리 1개와 2원짜리 4개로 총 5개를 주어야 동전의 개수가 최소가 된다.

🍗 제한 사항

🎁 입출력 예시

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

• 거스름돈 동전의 최소 개수를 출력한다. 만약 거슬러 줄 수 없으면 -1을 출력한다.

😎 나의 풀이

N = int(input()) # N = 13

count = 0

while True:
  if N % 5 == 0:
    count += N//5
    break
  else:
    N -= 2
    count += 1

  if N < 0:
    break

if N < 0:
  print(-1)
else:
  print(count)

1. 그리디를 이용해서 풀었다. 5원 짜리를 최대한 많이 쓰는 방식으로 하면 된다.
2. N이 5로 나누어 떨어지면 나눈 몫 만큼 count에 추가하고 반복문 종료.
3. 나누어 떨어지지 않으면 2원을 썼다고 가정하고 N에서 2를 빼고 count에 1추가
4. N이 음수가 되면 나눌 수 없기 때문에 반복문 종료.
5. 정확하게 나눌 수 없었으면 -1 출력, 아니면 count 출력

🧵 다른 풀이

import sys
input = sys.stdin.readline

n = int(input())
if n == 1 or n == 3:
    print(-1)
    sys.exit()
t = n // 10
print(2*t + (0, 2, 1, 3, 2, 1, 3, 2, 4, 3)[n%10])

1. 튜플형식으로 뭔가 담아서 푼거같은데 잘 이해는 안간다.

• 그리디를 이용한 좋은 문제

• 1부터 N까지의 수를 이어서 쓰면 다음과 같이 새로운 하나의 수를 얻을 수 있다.

• 1234567891011121314151617181920212223...

• 이렇게 만들어진 새로운 수는 몇 자리 수일까? 이 수의 자릿수를 구하는 프로그램을 작성하시오.

🍗 제한 사항

🎁 입출력 예시

• 첫째 줄에 N(1 ≤ N ≤ 100,000,000)이 주어진다.

• 첫째 줄에 새로운 수의 자릿수를 출력한다.

😎 나의 풀이

left = [
  1,
  10,
  100,
  10000,
  100000,
  1000000,
  10000000,
  100000000,
  1000000000
]

right = [
  9,
  99,
  999,
  9999,
  99999,
  999999,
  9999999,
  99999999,
  999999999
]

N = int(input()) # N이 15면 

sum = 0

for i in range(len(left)):
  if N >= left[i] and N <= right[i]: # i가 1일 때 true
    sum += (N - left[i] + 1) * (i + 1)
    break
  else: # 1. 먼저 이거 실행 
    sum += (right[i] - left[i] + 1) * (i + 1)

# sum 에 +9 , +12 되서 sum은 21출력
print(sum)

1. 처음엔 단순하게 join으로 문자열로 풀다가 당연히 시간초과가 났다.
2. 문제의 범위 만큼 left, right 각 자릿수의 시작값과 끝값을 정의 한다.
3. 자릿수 범위 만큼 for문을 돌고 , N이 현재 자릿수 범위에 해당하면 현재 자릿수 범위에서 남은 숫자 개수 * 자릿수를 더해준다.
4. N이 현재 자릿수 범위보다 크면 현재 자리수 범위의 전체 숫자 개수 × 자리수를 더한다.
5. N이 15면 1자리수는 19까지 → 9개 × 1자리 = 9 , 2자리수는 1015까지 → 6개 × 2자리 = 12 총합 = 9 + 12 = 21자리

• 자릿수를 이해해야 풀 수 있던 문제였어서 처음에 좀 헤맸다.

• 자연수 N과 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오.

• 1부터 N까지 자연수 중에서 중복 없이M개를 고른 수열

• 고른 수열은 오름차순이어야 한다.

🍗 제한 사항

🎁 입출력 예시

• 첫째 줄에 자연수 N과 M이 주어진다. (1 ≤ M ≤ N ≤ 8)

• 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다.

• 수열은 사전 순으로 증가하는 순서로 출력해야 한다.

😎 나의 풀이

from itertools import combinations # 순열 라이브러리

# 1부터 N까지 자연수 중에서 중복 없이 M개를 고른 수열 , 오름 차순
N, M = map(int, input().split()) # N : 4 , M : 2

nums = list(range(1,N+1)) 
perm = list(combinations(nums, M))
sorted(perm) # 오름 차순

for p in perm:
    print(*p) # 튜플 p의 요소를 unpack해서 공백으로 구분해 출력

1. 순열을 써서 풀었다.
2. 1부터 N까지 배열을 만들고 만든 배열을 가지고 M개를 순열로 뽑는다.
3. 오름차순 정렬
4. 뽑은 요소들은 튜플의 형태이기 때문에 *을 붙여서 출력한다.

🧵 다른 풀이

def backtracking(arr):
    if len(arr) == m:
        print(' '.join(map(str, arr)))
        return
    for i in range(arr[-1] if arr else 1, n + 1):
        if i not in arr:
            arr.append(i)
            backtracking(arr)
            arr.pop()


n, m = map(int, input().split())
backtracking([])

1. 백트래킹으로 푼 풀이

• 다른 풀이를 보니 dfs나 백트래킹으로도 풀 수 있던 문제였다.

• 루트 없는 트리가 주어진다. 이때, 트리의 루트를 1이라고 정했을 때, 각 노드의 부모를 구하는 프로그램을 작성하시오.

🍗 제한 사항

🎁 입출력 예시

• 첫째 줄에 노드의 개수 N (2 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N-1개의 줄에 트리 상에서 연결된 두 정점이 주어진다.

• 첫째 줄부터 N-1개의 줄에 각 노드의 부모 노드 번호를 2번 노드부터 순서대로 출력한다.

😎 나의 풀이

import sys
sys.setrecursionlimit(10**6) # 런타임에러 방지
N = int(sys.stdin.readline()) # 노드의 개수 N

adj = [[] for _ in range(N)] # 인접 노드 담아둘 adj

for i in range(N - 1): # N-1개의 줄에 입력을 받는다.
    a, b = map(int, sys.stdin.readline().split())
    adj[a - 1].append(b - 1) # 0부터 N-1
    adj[b - 1].append(a - 1)

visit = [False] * N # 방문체크 배열
parent = [0] * N # 부모노드를 담아둘 배열

# DFS
def dfs(u): 
  visit[u] = True # 방문한 노드에 True로 업데이트
  for v in adj[u]: # 인접노드 방문
    if not visit[v]: # 방문하지 않았다면
      parent[v] = u # parent배열의 해당 노드의 값을 u(부모)의 값으로 업데이트
      dfs(v) # 재귀호출 

dfs(0) # 1번 노드부터 탐색

for i in range(1, N): # 2번노드부터 출력 
  print(parent[i] + 1) # +1 을 해야 올바르게 출력됨

1. DFS 알고리즘 재귀호출을 이용한 풀이다. **(주석 확인!)

**

🧵 다른 풀이

from collections import deque # deque(덱) 모듈을 불러와, 스택구현에 사용
import sys                                      
input = sys.stdin.readline       

N = int(input()) # 노드의 개수 N
visited = [False] * (N + 1) # 방문체크 배열, 인덱스 맞추기 위해 N+1 사용
answer = [0] * (N + 1) # 각 노드의 부모 노드를 저장할 리스트
E = [[] for _ in range(N + 1)] # 인접 리스트, 1번부터 N번까지 각 노드에 연결된 노드 저장

for i in range(N - 1): # 트리이므로 간선의 개수는 N-1개, 각 간선 정보를 입력받음
    S, D = map(int, input().split()) # S,D 입력 받음
    E[S].append(D) # S와 연결된 노드 리스트에 D 추가
    E[D].append(S) # D와 연결된 노드 리스트에 S 추가 (양방향 그래프이므로)

# DFS 스택 구현
def dfs(E, v, visited):
    visited[v] = True # 방문한 노드 True로 업데이트
    stack = deque([v]) # 스택에 시작 노드 v를 넣음

    while stack: # 스택이 빌 때까지 반복
        x = stack.pop() # 스택의 마지막 원소 x를 꺼냄 (후입선출)
        for i in E[x]: # 노드 x에 인접한 모든 노드를 순회
            if not visited[i]: # 방문하지 않았다면
                stack.append(i) # 노드 i를 스택에 추가 (나중에 방문할 예정)
                visited[i] = True # 노드 i를 방문 처리
                answer[i] = x # 노드 i의 부모 노드를 x로 기록

dfs(E, 1, visited) # 1번 노드를 시작으로 DFS 실행

for i in range(2, N + 1): # 2번 노드부터 N번 노드까지 부모 노드를 출력 (1번은 루트이므로 출력하지 않음)
    print(answer[i]) # 부모 노드 출력

1. DFS풀이 이지만, 스택으로 구현한 풀이이다. (주석 확인)

• 답을 제출했을 때 런타임 에러가 발생해서 보니 재귀함수의 리밋을 설정하지 않아서였다. 다른 분의 풀이를 보니 스택으로 구현하는 방법을 쓰면 런타임 에러도 안 걸리고 익숙해지면 좋은 방법인 것 같다.

• 신종 바이러스인 웜 바이러스는 네트워크를 통해 전파된다. 한 컴퓨터가 웜 바이러스에 걸리면 그 컴퓨터와 네트워크 상에서 연결되어 있는 모든 컴퓨터는 웜 바이러스에 걸리게 된다.

• 예를 들어 7대의 컴퓨터가 <그림 1>과 같이 네트워크 상에서 연결되어 있다고 하자. 1번 컴퓨터가 웜 바이러스에 걸리면 웜 바이러스는 2번과 5번 컴퓨터를 거쳐 3번과 6번 컴퓨터까지 전파되어 2, 3, 5, 6 네 대의 컴퓨터는 웜 바이러스에 걸리게 된다. 하지만 4번과 7번 컴퓨터는 1번 컴퓨터와 네트워크상에서 연결되어 있지 않기 때문에 영향을 받지 않는다.

• 어느 날 1번 컴퓨터가 웜 바이러스에 걸렸다. 컴퓨터의 수와 네트워크 상에서 서로 연결되어 있는 정보가 주어질 때, 1번 컴퓨터를 통해 웜 바이러스에 걸리게 되는 컴퓨터의 수를 출력하는 프로그램을 작성하시오.

🍗 제한 사항

🎁 입출력 예시

• 첫째 줄에는 컴퓨터의 수가 주어진다. 컴퓨터의 수는 100 이하인 양의 정수이고 각 컴퓨터에는 1번 부터 차례대로 번호가 매겨진다. 둘째 줄에는 네트워크 상에서 직접 연결되어 있는 컴퓨터 쌍의 수가 주어진다. 이어서 그 수만큼 한 줄에 한 쌍씩 네트워크 상에서 직접 연결되어 있는 컴퓨터의 번호 쌍이 주어진다.

• 1번 컴퓨터가 웜 바이러스에 걸렸을 때, 1번 컴퓨터를 통해 웜 바이러스에 걸리게 되는 컴퓨터의 수를 첫째 줄에 출력한다.

😎 나의 풀이

N = int(input()) # 컴퓨터의 수 
M = int(input()) # 연결된 컴퓨터 쌍의 수

adj = [[] for _ in range(N)] # 인접리스트 선언

for _ in range(M):
  a, b = map(int, input().split())
  adj[a - 1].append(b - 1) # 0 부터 N-1 까지로 사용하려면 -1 해줌
  adj[b - 1].append(a - 1)

visit = [False] * N # visit 배열 초기화
# DFS 
def dfs(u):
  visit[u] = True # 방문한 노드 True로 업데이트

  for v in adj[u]: # 인접노드 검사
    if not visit[v]:
      dfs(v) # 방문 안한 노드 재귀 호출

dfs(0) # 1부터 수행해서 도달할 수 있는 노드 검사
count = 0
for i in range(1, N): # 0번 제외한 1번부터 N-1번 컴퓨터 중 
  if visit[i]: # 방문했다면 (True)
    count += 1 # count + 1

print(count) # count값 출력

1. DFS 알고리즘 재귀호출을 이용한 풀이다.
2. 인접 노드들을 adj에 담아 주고 , 방을 체크할 visit 배열을 초기화 한다.
3. DFS 함수에서 방문한 노드를 True로 업데이트 해준다.
4. 인접 노드를 검사를 하는데 방문 안한 노드라면 재귀 호출을 통해 다시 DFS 함수를 실행해준다.
5. 문제에서 1부터 시작해서 노드를 검사한다고 했으니 dfs(0)을 호출하여 함수를 시작해준다.
6. 개수를 세줄 count 변수를 초기화 하고, 0번을 제외한 N-1번 컴퓨터 중 방문한 노드만 count에 개수를 세주고 count를 출력하면 된다.

🧵 다른 풀이

import sys
from collections import deque
N = int(sys.stdin.readline())
M = int(sys.stdin.readline())
net = [[] for _ in range(N+1)]
for _ in range(M):
    a, b = map(int, sys.stdin.readline().split())
    net[a].append(b)
    net[b].append(a)

def bfs():
    q = deque()
    count = 0 # 감염된 컴퓨터 수
    q.append(1) # 1번 컴퓨터로부터 시작
    visited[1] = True # 1번 컴퓨터 감염완료
    while q:
        cur = q.popleft()
        for i, val in enumerate(net[cur]): # 감염된 컴퓨터로부터 연결된 컴퓨터들에서
            if visited[val]==False: # 감염되지 않았다면
                q.append(val) # 감염리스트에 추가
                visited[val] = True # 감염완료
                count += 1 # 감염된 컴퓨터 수 1 증가
    print(count) # 모두 감염되었을 때 출력

visited = [False for _ in range(N+1)]
bfs()

1. BFS를 이용한 풀이이다.

• 이 문제는 DFS , BFS , 그래프 등 다양한 방법으로 풀 수 있는데 개인적으로는 DFS를 이용한 풀이가 가장 깔끔한 것 같다.

프로젝트를 진행하면서 express로도 서버를 구축해봤고 , NestJS로도 구축을 해보았는데, 이 두 개의 프레임워크를 개발에 사용하면서 느낀점과 차이점을 간단하게 비교해보려고 한다.

✔ Express

const express = require('express');
const app = express();
const port = 3000;

// GET 라우트
app.get('/', (req, res) => {
  res.send('Hello, World!');
});

// 서버 시작
app.listen(port, () => {
  console.log(`Server is running at http://localhost:${port}`);
});

❗ 장점

• 위의 코드 처럼 딱 이정도 세팅만 하면 서버를 실행할 수 있어서 간편하고 빠르게 서버 애플리케이션을 구성할 수 있는 장점이 있다.

• 미들웨어를 통해 필요한 기능을 추가할 수 있다.

❗ 단점

• 타입 안정성 부족

  Express는 기본적으로 JavaScript로 작성되어 있어, 타입 안정성이 보장되지 않는다. TypeScript를 사용하려면 별도의 설정이 필요하고, Express 프레임워크 내부에서 선언된 Body, Query, Params, Cookies 타입 같은 경우에는 Express.Request를 확장을 해줘야 한다.

• 프로젝트가 커질수록 관리하기 어렵다.

  • 내가 경험한 Express는 정말 코드 몇줄로 서버를 실행시키는 대신 뭔가 틀이라던지 프레임워크에서 제공해주는 것들이 많이 빈약한 느낌이였다. 그래서 Layered Architecture를 도입해서 프로젝트의 구조를 맞추고 해당 프로젝트만의 틀을 짰던 기억이 있다.
  • Express는 기본적으로 Middleware 기반으로 돌아가기 때문에 Guard 라던지 Interceptor 등을 전부 Middelware라고 부른다. 그래서 개발자가 알아서 라이프사이클을 직접 조정을 해줘야 한다. 당연히 프로젝트가 커지면 커질수록 관리해야하는 부분이 커질 것이다.

app.use((req, res, next) => {
  console.log('Request received');
  next(); // 다음 미들웨어로 넘어감
});

위 코드처럼 next()로 다음 미들웨어로 넘기는 방식으로 구성되어있다.

✔ NestJS

• NestJS의 Documentation에 나와있는 철학을 보면 이게 어떤 프레임워크인지 대략 파악할 수 있는데 However, while plenty of superb libraries, helpers, and tools exist for Node (and server-side JavaScript), none of them effectively solve the main problem of architecture. 라고 표현했다. 한마디로 아키텍처적인 문제를 효과적으로 해결 할 수 있는 Node.js 관련 도구가 없다는 것이다.

  • 다음 문단을 보면 NestJS는 개발자와 팀이 테스트하기 쉽고, 확장 가능하고, 느슨하게 결합되고, 쉽게 유지 관리할 수 있는 애플리케이션을 만들 수 있는 즉시 사용 가능한 애플리케이션 아키텍처를 제공한다고 하고, Angular에서 많은 영감을 받았다고 한다. (뭔가 많은 문제들을 해결한 것? 같은 느낌이다.)

❗ 장점

• 모듈화된 아키텍처: 대규모 애플리케이션을 모듈 단위로 나눠서 관리할 수 있어 확장성과 유지보수가 용이하다.

• 타입 안전성: TypeScript를 기본적으로 지원하여, 코드 작성 시 강력한 타입 검사를 제공한다.
• 의존성 주입: 의존성 주입(Dependency Injection) 패턴을 사용하여 객체 간의 관계를 효율적으로 관리할 수 있다.
• 내장된 기능: 라우팅, 미들웨어, 예외 처리 등 다양한 기능이 내장되어 있다.
• 프로젝트를 세팅할 때 구조가 잡혀있어서 다른 NestJS프로젝트의 코드를 보기 편하고 이식성이 높다고 할 수 있다.

• 위 사진처럼 NestJS의 라이프사이클이 구성되어있다.

❗ 단점

• Express와는 다르게 러닝커브가 있다. TypeScript에 익숙하지 않은 개발자 또는 나도 공부할 때 이해하는데 시간이 걸렸던 데코레이터 , 의존성 주입 , 제어역전 등 알아야할 개념들이 있어서 학습이 필요하다.

• 제공해주는 설정들이 Express에 비해 많아서 처음에는 복잡하게 느껴질 수 있다.

✔ 결론

Express를 처음 프로젝트에 사용해보고 정말 뭐가 제공되는 것이 없구나를 느꼈다가 NestJS를 사용해보고 초반 세팅부터 너무 편했던 기억이 있다. NestJS도 내부적으로는 Express로 이루어져 있고, 확장판이라고 생각하면 좋을 것 같다. NestJS를 공부하면 공부할 수록 NodeJs를 이용한 서버 개발에는 정말 좋은 프레임워크라고 생각이 되서 앞으로도 NestJS 를 더욱 이용할 것 같다.

https://nodejs.org/ko/about (Express 공식문서) https://docs.nestjs.com/ (NestJS 공식문서)

• 케빈 베이컨의 6단계 법칙에 의하면 지구에 있는 모든 사람들은 최대 6단계 이내에서 서로 아는 사람으로 연결될 수 있다. 케빈 베이컨 게임은 임의의 두 사람이 최소 몇 단계 만에 이어질 수 있는지 계산하는 게임이다.

• 예를 들면, 전혀 상관없을 것 같은 인하대학교의 이강호와 서강대학교의 민세희는 몇 단계만에 이어질 수 있을까?

• 천민호는 이강호와 같은 학교에 다니는 사이이다. 천민호와 최백준은 Baekjoon Online Judge를 통해 알게 되었다. 최백준과 김선영은 같이 Startlink를 창업했다. 김선영과 김도현은 같은 학교 동아리 소속이다. 김도현과 민세희는 같은 학교에 다니는 사이로 서로 알고 있다. 즉, 이강호-천민호-최백준-김선영-김도현-민세희 와 같이 5단계만 거치면 된다.

• 케빈 베이컨은 미국 헐리우드 영화배우들 끼리 케빈 베이컨 게임을 했을때 나오는 단계의 총 합이 가장 적은 사람이라고 한다.

• 오늘은 Baekjoon Online Judge의 유저 중에서 케빈 베이컨의 수가 가장 작은 사람을 찾으려고 한다. 케빈 베이컨 수는 모든 사람과 케빈 베이컨 게임을 했을 때, 나오는 단계의 합이다.

• 예를 들어, BOJ의 유저가 5명이고, 1과 3, 1과 4, 2와 3, 3과 4, 4와 5가 친구인 경우를 생각해보자.

• 1은 2까지 3을 통해 2단계 만에, 3까지 1단계, 4까지 1단계, 5까지 4를 통해서 2단계 만에 알 수 있다. 따라서, 케빈 베이컨의 수는 2+1+1+2 = 6이다.

• 2는 1까지 3을 통해서 2단계 만에, 3까지 1단계 만에, 4까지 3을 통해서 2단계 만에, 5까지 3과 4를 통해서 3단계 만에 알 수 있다. 따라서, 케빈 베이컨의 수는 2+1+2+3 = 8이다.

• 3은 1까지 1단계, 2까지 1단계, 4까지 1단계, 5까지 4를 통해 2단계 만에 알 수 있다. 따라서, 케빈 베이컨의 수는 1+1+1+2 = 5이다.

• 4는 1까지 1단계, 2까지 3을 통해 2단계, 3까지 1단계, 5까지 1단계 만에 알 수 있다. 4의 케빈 베이컨의 수는 1+2+1+1 = 5가 된다.

• 마지막으로 5는 1까지 4를 통해 2단계, 2까지 4와 3을 통해 3단계, 3까지 4를 통해 2단계, 4까지 1단계 만에 알 수 있다. 5의 케빈 베이컨의 수는 2+3+2+1 = 8이다.

• 5명의 유저 중에서 케빈 베이컨의 수가 가장 작은 사람은 3과 4이다.

• BOJ 유저의 수와 친구 관계가 입력으로 주어졌을 때, 케빈 베이컨의 수가 가장 작은 사람을 구하는 프로그램을 작성하시오.

🍗 제한 사항

🎁 입출력 예시

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

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

😎 나의 풀이

import sys
from collections import deque

input = sys.stdin.readline

N,M = list(map(int, input().split()))

graph = [[] for _ in range(N)]

for _ in range(M):
  a, b = list(map(int, input().split()))

  graph[a - 1].append(b - 1)
  graph[b - 1].append(a - 1)

def BFS(graph, start):
  # i를 시작점으로 하는 BFS 수행
  # 각 노드까지의 최단거리 구해서 다 합한다.
  visit = [False] * N
  # 최단거리 담아둘 배열
  dist = [-1] * N

  # BFS 큐 생성
  queue = deque([start])
  # i가 큐에 있으므로 True (방문함)
  visit[start] = True
  # i번째 값에는 0으로 설정 (자기자신 거리)
  dist[start] = 0  

  while queue:
    u = queue.popleft() # 현재 노드 꺼내기

    for v in graph[u]: # 연결노드 탐색
      if not visit[v]: # 방문하지 않았으면 
        queue.append(v) # 큐에 추가
        visit[v] = True # 방문 표시
        dist[v] = dist[u] + 1 # 최단거리 업데이트 (v까지 가는 거리는 현재 u까지 온 거리 + 1) 

  return sum(dist) # 모든 거리의 합 리턴 (케빈베이컨 수)

# 케빈베이컨 수의 최솟값 저장 변수 (초기값: 무한대)
min_kevin_bacon = float('inf')
# 가장 작은 케빈베이컨 수를 가진 사람 (초기값 -1)
min_person = -1

for i in range(N):
  kevin_bacon = BFS(graph,i) # i번째 사람 케빈베이컨 수 계산

  # i번째 사람의 케빈베이컨 수를 계산한 시점에서 
  # 현재까지의 min_kevin_bacon 값보다 i번째 사람의 케빈베이컨 수가 더 작다면 
  if kevin_bacon < min_kevin_bacon:
    min_kevin_bacon = kevin_bacon # i번째 사람의 케빈베이컨으로 최솟값 갱신
    min_person = i # 가장 작은 케빈베이컨을 갖는 사람의 번호가 담긴다.

# 결과 출력 (1부터 시작하는 번호로 변환)
print(min_person + 1)

1. 이번 문제 풀이에선 BFS를 함수로 빼서 사용했다.
2. N,M을 입력 받고 , 노드를 담아둘 graph 선언
3. a, b로 각 노드들을 graph에 추가한다. (양방향)
4. BFS를 수행하는데 문제에서 요구하는 각 노드까지의 최단거리를 구해서 합하면 된다.
5. 방문 배열인 visit을 False로 초기화 하고, 최단거리를 담아둘 배열인 dist를 -1로 초기화 한다.
6. BFS를 위한 큐를 만들고, 현재 시점에서 i가 큐에 있으므로 True로 visit값을 바꾸고, 자기자신의 거리는 0이므로 dist의 값을 0으로 만든다.
7. queue가 없어질 때까지 반복한다. 현재 노드를 꺼내서 u에 저장
8. 연결된 노드를 탐색하고 방문하지 않았으면 큐에 추가하고 해당 노드를 방문했다는 의미로 visit값을 True로 업데이트 , 최단거리인 dist의 값을 +1 해서 업데이트 해준다.
9. 모든 거리의 합을 리턴해준다.
10. 케빈베이컨 수를 계산해주면 된다.

🧵 다른 풀이

from collections import deque

N, M = map(int, input().split())

arr = [[] for _ in range(N+1)]
for i in range(M):
    u, v = map(int, input().split())
    arr[u].append(v)
    arr[v].append(u)

def bfs(start):
    visited = [-1] * (N + 1)

    q = deque()
    q.append(start)
    visited[start] = 0

    while q:
        node = q.popleft()

        for next_node in arr[node]:
            if visited[next_node] == -1:
                visited[next_node] = visited[node] + 1
                q.append(next_node)
    total = sum(visited)
    return total

min_total = float("INF")
ans = 0
for i in range(1, N+1):

    total = bfs(i)
    if total < min_total:
        min_total = total
        ans = i

print(ans)

1. BFS를 이용한 풀이이다.

• BFS를 이용해서 최단거리까지 구하는 방법은 처음 알게되었다. 좀 더 많이 풀어봐야할 것 같다.

• 방향 없는 그래프가 주어졌을 때, 연결 요소 (Connected Component)의 개수를 구하는 프로그램을 작성하시오.

🍗 제한 사항

🎁 입출력 예시

• 첫째 줄에 정점의 개수 N과 간선의 개수 M이 주어진다. (1 ≤ N ≤ 1,000, 0 ≤ M ≤ N×(N-1)/2) 둘째 줄부터 M개의 줄에 간선의 양 끝점 u와 v가 주어진다. (1 ≤ u, v ≤ N, u ≠ v) 같은 간선은 한 번만 주어진다.

• 첫째 줄에 연결 요소의 개수를 출력한다.

😎 나의 풀이

import sys
from collections import deque

input = sys.stdin.readline

N,M = list(map(int, input().split()))

# 인접리스트 (각 노드가 어떤 노드랑 연결됐는지 저장)
adj = [[] for _ in range(N)]

for _ in range(M): # M개의 간선 입력받음
  u, v = list(map(int, input().split()))

  # 인접 노드 추가
  # 0번부터 시작하는 리스트를 사용하기 위해 -1 해줌
  adj[u - 1].append(v - 1)
  adj[v - 1].append(u - 1)

# visit 배열
visit = [False] * N
# 연결 요소의 개수
count = 0

for i in range(N): # 0부터 N-1까지 확인
  if visit[i]: # visit 배열에 체크가 되어있으면 넘어간다. (이미 방문한 노드 건너뜀)
    continue

  # bfs를 시작
  # 시작점(새로운 연결 요소)을 찾았기 때문에 count + 1
  count += 1

  # BFS를 위한 큐 선언
  queue = deque([i])
  # visit 배열에 방문 체크
  visit[i] = True

  # 큐가 빌때까지 반복
  while len(queue) != 0:
    # 큐에서 노드를 하나 꺼내온다.
    u = queue.popleft()

    # 현재 노드와 연결된 노드를 탐색.
    for v in adj[u]:
      # 방문안한 노드들만 확인하고 싶기 때문에
      # visit 배열에 체크가 안되어있는 노드들을 큐에 넣어준다.
      if not visit[v]: # 방문하지 않았다면
        # 큐에 넣는다.
        queue.append(v)
        # 방문 체크
        visit[v] = True

print(count)

1. BFS를 이용한 풀이

🧵 다른 풀이

import sys
sys.setrecursionlimit(10**6)
input = sys.stdin.readline

# dfs 함수
def dfs(graph, v, visited):
    visited[v] = True
    for i in graph[v]:
        if not visited[i]:
            dfs(graph, i, visited)

n, m = map(int, input().split()) # 정점의 개수, 간선의 개수
graph = [[] for _ in range(n+1)]
for i in range(m):
    u, v = map(int, input().split())
    graph[u].append(v)
    graph[v].append(u)

count = 0 # 연결 노드의 수
visited = [False] * (n+1)
for i in range(1, n+1):
    if not visited[i]:
        dfs(graph, i, visited)
        count += 1 # dfs 한 번 끝날 때마다 count+1

print(count)

1. DFS를 이용한 풀이이다.

• BFS의 개념을 공부하고 풀어봤는데 BFS를 활용할 수 있는 기본적인 문제 인 것 같다.

• N+1개의 I와 N개의 O로 이루어져 있으면, I와 O이 교대로 나오는 문자열을 PN이라고 한다.

• P1 IOI

• P2 IOIOI

• P3 IOIOIOI

• PN IOIOI...OI (O가 N개)

• I와 O로만 이루어진 문자열 S와 정수 N이 주어졌을 때, S안에 PN이 몇 군데 포함되어 있는지 구하는 프로그램을 작성하시오.

🍗 제한 사항

🎁 입출력 예시

• 첫째 줄에 N이 주어진다. 둘째 줄에는 S의 길이 M이 주어지며, 셋째 줄에 S가 주어진다.

• S에 PN이 몇 군데 포함되어 있는지 출력한다.

😎 나의 풀이

N = int(input()) # 2
M = int(input()) # 13
S = input() # "OOIOIOIOIIOII"

cursor, count, result = 0, 0, 0

while cursor < (M - 1): # cursor가 M-1 보다 작을 동안 실행 (끝까지)
    if S[cursor:cursor + 3] == 'IOI': # 현재 위치부터 3글자를 잘라서 "IOI"인지 확인
        count += 1 # IOI면 count + 1
        cursor += 2 # cursor는 두칸 이동(I가 겹침)
        if count == N: # IOI가 N번 연속해서 나오면 result + 1
            result += 1
            count -= 1 # 다음 패턴을 위해 하나 줄인다.(다음 IOI 체크)
    else: # IOI가 아니면 cursor를 한 칸 이동한다.
        cursor += 1
        count = 0 # IOI 패턴이 끊기므로 count = 0 리셋

print(result)

1. 현재 위치를 의미하는 cursor, "IOI"가 몇번나왔는지 세는 count, 찾은 패턴의 개수를 나타내는 result를 초기화해준다.
2. 최소 3글자를 비교해야하므로 M - 1까지 반복
3. 현재 위치부터 3글자를 잘라서 "IOI"인지 확인한다.
4. IOI면 count에 1을 더해주고 cursor는 두칸을 이동한다.
5. count가 N번 연속해서 나오면 result에 1을 더해주고 다음 IOI를 체크하기 위해 count - 1을 한다.
6. IOI가 아니면 cursor를 한칸 이동하고, count는 IOI패턴이 끊기므로 0으로 리셋한다.
7. 누적된 result 출력

🧵 다른 풀이

N = int(input())
M = int(input())
S = input()

# 해쉬 값을 계산 하기 위한 준비물
mod = 1e9 + 7
po = [0] * M # 제곱한 값들 저장 배열
po[0] = 1 # 31^0 = 1 이기 때문에 1로 설정
for i in range(1, M):
  po[i] = po[i - 1] * 31 % mod # 이전 값에 31 곱하고 mod 나머지 연산

# Pn 만들기
Pn = "I"
for i in range(N):
  Pn += "OI"

# Pn의 해쉬값 계산
# 0에서 시작해서 매번 한자리씩 올림을 하고 현재 자릿수를 더해준다.
Pn_hash = 0
for i in range(len(Pn)):
  Pn_hash *= 31
  Pn_hash %= mod

  # A를 1로 했을 때 알파벳 값을 구하기 위해 ASCII 코드로 계산하면 I,O의 값을 알 수 있다.
  Pn_hash += ord(Pn[i]) - ord('A') + 1
  Pn_hash %= mod


# S[0:len(Pn)] S의 맨 처음 부분문자열은 무조건 계산해줘야 한다.(값을 다른데서 가져올 수 없음)
S_hash = 0
for i in range(len(Pn)):
  S_hash *= 31
  S_hash %= mod

  S_hash += ord(S[i]) - ord('A') + 1
  S_hash %= mod

# S의 부분 문자열들의 해쉬 값 계산
count = 0 # 답 출력 카운트
for i in range(0, M - len(Pn) + 1):
  if S_hash == Pn_hash:
    count += 1

  # S_hash 갱신
  # (OIOIO - 15*31^4)
  largest = ord(S[i]) - ord('A') + 1
  S_hash += mod - largest * po[len(Pn) - 1] % mod
  S_hash %= mod

  # 한자리수 올림
  S_hash *= 31
  S_hash %= mod

  # 새로 오는 알파벳 더해줌 
  # 맨 마지막은 새로 갱신할 필요없어서 맨 마지막 전까지 갱신 
  if i + len(Pn) < M:
    S_hash += ord(S[i + len(Pn)]) - ord('A') + 1
    S_hash %= mod
print(count)

1. 해쉬를 이용한 풀이이다.

• 해쉬 개념을 공부해서 풀이를 해보려고 했지만 막상 어려워서 풀이를 보고 코드만 이해했다. 😂