이것이 취업을 위한 코딩테스트다 with Python3

• 

  [알고리즘] 그래프 이론 : 서로소 집합, 신장 트리, 크루스칼, 위상 정렬 본 정리내용은 '이것이 취업을 위한 코딩 테스트다 with 파이썬' 교재를 참고 했습니다. 독학하는 용도로 글을 작성하는 것이고, 혹여나 잘못된 부분이 있다면 댓글 써주시면 감사하겠습니다. [그래프의 구현 방법] 인접 행렬 (Adjacency Matrix) : 2차원 배열을 사용하는 방식 간선 정보를 저장하기 위해 $O(V^2)$만큼의 메모리 공간이 필요 (V : 노드의 개수) 특정한 노드 A에서 다른 특정한 노드 B로 이어진 간선의 비용을 $O(1)$의 시간으로 즉시 알 수 있음 인접 리스트 (Adjacency List) : 리스트를 사용하는 방식 간선 정보를 저장하기 위해 $O(E)$만큼만 메모리 공간이 필요 (E : 간선의 개수) 특정한 노드 A에서 다른 특정한 노드 B로 이어진 간선의 비용을 $O.. Coding Test/Python 2021. 10. 12.

• 

  [알고리즘] 최단 경로 (Shortest Path) : Dijkstra (다익스트라), Floyd-Warshall (플로이드 워셜) 본 정리내용은 '이것이 취업을 위한 코딩 테스트다 with 파이썬' 교재를 참고 했습니다. 독학하는 용도로 글을 작성하는 것이고, 혹여나 잘못된 부분이 있다면 댓글 써주시면 감사하겠습니다. 최단 경로 알고리즘 최단 경로 알고리즘은 가장 짧은 경로를 찾는 알고리즘을 의미함. '길 찾기' 문제라고도 불린다. 다양한 문제 상황 한 지점에서 다른 한 지점까지의 최단 경로 한 지점에서 다른 모든 지점까지의 최단 경로 모든 지점에서 다른 모든 지점까지의 최단 경로 각 지점은 그래프에서 노드로 표현 지점 간 연결된 도로는 그래프에서 간선으로 표현 코딩 테스트에서는 최단 경로를 모두 출력하는 문제보다는 단순히 최단 거리를 출력하도록 요구하는 문제가 많이 출제됨. 최단 경로 알고리즘 : 다익스트라 최단 경로 알고리즘, .. Coding Test/Python 2021. 10. 11.

• 

  [알고리즘] 다이나믹 프로그래밍 (Dynamic Programming) 본 정리내용은 '이것이 취업을 위한 코딩 테스트다 with 파이썬' 교재를 참고 했습니다. 독학하는 용도로 글을 작성하는 것이고, 혹여나 잘못된 부분이 있다면 댓글 써주시면 감사하겠습니다. 다이나믹 프로그래밍 다이나믹 프로그래밍은 메모리를 적절히 사용하여 수행 시간 효율성을 비약적으로 향상시키는 방법이다. 이미 계산된 결과(작은 문제)는 별도의 메모리 영역에 저장하여 다시 계산하지 않도록 한다. 다이나믹 프로그래밍의 구현은 일반적으로 두 가지 방식(탐다운과 보텀업)으로 구성된다. 다이나믹 프로그래밍은 동적 계획법이라고도 부른다. 일반적인 프로그래밍 분야에서의 동적(Dynamic)이란? 자료구조에서 동적 할당 (Dynamic Allocation)은 '프로그램이 실행되는 도중에 실행에 필요한 메모리를 할당하.. Coding Test/Python 2021. 8. 22.