PLOD

MST하나의 그래프가 있을 때 모든 노드를 포함하면서 사이클이 존재하지 않는 부분 그래프를 의미한다. 이때 모든 노드가 포함되어 서로 연결되면서 사이클이 존재하지 않는다는 조건은 트리의 성립 조건이기도 하다. 최소 길이의 간선으로 모든 노드들을 연결해야 되는 문제가 나올 때 최소 신장 트리 알고리즘을 사용 할 수 있다.Kruskal Algorithm크루스칼 알고리즘은 대표 적인 최소 신장 트리 알고리즘이다. 크루스칼 알고리즘은 greedy algorithm(탐욕 기법)에 속한다. 먼저 모든 간선에 대하여 정렬을 수행한 뒤에 가장 거리가 짧은 간선부터 집합에 포함시키면 된다.  Kruskal 알고리즘은 간선을 정렬하는데 시간이 가장 오래 걸리기 때문에 간선의 개수가 E 일때, O(ElogE)의 시간 복잡도..

순차 탐색(sequential Search)선형 탐색이라고도 불린다. 리스트 안에 있는 특정한 데이터를 찾기 위해 앞에서부터 데이터를 하나씩 차례대로 확인하는 방법이다. 보통 정렬되지 않은 리스트에서 데이터를 찾아야 할 때 사용한다 .적용리스트가 아무리 많아도 시간만 충분하다면 항상 원하는 원소를 찾을 수 있다는 장점이 있다. 순차 탐색은 이름처럼 순차로 데이터를 탐색한다는 의미이다. 정렬되지 않은 데이터나 작은 데이터 셋을 탐색해야 할 때 간단히 구현 가능하다.시간복잡도는 O(n)이다.ex) 순차탐색으로 이름 리스트에서 원하는 이름의 순서 찾기#sequential_searchdef sequential_search(n,target,array) : for i in range(n) : if array..

정렬(sorting)이란 데이터를 특정한 기준에 따라서 순서대로 나열하는 것을 말한다. 프로그램에서 데이터를 가공할 때 오름차순이나 내림차순 등으로 대부분 어떤 식으로든 정렬해서 사용하는 경우가 많기에 정렬 알고리즘은 프로그램을 작성할 때 가장 많이 사용되는 알고리즘 중 하나다. 정렬 알고리즘으로 데이터를 정렬하면 이진탐색(binary search)가 가능해진다. 파이썬에서 버블정렬, 선택정렬 알고리즘을 사용하는 것보다 sort()함수와 sorted()함수가 O(NlogN)의 시간 복잡도를 보장해주기 때문에 더 효율적이지만, 간혹 수기로 코딩테스트를 보거나 직접 정렬 알고리즘을 아는지 물어보는 경우가 있기 때문에 알고 있는 것이 좋다1. 선택 정렬(selection sorting)컴퓨터가 데이터를 정렬할..

1. 흐른 시간 계산 2시 5분에서 4시 1분이 되려면 몇 분이 흘러야 하는지를 어떻게 계산해 볼 수 있을까? 단순히 다음과 같이 2시 5분에서 시작하여 1분 단위로 시뮬레이션을 하며 60분이 되면 시간을 늘리고 분을 다시 0으로 맞추는 식으로 진행해볼 수 있다. hour, mins = 2, 5 elapsed_time = 0 while True: if hour == 4 and mins == 1: break elapsed_time += 1 mins += 1 if mins == 60: hour += 1 mins = 0 print(elapsed_time) 2. 흐른 날짜 계산 2월 5일에서 4월 1일이 되려면 몇 일이 흘러야 하는지를 어떻게 계산해 볼 수 있을까? 윤년이 아니라고 가정하고 2월 5일에서 시작하..

컴퓨터는 문자를 문자로 기억하지 않는다. 그대신 순자로 기억하고 표현한다. 예를 들면 문자 'A'는 65로, 'B'는 66으로 표현한다. 그런데 사람마다 규칙을 개인대로 정하면 자칫 소통하는데 오류가 생길 것이다. 예를 들어 어떤 사람은 'A'는 1로, 'B'는 2로 표현 할 수 도 있을 것이다. 그래서 모든 사람이 공통적으로 쓸 수 있는 표준 규격이 필요한데, 이것이 바로 아스키(ASCII : American Standard Code for Information Interchange)다. 1967년에 만들어졌고 알파벳에 기초를 둔 문자 인코딩 방법이다. 아스키 코드에는 인쇄가 불가능한 33개의 제어문자 코드와 95개의 인쇄가 가능한 문자 코드가 있다. 아스키 코드는 0에서 127까지의 숫자를 이용하여 ..

1. BFS(Breadth - First -Search) : 너비우선탐색https://www.codecademy.com/article/tree-traversal Tree Traversal: Breadth-First Search vs Depth-First Search | CodecademyLearn about two standard tree traversal algorithms: breadth-first search and depth-first search.www.codecademy.com  시작 노드에서 인접 노드를 모두 방문하고 방문한 노드에서 인접 노드를 모두 방문하는 것을 반복하게 된다.  BFS를 이용하게 되면 가중치가 없다는 가정 하에 처음 방문한 노드들의 집합이 최단 경로가 없다.최대한 넓게 ..