본문 바로가기

개발 관련 공부/코테용 파이썬12

힙과 우선순위 큐 이 포스트는 2021.12~2022.09 기간동안 벨로그에 작성한 글을 티스토리에 옮겨 적은 것입니다. 우선순위 큐 보통 큐는 가장 먼저 삽입된 데이터를 먼저 삭제하지만.. 우선순위 큐는 우선순위가 가장 높은 데이터를 가장 먼저 삭제한다. 삽입/삭제의 시간복잡도는 logN 이다. 힙 자료구조 힙 자료구조는 우선순위 큐를 구현하기 위하여 사용하는 자료구조 중 하나다. 대부분의 프로그래밍 환경에서 우선순위 큐 라이브러리를 지원하기 때문에 직접 힙 자료구조를 작성해서 우선순위 큐를 구현할 일은 없다. 라이브러리 임포트 하는 방식만 잘 외워두자! import heapq 사용 방법 import heapq heap = [] heapq.heappush(heap, 50) heapq.heappush(heap, 10) h.. 2022. 9. 14.
itertools 이 포스트는 2021.12~2022.09 기간동안 벨로그에 작성한 글을 티스토리에 옮겨 적은 것입니다. 코테 연습 중 리스트에서 3개의 원소를 조합 중복 없이 뽑아야 하는 문제가 있어서 3중루프를 돌며 뻘짓을 하고 있었다.🤯 그런데 알고 보니 itertools 라이브러리를 사용하면 한 줄로 해결할 수 있었다....🤦‍♀️ itertools 파이썬에서 반복되는 데이터를 처리하는 기능을 포함하고 있는 라이브러리이다. permutations 리스트와 같은 iterable 객체에서 r개의 데이터를 뽑아 일렬로 나열하는 모든 경우(순열=permutations)을 계산한다. 시간복잡도는 O(n!)이다. from itertools import permutations data=['A','B','C'] #data 리스트.. 2022. 9. 13.
사전자료형, 집합 자료형 이 포스트는 2021.12~2022.09 기간동안 벨로그에 작성한 글을 티스토리에 옮겨 적은 것입니다. 사전자료형 사전 자료형은 key와 value의 쌍을 데이터로 가지는 자료형이다. 사전 자료형이 사용되는 대표적인 예시는 dictionary이다. 파이썬의 사전 자료형은 내부적으로 해시 테이블을 이용하므로 기본적으로 검색 및 수정에 있어서 O(1)의 시간에 처리할 수 있다. data=dict() data['사과']='apple' data['바나나']='banana' if '사과' in data: print('사과를 키로 가지는 데이터가 존재합니다.') 사전 자료형에 특정한 원소가 있는지 검사할 대는 '원소 in 사전'의 형태를 사용할 수 있다. (리스트나 튜플에 대해서도 사용할 수 있는 문법) data=.. 2022. 9. 13.
스택, 큐, 재귀함수와 그래프 이 포스트는 2021.12~2022.09 기간동안 벨로그에 작성한 글을 티스토리에 옮겨 적은 것입니다. 스택 stack = [] stack.append(2) stack.append(3) stack.pop() stack.append(5) print(stack) print(stack[::-1]) #최상단 원소부터 출력 따로 import할 필요 없이 일반 리스트라고 생각하면 됨 큐 from collections import deque queue=deque() queue.append(5) queue.append(2) queue.append(3) queue.popleft() queue.append(1) queue.popleft() print(queue) #나중에 들어온 원소부터 출력하려면 (거꾸로 출력) queu.. 2022. 9. 13.
파이썬 람다 표현식 이 포스트는 2021.12~2022.09 기간동안 벨로그에 작성한 글을 티스토리에 옮겨 적은 것입니다. 개요 람다 표현식을 사용하면 함수를 매우 간단하게 작성할 수 있다. 예를 들어 add 메소드를 사용한다고 치면 def add(a,b): return a+b print(add(3,7)) 이 코드를 print((lambda a,b:a+b)(3,7)) 로 줄일 수 있다. lambda에서 : 왼쪽에 오는 값이 인자, 오른쪽에 오는 값이 반환값이다. 람다식을 괄호로 묶고, 그 옆에 또 괄호를 붙여서 인자를 넣어서 호출할 수 있다. 이 람다식은 sort 함수를 쓸때 key를 설정하기 위해 자주 사용된다. 백준 1931번을 보자. 문제 한 개의 회의실이 있는데 이를 사용하고자 하는 N개의 회의에 대하여 회의실 사용.. 2022. 9. 13.
파이썬 입출력 이 포스트는 2021.12~2022.09 기간동안 벨로그에 작성한 글을 티스토리에 옮겨 적은 것입니다. 숫자 하나 입력받는 경우 x=int(input()) 공백으로 구분된 N,M,K를 입력받는다고 하면 N,M,K=list(map(int,input().split())) x=list(map(int,input().split())) N=x[0] M=x[1] K=x[2] 이렇게 쓰지 말자..🤦‍♀️ 원리: input()으로 입력받은 문자열을 split()으로 나눈 리스트로 바꾸고, map을 이용하여 해당 리스트의 모든 원소를 int로 바꾼것! import sys n,m=list(map(int, sys.stdin.readline().split())) array=list(map(int,sys.stdin.readlin.. 2022. 9. 13.
반응형

티스토리툴바