본문 바로가기

알고리즘5

알고리즘 키워드 정수론, 배열, 문자열, 재귀함수, 정렬, 완전탐색, 시간복잡도 이분탐색, 분할정복, 스택, 큐, 우선순위 큐 그래프(vertex, edge, node, arc), BFS, DFS, 위상정렬 동적 프로그래밍, 그리디 알고리즘 2022. 9. 29.

[Week05] C언어 - Red Black Tree Red - Black Tree 레드 블랙 트리 https://ko.wikipedia.org/wiki/레드-블랙_트리 레드-블랙 트리 - 위키백과, 우리 모두의 백과사전 레드-블랙 트리(red-black tree)는 자가 균형 이진 탐색 트리(self-balancing binary search tree)로서, 대표적으로는 연관 배열 등을 구현하는 데 쓰이는 자료구조다. 1978년 레오 귀바스(Leo J. Guibas)와 로버트 ko.wikipedia.org 이진 탐색트리의 한 종류 BTS의 worst case의 단점을 개선 - 스스로 균형을 맞추며 편향된 트리가 되지않도록 한다. 최악의 경우에도 시간복잡도가 O(logN) 규칙 레드와 블랙으로만 이루워진다. 루트 노드는 블랙이다. nil노드는 블랙이다. 레.. 2022. 5. 5.

[Week03] 알고리즘 - DFS / BFS 백준 문제 두 문제를 구분하는 기준이 약간 모호하지만.. 문제를 풀면서 만났던 몇몇 유형들을 까먹지않기 위해 정리해둔다. DFS / 백트래킹 nums = [1,2,3] result = [] permute = [] def dfs(): if len(permute) == len(nums) : result.append(permute[:]) return for i in range(len(nums)) : if nums[i] not in permute : permute.append(nums[i]) dfs() permute.pop() dfs() print(result) DFS 25731번 : 빙산 https://www.acmicpc.net/problem/2573 2573번: 빙산 첫 줄에는 이차원 배열의 행의 개수와 열의 개수를.. 2022. 4. 21.

[Week03] 알고리즘 - 유니온 파인드 트리 탐색 알고리즘 - 유니온 파인드 Union Find ✅ 개념 / 원리 : 대표적인 트리 알고리즘 : 합집합 찾기, 서로소 집합 알고리즘 이라고도 부른다. 유니온 파인드는 집합(set)을 합하기위한 연산이다. 양뱡향 연결 리스트를 사용해 합집합 연산 구현이 가능하지만 시작 복잡도가 안좋아 트리 형태를 활용한다. 부모를 가르키는 트리처럼 링크를 만들어 집합을 표현한다. 하나의 트리가 하나의 set이며 트리의 parents를 찾아 올라가 루트를 만나면 루트값이 집합의 대표값이다. 두개의 집합에 루트값을 찾아서(find) 루트값이 다르면 하나의 트리로 만든다.(union) > 트리 높이 h만큼의 시간 복잡도를 갖는다. 집합의 합집합 시킨다는 개념을 생각하면 문제 풀때 헷갈려서 주어진 그래프의 루트를 찾는 .. 2022. 4. 20.

[Week01] 알고리즘 - 정렬01 정렬01 ✅ 파이썬 내장함수 arr.sort() : 오름차순 정렬 arr.sort(reverse = True) : 내림차순 정렬 #백준11650 - key값으로 정렬 arr = [] for _ in range(int(input())): arr.append(list(map(int, input().split()))) arr.sort(key=lambda x:(x[0], x[1])) #x[0]의 크기를 기준으로 정렬, 값이 같다면 x[1]으로 비교 for e in arr: print(str(e[0]) + " " + str(e[1])) ✅ 버블 정렬 : 서로 인접한 두 원소를 검사하여 정렬한다. (swap) 시간복잡도 O(N^2) def bubble_sort(arr): for i in range(len(arr) .. 2022. 4. 9.

이전 1 다음

티스토리툴바