💡 학습 일기
문제를 잘 읽어야 한다 - Day16
처음에 문제 이해가 되지 않아 예제의 답이 왜 그렇게 나오는지 몰랐는데,
알고보니 다른 섬과 연합을 결성하지 않은 섬들도 각각 하나의 연합에 속해 있는 것으로 볼 때라는 조건이 문제 속에 숨어 있었다.
답변 출력을 위해서는 문제를 꼼꼼히 읽는 것이 중요하다...
바빠져서 문제를 풀기 위한 시간을 들이기 어려웠다ㅠ
KDT 심화 과정에 등록해서 다시 학원에 다니기 시작했다.
틈틈이 구름에 들어와서 문제를 봤지만, 흐름이 끊기다보니 내가 작성한 변수를 어떤 의도로 넣었는지 까먹게 됐다.
한번에 쭉 이어서 공부할 수 있는 시간을 낼 수 있다면 좋을 것 같다.
아니면 주석으로 잘 노트해놓기!!
소수점 이하로 나오는 숫자를 다룰 때 주의 - Day17
몫이나 나머지를 활용하는 게 아닌 나눗셈 결과를 가지고 코드를 풀어나갈 때,
숫자가 동일한지 비교하는 것은 불가능하다.
두 실수의 차이의 절댓값이 아주 작은 수보다 작을 때 같은 값으로 보고 코드를 풀어나갈 수 있다.
💡 코드 공부
Day 16 : 연합
- 이전 문제에서는 특정 조건일 때 결과값에 +1을 해주는 방식이었다.
- 문제를 해결하기 위해서는 반대로 쓸 수도 있다는 것을 유의하자.
- 알고리즘 : 연합이 끝나서 새로운 섬을 만났을 때 +1
for i in range(1, N + 1): # 모든 섬에 대해 탐색 if visited[i]: continue q = deque([i]) result += 1 visited[i] = 1 while q: now = q.popleft() for to in graph[now]: # 반대 섬에 방문하지 않았고, 오는 방향이 있으면 if not visited[to] and now in graph[to]: # 연합 : q가 0이 되기 전까지 result에 1이 더해지지 않는다. q.append(to) visited[to] = 1
Day 17 : 그래프의 밀집도
- 조건을 만족하는 결과값을 출력하기 위해서 조건문을 잘 활용해야한다.
- 가장 밀도가 높은 컴포넌트를 출력한다.
- 1을 만족하는 컴포넌트가 여러 개라면, 컴포넌트를 구성하는 컴퓨터의 수가 가장 작은 컴포넌트를 출력한다.
- 2를 만족하는 컴포넌트가 여러 개라면, 더 작은 번호를 가진 컴퓨터가 있는 컴포넌트를 출력한다.
for i in range(1, N + 1): if not visited[i]: temp, tempDensity = bfs(i) if abs(tempDensity - density) < 1e-8: # 2. 만약! 밀도가 같다면 if len(result) > len(temp): # - 컴퓨터 수가 적은 컴포넌트 & 밀도 업데이트 result = temp density = tempDensity elif len(result) == len(temp): # 3. 컴퓨터 수도 같다면 if temp[0] < result[0]: # - 더 작은 번호가 있는 컴포넌트 & 밀도 업데이트 result = temp density = tempDensity elif tempDensity > density: # 1. 비교했을 때 밀도가 높다면 result = temp # - 가장 밀도가 높은 컴포넌트 업데이트 density = tempDensity # - 밀도 정보 업데이트
