728x90 전체 글171 플로이드 워셜 Floyd-Warshall 알고리즘 " 모든 지점에서 다른 모든 지점까지의 최단 경로를 모두 구해야 하는 경우 " - 다익스트라 알고리즘과 비교하면 구현 과정에서 어렵진 않음 - 다만, 핵심 아이디어를 이해하는 것이 중요 그래프의 정보를 2차원 행렬(배열)을 이용하여 3중 루프를 반복하여 구성된 최단 경로 알고리즘 다익스트라(Greedy) VS 플로이드 워셜(Dynaminc) https://cord-ai.tistory.com/165 최단경로 Shortest Path " 가장 짧은 경로를 찾는 알고리즘이다 " - "길 찾기" 문제라고도 불린다. - 그래프를 이용해 표현(= 각 지점은 그래프에서 " 노드 ", 지점간 연결된 도로는 그래프에서 "간선") - 최단 경로를 모두 cord-ai.tistory.com - 단계마다 최단 거리를 가지는 노.. 2022. 9. 2. 힙 Heap 자료구조 " 우선순위 Priority Queue를 구현하기 위하여 사용하는 자료구조 - Tree 자료구조 " Tree 자료구조??? - 부모에서 자식으로 내려오는 계층적인 모델에 속한다. - DFS/BFS 스택과 큐의 원리를 알아보았다. https://cord-ai.tistory.com/158 DFS / BFS , Graph Structure "Stack, Queue, Recursive Func는 DFS / BFS에서 가장 중요한 개념" https://cord-ai.tistory.com/156 Stack, Queue, Recursive Function " 그래프를 탐색하기 위한 대표적인 두 가지 알고리즘 " 탐색(Search)이란.. cord-ai.tistory.com "스택"은 가장 나중에 삽입된 데이터가 가장.. 2022. 8. 31. 최단경로 Shortest Path " 가장 짧은 경로를 찾는 알고리즘이다 " - "길 찾기" 문제라고도 불린다. - 그래프를 이용해 표현(= 각 지점은 그래프에서 " 노드 ", 지점간 연결된 도로는 그래프에서 "간선") - 최단 경로를 모두 출력하는 문제보다는 단순히 최단 거리를 출력하도록 요구하는 문제가 많이 출제 1. 한 지점에서 다른 특정 지점까지 최단 경로를 구해야 하는 경우 - 다익스트라 2. 모든 지점에서 다른 모든 지점까지의 최단 경로를 모두 구해야 하는 경우 - 플로이드 워셜 https://cord-ai.tistory.com/167 플로이드 워셜 Floyd-Warshall 알고리즘 " 모든 지점에서 다른 모든 지점까지의 최단 경로를 모두 구해야 하는 경우 " - 다익스트라 알고리즘과 비교하면 구현 과정에서 어렵진 않음 - .. 2022. 8. 31. Python 함수 주석 def function(a, b, c): """ # 주석 test 함수입니다. Args: a (str): a value b int: b value c (str): c value Retruns: None """ pass 2022. 8. 29. 다이나믹 프로그래밍(Dynamic Programming) " 중복되는 연산을 줄이자 " " 메모리 공간을 약간 더 사용하면 연산 속도를 비약적으로 증가시킬 수 있는 방법 " " 완전 탐색 알고리즘으로 접근했을 때 시간이 매우 오래 걸리면 다이나믹 프로그래밍을 적용할 수 있는지 해결하고자 하는 부분 문제들의 중복 여부를 확인해보자 " - (해결하기 어려운 문제) = 깊게 다루는 분야로는 계산 복잡도 이론이 있다. => P-NP??? 공부 추천 - 3차원 리스트를 이용해야하는 복잡한 난이도 문제 = 9장 "최단 경로" 컴퓨터를 활용해도 해결하기 어려운 문제란 무엇인가??? - 최적의 해를 구하기에 시간이 매우 많이 필요하거나 - 메모리 공간이 매우 많이 필요한 문제 등 컴퓨터는 연산 속도에 한계가 있고 메모리 공간을 사용할 수 있는 데이터의 개수도 한정적이라는 점.. 2022. 8. 28. 이진 탐색 Binary Search " 범위를 반씩 좁혀가는 탐색 " 순차 탐색 Sequential Search - 리스트 내에서 특정한 데이터를 찾기 위해 앞에서부터 데이터를 하나씩 매우 빠르게 탐색하는 이진 탐색 알고리즘 - 예시) Greedy '거스름돈' 문제에서 가장 큰 화폐 단위부터 확인(탐색)해서 각 단위에 대하여 처리한 것 - 리스트 내에 데이터가 아무리 많아도 시간만 충분하다면 항상 원하는 원소(데이터)를 찾을 수 있다는 장점 - 데이터의 개수가 N개일 때 최대 N번의 비교 연산이 필요하므로 최악의 경우 시간복잡도 O(N) - 리스트에 특정 값의 원소가 있는지 체크할 때 순차 탐색으로 원소를 확인하고, 리스트 자료형에서 특정한 값을 가지는 원소의 개수를 세는 count() 메서드를 이용할 때에도 내부에서는 순차 탐색이 수행됨.. 2022. 8. 24. Sorting 정렬 정렬이란 " 데이터를 특정한 기준에 따라서 순서대로 나열 " 정렬 알고리즘으로 데이터를 정렬하면 => 이진 탐색(Binary Search)이 가능해짐 ??? - 정렬 알고리즘은 이진 탐색의 전처리 과정이기도 하다 https://cord-ai.tistory.com/161 정렬 알고리즘 - 선택 정렬, 삽입 정렬, 퀵 정렬, 계수 정렬 - Python에서 제공하는 기본 정렬 라이브러리 적용 가능(= 더 효율적인 정렬 수행 방법) - 면접에서도 단골 문제로 출제 # 단순 정렬해야하는 상황에서는 기본 정렬 라이브러리(sort, sorted) 사용 # 데이터의 범위가 한정되어 있으며 더 빠르게 동작해야할 경우 계수 정렬 사용 1. 정렬 라이브러리로 풀 수 있는 문제 : 단순히 정렬 기법을 알고 있는지 물어보는 문.. 2022. 8. 19. if not 문 if not x 의 조건에 들어맞는 x는 다음과 같다. 1) False 2) 0 3) 빈 리스트 [] 4) 빈 튜플 () 5) 빈 딕셔너리 {} 6) 문자길이 0의 문자열 "" 7) None 8) 등등 if 로 None 여부를 알고 싶을 때는 if x==None으로 하지 말고, if x is None 으로 하기. => 의미는 같지만, if x is None이 내부적으로 약간 빠르다고 한다. ## if not X: => X의 결과가 False 이면 해당 조건 출력 if not False: print ("not of False is True.") if not True: print ("not of True is False.") not of 0 is True. 2022. 8. 15. DFS / BFS , Graph Structure "Stack, Queue, Recursive Func는 DFS / BFS에서 가장 중요한 개념" https://cord-ai.tistory.com/156 Stack, Queue, Recursive Function " 그래프를 탐색하기 위한 대표적인 두 가지 알고리즘 " 탐색(Search)이란??? - 많은 양의 데이터 중에서 원하는 데이터를 찾는 과정 - 프로그래밍에서는 그래프, 트리 등의 자료구조 안에서 탐색을 cord-ai.tistory.com 그래프 구조, Graph Structure - 노드 Node, 간선 Edge로 표현됨(이 때 노드를 정점 Vertex라고도 말한다) - 예를 들어 노드 == 도시, 간선 == 도로 - 그래프 탐색이란 하나의 노드를 시작으로 다수의 노드를 방문하는 것을 말한다... 2022. 8. 15. 이전 1 2 3 4 5 6 ··· 19 다음 728x90
