ALGORITHM/개념 (5) 썸네일형 리스트형 [Java] 순열, 조합, 부분집합 순열 서로 다른 것들 중 몇 개를 뽑아서 한 줄로 나열하는 것 DFS 로 for문을 0부터 시작 int (boolean) 배열 visited 사용 [1, 3, 5] 배열에서 순열을 찾는 코드 import java.util.Arrays; public class Recursive7 { static void permutation(int[] arr, int[] p, int[] visited, int idx) { if (idx == arr.length) { System.out.println(Arrays.toString(p)); return; } for (int i=0; i 트라이 Trie (c++ 구조체 구현) Trie 문자열을 저장하고 효율적으로 탐색하기 위한 트리 형태의 자료구조 입니다. 트리 구조로 문자열을 저장하기 때문에 단순히 비교하면서 탐색하는 것보다 효율성이 좋습니다. 주로 문자열이 키인 경우가 많습니다. 이진 탐색 트리와 달리 트리의 어떤 노드도 그 노드 자체와 연관된 키는 저장하지 않습니다. 즉, 키의 값은 자료구조 전체에 분산됩니다. 노드의 모든 자손은 노드에 연관된 문자열의 공통 접두사를 공유하기 때문에 '접두사 트리'라고도 불립니다. 루트는 빈 문자열 입니다. 정수나 메모리 주소 같은 고정 길이 이진 자료를 표현하는 각각의 비트로 구성된 트라이를 특별히 비트 트라이라고 부릅니다. Trie 의 장점 불완전한 해시 함수를 사용하는 해시테이블과 비교할 때, 자료에 접근할 때 최악의 경우 더 유리.. [c++] string 문자열 #include 문자열에 대해 파헤쳐 봅시다 ~ ASCII 코드 가장 많이 쓰는 알파벳을 알아봅시다. A : 65 a : 97 리턴값 front, back 맨 앞 문자와 맨 뒤 문자를 뽑아주는 함수입니다. begin, end 맨 앞 iterator, 맨 뒤 iterator 입니다. find 특정 문자열을 찾으면 시작 위치를 리턴 더보기 first 'needle' found at: 14 second 'needle' found at: 44 'haystack' also found at: 30 Period found at: 51 There are two prepositions in this haystack with needles. 뒤에 붙는 숫자는 그 문자열부터 시작한다. // string::find #incl.. [c++] unordered_set / unordered_map 대부분의 STL 컨테이너들은 레드블랙 트리 기반으로 되어있다고 합니다. ㅇ0ㅇ unordered_set 정렬되지 않은 set 해시함수를 이용하여 원소를 탐색합니다. 고로 정렬될 필요가 없습니다. 해시함수 : 해시함수 값이 같은 값이 나오면 같은 상자에 저장됩니다. 다른 원소 값이 우연히 같은 해시함수 값이 나와서 같은 상자에 저장된다면 해시충돌이 일어날 수 있습니다. 해시함수 값을 받아 바로 주소로 찾아가면 되므로 탐색 시간은 O(1) 이지만, 최악의 경우 모든 원소가 같은 곳에 저장되면 O(N) 의 시간이 발생할 수 있습니다. set 과의 차이점 set 은 정렬되었기 때문에 평균, 최악의 상황 모두 O(log N) 의 탐색시간을 가집니다. 원소의 개수가 적을 땐 unordered_set 원소의 개수가 .. [c++] stack, queue http://www.cplusplus.com/reference/stack/stack/?kw=stack stack - C++ Reference container_typeThe second template parameter (Container)Type of the underlying container www.cplusplus.com Stack의 정의 template class stack; stack은 Last-In-First-Out인 자료구조로 마지막에 들어온 것이 가장 먼저 나가는 자료구조입니다. (LIFO) (여기서 deque은 vector의 단점을 보완하기 위해 만들어진 container로 배열기반의 구조입니다. vector는 새로운 원소가 추가 될 때 메모리를 재할당하고 이전 원소를 복사하는 방식으로.. 이전 1 다음
