평생공부하는사람

안녕하세요😀 오늘은 프로그래머스 전력망을 둘로 나누기 문제를 풀어보겠습니다! 코딩테스트 연습 - 전력망을 둘로 나누기 9 [[1,3],[2,3],[3,4],[4,5],[4,6],[4,7],[7,8],[7,9]] 3 7 [[1,2],[2,7],[3,7],[3,4],[4,5],[6,7]] 1 programmers.co.kr 전력망을 둘로 나누기 문제는 완전탐색을 이용해서 풀었습니다. 최대 노드 갯수가 100개이기 때문에 bfs알고리즘으로 풀 경우 최악의 상황에서 O(n * nlogn) 의 시간이 걸리기 때문에 시간제한이 걸리진 않을듯 합니다! 이제 문제를 풀어보겠습니다! wireGraph와 isVisitedNode를 선언하고 완전탐색이므로 전력망을 둘로 나누기 위해 wire를 자르는데 모든 와이어를 한번씩 ..

안녕하세요. 오늘은 DFS와 BFS알고리즘에 대해서 알아 보겠습니다. DFS와 BFS는 그래프의 완전탐색 알고리즘입니다. 시간복잡도 두 알고리즘의 시간 복잡도에 대해서 먼저 설명드리겠습니다. 인접리스트형식으로 표현된 그래프와 인접행렬법으로 표현된 그래프에서의 시간복잡도는 다릅니다. 우선 인접행렬법(V by V 행렬 : V은 정점의 개수 입니다.)에서는 O(V^2)입니다. 각각의 노드에서 모든 노드로 간선이 있는지 여부를 알아야 하기 때문입니다. 두번째로 인접리스트형식(V: 정점의 개수, E: 간선의 개수)으로 표현된 그래프에서는 O(V+E)입니다. 각각의 노드에서 다른 노드로 간선이 리스트형식으로 존재함을 알기 때문에 V+E로 모두 탐색 가능합니다. 알고리즘 설명 DFS부터 알고리즘 설명 드리겠습니다. ..

안녕하세요! 오늘은 프로그래머스 2레벨 거리두기 확인하기 문제를 풀어보겠습니다! 이번 문제는 맨허튼 거리를 이용해서 거리를 확인하는 문제입니다! 소스 코드량(함수로 안만들어서 뻥튀기된 부분이 있어요 ㅠㅠ)에 비해서 생각보다 문제가 쉬우니 다들 풀어보시기 바랍니다! 우선 이 문제는 사람이 앉은 포인트를 잡아서 맨허튼 거리 2안에서 사람이 또 있는지 없는지를 확인하는 문제입니다! 장애물도 있기 때문에 일반적인 거리측정방법말고 DFS나 BFS를 이용해야합니다. 저번에 DFS로 문제를 풀었던게 있어서 BFS로 문제를 풀어보겠습니다! 우선 BFS에 쓸 Queue가 필요한데 Swift에는 기본적으로 지원해주는 Queue가 없으니 대충 만들어 씁시다! Queue도 거리가 2까지이다 보니 Queue도 완벽하게 구현할 ..