자료구조+알고리즘

이진트리

이진 트리 모든 노드가 최대 두개의 자식을 가지는 트리 하위 노드가 3개 이상이면 안되고 무조건 0, 1, 2개 있어야 한다! 완전 이진 트리 노드를 삽입할 때 최하단 왼쪽부터 차례로 삽입하는 이진 트리 완전 이진 트리를 배열로 표현 BFS로 탐색을 할 때 왼쪽에서부터 읽어서 넣는다고 생각하자! 완전 이진 트리 노드 갯수 레벨을 n이라고 하면각 레벨에 최대로 들어갈 수 있는 노드의 수는 2^k개이다. 완전 이진 트리의 높이 트리의 높이는 루트 노드부터 가장 아래 리프노드 까지의 길이이다. 아래 같은 경우 2 - 0 = 2, 즉 높이가 2다 만약 높이가 h 일때, 최대 노드 갯수가 N이라고 하면 N = 2^(h+1) - 1개이다! N = 2^(h+1) - 1 → h = log2(N+1) - 1 으로 노드의..

백트래킹, N-Queen

Why? 필요없는 경우를 가지치기(pruning)함으로써 시간복잡도를 줄이는 방법을 백트래킹이라고 한다. DFS, BFS를 처럼 완전탐색을 할 때, 효율적으로 만들어주는 기법이다. 볼 필요가 없는 수는 보지 않음! 예를 들어 DFS를 할 때, 조건문으로 이미 탐색한 노드나 탐색이 필요 없는 노드를 만나면 return 해버림 대표적인 문제 N-Queen이 있다 N-Queen https://programmers.co.kr/learn/courses/30/lessons/12952 코딩테스트 연습 - N-Queen 가로, 세로 길이가 n인 정사각형으로된 체스판이 있습니다. 체스판 위의 n개의 퀸이 서로를 공격할 수 없도록 배치하고 싶습니다. 예를 들어서 n이 4인경우 다음과 같이 퀸을 배치하면 n개의 퀸은 pro..

해시 테이블

해시 테이블 해시 테이블(맵)은 키를 값에 매핑할 수 있는 구조인 연관 배열 추상 자료형을 구현하는 자료구조! 해시 테이블의 가장 큰 특징은 삽입, 삭제, 탐색 등 연산의 시간복잡도가 O(1) 데이터 양과 관련 없이 빠른 속도를 기대할 수 있음 해시함수는 임의 크기 데이터를 고정 크기 값으로 매핑하는데 사용할 수 있다! 해시 테이블을 인덱싱하기 위해서 해시함수를 사용하는 것을 해싱(Hashing)이라고 한다! 해시 함수 값이 충돌을 최소화 시켜서 성능이 좋게 만들 수 있다! 로드 팩터 해시 테이블에 저장된 데이터 개수 n을 버킷의 개수 k로 나눈 것! → 공간이 얼마나 차있는 지! load factor = n/k 로드 팩터 비율에 따라서 해시 함수를 재작성해야 할지 또는 테이블의 크기를 조정해야할 지를 ..

defaultDict

Why? 파이썬에서 딕셔너리를 사용할 때, 딕셔너리 안에 없는 키 값을 조회하면 오류가 발생한다! dict = {} print(dict['a']) # 오류발생!! defaultDict는 존재하지 않는 인덱스로 조회를 시도할 경우 에러를 발생하지 않고 그 자리에서 바로 디폴트 객체를 생성해준다! defaultDict의 인자에 디폴트 객체를 넘겨줘서 존재하지 않는 키를 조회할 때 디폴트 값을 넘겨줘서 이러한 문제를 수월하게 해결할 수 있다! 어떤 딕셔너리에 값이 있는지 확인하고 없으면 해당 key와 value를 넣는 경우에 사용하면 좋을 것 같다 사용법 default 객체의 인자에 값이 아닌 객체를 넘겨줘야 한다! int, class, set, list, tuple 등등.. int를 넘겨준 경우 디폴트 값으..