전체 글(121)
-
BOJ_1931_회의실 배정
1. 구분: 그리디 알고리즘 언어: Python 전략: 회의의 끝나는 시간을 기준으로 가장 일찍 끝나는 회의들을 회의실에 배정한다. 2. 코드 3. - DP로도 풀 수 있을 것이라 착각했다. - 확실하게 그리디 알고리즘의 정당성을 부여하지 못한 것 같다. - lambda를 이용해 문제를 푼 코드들을 여럿 보았다. 공부 후 적용해보도록 해야겠다.
2021.07.13 -
BOJ_2217
1. 구분: 그리디 알고리즘 언어: 파이썬 전략: 2. 코드 3. - 처음 이 방법을 고안했는데, 시간 초과가 나지 않을까 걱정했다. 하지만 N
2021.07.13 -
B - Tree & B + Tree
B-Tree 하나의 노드에 여러 자료(데이터)가 배치되는 트리 구조 스스로 균형을 맞추는 트리 --> 최악의 경우에도 O(logN)의 검색 성능을 보인다. 한 개의 노드에 M개의 자료가 배치되면 M차 B 트리라 한다 규칙 - 노드의 자료수가 n이라면, 자식 수는 n+1 - 각 노드의 자료는 정렬된 상태 - root노드는 적어도 2개 이상의 자식을 가짐 - root노드 제외 모든 노드는 적어도 M/2개의 자료를 가짐 B+ Tree 색인 구조에서 순차 접근에 대한 문제의 해결책으로 제시 key값이 leaf node와 leaf의 부모 노드에 공존 B-Tree의 변형 구조로 index부분과 leaf노드로 구성된 순차 data부분으로 이루어짐 index 부분의 key값은 leaf에 있는 key값을 직접 찾아, 모..
2021.07.12 -
BOJ_9095_1,2,3 더하기
1. 구분: 다이나믹 프로그래밍 언어: Python 2. 코드 3. 탑 다운 방식을 이용한 다이나믹 프로그래밍 dp는 한번 계산된 결과값을 메모이제이션 하기 위함이다. 점화식을 구하기 위해, 약간의 노동이 있었는데, 이렇게 구하는 것이 맞는지 잘 모르겠다. 함수 find에서 n >= 4 이상이라는 조건을 주지 않아 처음에 오류가 발생했다,
2021.07.11 -
Red - Black Tree
red-black 트리는 binary 트리의 일종, 균형 잡힌 tree, 가장 유명하다. Red - Black Tree의 조건 모든 노드는 red 혹은 black의 색깔을 가지고 있다. root 노드는 무조건 black이다. leaf(None) 노드는 black이다. red 노드의 child는 모두 black이다. black노드의 자식 색깔은 상관이 없다. 각 노드에서 leaf node 까지 갈 때의 black 노드 수가 항상 같아야 한다. Red - Black Tree의 사실 및 증명 h(v) = v의 높이(height) bh(v) = v에서 leaf node까지 v를 제외한 black노드의 개수 사실 1. v의 서브 트리의 내부 노드 수 >= 2^bh(v) - 1 사실 2. h = O(logn) re..
2021.07.11 -
Hash Table
해시 테이블 Hash Table: Key와 Value를 1:1로 매핑시켜, Key를 통해 Value값을 도출한다. Hash Table은 매우 빠른 평균, 삽입, 삭제, 탐색 연산을 제공한다. 해시 함수 key ---f(key)---> index: f(x)는 해시함수이다. 해시함수의 역할: key값을 작은 범위의 값인hash로 변경한다. hash는 저장소에 value와 매핑되어 저장된다. 해시함수의 종류와 특징 충돌(collision): 서로 다른 여러 key값이 동일한 hash값으로 결과가 되는 경우 - 충돌을 막기 (최소화 하기) 위한 hash function이 필요하다. open addressing - 추가 메모리 공간의 사용 없이, 기존 메모리 공간을 이용한다. - 충돌이 발생했을 때, 빈 공간에 ..
2021.07.10