[DFS/BFS] 네트워크 (Lv.3)
걸린 시간
37분
접근 방식
대충 BFS해서 한 덩어리 찾는 함수 만들어서 visited가 False인 곳 찾아서 카운트 하면 될 듯했다.
1이 연결된 얘가 3, 5라면 3이랑 5를 탐색
정답 코드
from collections import deque
def solution(n, computers):
if n == 1:
return 1
cnt = 0
visited = [[False for _ in range(n)] for _ in range(n)]
for i in range(n):
visited[i][i] = True
# 1부터 시작해서 연결되는 얘 queue에 넣기
for y in range(n):
queue = deque([y])
if all(visited[y]):
continue
while queue:
val = queue.popleft()
for i in range(n):
if i == val:
continue
if computers[val][i] and not visited[val][i]:
queue.append(i)
visited[i][val] = True
visited[val][i] = True
cnt += 1
return cnt배운점
2차원 배열에서 트리로 넣는 것을 살짝 헤맸던 것 같다.
all 함수는 iterable 객체에 모든 요소가 참이면 참을 반환한다.
정확히는 False를 발견하면 즉시 False를 반환하는 함수이다.
단, 빈 배열 같은 경우는 True를 반환한다.
[그래프] 가장 먼 노드 (Lv.3)
걸린 시간
40분
접근 방식
기억 상 다익스트라가 모든 노드의 최단 거리를 구해주는 것으로 알아서 그런 문제인가 생각했다.
근데 정확히 알고리즘은 몰라서 기억을 되짚고 논리적인 절차를 하나 하나 생각해서 풀어보았다.
BFS 느낌으로 하는건가 싶어서 조사하면서 제한조건을 부여하고 최단거리를 갱신하면 되겠다 싶었다.
위 표 기준으로 1부터 BFS를 들어간다고 가정하면 다음과 같은 시나리오가 진행된다.
queue = [1]
1(len = 1)에서 출발하면 2, 3 이때 이건 len에 2을 부여함
queue = [2, 3] (1 out)
2(len = 2)에서 출발하면 3, 4, 5인데 3은 1이라서 제외하고 4, 5에 len을 3 부여함
queue = [3, 4, 5] (2 out)
3(len = 2)에서 출발하면 2, 4, 6인데 2는 2라서 제외하고 4도 3지만 부여할 것도 3이라서 queue에 포함하진 않음 6에는 3를 부여
queue = [4, 5, 6] (3 out)
4(len = 3)에서 출발하면 2, 3인데 둘다 2이라서 3을 부여 못하므로 제외 끝
queue = [5, 6] (4 out)
...
대충 이런식으로 진행 될 것 같다.
필요한 변수 초기화는 다음과 같이 메모하면서 진행했다.
그럼 1만 0을 부여하고 나머지는 -1을 부여해서
-1 : queue에 추가시키고 len+1 부여함
자신+1보다 작거나 같음 : queue에 추가시키지 않고 len도 부여하지 않음
자신+1보다 큼 : 최단거리 갱신 필요! queue에 추가시키고 len+1을 부여함
그럼 len에 해당하는 값을 넣는 배열에 [0, -1, -1, ...]
vertex의 연결된 값은 dict에 {1:[2,3], 2:[1,3,4,5], ...} 넣고 조사하게 하자
정답 코드
from collections import deque
def solution(n, vertex):
min_len = [-1 for _ in range(n+1)]
min_len[1] = 0
vertex_dict = {}
for i in range(1, n+1):
vertex_dict[i] = []
for v in vertex:
n1, n2 = v[0], v[1]
vertex_dict[n1].append(n2)
vertex_dict[n2].append(n1)
q = deque([1])
while q:
val = q.popleft()
for i in vertex_dict[val]:
# 조사하는 노드가 -1이라 개척해야하거나,
# 조사하는 노드가 자신+1보다 크면? 갱신!
if min_len[i] == -1 or min_len[i] > min_len[val] + 1:
q.append(i)
min_len[i] = min_len[val] + 1
cnt = 0
m = max(min_len)
for l in min_len:
if l == m:
cnt += 1
return cnt배운점
다익스트라는 2차원배열에 체크하는 방식이라 조금 다르게 풀긴 했지만 나름 잘 최적화 해서 푼 것 같다.
다만 모든 가중치가 1로 동일한 그래프라 BFS 특성상 다른 경로에서 다시 노드를 방문한다면 min_len[i] > min_len[val] + 1 이 조건이 항상 거짓이라 체크할 필요가 없다고 한다.
그리고 딕셔너리 대신 2차원 배열로 인접 리스트를 생성해서 노드 정보를 담아두는게 딕셔너리 해시 오버헤드도 줄일 수 있다고 한다.
[구현] [1차] 셔틀버스 (Lv.3)
걸린 시간
1시간 30분
접근 방식
요컨데 이미 줄서있는 크루들이 서는 버스 줄이 있을 때 어떤 시간에 줄을 서야 가장 늦게 버스를 탈 수 있는지를 구하는 것이다.
09:00 같은 포맷은 540 처럼 분에 해당하는 int값으로 변환해서 계산했다.
어느 버스에 ‘언제 줄 선 크루’가 탈 예정인지 배열에 채워넣고, 동시간대 가장 뒤에 줄 서는 콘(주인공)이 끼어들 수 있는 버스가 언제인지 계산하려 했다.
이렇게 하니까 논리구조가 부족해져서 구현에 시간이 오래걸렸다.
1시간이 넘어가서 AI에게 물어보니
마지막 버스에 자리가 남으면 마지막 버스 출발 시간이 답이고,
마지막 버스인데 자리가 없다면 맨 마지막으로 간신히 탑승한 크루보다 1분 먼저 와야 자리를 뺏을 수 있다.
이 논리로 계산하면 됐었다.
정답 코드
def time_to_int(time):
h, m = time.split(":")
return int(h)*60 + int(m)
def int_to_time(i):
return '{0:02d}'.format(i//60) + ":" + '{0:02d}'.format(i%60)
def solution(n, t, m, timetable):
bus_time = [540 + i for i in range(0,n*t,t)]
int_table = []
boarding = [[] for _ in range(n)]
for time in timetable:
val = time_to_int(time)
if val <= bus_time[-1]:
int_table.append(val)
int_table = sorted(int_table)
l = len(int_table) # crue_idx 바운더리용
# 크루들이 탈 버스에 넣기
board_idx = 0
crue_idx = 0
for bt in bus_time:
if crue_idx >= l:
break
start, end = 0, bt
# 정원만큼 넣기
for i in range(m):
if start <= int_table[crue_idx] <= end:
boarding[board_idx].append(int_table[crue_idx])
crue_idx += 1
if crue_idx >= l:
break
board_idx += 1
# 마지막 버스가 꽉찬 버스가 아니라면?
if len(boarding[-1]) < m:
return int_to_time(bus_time[-1])
# 꽉찬 버스라면?
val = boarding[-1][-1] - 1
return int_to_time(val)배운점
구현의 경우 변수의 이름과 쓰임새를 잘 정해야 하는 것도 있지만 경우의 수 분기를 잘해야 시간이 단축되는 것 같다. (DP에서도 그렇지만 말이다)
파이썬의 포매팅을 까먹어서 다시 검색해서 배웠다…
.format() 기억하자
근데 f-string이 더 나을지도
1. 기본 사용법
가장 기본적인 형태는 중괄호 {}를 문자열 안에 넣고 .format()의 인자를 순서대로 매핑하는 것입니다.
1) 순서대로 넣기 (위치 기반)
중괄호를 비워두면 .format()에 넘어온 순서대로 값이 들어갑니다.
print("이름: {}, 나이: {}".format("홍길동", 20))
# 출력: 이름: 홍길동, 나이: 202) 인덱스 지정하기
중괄호 안에 숫자를 넣으면 특정 위치의 인자를 가리킬 수 있습니다. 같은 값을 여러 번 재사용할 때 유용합니다.
print("{0}의 나이는 {1}살입니다. {0}은(는) 학생입니다.".format("철수", 24))
# 출력: 철수의 나이는 24살입니다. 철수은(는) 학생입니다.3) 키워드(이름) 지정하기
인덱스 대신 이름을 지정해 주면 코드가 훨씬 직관적이고 읽기 편해집니다.
print("가로: {width}, 세로: {height}".format(width=100, height=200))
# 출력: 가로: 100, 세로: 2002. 문자열 정렬과 공백 채우기
문자열의 길이를 고정하고 왼쪽, 오른쪽, 혹은 가운데로 정렬해야 할 때 사용합니다. 형식은 {인덱스:콜론(:) 뒤에 옵션} 구조를 가집니다.
<: 왼쪽 정렬>: 오른쪽 정렬^: 가운데 정렬
# 10칸을 확보하고 정렬
print("{:<10}".format("hi")) # 'hi ' (왼쪽 정렬)
print("{:>10}".format("hi")) # ' hi' (오른쪽 정렬)
print("{:^10}".format("hi")) # ' hi ' (가운데 정렬)💡 빈칸을 특정 문자로 채우기
정렬 기호(<, >, ^) 바로 앞에 채우고 싶은 문자를 넣으면, 공백 대신 그 문자로 채워집니다.
print("{:=<10}".format("hi")) # 'hi========'
print("{:-^10}".format("hi")) # '----hi----'
print("{:0>10}".format("5")) # '0000000005'3. 숫자 표현식 (소수점, 천 단위 콤마)
알고리즘 문제나 데이터 처리 시 가장 자주 쓰이는 핵심 기능입니다.
1) 소수점 자리수 지정 (f)
:.자릿수f 형태로 작성하면 실수를 소수점 아래 원하는 자리까지 반올림하여 표현합니다.
print("{:.2f}".format(3.141592)) # '3.14' (소수점 둘째 자리까지)
print("{:.0f}".format(3.141592)) # '3' (정수 형태로 반올림)2) 천 단위 콤마(,) 찍기
숫자가 클 때 보기 편하게 3자리마다 콤마를 추가합니다.
print("{:,}".format(1234567890)) # '1,234,567,890'3) 자릿수 맞추기와 소수점 함께 쓰기
10칸을 확보하고 소수점 2자리까지 표현하면서 빈칸은 0으로 채우고 싶다면 다음과 같이 조합할 수 있습니다.
print("{:010.2f}".format(3.141592)) # '0000003.14'4. 진수 변환 및 패딩
코딩 테스트에서 간혹 등장하는 진수 변환도 .format()으로 쉽게 처리할 수 있습니다.
b: 2진수 (Binary)o: 8진수 (Octal)x: 16진수 (Hexadecimal)
print("{:b}".format(10)) # '1010' (2진수)
print("{:x}".format(255)) # 'ff' (16진수)
# 8자리로 맞추고 빈 앞자리는 0으로 채운 2진수
print("{:08b}".format(10)) # '00001010'5. 중괄호 {} 문자 자체를 출력하고 싶을 때
포매팅을 사용하면서 문자열에 진짜 중괄호 기호를 넣고 싶다면, 중괄호를 두 번 연속({{, }}) 써주면 됩니다.
print("JSON 형태 예시: {{ 'id': {} }}".format(1))
# 출력: JSON 형태 예시: { 'id': 1 }💬 참고: Python 3.6+
f-string
최근 파이썬 버전에서는.format()보다 더 직관적이고 빠른f-string방식을 권장하곤 합니다. 콜론(:) 뒤에 붙는 정렬이나 숫자 옵션 규칙은 완전히 똑같으니 참고해 두세요!age = 20 # f-string 방식 print(f"나이: {age:03d}") # '나이: 020'
