목록분류 전체보기 (116)
Game Tech Blog
Data Structure - Red Black Tree (작업중, 알고리즘으로 이전할 것)
Binary Search Tree? 레드 블랙 트리를 배우기 전 알아야할 자료구조. 이진 검색 트리는 저장과 검색에 평균 O(LogN) , 최악 O(N) 의 비교적 불완전한 구조를 가진다. 이 불 완전성을 해결하기 위해 고안된 것이 균형잡힌 이진트리 이다. 균형잡힌 이진트리로 대표적인 것은 레드 블랙 트리, AVL 트리이다. 여기서는 레드 블랙 트리를 다룬다. 이 Tree 에서 중위 순회(왼쪽자식 -> 부모 -> 오른쪽자식)를 할 때, 다음과 같은 Key를 얻는다. 결과 : 20 -> 30 -> 40 -> 50 -> 60 -> 80 이를 다시 트리에 넣게 되면, 다음과 같은 최악의 구조가 나온다. 이 Depth 를 Balance 있게 잡아줄 트리라고 생각하면 된다. Red Black Tree ? 기본은 ..
Data Structures - Hash Table
Hasing ? - 임의의 길이의 값을 해시함수를 사용하여 고정된 크기의 값으로 변환하는 작업 Hash Table ? - 해시 함수를 사용하여 변환 값을 Index 로 삼아 Key, Value를 저장하는 자료구조 - 기본연산으로는 탐색, 삽입, 삭제 등이 존재 - 저장된 데이터를 찾을 때, hash_function을 한번만 수행하면 array내 저장된 Index위치를 찾아낼 수 있어서 탐색이 O(1) 이다. - 순차 검색에 비해 비교도 안될정도로 빠르다. 해쉬 함수의 알고리즘 - Division Method (나눗셈 법) 입력 값을 테이블의 크기로 나누고 그 나머지를 테이블의 인덱스로 이용하는 알고리즘 // 인덱스 (해시 값) = 입력 값 % 테이블의 크기 - Digit Folding (자릿수 접기) 숫..
Dictionary ? - Dictionary 란 Key, Value 로 나누어진 값으로 이루어져 있다. Python 에서 사용된다고 한다. - Vector, List , Array 에서는 숫자 인덱스로 Value 를 참조했으나, Dictionary 에서는 문자로 값을 참조할 수 있다고 한다. Dictionary Vs Map - 공통 1. Key , Value 를 가지고 있으며, Key로 찾아서 Value를 참조하는 자료구조 2. 중복 Key 값이 존재할 때 값을 넣지 않는다. (중복 Key 불허함, Key의 Unique한 성질을 보장해야함) - 차이 - Map 1. Key값을 기준으로 요소들이 추가,삽입,삭제될 때, 재정렬을 수행한다. 2. 내부가 트리로 구성된다 (레드 블랙 트리로 구성) 3. 트리로..
1463번 - 1로 만들기 풀이
문제 정수 X에 사용할 수 있는 연산은 다음과 같이 세 가지 이다. X가 3으로 나누어 떨어지면, 3으로 나눈다. X가 2로 나누어 떨어지면, 2로 나눈다. 1을 뺀다. 정수 N이 주어졌을 때, 위와 같은 연산 세 개를 적절히 사용해서 1을 만들려고 한다. 연산을 사용하는 횟수의 최솟값을 출력하시오. 입력 첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다. 출력 첫째 줄에 연산을 하는 횟수의 최솟값을 출력한다. 예제 입력 1 2 예제 출력 1 1 예제 입력 2 10 예제 출력 2 3 힌트 10의 경우에 10 -> 9 -> 3 -> 1 로 3번 만에 만들 수 있다. 문제풀이 이 문제의 경우 분류가 DP로 들어가있다. 이런 경우, 항상 끝이 좋지 않았는데, 이유는 절대 단순히 풀어서..
보호되어 있는 글입니다.
보호되어 있는 글입니다.
모래시계 만들기
2020 C 코딩테스트 1번 문제.. 조건 1. 가로세로가 n 인 사각형이 주어짐 (n은 양수이며, 그 중에서도 홀 수만 주어진다.) 2. Input과 Output은 다음과 같다. Input 5 Output 1 2 3 4 5 0 2 3 4 0 0 0 3 0 0 0 2 3 4 0 1 2 3 4 5 --------------------------------------------------------------------------------------------------- 풀이 1. 먼저 섹션을 생각해보자. 2. 별을 먼저 찍어보고, 숫자로 출력해보자. 풀면서, 내 접근 방식이 틀렸다는 것은 두가지였다. 하나는 무의식적으로 메모리를 할당하여 하는 방법을 선택했다는 점 또 하나는, 처음부터 0이 아닌 수의 ..
보호되어 있는 글입니다.