Study Blog

재귀 알아보기어떠한 이벤트에서 자기 자신을 포함하고 다시 자기 자신을 사용하여 정의되는 경우 재귀라고 한다.이러한 재귀의 개념을 사용하여 1, 2, 3, ... 과 같이 무한하게 이어지는 자연수를 다음과 같이 정의할 수 있다. 자연수의 정의1은 자연수이다.어떤 자연수의 바로 다음 수도 자연수이다. 팩토리얼 알아보기재귀를 사용하는 대표적인 예로 양의 정수 곱을 구하는 팩토리얼 문제가 있다.팩토리얼은 양의 정수를 순서대로 곱한다는 의미로 순차 곱셈이라고도 한다. 양의 정수 n의 팩토리얼(n!)은 다음과 같이 재귀적 정의를 할 수 있다.팩토리얼 n!의 정의(n은 양의 정수)0! = 1n > 0 이면 n! = n × (n - 1)! 예를 들어 10!(10의 팩토리얼)은 10 × 9!로 구할 수 있고, 다시 9!..

큐 알아보기큐는 가장 먼저 넣은 데이터를 가장 먼저 꺼내는 선입선출 구조이다.큐에 데이터를 추가하는 작업을 인큐(enqueue), 데이터를 꺼내는 작업을 디큐(dequeue)라고 한다. 또 데이터를 꺼내는 쪽을 프런트(front), 데이터를 넣는 쪽을 리어(rear)라고 한다. 배열로 큐 구현하기스택과 마찬가지로 큐 또한 배열을 사용하여 구현할 수 있다.아래 그림은 배열의 맨 앞부터 순서대로 4개의 데이터 19, 22, 37, 53이 들어있다.배열 이름을 que라고 할 때 que[0] ~ que[3]까지 int형 데이터가 저장된다.(인덱스 0인 원소가 큐의 첫 번째 원소이다.)이 상태에서 데이터 24를 인큐하고 19를 디큐하는 과정을 알아보자.24를 인큐하기맨 끝 데이터가 저장되어 있는 que[3]의 다..

스택 알아보기데이터를 임시 저장할 때 사용하는 자료구조로, 데이터의 입력과 출력 순서는 후입선출(LIFO) 방식 스택에 데이터를 넣는 작업을 푸시(push)스택에서 데이터를 꺼내는 작업을 팝(pop)푸시하고 팝하는 윗부분을 꼭대기(top)아랫부분을 바닥(bottom) 스택 구현하기스택 배열: stk푸시한 데이터를 저장하는 스택 본체인 list형 배열, 인덱스가 0인 원소를 스택의 바닥이라고 한다.따라서 가장 먼저 푸시하여 데이터를 저장하는 곳은 stk[0]이다. 스택 크기: capacity스택의 최대 크기를 나타내는 int형 정수이며, 이 값은 배열 stk의 원소 수인 len(stk)와 일치한다. 스택 포인터: ptr스택에 쌓여 있는 데이터의 개수를 나타내는 정숫값을 스택 포인터라고 한다.물론 스택이 비..

https://vibeee.tistory.com/284 검색 알고리즘 - 해시법해시법해시법을 이용하면 검색과 더불어 데이터의 추가·삭제도 효율적으로 수행할 수 있다.해시법은 '데이터를 저장할 위치 = 인덱스'를 간단한 연산으로 구하는 것을 말한다. 원소 갯수가 13vibeee.tistory.com 지난 포스팅에서 소개했던 것처럼 해시 충돌이 발생할 때 해결하는 방법으로 체인법 외 오픈주소법이 있다.오픈 주소법오픈 주소법은 충돌이 발생했을 때 재해시(rehashing)를 수행하여 빈 버킷을 찾는 방법을 말하며 닫힌 해시법(closed hashing)이라고도 한다. 원소 추가하기아래 그림은 18을 추가하는 과정에서 충돌이 발생하는 상태를 보여준다. 이럴 때 재해시를 수행할 수 있다. 재해시를 위한 해시 함수..

해시법해시법을 이용하면 검색과 더불어 데이터의 추가·삭제도 효율적으로 수행할 수 있다.해시법은 '데이터를 저장할 위치 = 인덱스'를 간단한 연산으로 구하는 것을 말한다. 원소 갯수가 13인 경우 키를 원소 갯수에 나누면 아래와 같이 해시값을 구할 수 있다. 위 표에서 해시값 부분에서 새로 원소를 구해 저장한 배열을 해시 테이블이라고 하며, 해시 테이블은 아래와 같이 구해지게 된다. 이와 같이 키를 해시값으로 변환하는 과정을 해시 함수라고 하며, 일반적으로 해시 함수는 나머지를 구하는 연산 또는 그 연산을 응용할 때 주로 사용한다.해시 테이블에서 만들어진 원소를 버킷(Bucket)이라고 한다.(위 그림에서 0~12의 인덱스를 가진 배열) 해시 충돌위 해시 테이블에 18이라는 값을 추가하려고 할 때, 18을..