알고리즘(Python)/이론 (10) 썸네일형 리스트형 유클리드 호제법(Euclidean algorithm) 최대공약수와 최소공배수 구하기 최대공약수와 최소공배수는 수학의 기초 중 기초라고 할 수 있을 정도로 널리 알려진 개념이다.다음 이미지를 예시로 보자 상위의 숫자를 공통적으로 2로 나눌 수 있다.그 다음에도 2로 나눌 수 있다. 하지만 맨 하단에 있는5, 6, 9는 공통적으로 나눌 수 없다. 이 때 2 X 2 를 한 값인 4가 최대 공약수가 되는 것이다. 유클리드 호제법최대 공약수 최대공약수를 구하기 가장 쉬운 방법이 유클리드 호제법이다. 정의는 다음과 같다. "2개의 자연수 a,b (a > b)에 대해서 a를 b로 나눈 나머지가 r일 때, a와 b의 최대공약수는 b와r의 최대공약수와 같다." 예를 들어보자 두 수 a(270)과 b(192)가 있다. 큰 수에서 작은 수로 MOD(나머지 연산)을 수행한다.. 그리디(Greedy) 알고리즘 정의 : 그리디 알고리즘은 현재 상태에서 보는 선택지 중 최선의 선택지가 전체 선택지 중 최선의 선택지라고 가정하는 알고리즘이다. 수행과정1) 해 선택 : 현재 상태에서 가장 최선이라고 생각되는 해를 선택한다.2) 적절성 검사 : 현재 선택한 해가 전체 문제의 제약 조건에 벗어나지 않는지 검사한다.3) 해 검사 : 현재까지 선택한 해 집합이 전체 문제를 해결할 수 있는지 검사한다. 전체 문제를 해결하지 못한다면 1) 로 돌아가 같은 과정을 반복한다.여기서 현재 상태에서 가장 최선이라는 말을 봐야 한다. 전체적인 그림을 보면 Maximum값은 $100 이다. 그러나 Greedy의 경우는 $20을 선택한다. 즉 현재 상태에서 가장 최선은 $20인 값인 것이다.이 말을 다시 정.. 이진 탐색(Binary search) 정의 : 이진 탐색은 데이터가 정렬돼 있는 상태에서 원하는 값을 찾아내는 알고리즘이다. ※ 피봇은 특정한 값(꼭 가운데일 필요는 없지만 일반적으로 가운데를 선택)을 기준으로 나눠서 정렬하는 것이고 이진 탐색은 정렬이 되어 있다. 대상 데이터의 중앙값과 찾고자 하는 값을 비교해 데이터의 크기를 절반씩 줄이면서 대상을 찾습니다. 기능 : 타킷 데이터 탐색특징 : 중앙값 비교를 통한 대상 축소 방식시간 복잡도 : O(logN) 1) 40보다 커 작아? 커2) 69보다 커 작아? 작아3) 54보다 커 작아? 커 → 더 이상 없네? 66이다. 깊이 우선 탐색(DFS), 너비 우선 탐색(BFS) DFS - BFS의 공통점, 차이점 그래프란, 정점(node)와 그 정점을 연결하는 간선(edge)으로 이루어진 자료구조의 일종을 말한다.그래프를 탐색한다는 것은 하나의 정점으로부터 시작하여 차례대로 모든 정점들을 한 번씩 방문하는 것을의미한다. 단순히 모든 정점을 방분하는 것이 중요한 문제의 경우 아무거나 상관없다.그러나 방식마다 다르다. ● DFS(깊이 우선 탐색)- 현재 정점에서 갈 수 있는 점들까지 들어가면서 탐색- 경로의 특징을 저장해둬야 할 때는 DFS를 사용한다. ● BFS(너비우선탐색)- 현재 정점에 연결된 가까운 점들부터 탐색- 미로 찾기 등 최단 거리를 구해야 할 경우, BFS가 유리하다 1) 깊이 우선 탐색깊이 우선 탐색은 그래프의 시작 노드에서 출발하여 탐색할 한 쪽 분기를 정하여 .. 재귀함수(Recursive Function) 정의 : 함수 안에 자신의 함수를 다시 호출하는 함수를 의미한다. 이러한 재귀함수는 로직을 내부적으로 반복하다가 일정한 조건이 만족되면 함수를 이탈하여 결과를 출한다. 이러한 재귀함수의 가장 대표적인 사용 예제는 팩토리얼(Factorial)이다. 다음 예시 그림을 보자 인자를 5를 넣으면 5 * 4 * 3 * 2 * 1이 되는 것이다. 함수를 호출할 때마다 콜스택에는 함수의 매개변수, 지역변수, 반환주소 값 등을 모두 저장하게 되는데, factorial(5)를호출하게되면 반환타입 부분에서 5 * factorial(5-1)이 수행되면서 factorial(4)가 호출되고 반환을 기다리게 된다.→ 이 방식을 반복 문제점이러한 재귀 함수 사용에는 스택 오버플로우(stack overflow)를 .. 정렬 알고리즘 p-113부터 풀기 버블(Bubble)정의 : 데이터의 인접 요소끼리 비교하고. swap연산을 수행하며 정렬하는 방식- 두 인접한 데이터의 크기를 비교해 정렬하는 방법이다. 시간 복잡도는 O(n^2),으로 다른 알고리즘보다 속도가 느린 편이다. 선택(Selection)정의 : 대상에서 가장 크거나 작은 데이터를 찾아가 선택을 반복하면서 정렬하는 방식- 선택 정렬(selection sort)은 대상 데이터에서 최대나 최소 데이터를 데이터가 나열된 순으로 찾아 가며 선택하는 방법이다. 삽입(Insertion)정의 : 대상을 선택해 정렬된 영역에서 선택 데이터의 적절한 위치를 찾아 삽입하면서 정렬하는 방식이미 정렬된 데이터 범위에 정렬되지 않은 데이터를 적절한 위치에 삽입시켜 정렬하는 방식이다.퀵(Quick)정의 : pivo.. 스택(Stack)과 큐(Queue) - P 89부터 다시 기본적인 자료구조의 입출력에 대한 정의는 알고 있다. 스택은 LIFO(Last In First Out)이고 큐는 FIFO(First in First Out)이다. 이를 토대로 알고리즘 관련을 푼다. 스택스택은 삽입과 삭제 연산이 후입선출로 이뤄지는 자료구조이다. 삽입과 삭제가 한 쪽에서만 일어나는 특징이 있다.다음의 그림과 같다. 파이썬의 스택위치- top : 삽입과 삭제가 일어나는 위치를 뜻한다. 연산(리스트 이름이 s일 때)- s.appned(data) : top 위치에 새로운 데이터를 삽입하는 연산이다.- s.pop() : top 위치에 현재 있는 데이터를 삭제하고 확인하는 연산이다.- s[-1] : top위치에 현재 있는 데이터를 단순 확인하는 연산이다. 다음의 그림은 예시이다. 스택은 깊이 우선.. 투 포인터 2개의 포인터로 알고리즘의 시간 복잡도를 최적화한다. - 문제어떠한 자연수 N은 몇 개의 연속된 자연수의 합으로 나타낼 수 있다. 당신은 어떤 자연수 N(1 ≤ N ≤ 10,000,000)을 몇 개의 연속된 자연수의 합으로 나타내는 가짓수를 알고 싶다. 이 때 사용하는 자연수는 N이어야 한다. 예를 들어 15를 나타내는 방법은 15, 7+8, 4+5+6, 1+2+3+4+5이다. ① 문제분석하기시간 제한은 2초이다. N의 최댓값은 10,000,000으로 "매우 크게 잡혀"있다. 이런 상황에서는 O(nlogn)의 시간 복잡도 알고리즘을 사용하면 제한 시간을 초과하므로 O(n)의 시간 복잡도 알고리즘을 사용해야 한다.파이썬의 연산은 1초에 2000번~1억 번사이다. 최악의 경우인 2000번으로 이해한다. - .. 이전 1 2 다음 목록 더보기
