본문 바로가기

분류 전체보기156

Refectoring Refectoring 이란? 외부 동작을 바꾸지 않으면서 내부 구조를 개선하는 방법 버그가 끼어들 가능성을 최소화하면서 코드를 정리하는 "정형화된 방법" 코드를 작성한 후에 코드의 디자인을 개선하는 것 Refectoring 에서 요구하는 코드 = 깔끔한 코드 깔끔한 코드는 모든 테스트를 통과한다. 깔끔한 코드는 다른 프로그래머에게도 그 의미가 명백하다 깔끔한 코드에는 중복이 존재하지 않는다. 깔끔한 코드는 최소한의 클래스, 즉 꼭 픽요한 클래스만을 가진다. 깔끔한 코드는 더 적은 비용으로 , 더 쉽게 유지보수 할 수 있다. Bad smells in Code Refectoring의 깔끔한 코드에 속하지 않는 고쳐야 할 코드 Bad smell code 중복된 코드 코드가 여기저기 겹쳐 있는 경우 긴 메소드 .. 2021. 9. 15.
최단 경로 알고리즘 (3) 플로이드 워셜 알고리즘 플로이드 알고리즘은 '모든 지점에서 다른 모든 지점까지의 최단 경로를 모두 구해야 하는 경우'에 사용할 수 있는 알고리즘이다. 다익스트라 : 단계마다 최단 거리를 가지는 노드를 하나씩 반복적 선택 , 해당 노드를 거치는 경로를 확인하며 테이블을 갱신해 나간다. ( 탐욕법 ) 플로이드 : 단계마다 ' 거쳐 가는 노드'를 기준으로 수행되지만 매번 방문하지 않는 노드 중에서 최단 거리를 갖는 노드를 찾을 필요가 없다. ( 동적 프로그래밍 ) 노드의 개수가 N개일 때, 알고리즘상 N번의 단계를 수행하고 단계마다 O(N^2)의 연산을 통해 '현재 노드를 거쳐 가는 모든 경로'를 고려한다. 따라서 총 시간 복잡도는 O(N^3)이다. 플로이드 알고리즘에서는 모든 노드에 대하여 다른 모든 노드로.. 2021. 9. 8.
최단 경로 알고리즘 (2) 개선된 다익스트라 알고리즘 저번장의 알고리즘은 시간 복잡도가 O(V^2)으로 노드의 개수가 10,000개를 넘어가는 순간 해결이 어려워졌었다. 하지만 다음의 구현 방법을 이용하면 최악의 경우에도 시간 복잡도 O(E logV)를 보장하여 해결할 수 있다. 여기서 V는 노드 개수 , E는 간선 개수이다. 저번 장의 알고리즘에서 최단 거리가 짧으면서 탐색하지 않은 노드를 찾기 위해서 선형적으로 테이블을 탐색해야 했다 => N 이 때 힙 자료구조를 사용하여 최단거리에 대한 정보를 빠르게 찾도록 하자 힙을 사용하면 선형시간이 아닌 로그시간이 걸리므로 N이 1,000,000 이라면 로그시간에서 약 20 정도로. 속도가 크게 빨라진다. - 파이썬에서 우선순위 큐를 지원하기 위해 PriorityQueue 와 heapq.. 2021. 9. 6.
최단 경로 알고리즘 최단 경로 알고리즘에 대표적인 알고리즘으로는 다익스트라, 플로이드 워셜, 벨만 포드 알고리즘이 있다. 다익스트라 최단 경로 알고리즘 그래프에서 여러 개의 노드가 있을 때, 특정한 노드에서 출발하여 다른 노드로 가는 각각의 최단 경로를 구해주는 알고리즘이다. 이 때 조건은 음의 간선이 없는 경우에 정상적으로 동작한다는 점이다. 현실 세계에서의 길에는 음의 간선의 표현될 일이 없으므로 실제 GPS 소프트웨어의 기본 알고리즘으로 채택되곤 한다. 다익스트라 알고리즘을 그리디 알고리즘(탐욕법)으로도 분류된다. '매번 가장 적은 비용의 노드를 선택'하는 임의의 과정을 반복하기 때문이다. 알고리즘은 최단 경로를 구하는 과정에서 각 노드에 대한 현재까지의 최단거리를 단계마다 게속 갱신해 나간다. 즉 매번 현재 처리하고.. 2021. 9. 1.
반응형

티스토리툴바