[TIL] 99클럽 코테 스터디 4일차 TIL + BFS, DFS

✅ 오늘의 TODO

- 알고리즘 오늘의 문제 ✅ (3h 30m)

- 알고리즘 어제 챌린저 문제 ✅ (어제 + 40m)

- 알고리즘 예전에 푼 문제 기억 되살리기 🔜 (2h)

- 혼공네트워크 2장 물리 계층 ✅ (2h)

- 컴피

  - 위치 기능 구현 🔜

  - 컴피존 설정 화면 구현 🔜

- 13주차 주간 회고 ❌

- TIL 작성 ✅ (20m)

 

🌼 오늘의 문제 - 백준 2468. 안전 영역

[Algorithm] 백준 2468 안전 영역 | BFS, DFS

문제 번호가 너무 마음에 드는 오늘의 문제는 BFS/DFS로 그래프 탐색 문제였다. 이 풀이 과정이 꽤 길고 이해가 필요했어서 문제를 푸는데 30분, 결국 풀이를 보고 이해하는 데 1시간 30분, 글로 써 내려가는 데 1시간 30분 정도가 걸렸다. 총 3시간 30분이 소요된.. 생각보다 오랫동안 문제를 풀었던 오늘 문제. 하지만 덕분에 이전부터 헷갈리던 BFS/DFS 풀이가 좀 더 이해되기 시작했다. 야호. !

 

 

💻 네트워크 - 물리 계층, 데이터 링크 계층

[네트워크] NIC와 케이블, 허브, 스위치

 

 

🌼 어제의 챌린저 문제 - 백준 1450. 냅색 문제

이진 탐색과 MITM(Meet in the Middle) 중간에서 만나기 알고리즘으로 풀이하는 문제였다. 가방에 들어갈 수 있는 최대 무게와 물건들의 무게를 가지고, 넣을 수 있는 조합의 개수를 구하는 문제였다. 나는 처음에 최대 무게에서 물건들의 무게를 빼는 방식으로 접근했는데, 아니었다! 오히려 가지고 있는 물건들로 만들 수 있는 합을 구하고, 최대 무게보다 작은 값들을 찾아내는 방식이었다.

 

모든 배열의 값으로 부분집합의 합을 구하면 n의 제한이 30이라지만, 2^30 = 1,073,741,824 개의 합을 구해야한다. 계산은 훨씬 더 많이 해야겠지? ^^ 그래서 배열을 반으로 나누어 각각의 부분집합의 합을 구하고, 한쪽을 순환하면서 다른 쪽에서 몇 개까지 더할 수 있는지 찾는 과정이다. 휴.. 확실히 챌린저 문제는 챌린저 문제인가보다! 알고리즘 새내기인 나에게는 이해하는데 시간이 많이 필요했다ㅎㅎ.. 하하..

from bisect import bisect_right


def subset_sum(arr):
    result = []
    n = len(arr)

    # << 는 비트 연산자 - n만큼 비트를 움직임 2^n
    # arr 가 가질 수 있는 모든 부분집합
    for i in range(1 << n):
        total = 0

        # i로 나타낸 부분집합에서 포함하는 값만 더하기
        # ex, 101 이라면 arr[2] + arr[0] 를 하기 위해 101을 순환
        for j in range(n):
            if i & (1 << j):
                total += arr[j]

        result.append(total)
    return result


n, c = map(int, input().split())
weights = list(map(int, input().split()))

left = weights[: n // 2]   # 왼쪽 반
right = weights[n // 2 :]  # 오른쪽 반

sum_left = subset_sum(left)    # 왼쪽 배열의 부분집합 합 리스트
sum_right = subset_sum(right)  # 오른쪽 배열의 부분집합 합 리스트

sum_right.sort()

print(sum_left)
print(sum_right)

count = 0
# (x + y ≤ C)인 모든 조합의 수 구하기
for x in sum_left:
    # x + y <= c → y <= c - x
    # 왼쪽 합 + 오른쪽 합 <= c 를 만족하려면 오른쪽 합 <= c - 왼쪽 합
    # bisect_right(a, b)는 a에서 b 이하인 값이 몇 개인지
    count += bisect_right(sum_right, c - x)

print(count)

 

 

 

🍀 오늘의 회고

밤 11시 반.. 그림에게서 소비짹 코드를 물어보겠다는 연락이 왔다. 후후.. 벌써 5개월 전의 코드라 긴장이 됐다. 설계 + 기능을 확장했을 때의 고려 + 테스트 용이성에 대한 칭찬(?)을 해주었다. 그리고 그림만의 그런 이야기와 질문들이 있는데.. UIKit을 사용한 CollectionView에서의 질문과 각각의 Coordinator를 만든 이유에 대한 이야기였다. 화면쪽은 거의 보노가 구현해서 코드를 자세히 들여다보지 못했는데, 나도 이번 계기로 다시 봐보면 좋을 것 같다. 추가로 환율 실시간 그래프를 만들어 달라고 했다 ^^ 하하.. (개발자 입장이냐고, 사용자 입장이냐고 물었지만 사용자 입장이라고 해서 생각해보겠다고 했다 ㅎㅎ..) 나도 소비짹에 남는 미련이 많아서 다시 봐볼 좋은 계기이자 기회가 되는 것 같다.

 

알고리즘이 점점 재미있다. 동시에 개발을 많이 못하고 있는데, 이번 주말까지 컴피 개발을 마무리해야해서 내일부터는 위치 기능 스터디와 개발에 몰두해야겠다. 새로운 스터디카페를 찾았다. 공간이 너무 깔끔하고, 집중도 잘된다. 넓고 트인 공간이라 마음에 든다.

 

내일 할 일

- 컴피

  - 호랑 PR 리뷰하기

  - 위치 기능 구현

  - 컴피존 설정 화면 구현

- 알고리즘(오늘의 문제, 이전 기억 되살리기)

- 이력서/포트폴리오 보완하기

- TIL 작성하기