pr이 늦어서 죄송합니다! 마지막문제는 시간이 부족해서 풀지 못했습니다. 코드 리뷰는 오늘 저녁 쯤 올리겠습니다!
문제명 : 드래곤 커브
1. 풀이 과정
좌표폄면에서 회전에대한 기본적인 이해가 필요해서 조금 오래 걸렸던 것 같습니다.
최종적인 풀이는 좌표의 시계방향으로 90도 회전시 변하는 규칙을 찾아내고, 기준점을 이동했을때의 좌표 규칙을 반영하여 코드로 정의한뒤에 모든 드래곤커브를 만들어 냈습니다.
구현문제 중 이문제 처럼 회전의 개념을 적용하는 문제가 많았던것 같은데 이번에 확실히 배운것 같습니다.
문제명 : 다리 건설하기
실행속도 : 148 ms
1. 풀이 과정
이문제는 크게 두가지 부분문제로 생각할 수 있었는데요
첫번째는 그룹핑으로 여기서는 dfs로 해결했습니다.
두번째는 최단 거리 건설인데
처음 문제를 풀땐 bfs로 진행하다가 다른 대륙이 도달할시 현재 노드에서 건설할 수 있는 최단거리의 다리로 생각하여
모든 노드에서 탐색하는 식으로 하여 정답에 도달하긴했지만 이렇게 했을경우 같은 다리를 반복해서 찾아내는 비효율이 발생하더라구요.
이부분에서는 문제풀이 후 다른 분의 풀이를 참고해서 시간복잡도를 줄일 수 있었습니다. 최종적으로 처음풀이시 272ms 시간 복잡도 개선 후, 148ms까지 줄일 수 있었습니다.
로직에 대해선 글로 설명하기 힘들것같아, 코드를 봐주시거나 설명이 필요하면 내일 질문주십쇼! 한주동안 고생많으셨습니다.!
문제명 :
드래곤 커브1. 풀이 과정
좌표폄면에서 회전에대한 기본적인 이해가 필요해서 조금 오래 걸렸던 것 같습니다.
최종적인 풀이는 좌표의 시계방향으로 90도 회전시 변하는 규칙을 찾아내고, 기준점을 이동했을때의 좌표 규칙을 반영하여 코드로 정의한뒤에 모든 드래곤커브를 만들어 냈습니다.
구현문제 중 이문제 처럼 회전의 개념을 적용하는 문제가 많았던것 같은데 이번에 확실히 배운것 같습니다.
문제명 :
다리 건설하기실행속도 : 148 ms
1. 풀이 과정
이문제는 크게 두가지 부분문제로 생각할 수 있었는데요
첫번째는 그룹핑으로 여기서는
dfs로 해결했습니다.두번째는 최단 거리 건설인데 처음 문제를 풀땐
bfs로 진행하다가 다른 대륙이 도달할시 현재 노드에서 건설할 수 있는 최단거리의 다리로 생각하여 모든 노드에서 탐색하는 식으로 하여 정답에 도달하긴했지만 이렇게 했을경우 같은 다리를 반복해서 찾아내는 비효율이 발생하더라구요. 이부분에서는 문제풀이 후 다른 분의 풀이를 참고해서 시간복잡도를 줄일 수 있었습니다. 최종적으로 처음풀이시272ms시간 복잡도 개선 후,148ms까지 줄일 수 있었습니다. 로직에 대해선 글로 설명하기 힘들것같아, 코드를 봐주시거나 설명이 필요하면 내일 질문주십쇼! 한주동안 고생많으셨습니다.!