일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
1 | 2 | 3 | 4 | |||
5 | 6 | 7 | 8 | 9 | 10 | 11 |
12 | 13 | 14 | 15 | 16 | 17 | 18 |
19 | 20 | 21 | 22 | 23 | 24 | 25 |
26 | 27 | 28 | 29 | 30 | 31 |
- 킥스타트
- PYTHON
- nlp
- 코딩 테스트
- 코딩
- 파이썬
- google coding competition
- 구글 킥스타트
- 리눅스
- CSS
- 네트워크
- linux
- DFS
- 프로그래머스
- 동적프로그래밍
- 코딩테스트
- BFS
- AI
- 브루트포스
- 동적 프로그래밍
- 운영체제
- 순열
- 그래프
- 백준
- OS
- 프로그래밍
- kick start
- dp
- 딥러닝
- 알고리즘
- Today
- Total
목록파이썬 (136)
오뚝이개발자
list와 tuple은 모두 순차자료형이다. A = [1, 2, 3]# list B = (1, 2, 3)# tuple 하지만 차이점은 리스트의 경우 원소를 바꿀 수 있으나(가변적), 튜플의 경우 원소의 값을 변경할 수 없다(불변적)는 점이다. 이 같은 차이가 왜 중요한 이유가 있다. 만약 아래와 같이 "리스트"를 key로 하는 딕셔너리를 만들고 싶다고 해보자. A = [1,2,3] B = [4,5,6] dictionary = {} dictionary[A] = 1 dictionary[B] = 2 안타깝지만, 위의 코드는 제대로 실행되지 않는다. 아마 실행해보면 TypeError: unhashable type: 'list'라는 에러 문구가 뜰 것이다. 이유는 파이썬에서 딕셔너리의 key값은 hash가 가능토..
deque(double ended queue)는 양방향 연결리스트로 구현되어 있어 양 끝단에 접근이 가능하고 데이터의 삽입, 삭제가 용이하다.(단, 중간 데이터는 제외) 여기선 대표적으로 많이 쓰이는 5가지 operation에 대해 사용법을 정리하려고 한다. 아, 참고로 deque를 사용하려면 import collections.deque를 해주어야 한다. append(x), appendleft(x) append(x)는 오른쪽 끝에 데이터 x를 추가, appendleft(x)는 왼쪽 끝에 데이터 x를 추가한다. 리스트와 달리 deque는 doubly linked list라 둘의 시간복잡도는 모두 O(1)이다. pop(), popleft() pop()은 일반적으로 알고있는 그 pop 연산이 맞다. 즉, st..
시간복잡도 아래는 자주 등장하는 시간복잡도 표기들이다. 표에서 아래로 갈수록 수행시간이 오래 걸린다. list 리스트는 배열이다. 그렇기 때문에 사이즈가 커질수록 삽입과 삭제 연산이 비효율적으로 된다. 이럴 땐 차라리 deque를 쓰는 것이 효율적이다. Operation Average Worst Copy O(n) O(n) Append O(1) O(1) Pop last O(1) O(1) Pop intermediate O(k) O(k) Get item O(1) O(1) Set item O(1) O(1) Delete item O(n) O(n) sort O(nlogn) O(nlogn) min,max O(n) O(n) len O(1) O(1) collections.deque deque(double ended qu..
정렬 방법 중 가장 빠른 것은 O(nlogn)의 시간복잡도를 갖는다고 생각할 수 있다. 하지만 이보다 빠른 O(n)의 시간복잡도를 갖는 정렬방법도 있다. 바로 계수 정렬 다른 말로, 카운팅 정렬이다. 하지만 이러한 계수 정렬은 약간 제한된 조건 하에서 사용가능하다. 1 5 2 3 2 5 1 4 4 2 5 1 위와 같은 수가 나열되어있고 이를 정렬해보자. 그런데 자세히 보면, 위에서 등장하는 수의 범위가 1~5까지라는 것을 알 수 있다. 이처럼 수의 범위가 정해져 있는 경우 계수 정렬을 사용하면 효율적으로 정렬할 수 있다. 카운팅 정렬이란 말 그대로 수가 등장하는 횟수를 카운트 하는 것이다. 카운팅이 다 끝나면 크기 순서대로, 해당 수가 등장하는 횟수만큼 print해주면 된다. 위의 경우, 등장하는 수를 ..
파이썬에는 in 연산자가 있다. 보통 리스트, 튜플, 집합, 딕셔너리 같이 연속적인 자료구조에 속한 멤버를 확인하거나 순회할 때 사용한다. 그렇다면 in 연산자의 시간복잡도는 어떻게 될까? List l = [1, 2, 3, 4, 5] # 멤버 확인 if 1 in l : print("1 is in l") # 순회 for i in l : print(i) Tuple t = (1, 2, 3, 4, 5) # 멤버 확인 if 1 in t : print("1 is in t") # 순회 for i in t : print(i) Set s = {1, 2, 3, 4, 5} # 멤버 확인 if 1 in s : print("1 is in s") # 순회 for i in s : print(i) Dictionary d = {1: ..
파이썬에서 전역변수를 사용하려면 global 키워드를 사용해야 한다. 파이썬은 함수 내에서 사용하는 변수는 자동적으로 지역변수로 간주하기 때문이다. 따라서 global이라는 키워드를 붙여줌으로 해당 변수는 전역변수를 사용하는 것이라는 점을 명시해주어야 한다. x = 5 def solution(): global x x += 1 print(x)# 6 위와 같이 x를 처음에 전역변수로 선언해 5를 할당한 뒤 solution이란 함수에서 global x 키워드를 사용하여 1을 더해주었다. 만약 global x를 지워버리면 어떻게 될까? x = 5 def solution(): x += 1 print(x) 위 코드를 실행시키면 "UnboundLocalError: local variable 'x' referenced..
파이썬 내장함수 중 chr(), ord()를 사용하면 문자와 아스키 코드를 서로 변환할 수 있다. chr()은 숫자를 문자로, ord()는 문자를 숫자로 변환시켜 준다. 여기서 말하는 숫자는 아스키 코드표에서의 숫자이다. 아래 예시를 참고해보자. print(chr(65))# A print(ord('A'))# 65 응용해서, 만약 C가 A로부터 얼마나 떨어져있는지를 알고싶다면 아래와 같이 계산할 수 있다. print(ord('C')-ord('A'))# 2
프로그래머스에서 코딩 문제를 풀다가 heap을 써서 풀어야 만족할 수 있는 문제를 접했다...(반드시 모듈을 import해서 풀도록 유도하는 문제는 그리 좋은 것 같지 않지만....) 공부도 할겸 파이썬에서 heap을 사용하는 법을 정리해본다. 사실 정확히는 heapq이다. 풀이를 찾아보니 아래와 같이 코드를 구현하면 된다. 여기서 핵심인 heapify, heappop, heappush에 대해 알아보자. import heapq as hq def solution(scoville, K): hq.heapify(scoville) answer = 0 while True: first = hq.heappop(scoville) if first >= K: break if len(scoville) == 0: return ..