재귀
-
어떤 문제를 해결하기 위해 알고리즘을 설계할때 동일한 문제의 작은 경우를 해결함으로써 그 문제를 해결하는 것. 문제가 간단해져서 바로 풀 수 있는 문제로 작아질 때 까지
-
호출 관계로 재귀를 이해 해보자(호출 순서까지 들어가지 말자)
-> 문제가 주어졌을때 논리(재귀)로 표현하고 code를 작성하는 것으로 끝내보자.
우리는 컴퓨터 구조에서 우리가 입력한 코드들이 컴파일이 되어 main memory에 명령문들이 저장이 되고 cpu가 가져와서 처리하는 것을 배웠다. 즉 우리가 만든 함수가 연속적으로 이동이 되는 것 으로 이해 해보자
- 재귀함수의 중요한 포인트
-
base case 도달 -> 탈출 조건
-
논리의 구현
.(윤성우의 열혈 자료구조 참조)
(우리가 고등학교에서 배웠던 표현이 재귀다, 위의 식을 컴퓨터로 표현 가능해보자)
이 또한 f(n)의 값을 더 작은 범위의 함수인 f(n-1)을 이용하여 구하였다.
수학적인 표현을 만들고 변환 해보자!
f(n)구하려고 더 넓은 범위의 f(n+1)을 구할 수 없다
이진 탐색 (binary Search)
-
정렬된 리스트에서 원하는 항목을 찾기에 효율적인 알고리즘.
-
후보 범위가 한 항목으로 좁아질때 까지 찾고자 하는 항목을 포함하고 있는 리스트를 반으로 나누는 과정을 계속 반복
#대략적인 코드
numbers =[] # 사용자 입력 받기
min = 0
guess = min + max //2
max= n-1
if numbers[guess] == target:
return numbers[guess]
elif numbers[guess] <= target:
min = guess +1
else:
max = guess - 1
분할 정복
그대로 해결할 수 없는 문제를 작은 문제로 분할하여 문제를 해결하는 방법이다. 예를 들면 binary search, merge sort, quick sort가 있다.
- 분할하여 재귀적으로 해결한후, 결과를 합쳐 원래의 문제의 답을 얻어 해결한다
우선순위 큐
-
우선 순위가 가장 높은 데이터를 먼저 삭제하는 자료구조
-
리스트를 이용한 구현한 방법
-
힙을 이용한 구현한 방법
링크드 리스트
- 메모리의 효율적 사용을 위한 방법
- array list :같은 타입의 메모리상에 실제로 연속적으로 붙어있음
- linked list : 각각의 element들이 서로 떨어져 저장 되어 있으나 연결되어있음
- 구조: 노드가 data filed와 link field로 나누어져 있음 ,head 변수는 항상 첫번째 노드(시작 노드) 가리키고 있음, 시작부분에 추가되면 head는 변경됨
해시 테이블
- 원소가 저장될 자리가 원소의 값에 의해 결정되는 자료구조
- 평균 상수 시간에 삽입,삭제 검색
- 매우 빠른 응답을 요하는 응용에 유용
- 최소 원소를 찾는 것과 같은 작업은 지원하지 않는다.
- 해시 함수: 테이블에 데이터 저장할때 사용(나누기, 곱하기 방법 존재)
h(x) = x mod m
m:해시 테이블 사이즈 ,대개 prime number로 되어있음
크기가 13인 해시 테이블에 5개의 원소가 저장 되었을때 입력이 25,13,16,15,7이다. 이때 테이블에 저장된 데이터를 그려보자
충돌 : 해시 테이블의 한 주소를 놓고 두개 이상의 원소가 다투는 것
충돌 해결: 체이닝 ,개방주소 방법
체이닝 : 같은 주소로 해싱 되는 원소를 모두 하나의 연결 리스트로 관리한다, 추가적인 연결 리스트 필요
개방주소 : 기존 공간에서 빈 공간을 찾아간다. 추가적인 공간 불 필요,빈자리가 생길때 까지 해시값을 계속 만들어 낸다(선형 조사 ,이차원 조사 ,더블 해싱)
선형 조사 : 빈 공간 나올때 까지 계속 찾는다
이차원 조사: 1칸아래 다음에는 2칸 다음에는 3칸 씩 빈공간 나올때 까지 찾아본다
더블 해싱 : 해싱함수 2개를 두겠다
데이터 삭제: 삭제시 표시를 해두어야 테이블에 저장된 값을 찾을때 문제가 발생하지 않는다
