오늘의 알고리즘

알고리즘 공부

이번에 일요일 문제를 풀어보니 내가 진짜 그래프나 도형문제에서 엄청 약하고 겁을 먹는다는 사실을 알게됐다. 도형 문제도 많이 풀어봐야겠다.

boj-6502

count = 1
while True:
    cur_input = input()
    if cur_input == "0":
        break
    R, W, L = map(int, cur_input.split())
    
    if (W**2 + L**2) ** (1/2) <= 2*R:
        print(f"Pizza {count} fits on the table.")
    else: print(f"Pizza {count} does not fit on the table.")
        
    count +=1

그림을 그려보니 원안에 4각형이 들어오려면 사각형을 관통하는 대각선의 길이가 원의 지름보다 작으면 피자를 식탁위에 놓을 수 있겠다는 생각이 들었다.

그래서 대각선의 길이를 피타고라스의 정리로 구해주고 그 길이보다 지름이 크거나 같으면 피자는 테이블에 맞는 것이기 때문에 맞다는 출력을 해주고 반대라면 안맞다고 프린트해주면 되는 문제였다.

boj-5567

from collections import deque
N = int(input())
M = int(input())

friend_graph = [[ ] for _ in range(N+1)]
visited = [0] * (N+1)

for _ in range(M):
    person, friend = map(int, input().split())
    
    friend_graph[person].append(friend)
    friend_graph[friend].append(person)
    
friend_queue = deque()
friend_queue.append((1, 0))
visited[1] = 1
answer = 0

while friend_queue:
    friend_node, distance = friend_queue.popleft()
    
    if 0 < distance <= 2:
        answer +=1
    
    for next_node in friend_graph[friend_node]:
        if visited[next_node] == 0:
            visited[next_node]= 1
            friend_queue.append((next_node, distance+1))
            
print(answer)

간단한 BFS 문제였다. 각 사람과의 연결 거리를 생각해보면 친구의 친구라고 한다면 거리가 1, 2만큼 차이나는 사람을 구해서 그 사람의 수를 카운트하면 된다. visited로 중복 검사를 하고 있기 때문에 queue에서 팝해온 데이터의 distance 값을 검사해 그 값이 2이하이고 0보다 크다면(처음 값 때문에 0보다 크게 설정) answer의 값을 업데이트 해주고 마지막으로 프린트 해주면 된다.

boj-2660

import sys
N = int(input())
INF = sys.maxsize
distances = [[INF]*(N+1) for _ in range(N+1)]

while True:
    member1, member2 = map(int, input().split())
    if member1 == member2 == -1: break
    distances[member1][member2] = 1
    distances[member2][member1] = 1
    
for i in range(1, N+1):
    distances[i][i] = 0
    
for k in range(1, N+1):
    for i in range(1, N+1):
        for j in range(1, N+1):
            distances[i][j] = min(distances[i][j], distances[i][k]+distances[k][j])

result = []
for i in range(1, N+1):
    result.append(max(distances[i][1:]))

minimum = min(result)
answer = [i+1 for i, v in enumerate(result) if v == minimum]
print(minimum, len(answer))
print(*answer)

문제를 이해 못해서 시간이 좀 걸렸다. 결국 구하고자 하는 값은 회원 한 명당 제일 먼 사람과 연결이 되어있는 사람과의 거리를 구하고 그 수가 가장 낮은 사람을 구하면 되는 문제다.

그래서 결국 bfs로 다 구하려고 하니까 새로운 것도 시도해보고 싶어져서 플로이드 워셜 기본 코드를 가져와서 이 문제에 적용시켜서 시도를 해보았다. 내일은 플로이드 워셜 강의도 한 번 봐야겠다.

피드백

오늘은 면접을 보고 나서 다시 집중하기 위해 돌아오기까지 시간이 많이 걸렸다. 내일부터 다시 마음잡고 제대로 블럭별로 공부를 해야겠다.

이제부터 공부 블럭을 잘 지키는지 블럭별로 하나씩 피드백을 남기면서 TIL을 작성해보려고 한다.