[내일배움캠프 4-5일] 코드카타 문제, 스쿼드 문제, bfs

로또의 최고 순위와 최저 순위

def solution(lottos, win_nums):
    # 맞은 당첨 숫자의 개수를 카운트
    cnt = 0
    # 0이 몇 개인지 카운트
    zero_cnt = 0

    for i in lottos:
        if i == 0:
            zero_cnt += 1
        elif i in win_nums:
            cnt += 1

    # 개수에 따른 순위 딕셔너리로 저장
    dict = {6:1, 5:2, 4:3, 3:4, 2:5, 1:6, 0:6}

    answer = []
    answer.extend([dict[cnt + zero_cnt], dict[cnt]]) # answer.extend([3, 5])
    return answer

쉬운 문제였지만 extend가 생소해서 가져와봤음.

append로 하나씩 추가하지 않고 요소를 전부 가져올 수 있다.

append는 y 자체를 원소로 넣고, extend는 y의 각 항목을 넣는다.

 

append와 extend의 차이 : https://m.blog.naver.com/wideeyed/221541104629

[Python] list append()와 extend() 차이점

---

바이러스

def bfs(start):
    visited = [start]
    queue = deque([start])

    while queue:
        current = queue.popleft()
        for i in graph[current]:
            if i not in visited:
                queue.append(i)
                visited.append(i)
    return len(visited)

bfs로 풀어봤다.

visited 리스트를 만들어서 start(이 문제는 무조건 1)를 넣어놓고 평소 했던 것처럼 인접한 이웃부터 탐색.

graph에서 현재 pop된 노드(current)의 이웃을 다 찾고, 그 이웃이 visited에 없다면 queue와 visited에 모두 추가한다.

반환은 visited 개수를 하면 됨.(여기서 1이 포함되는데 아래에서 따로 설명)

 

강의에서 배운대로 그냥 하던대로 하고 gpt한테 효율성 검사를 받음.
그런데 visited 리스트를 set로 바꾸라는 피드백을 받았다.

def bfs(start):
    visited = set()
    queue = deque([start])
    visited.add(start)

    while queue:
        current = queue.popleft()
        for i in graph[current]:
            if i not in visited:
                queue.append(i)
                visited.add(i)
    return len(visited)

놀랍게도 속도가 더 느려짐.

집합을 사용할 경우 탐색의 과정을 줄일 수 있다는 점은 이해했다.

그런데 이번 문제는 컴퓨터의 수가 100 이하로 제한이 걸려있고, 입력 데이터의 크기가 작다보니 list가 더 빠른듯 하다.

이유를 찾아보니 집합의 경우 해시 테이블을 사용하여 구현되므로, 삽입과 삭제 시 오버헤드가 존재하기 때문이라고 한다. 리스트는 순차 탐색이기 때문에 작은 데이터에서 오버헤드가 적은 것.

하지만 입력데이터의 크기가 커짐에 따라 set를 고려하는 것은 좋은 방법인 것 같다.

 

# 그래프 초기화
# 0번 인덱스는 안쓰는 역할이므로 N+1로 해준다
graph = [[] for i in range(N+1)]

# 그래프 구현 파트
for _ in range(S):
    a, b = map(int, input().split())
    graph[a].append(b)
    graph[b].append(a)

# 1번에 의해 감염된 컴퓨터 수를 출력해야 함
# 1번도 visited에 입력되기 때문에 자기 자신은 -1 해준다
print(bfs(1) - 1)

이후 그래프를 구현.
그런데 아까 말했듯이 자기 자신인 1도 visited에 저장됨.
우리는 1 에 의해 감염된 컴퓨터의 수를 필요로 하기 때문에 마지막에 -1을 해준다.

 

import sys
from collections import deque

input = sys.stdin.readline

def bfs(start):
    visited = set()
    queue = deque([start])
    visited.add(start)

    while queue:
        current = queue.popleft()
        for i in graph[current]:
            if i not in visited:
                queue.append(i)
                visited.add(i)
    return len(visited)

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

# 그래프 초기화
# 0번 인덱스는 안쓰는 역할이므로 N+1로 해준다
graph = [[] for i in range(N+1)]

# 그래프 구현 파트
for _ in range(S):
    a, b = map(int, input().split())
    graph[a].append(b)
    graph[b].append(a)

# 1번에 의해 감염된 컴퓨터 수를 출력해야 함
# 1번도 visited에 입력되기 때문에 자기 자신은 -1 해준다
print(bfs(1) - 1)

최종 코드

---

오늘의 회고

복습도 잘 했고 문제를 풀면서 bfs, dfs 부분에 대해 어느정도 이해를 완료했다.

진도는 나가지 못했지만 그래도 배웠던 내용들이 더 익숙해지고 있다.

 

내일의 목표는 쉬면서 코드카타 풀기