학습저널

해시 함수(Hash function) 해시 함수는 임의 길이의 데이터를 고정된 길이의 데이터로 바꿔주는 함수이다. 해시 함수에 의해 얻어지는 값은 해시 값 또는 해시라고 부른다. 위키백과에 게재되어 있는 해시 함수의 정의다. 간단히 말하면 특정 값을 넣었을 때, 내가 원하는 범위의 값이 나오게 만드는 함수라고 말 할 수 있다. 간단히 그림으로 표현하자면 다음과 같이 표현할 수 있다. 해시 함수의 용어로는 충돌(Collision)과 클러스터(Cluster)가 있다. 충돌은 다른 값을 넣었을 때 같은 해시 값이 나오는 경우를 말한다. 클러스터는 해시 값에 의해 저장된 값들이 특정 구역에 몰리는 현상을 말한다. 그럼 이런 해시 함수는 왜 존재하는 걸까? 해시 함수는 주로 보안, 오류 검사, 자료구조 등 활용 ..

https://www.hackerrank.com/challenges/ctci-fibonacci-numbers/problem 피보나치 수열을 구하는 아주 간단한 예제다. 거의 시키는 대로 구현만 하면 되므로 아주 간단하게 짤 수 있지만 아래 코드의 시간복잡도를 계산해 보면 효율적이지 못한 코드다. 풀이시간 : 1분 50초 1234567891011121314int fibonacci(int n) { if(n == 0) { return 0; } else if(n == 1) { return 1; } else { return fibonacci(n-1) + fibonacci(n-2); }}Colored by Color Scriptercs 한번 함수가 호출 될 때 마다 2번씩 함수를 호출하므로 그림으로 그려보면 바이너..

https://www.hackerrank.com/challenges/ctci-queue-using-two-stacks/problem Queue를 Stack 두개로 구현하는 문제이다. 처음 생각난 방법으로 구현했을 때 Time Out이 발생했고, 두번째 방법으로 풀었을때 성공을 했다. 방법 1 Push : 1. Push를 할 떄마다 Stack1의모든 원소를 순차적으로 꺼내 Stack2에 넣고 주어진 원소를 Stack1에 Push 한다. 2. Stack2의 모든 원소를 순차적으로 꺼내어 Stack1에 Push 한다.Pop : 1. Stack1은 이미 Queue 형태로 정렬되어 있기 때문에 Pop하면 된다. 하지만 이 방법을 쓰면 모든 원소를 총 두번 이동시키므로 Push는 2N의 시간복잡도를 가지게 된다. ..

https://www.hackerrank.com/challenges/ctci-balanced-brackets/problem ( ), { }, [ ] 로 이루어진 String이 주어졌을 때, 이 괄호 문자열이 Balanced 인지 판별하는 문제다. 이 문제에서 말하는 Balanced는 한번 열린 괄호가 짝이 맞춰지면서 모두 닫히는 조건을 말한다. 괄호 문제는 Stack 자료구조를 활용하면 쉽게 풀 수 있다. 열린 괄호가 입력되면 Stack에 넣고, 닫힌 괄호가 입력되면 Stack의 맨 위 요소와 쌍이 맞는지 확인하고 Stack에서 제거하는 방식으로 진행하면 된다. 코드 상에서 Balanced 한 조건을 판별하기 위해서는 다음과 같은 조건을 갖추면 된다. 1. 닫힌 괄호인 경우 Stack이 비어있지 않은지 ..

https://www.hackerrank.com/challenges/ctci-ransom-note/problem 한 납치범이 몸값을 요구하는 편지를 작성하기 위해 주어진 잡지의 단어를 오려내고자 하는데, 원하는 편지를 주어진 잡지의 단어만으로 작성할 수 있는지 답을 내는 문제다. 생각난 방법은 다음과 같다. 1. 이중 for문을 통해 전수조사2. 해시 자료구조를 통해 O(n)의 시간으로 조사 (n : ransom-note의 단어 갯수) 1번 방법은 주어진 벡터 2개를 받아 일일히 검사하고, 같은 단어가 나올 때 마다 magazine 벡터에서 해당 원소를 제거하는 방식으로 알고리즘을 구현하였다. 1234567891011121314151617bool ransom_note(vector magazine, vec..

https://www.hackerrank.com/challenges/ctci-is-binary-search-tree/problem 주어진 Tree 자료구조가 BST(Binary Search Tree) 인지 판별하는 문제다. 처음에는 단순히 자료의 저장 방법에만 신경을 쓰며 풀어서 오답이 나왔다. 자료의 저장 방법은 데이터가 들어있는 노드의 값보다 작은값은 왼쪽 노드로, 큰 값은 오른쪽 노드로 진행하면서 비어있는 노드를 찾아 저장하는 방법이다. 오답이 나오고 다시 생각을 해 보니 단순히 각 노드의 Left, Right 값의 대소관계만을 고려하면 진짜로 BST인지 판별이 불가능 하다는 생각이 들었다. BST는 특정 노드 A의 왼쪽 서브트리의 모든 값은 A의 데이터값보다 작아야 되며, 오른쪽 서브트리의 값은 ..

https://www.hackerrank.com/challenges/ctci-array-left-rotation/problem 주어진 배열을 Left Rotation 시키는 아주 기본적인 문제이다. 예전 모 기업의 코드테스트 중 이 오퍼레이션이 나왔었는데, 첫문제로 주어져 긴장이 안풀려서 그런지 동작은 되는 엉망진창인 코드를 제출한 기억이 있다. 그래서 포스트로 작성해 본다. 1234567891011121314vector array_left_rotation(vector a, int n, int k) { int tmpValue = 0; int moveValue = a[0]; int dindex = 0; vector returnarray(n); for(int i = 0; i c, c -> d 순으로 순차적으..

졸업과제 프로젝트를 하던 중 이해가 잘 안가는 문법이 발견되었다. 12345678template size_t generateAdjacency(Graph* seqCollection){ typedef typename graph_traits::vertex_descriptor V; typedef typename Graph::Symbol Symbol; typedef typename Graph::SymbolSet SymbolSet;...}Colored by Color Scriptercs template 문법은 알고 있었지만 typename이라는 부분이 이해가 잘 가지 않았다. 여러 포스트들을 둘러 본 결과 typename은 다음과 같은 의미를 가진다 1. template 선언 시 class 대신에 사용할 수 있는 ..