본문 바로가기

SW사관학교 정글/개발일지 - TIL8

[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.

[Week04] 알고리즘 - 비트 마스킹 백준 외판원 순회 문제(TSP)를 풀려면 비트 마스킹에 관한 개념이 필요하여 공부하게되었다. 해당 문제 https://www.acmicpc.net/problem/2098 2098번: 외판원 순회 첫째 줄에 도시의 수 N이 주어진다. (2 ≤ N ≤ 16) 다음 N개의 줄에는 비용 행렬이 주어진다. 각 행렬의 성분은 1,000,000 이하의 양의 정수이며, 갈 수 없는 경우는 0이 주어진다. W[i][j]는 도시 i에서 j www.acmicpc.net keywords 비트마스킹 dp, 비트마스킹 bfs, 비트마스크 순열, 비트마스크 조합 비트 마스킹 컴퓨터는 내부적으로 모든 자료를 이진수로 표현한다. 이와 같은 특성을 이용해 정수의 이진수 표현을 자료구조로 쓰는 기법이다. check = [False] * .. 2022. 4. 26.

[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.

[Week02] 알고리즘 - 큐 (feat. python) 모듈 : 함수,변수 또는 클래스들을 모아놓은 파일 - 파일명이 모듈명이 된다. if __name__ == "__main__" 의 의미 👉 python은 c나 java와 다르게 스크립트 기반 인터프리터 언어로 특별히 시작 지점이 명시가 되어있지 않은 언어이다. 그래서 특별히 변수를 할당하여 현재 스트립트의 시작점이 어디인지 판단하는데 그 변수로서 이용하는 것이 __name__ 이다. 파일 실행시에는 __name__ 변수에 "__main__"을 저장하게 되지만 해당 모듈이 import 될 경우 변수에 "모듈명"이 들어가기때문에 if __name__ == "__main__" 문은 실행되지않는다. __init__의 의미 👉 생성자의 의미 ( 여기서 self는 인스턴스 자신, 메소드의 임의의 인수 정도의 의미를 .. 2022. 4. 14.

[Week02] 알고리즘 - 이분탐색 [Week02] 알고리즘 키워드 - 이분탐색, 분할정복, 스택, 큐, 우선순위 큐 검색 알고리즘 - 선형탐색 / 이분 탐색 이분탐색 정렬이 되어있는 배열에서 특정 데이터를 찾기 위해서 모든 데이터를 순차적으로 확인하는 대신 탐색의 범위를 절반으로 줄여나가는 탐색 방법 이분탐색 사용시 주의사항 주어진 배열은 정렬되어있어야한다. 무한 루프에 빠지지않게 mid값을 잘 지정해준다 차례로 증가(혹은 감소)시키면서 풀어야하는 탐색문제에 큰 수의 범위가 주어진다면 이분탐색을 떠올려보자. 시간복잡도 O(logN) ✅ 이분탐색 구현하기 while문을 이용하여 구현 def binary_serch(a,n_list) : st = 0 en = n-1 while st a : en = mid -1 else : st = mid + .. 2022. 4. 9.

이전 1 2 다음

티스토리툴바