반응형 🌈 백엔드/자료구조31 재귀함수 재귀함수 어떤 함수가 자신을 다시 호출하여 작업을 수행한다 (반복문) 재귀함수 예제 1 3 9 27 .. 의 n번째 수는 무슨 정수인가? 1 (1*3) (3*3) (3*3*3) .... n이 첫번째이면 결과값은 1 recursion 함수를 실행하면 함수에 n-1번째 값에 3을 곱한 값이다 n이 4라면 recursion(4-1) 3번째 수 (3*3) 에 3* 한 값 static int recursion (int n) { if( n ==1) { return 1; } return 3 * recursion(n-1);} 1 2 3 4 5 6 ... n번째 까지의 합 static int recursion (int n) { if( n ==1) { return 1; } return n + recursion(n-1);}.. 2023. 11. 20. 접미사 배열 & 맨버 마이어스 알고리즘 문자열 알고리즘 종류 KMP 알고리즘 라빈카프 알고리즘 접미사 배열 - 맨버 마이어스 알고리즘 아호-고라식 Z 알고리즘 접미사 배열 suffix array 정의 : 문자열 H가 문자열 N을 포함한다면 N은 H의 어떤 접미사의 접두어라는 전재로 전체 문자열 S 의 모든 접미사들을 사전순으로 정렬한 배열이다 S 문자열 = banana 에 대한 정렬되지 않은 Suffixr이다 (한글자씩 지우면 배열이 나온다) banana anana nana ana na a 맨버-마이어스 알고리즘 Manber-Myers 알고리즘은 랭크 개념과 기수 정렬을 사용하여 시간 복잡도를 줄이는 알고리즘이다 (한글자씩 비교하면 오래걸리잖아. 그럼 2글짜씩 겹쳐지는 단어로 구분해서 정렬해보자 , 2글짜씩 구분했는데도 또 겹쳐지는 단어가 있.. 2023. 11. 20. 자료구조_검색 ⑥ 해싱 검색 - 링크드해쉬셋 LinkedHashSet LinkedHashSet 특징 중복 허용 안됨 삽입 순서에 의해 반복 HashSet을 상속하여 구현된 형태이다 값의 저장된 순서가 중요할때 사용한다 LInkedHashSet LinkedHashSet 선언하기 import java.util.LinkedHashSet; LinkedHashSet set = new LinkedHashSet(); 메소드 add(데이터) 데이터 넣기 a.add(1); a,add("아름") size() 집합 크기 반환 a.size(); contains(데이터) 집합 안에 객체가 있다면 true 반환 a.contains(2); remove(데이터) 데이터 삭제 a.remove(1); retainAll() 교집합 데이터 반환 a.retainAll(b); return a; addAll() .. 2023. 11. 20. 자료구조_검색 ⑥ 해싱 검색 - 해쉬셋 HashSet [1] HashSet 특징 (1) HashSet 클래스 Set 인터페이스를 구현한 클래스와 멤버의 중복 여부를 체크하기 위해 인스턴스의 동일성을 확인해야 함 동일성 구현을 위해 필요에 따라 equals()와 hashCode()메서드를 재정의함 빠른 접근 속도 중복 허용 안됨 순서 제공 안됨 데이터 저장방식이 HashTable 이용 HashMap을 이용하여 구현된 형태이다 인덱스 위치를 통해 저장과 접근을 하는것이 아닌 key를 이용하고 싶을 경우 사용한다 데이터의 크기가 예상되는 경우 사용한다 삽입 삭제가 빈번할경우 사용한다 [2] HashSet 메소드 (1) HashSet 선언하기 import java.util.HashSet; HashSet a = new HashSet(); HashSet a = new.. 2023. 11. 20. 자료구조_검색 ⑥ 해싱 검색 - 해쉬테이블 Hashtable 2023. 6. 19. 자료구조_검색 ⑥ 해싱 검색 - 해쉬맵 Hashmap [1] Hashmap정의 Map 인터페이스를 구현한 클래스와 가장 많이 사용되는 Map 인터페이스 기반 클래스 key - value를 쌍으로 관리하는 메서드를 구현함 검색을 위한 자료구조 key를 이용하여 값을 저정하고 key를 이용하여 값을 꺼내오는 방식 - hash 알고리즘으로 구현 됨 key가 되는 객체는 중복될 수 없고 객체의 유일성을 비교를 위한 equals()와 hashCode() 메서드를 구현해야 함 HashMap map = new HashMap() put() (key , value 의 값을 넣는다) HashMap a1 = new HashMap(); a1.put("apple", 9000); a1.put("banana", 10000); a1.put("kiwi", 11000); // 출력되는 값.. 2023. 6. 19. 자료구조_검색 ⑥ 해싱 검색의 개요 [1] 해싱 검색 (1) 해싱검색 개요 hashing 검색 해시함수를 사용하여 키를 고정된 길이의 해시값으로 매핑하고 해시값을 인덱스 , 메모리 주소 기반으로 데이터를 키와 함께 저장하는 자료구조 순차적으로 데이터를 저장하지 않는다 value는 중복이 가능하지만 key는 중복 불가 기억장치를 직접 접근하고 연산에 의한 방식으로 데이터 주소를 찾는다 key에 대한 자료를 검색한다 연산에 의해 데이터의 기억공간을 찾는다 인덱싱 , 암호화 ,복호화 , 비교를 위해 사용한다. index = h(key) : 해시 함수가 key에 대한 인덱스를 반환해줌 해당 인덱스 위치에 자료를 저장하거나 검색하게 됨 키 key input-> 해시함수 ouput-> 버킷 해시값 (key) value kim 01 123-123 pa.. 2023. 6. 19. 자료구조_검색 ⑤ 블록검색 [1] 블록 검색 (1) 블록검색 개요 초기 데이터를 여러 개의 블록으로 분리하여 검색한다 블록 내부의 데이터는 정렬과 상관없지만 블록간은 정렬이 되어있어야함 블록 내에서 순차 검색한다 (2) 블록 검색 과정 데이터의 개수가 16개라면 제곱근을 구하면 4가 되므로 각 블록은 4개의 데이터로 구성한다 각 블록의 최대값인 key를 검색하여 선택하고 블록 내 순차검색하여 검색한다 2023. 6. 19. 자료구조_검색 ④ 보간검색 [1] 보간 검색 (1) 보간검색 개요 제어검색의 종류 데이터의 개수와 찾는 값의 성질에 따라 있음직한 위치를 처음 검색위치로 지정하는 방식 성능 : 이진검색 < 피보나치검색 2023. 5. 3. 자료구조_검색 ③ 피보나치 검색 [1] 피보나치 검색 (1) 피보나치 검색 개요 제어검색의 종류 검색에 사용하는 위치를 피보나치 수열을 이용하여 선정함 성능 : 이진검색 < 피보나치검색 2023. 5. 2. 이전 1 2 3 4 다음 반응형
