본문 바로가기

알고리즘 자료구조11

[알고리즘] 정렬 (선택정렬, 삽입정렬, 퀵정렬, 계수정렬) 정렬 데이터를 특정한 기준에 따라서 순서대로 나열하는 것 이진 탐색을 하기위한 전처리과정 선택정렬, 삽입정렬, 퀵정렬, 계수정렬만 다뤄보자 선택 정렬 O(N^2) 가장 작은것을 선택하여 맨 앞과 바꾼다 특정한 리스트에서 가장 작은 데이터를 찾는 일이 코딩테스트에서 잦으므로 선택정렬 소스코드에 익숙해지자 array = [7, 5, 9, 0, 3, 1, 6, 2, 4, 8] for i in range(len(array)): min_index = i # 가장 작은 원소의 인덱스, i번째 인덱스와 바꿀 가장 작은 인덱스를 찾는다. for j in range(i+1, len(array)): if array[min_index] > array[j]: min_index =j array[i], array[min_inde.. 2021. 3. 17.

[알고리즘] 백트래킹 백트래킹 DFS (재귀) + 가지치기 (break or continue) 모든 경우의 수를 탐색하는 DFS의 기본개념과 다르게 DFS이면서 break나 continue등으로 가지치기를 해서 경우의 수를 줄이면 백트래킹이라고 한다. 대표적인 문제는 N-Queen이 있다. 2021. 3. 17.

[알고리즘] 최단경로 알고리즘 (다익스트라, 플루이드워셜) 최단 경로 알고리즘 한 지점에서 다른 특정 지점까지의 최단 경로를 구해야 하는 경우 다익스트라 최단 경로 알고리즘 O(ElogV), O(V^2) 그래프에서 여러개의 노드가 있을 때, 특정한 노드에서 출발하여 다른 노드로 가는 각각의 최단 경로를 구해주는 알고리즘 0 보다 작은 간선이 없을 때 이용된다 매 상황마다 가장 비용이 적은 노드를 선택해서 임의의 과정을 반복하기 때문에 그리디 알고리즘에 속한다. 알고리즘 원리 출발 노드를 설정한다. 최단 거리 테이블을 초기화한다. 방문하지 않은 노드 중에서 최단 거리가 가장 짧은 노드를 선택한다. 해당 노드를 거쳐 다른 노드로 가는 비용을 계산하여 최단 거리 테이블을 갱신한다. 위 과정에서 3번과 4번을 반복한다. 특징 각 노드에 대한 현재까지의 최단 거리 정보를.. 2021. 3. 17.

[알고리즘] 순열 (Permutation)과 조합(Combination) (파이썬) 순열과 조합 경우의수 한 번의 시행에서 일어날 수 있는 사건의 가지 수 재귀 함수, 반복문을 이용해서 직접 구현 가능하지만 실제 코딩테스트에서 직접 구현하기는 매우 번거롭다 순열 (Permutation) 서로 다른 n개에서 r개를 선택하여 일렬로 나열하는 것 $nPr = n! / (n-r)!$ 코딩테스트에서는 경우의 수 값만 출력하는 것이 아니라 모든 경우(사건)를 다 출력하도록 요구 파이썬 itertools 라이브러리를 이용한다. import itertools data = [1, 2, 3] for x in itertools.permutations(data,2): print(list(x), end= '') # [1, 2] [1, 3] [2, 1] [2, 3] [3, 1] [3, 2] 조합 .. 2021. 3. 15.

[알고리즘] 유클리드 호제법 (최대공약수, 최소공배수) 유클리드 호제법 유클리드 호제로 최대 공약수 구하기 두 자연수 A,B에 대하여 (A>B) A를 B로 나눈 나머지를 R이라고 한다. 이때 A와 B의 최대공약수는 B와 R의 최대 공약수와 같다 최소공배수 = 두 수의 곱 / 최대공약수 def gcd(a,b): if a % b == 0: return b else: return gcd(b, a % b) 2021. 3. 14.

[알고리즘] 투 포인터 투 포인터 리스트에 순차적으로 접근해야 할 때 2개의 점의 위치를 기록하면서 처리하는 알고리즘 특정한 합을 가지는 부분 연속 수열 찾기 시작점(start)와 끝점(end)이 첫 번째 원소의 인덱스(0)를 가르키도록 한다. 현재 부분합이 M과 같다면 카운트한다. 현재 부분합이 M보다 작으면 end를 1 증가시킨다 현재 부분합이 M보다 크거나 같으면 start를 1 증가시킨다 모든 경우를 확인할 때까지 2번부터 4번까지의 과정을 반복한다. 시작점을 오른쪽으로 이동시키면 항상 합이 감소하고 끝점을 오른쪽으로 이동시키면 항상 합이 증가하기 때문에 투포인터 알고리즘으로 해결 할 수 있다. 만약 리스트 내 원소에 음수데이터가 포함되어있는 경우에는 위 알고리즘으로 해결 할 수 없다. # 특정 합계 값이 5라고 가정 .. 2021. 3. 14.

