'알고리즘' 카테고리의 글 목록

본문 바로가기

[프로그래머스/python] 불량 사용자 나올 수 있는 모든 user id의 순열 banned_id 와 비교 중복을 제거하기 위해 list를 정렬해서 set에 추가 from itertools import permutations def check(u, b): for i in range(len(b)): if len(u[i]) != len (b[i]): return False for j in range(len(b[i])): if b[i][j] == '*': continue elif u[i][j] != b[i][j]: return False return True def solution(user_id, banned_id): user_per_set = set([]) user_per = list(permutations(user_id, len(banned_i..

c++ vector / python list 함수 정리 python에 쉽게 적응하기 위해 기존에 사용하면 C++의 자료구조 함수들을 python과 비교해보려 한다 첫 번째는 c++의 vector와 그와 비슷한 용도로 쓰이는 list를 비교해보았다 c++ python list 선언 vector v; a = [] 초기값 설정 fill(v.begin(), v.end(), -1); a = [-1 for i in range(100)] 추가 v.push_back(5); a.append(5) 중간 요소 삭제 v.erase(v.begin()+5); del a[5] 맨뒤 요소 삭제 v.pop_back(); a.pop() 길이 v.size(); len(a) 정렬 sort(v.begin(), v.end()); a.sort() 비어있는지 확인 v.empty(); bool(a) t..

[Algorithm] KMP 알고리즘 KMP 알고리즘 ? 전체 문자열 : 문자열 전체 패턴 문자열 : 찾고 싶은 문자열 전체 문자열에서 일치하는 패턴 문자열을 찾아야 할 때 사용 패턴 문자열이 여러 번 존재할 수 있고 각각 어디 위치인지 찾아야 할 때 접두사, 접미사의 개념을 활용하여 반복되는 연산을 줄이고 매칭 할 문자열의 위치로 빠르게 점프 전체 시간복잡도 O(n+m) : n = 전체 문자열의 길이, m = 패턴 문자열의 길이 O(n^2)의 문자열 탐색 방식을 사용한 경우라면 for ( int i =0; i < 전체 문자열의 길이; i++) { // text[i] : 전체 문자열 중 i 번째 문자 bool flag = true for ( int j =0; j < 패턴 문자열의 길이; j++ ) { // pattern[j] : 패턴 문자열..

[자료구조] Trie 트라이 Trie는 ? 저장된 문자열을 효과적으로 탐색할 수 있는 자료구조 트리 구조 시간 복잡도 O(N) : N은 문자열의 길이 prefix tree, radix tree, retrieval tree 등으로 부름 단점 : 거대한 공간 복잡도 trie는 문자열 탐색에 굉장히 유용한 자료구조이다 문자열이 주어지게되면 문자를 저장하는 노드를 하나씩 생성해가면서 트리구조를 만든다 자동으로 정렬된 효과를 볼수 있다는 장점도 있다 예시 root 노드는 가장 상위 노드를 의미한다 "ALCUK" "EZ" "EZYUN" "EZYOON" 4글자를 넣은 Trie 트리 모양 구현 - 간단한 기본 코드 #include #include #include using namespace std; const int ptr_num = 10; st..

이전 1 다음

티스토리툴바