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 로드 팩터 비율에 따라서 해시 함수를 재작성해야 할지 또는 테이블의 크기를 조정해야할 지를 ..

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

쿠키와 세션을 사용하는 이유 HTTP의 connectionless, stateless 프로토콜 때문에 클라이언트가 서버와 통신을 할 때마다 계속 인증을 해야하기 때문 ㅠㅠ 아주 간단히 말해 쿠키는 클라이언트, 세션은 서버가 사용자에 대한 인증을 유지하는 것이다 HTTP 특징 → https://duckgugong.tistory.com/156 HTTP🍔 HTTP (Hypertext Transfer Protocol) HTTP는 서버와 클라이언트가 인터넷상에서 데이터를 주고받기 위한 프로토콜(Protocol)이다 HTTP는 HTML 문서와 같은 리소스들을 가져올 수 있도록 해주는 프로토콜이다. duckgugong.tistory.com 쿠키 - Cookie🍪 특징 쿠키는 클라이언트(브라우저)에 저장되는 key, ..

스택(Stack) 가장 처음에 들어간 요소가 가장 나중에 나오는 자료구조 Last In First Out - LIFO라고 부른다! 시간 복잡도 삽입: O(1) 삭제: O(1) 파이썬에선 사실 스택을 사용할 때, 그냥 list를 사용하면 된다 하지만 큐는 다르다!!! 왜 둘다 linked list를 기반으로 한 자료구조인데 차이가 날까? 파이썬의 list는 사실 array이고 스택을 사용하려면 맨 뒤의 요소를 pop()해도 시간 복잡도는 똑같지만 큐 같은 경우는 맨 앞의 요소를 빼기 위해 pop(0)을 해야하는데 array에서 맨 앞의 요소를 빼는 것은 O(n)의 시간이 걸리기 때문이다!! # 한쪽 끝으로만 자료를 넣고 뺄 수 있는 자료구조 class Node: def __init__(self, item,..

Array vs LinkedList array 파이썬의 list 타입 공간을 미리 할당하고 메모리를 할당한다. 각 자리에 순서가 정해져 있고 확장하면 메모리 확보를 더 해서 쭉쭉 붙여나간다. 데이터를 추가하려면 새로운 메모리 공간을 할당받아야 한다 탐색: 해당 인덱스에 있는 요소를 찾으려면 바로 찾기가 가능해서 탐색에 O(1)시간이 걸린다. 모두 붙어있어서 삽입 삭제가 어렵다. O(N) → 1, 2, 4, 5 에서 2에 3을 넣으려면 기존에 있는 2는 앞으로 당기고 4, 5는 뒤로 밀어야 한다! 이는 직접 구현해야함 데이터에 접근(탐색)하는 경우가 잦으면 array를 사용! linked list 서로 다른 요소가 이어져 있다고 생각!! 탐색: linked list에서 n번재 요소를 탐색하려면 앞에있는 n..