[자료구조] 스택, 큐 (파이썬) 탐색 많은 양의 데이터 중에서 원하는 데이터를 찾는 과정 자료구조 데이터를 표현하고 관리하고 처리하기 위한 구조 스택 후입 선출 구조 (LIFO) 재귀 함수의 수행 또한 스택 자료구조를 사용한다. 기본 자료 구조 사용 stack [5,3,2,1] stack.appned(3) stack.pop() print(stack) print(stack[::-1]) # 최하단 원소부터 출력 큐 선입 선출 구조 (FIFO) Collections 에서 제공하는 deque 라이브러리 사용 from collections import deque queue = deque() queue.append(5) queue.popleft() queue.reserve() # 순서를 역순으로 바꾸기 (정렬을 의미하지는 않음) x = list(.. 2021. 3. 10.

[알고리즘] 재귀 함수 재귀 함수(Recursive Function) DFS와 BFS를 구현하려면 재귀 함수도 이해하고 있어야한다. 자기 자신을 다시 호출하는 함수 팩토리얼 예제 # 반복적으로 구현한 n! def factorial_interative(n): result = 1 # 1부터 n까지의 수를 차례대로 곱하기 for i in range(1,n+1) result *= i return result # 재귀적으로 구한 n! def factorial_recursive(n): if n [백준] 하노이의 탑 이동 순서 1759 (파이썬) def hanoi(n, a, b): n > 1: hanoi(n-1, a, 6-a-b) # 기둥이 1개 이상이면 그룹으로 묶인 n-1개 원판을 중간으로 먼저 다 옮기겠다 1, 2, 3이기 때문에 중.. 2021. 3. 8.

[알고리즘] DFS와 BFS (깊이 우선탐색과 너비 우선탐색) DFS (깊이 우선탐색) 그래프에서 깊은 부분을 우선적으로 탐색하는 알고리즘 스택 자료구조( or 재귀함수)를 이용한다 탐색 시작 노드를 스택에 삽입하고 방문 처리를 한다. 스택의 최상단 노드에 방문하지 않은 인접한 노드가 하나라도 있으면 그 노드를 스택에 넣고 방문 처리합니다. 방문하지 않은 인접노드가 없으면 스택에서 최상단 노드를 꺼냅니다. 더이상 2번의 과정을 수행할수 없을 때까지 반복합니다. BFS (너비 우선 탐색) 그래프에서 가까운 노드부터 우선적으로 탐색하는 알고리즘 큐 자료구조를 이용한다. 탐색 시작노드를 큐에 삽입하고 방문처리를 합니다. 큐에서 노드를 꺼낸 뒤에 해당 노드의 인접 노드 중에서 방문하지 않은 노드를 모두 큐에 삽입하고 방문 처리를 합니다. 더 이상 2번의 과정을 수행할 수 .. 2021. 3. 7.

[알고리즘] 이진탐색 알고리즘과 파라메틱서치 이진탐색 정렬되어 있는 리스트에서 _탐색 범위를 절반씩 좁혀가며 데이터를 탐색_하는 방법 (로그시간의 시간복잡도) 이진탐색은 시작점, 끝점, 중간점을 이용하여 탐색 범위를 설정합니다 순차탐색 리스트 안에 있는 특정한 _데이터를 찾기 위해 앞에서부터 데이터를 하나씩 확인_하는 방법 단계마다 탐색 범위를 2로 나누는 것과 동일하므로 연산 횟수는 logN에 비례합니다 시간 복잡도는 _O(logN)_을 보장한다파이썬 이진 탐색 라이브러리 # 이진 탐색 소스코드 구현 (재귀 함수) def binary_search(array, target, start, end): if start > end: return None mid = (start + end) // 2 # 찾은 경우 중간점 인덱스 반환if array[mid] .. 2021. 3. 7.

[알고리즘] 선택정렬, 삽입정렬, 퀵정렬, 계수정렬 정리 정렬 선택 정렬 처리되지 않은 데이터 중에서 가장 작은 데이터를 선택해 맨앞에 있는 데이터와 바꾸는 것을 반복한다 시간 복잡도는 O(n^2) 삽입 정렬 처리되지 않은 데이터를 하나씩 골라 적합한 위치에 삽입한다 시간 복잡도 O(n^2) 가장 빠른 경우는 O(n) 거의 정렬이 되었다고 가정할 시 퀵 정렬 기준데이터(pivot)을 설정하고 그 기준보다 큰 데이터와 작은 데이터의 위치를 바꾸는 방법이다 병합정렬과 더불어 프로그래밍 언어의 정렬 라이브러리에 근간이 되는 알고리즘이다 가장 기본적인 퀵 정렬은 첫 번째 데이터를 기준 데이터(Pivot)로 설정합니다 피봇을 기준으로 왼쪽은 큰값, 오른쪽은 작은값을 골라서 서로 바꿔주고 이 값들의 인덱스가 엇갈리는 경우 작은데이터와 피봇값의 위치를 변경한다 한 번 작업.. 2020. 11. 24.

이전 1 다음

티스토리툴바