분류 전체보기
고성능 파이썬(4)
시간복잡도 정렬되지 않은 리스트, 튜플 최적화 모델 : 0(log n) 사전, 셋 : 0(1) - 해시 테이블 사전과 셋은 메모리를 많이 사용하기 때문에 실제 속도는 해시 함수에 전적으로 의존하여, 만일 해시 함수가 느리다면 사전과 셋의 모든 연산도 마찬가지로 느릴것이다. 리스트 vs 셋 유일한 이름찾기 항목 1만 개 중 유일한 이름이 7412 개인 phonebook 리스트를 사용하면 셋과 리스트의 차이가 252배정도 차이가 난다. 사전과 셋의 동작원리 해시 테이블을 처음 생성하면 배열을 사용할때처럼 메모리부터 할당한다. 배열은 데이터를 추가하려면 사용하지 않은 메모리 블록을 찾아 데이터를 추가하고, 필요할때 크기를 조정한다 그러나 해시 테이블에서는 먼저 이 연속적인 메모리에 데이터를 나열할 방법을 생각..
프로그래머스 - 짝지어 제거하기 (python)
문제 설명 더보기 짝지어 제거하기는, 알파벳 소문자로 이루어진 문자열을 가지고 시작합니다. 먼저 문자열에서 같은 알파벳이 2개 붙어 있는 짝을 찾습니다. 그다음, 그 둘을 제거한 뒤, 앞뒤로 문자열을 이어 붙입니다. 이 과정을 반복해서 문자열을 모두 제거한다면 짝지어 제거하기가 종료됩니다. 문자열 S가 주어졌을 때, 짝지어 제거하기를 성공적으로 수행할 수 있는지 반환하는 함수를 완성해 주세요. 성공적으로 수행할 수 있으면 1을, 아닐 경우 0을 리턴해주면 됩니다. 예를 들어, 문자열 S =baabaa라면 baabaa →bbaa →aa→ 의 순서로 문자열을 모두 제거할 수 있으므로 1을 반환합니다. 제한사항 문자열의 길이 : 1,000,000이하의 자연수 문자열은 모두 소문자로 이루어져 있습니다. 입출력 ..
고성능 파이썬(3)
효율적인 탐색 정렬 알고리즘, 탐색 알고리즘 파이썬 리스트는 정렬 알고리즘을 내장하며 팀정렬을 사용한다. 팀정렬은 시간복잡도는 최적일때 0(n), 최악일때 0(n log n) 팀정렬은 삽입정렬, 병합 정렬 알고리즘을 조합해서 최선의 알고리즘을 추측하는 휴리스틱을 사용 bisect 모듈을 이용하여 잘 최적화된 이진 탐색 기법 항목을 찾을수 있을 뿐 아니라 새로운 항목을 추가해도 정렬된 상태가 유지된다. 리스트와 튜플 리스트는 동적인 배열이다. 수정이 가능하며, 저장 용량을 늘리거나 줄일 수도 있다. 튜플은 정적인 배열이다. 일단 생성되면 배열의 크기뿐 아니라 그 안의 데이터도 변경할 수 없다. 튜플은 파이썬 런타임에서 캐시하므로 사용할때마다 커널에 메모리를 요청하지 않아도 된다. append 를 사용하면 ..
