용감해지고 싶은 쫄보의 도전기

1. 스택- 후입선출: 마지막에 넣은 데이터가 가장 먼저 나옴- 활용: 재귀 호출, 괄호 짝 맞추기, DFS 등- 주요 연산# 가장 흔한 방법stack = []stack.append(10)top = stack.pop()2. 큐- 선입선출: 먼저 들어간 데이터가 먼저 나옴- 활용: BFS, 캐시, 작업 예약 처리에 사용- collections.deque: 가장 빠르고 많이 쓰임- queue.Queue: 스레드 안전(멀티스레스 환경용)from collections import dequequeue = deque()queue.append(1)queue.append(2)x = queue.popleft()print(queue) # [2] 3. 트리- 계층적 자료 구조. 노드와 간선으로 구성된 비순환 그래프- 이진트..

1. Json- 왜 사용할까? 웹 환경에서 데이터를 주고 받는 가장 표준적인 방식이기 때문에- 키를 이용해 원하는 데이터만 빠르게 추출할 수 있다- 데이터가 쉽게 오염되지 않는다 => 데이터의 구조가 명확하고 규칙이 엄격하기 때문!- 다른 포맷에 비해 용량이 조금 크다 1) JSON과 딕셔너리 변환(*s가 있으면 문자열 다루기)- JSON 문자열을 파이썬 객체(딕셔너리 등)로 : json.loads(JSON문자열)- 파이썬 객체를(딕셔너리를) JSON 문자열로: json.dumps(파이썬객체) 2) 파일 다루기- JSON 파일을 읽어 파이썬객체로(딕셔너리 등): json.load(JSON파일) => python 객체가 됨- 파이썬객체를(딕셔너리 등) JSON 파일에 쓰기: json.dump(파이썬객체를,..

1. 그래프 탐색 : 어떤것(Vertex)들이 연속해서 이어질때(Edge), 모두 확인하는 방법 2. BFS vs DFS- BFS: 자식을 먼저 봄- DFS: 자식의 자식을 먼저 봄 3. BFS 아이디어- 시작점에 연결된 vertex 찾기- 찾은 vertex를 queue에 저장 (들어온 순서대로 나감) => 넓게 퍼지며 탐색- queue의 가장 먼저 것을 뽑아서 반복- 최단거리에 BFS 쓰는 이유? BFS는 가까운 노드부터(거리1짜리 다음 거리2짜리,,,) 차례차례 탐색하기 때문에 처음 도착한 순간이 곧 최단거리가 된다.# 큐에 들어오는 순서[1,2,5,3,4,6]1 => 2랑 5 추가 => 1 제거2 => 2랑 열된 3 => 2제거5 => 5랑 연결된 4 => 5제거3 => 4는 이미 있으니까 넘어감 ..

1. 미니포지란?- conda : 패키지/가상환경 관리도구(명령어) - anaconda: conda + python + 데이터 과학관련 수백개 패키지 포함 배포판 - miniconda: conda + python만 있는 최소한의 anaconda => 기본 채널은 defaults, 상업적으로 사용시 유료- miniforge: miniconda와 같은데, 기본 채널이 conda-forge, 상업 제한 없음- defaults: Anaconda,Inc의 상업 채널, conda install 로 패키지 설치시 해당 채널에서 가져옴- conda-forege : conda 패키지를 위한 커뮤니티 채널(공개적으로 빌드, 배포, 유지보수)* 파이썬 내장 가상환경 도구 venv는 DS/AI 패키지 설치시 문제가 많아 co..

0. 클래스와 함수- 함수는 동작만- 클래스는 함수+상태 저장 가능 1. 상속 : 같은 기능인데 이름만 다름 => 중복 방지 - 예: 좋아요, 싫어요 기능class Like: def __init__(self, post, user): self.post = post self.user = user class Sad: def __init__(self, post, user): self.post = post self.user = user # 공통된 부모 클래스를 만들어줌class React: def __init__(self, type, post, user): self.type = type self.post = post ..

1. sort()- len(list) 가 N일때 : N log N 2. list의 in- 내부적으로 for문을 돈다 => worst의 경우 O(N)# 예시lst = [1, 2, 3, 4, 5]print(3 in lst)found = Falsefor item in lst: if item == 3: found = True breakprint(found) *대안 : set이나 dict의 in- 해시 테이블 기반이라 in 연산이 매우 빠르다 => O(1) 평균 3. remove - 내부적으로 for문을 돈다 => worst의 경우 O(N)def remove(x): for i in range(len(lst)): # O(N) if lst[i] == x: ..

1. 시간제한 : 보통 1초 이내- 코딩테스트에서 보통 1초에 약 1억번(10^8) 연산이 가능하다- N을 보고 O(N^2)을 써도 되는지, O(N)까지 제한되는지 감을 잡아야 한다!!입력크기 N시간제한알고리즘NO(N^2)브루트포스, 백트래킹NO(N^2)이중 반복문, DPNO(N log N)정렬, 이진탐색, 해시, 슬라이딩 윈도우NO(N)누적합, 투포인터, 해시, deque, 그리디 1) 입력크기 N O(N^2) 가능=> 완전탐색 가능! => 브루트포스, 백트래킹- O(2^n) 의 경우 2^20 = 1,048,576으로 약 백만이 되므로, 가능!- n=20일때, 20!는 2.4*10^18로 너무 커서 안됨 2) 입력 N 이중 반복문, DP- 시간복잡도: O(N^2)이면 N*N = 1000*1000 = ..

1. 컴퓨터의 실수 계산print(0.1+0.2) # 0.30000000000000004- 부동소수점 오차 => 컴퓨터는 2진수로 숫자를 저장한다.- 0.1이나 0.2는 2진수로 정확히 표현할 수 없기 때문에 조금 부정확하게 됨* 부동소수점이란? 실수를 컴퓨터에서 표현하는 방식(10진수 0.1을 2진수로 완벽하게 표현할 수 없어 근사값으로 저장)- 대안: 소수점 둘째 자리까지만 보고 반올림print(round(0.1+0.2,2)) # 0.3 2. 0.5를 반올림하면 반드시 짝수가 나옴print(round(0.5)) # 0print(round(1.5)) # 2print(round(2.5)) # 2print(round(3.5)) # 4print(round(4.5)) # 4print(round(5.5)) # ..