728x90 IT 개인학습/이것이 취업을 위한 코딩테스트다 with 파이썬12 신장 트리, 크루스칼, 위상 정렬 알고리즘 신장 트리 " 하나의 그래프가 있을 때 모든 노드를 포함하면서 사이클이 존재하지 않는 부분 그래프 " - 모든 노드가 포함되어 서로 연결되면서 사이클이 존재하지 않는다는 조건은 트리의 성립 조건이기도 하다. - 그래프 알고리즘 문제로 자주 출제되는 문제 유형이다. 크루스칼 알고리즘, Greedy " 다양한 문제 상황에서 가능한 한 최소한의 비용으로 신장 트리를 찾아야 할 때가 있다. " 예시) N개의 도시가 존재하는 상황에서 두 도시 사이에 도로를 놓아 전체 도시가 서로 연결될 수 있게 도로를 설치하는 경우 2개의 도시 A, B를 선택했을 때, 도시 A에서 도시 B로 이동하는 경로가 반드시 존재하도록 도로를 설치하고자 한다. 모든 도시를 "연결"할 때, 최소한의 비용으로 연결하려면 어떤 알고리즘을 이용해.. 2022. 9. 20. 그래프 이론, 서로소 집합 " 여러 개의 도시가 연결되어 있다 " - 노드와 간선으로 이루어진 자료구조, 정점(Vertex)간의 관계를 표현하는 조직도 - 그래프 알고리즘을 의심해보자 - 그래프 자료구조 중에서 Tree 자료구조는 다양한 알고리즘에 사용됨 Tree 자료구조???- - 부모에서 자식으로 내려오는 계층적인 모델에 속한다. - Tree 자료구조는 노드가 N개일 때, 항상 간선의 개수가 N -1개 이다. * 크루스칼 알고리즘 Kruskal - Greedy 알고리즘 (참조) https://cord-ai.tistory.com/154 Greedy(탐욕) ' 현재 상황에서 지금 당장 좋은 것만 고르는 방법 ' ' 사전에 외우고 있지 않아도 풀 수 있을 가능성이 높은 문제 유형 ' - 최단 경로를 빠르게 찾아야 하는 문제는 플로이.. 2022. 9. 8. 플로이드 워셜 Floyd-Warshall 알고리즘 " 모든 지점에서 다른 모든 지점까지의 최단 경로를 모두 구해야 하는 경우 " - 다익스트라 알고리즘과 비교하면 구현 과정에서 어렵진 않음 - 다만, 핵심 아이디어를 이해하는 것이 중요 그래프의 정보를 2차원 행렬(배열)을 이용하여 3중 루프를 반복하여 구성된 최단 경로 알고리즘 다익스트라(Greedy) VS 플로이드 워셜(Dynaminc) https://cord-ai.tistory.com/165 최단경로 Shortest Path " 가장 짧은 경로를 찾는 알고리즘이다 " - "길 찾기" 문제라고도 불린다. - 그래프를 이용해 표현(= 각 지점은 그래프에서 " 노드 ", 지점간 연결된 도로는 그래프에서 "간선") - 최단 경로를 모두 cord-ai.tistory.com - 단계마다 최단 거리를 가지는 노.. 2022. 9. 2. 최단경로 Shortest Path " 가장 짧은 경로를 찾는 알고리즘이다 " - "길 찾기" 문제라고도 불린다. - 그래프를 이용해 표현(= 각 지점은 그래프에서 " 노드 ", 지점간 연결된 도로는 그래프에서 "간선") - 최단 경로를 모두 출력하는 문제보다는 단순히 최단 거리를 출력하도록 요구하는 문제가 많이 출제 1. 한 지점에서 다른 특정 지점까지 최단 경로를 구해야 하는 경우 - 다익스트라 2. 모든 지점에서 다른 모든 지점까지의 최단 경로를 모두 구해야 하는 경우 - 플로이드 워셜 https://cord-ai.tistory.com/167 플로이드 워셜 Floyd-Warshall 알고리즘 " 모든 지점에서 다른 모든 지점까지의 최단 경로를 모두 구해야 하는 경우 " - 다익스트라 알고리즘과 비교하면 구현 과정에서 어렵진 않음 - .. 2022. 8. 31. 다이나믹 프로그래밍(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. 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 다음 728x90
