python/python

[Python] 음수 나누기 - / 연산자, // 연산자

파이썬에서 나누기 연산자로 몫을 구하고자 할 때는 다음과 같이 두 경우를 생각할 수 있다. print(10//3) print(int(10/3)) # 결과 3 3 양수끼리 나누면 두 경우 모두 같지만 음수 나누기를 하면 두 값은 달라진다. print(-10//3) print(int(-10/3)) # 결과 -4 -3 -10 나누기 3은 -3.3333... 이다. // 연산자는 나누기 결과보다 작은 정수 중 가장 큰 정수인 -4를, int() 연산자는 그냥 소수 부분을 버려서 -3을 결과로 갖는다. 알고리즘을 풀다가 우연히 발견했다.

[Python] 비트 연산자

비트 연산자 비트 연산자 a = 0b1010, b = 0b0100 & AND a & b -> 0b0000 | OR a | b -> 0b1110 ^ XOR a ^ b -> 0b1110 ~ NOT ~a -> 0b0101 오른쪽 Shift a >> n -> a * 2^-n 비트 연산자 응용 나누기, 나머지 연산 흔히 쓰이는 /, % 연산자는 오버헤드가 크기 때문에 필요한 경우 더 빠른 비트 연산을 사용할 수 있다. 나누는 수가 2^n인 경우 >> 연산자가 / 연산자를 대체할 수 있다. ex) 9 / 8 = 1 -> 9 >> 3 = 1 나누는 수가 2^n인 경우 & 연산자를 활용해 % 연산자를 대체할 수 있다. 2^n 꼴의 숫자를 이진수로 표현하면 최상위 비트만 1인 형태를 띄게 되고, 2^n에 -1을 더하면 ..

[Python] datetime - fromtimestamp() (타임스탬프를 날짜로 변환하기)

Python에서 Unix timestamp (1970년 1월 1일(UTC)부터 몇 초가 흘렀는지를 나타내는 수치)를 날짜로 변환하는 법 from datetime import datetime x = 1537158105 d = datetime.fromtimestamp(x) print(d) 2018-09-17 4:21:45

cmp_to_key 정렬

functools 라이브러리를 사용해서 정렬 시 직접 비교 함수를 만들 수 있다. import functools def comparator(a,b): if a>b: return 1 elif a==b: return 0 else: return -1 data=[5,3,1,2,4] data.sort(key=functools.cmp_to_key(comparator)) print(data) 리스트에서 두 원소 a, b를 비교할 때 a가 b보다 크다면 1, 같다면 0, 작다면 -1을 리턴해서 비교한 값을 기반으로 오름차순으로 정렬하는 방식이다. lambda로 정렬하기 까다로운 조건에 대해서 위 방법을 사용하면 편리하다. cumtom한 comparator를 만들 수 있다는 장점이 있다.

우선순위 큐

우선순위 큐 우선순위가 가장 높은 데이터를 가장 먼저 삭제하는 자료구조이다. 예를 들어 어러 개의 물건 데이터를 자료구조에 넣었다가 가치가 높은 물건 데이터부터 꺼내서 확인해야 하는 경우에 우선순위 큐를 이용할 수 있다. 우선순위 값을 표현할 때는 일반적으로 정수형 자료형의 변수가 사용된다. 예를 들어, 물건 정보가 있고, 이 물건 정보는 물건의 가치와 물건의 무게로만 구성된다고 가정해보자. 그러면 모든 물건 데이터를 (가치, 물건)으로 묶어서 우선순위 큐 자료구조에 넣을 수 있다. 이후에 우선순위 큐에서 물건을 꺼내게 되면, 항상 가치가 높은 물건이 먼저 나오게 된다.(최대 힙 기준) 대부분의 프로그래밍 언어에서는 우선순위 큐 라이브러리에 데이터의 묶음을 넣으면, 첫 번째 원소를 기준으로 우선순위를 설..

이진 탐색 트리

이진 탐색 트리 트리 자료구조 중에서 이진 탐색이 동작할 수 있도록 고안된, 효율적인 탐색이 가능한 자료구조이다. 이진 탐색 트리는 다음과 같은 특징을 가진다. 부모 노드보다 왼쪽 자식 노드가 작다. 부모 노드보다 오른쪽 자식 노드가 크다. 실제 코딩 테스트에서 이진 탐색 트리 자료구조를 구현하도록 요구하는 문제는 출제 빈도가 낮다. 이진 탐색 트리가 이미 구현되어 있다고 가정하고 이진 탐색 트리에서 탐색하는 과정만 알아도 충분하다. 탐색은 루트 노드에서부터 자식노드로 내려가면서 찾는 원소값과 비교해가면 된다.

그래프

그래프 그래프는 노드(node)와 간선(edge)로 표현되며 이때 노드를 정점(vertex)이라고도 말한다. 또한 두 노드가 간선으로 연결되어 있다면 '두 노드는 인접하다(Adjacent)'라고 표현한다. 프로그래밍에서 그래프는 크게 2가지 방식으로 표현할 수 있다. 인접 행렬(Adjacent Matrix) 인접 리스트(Adjacent Lint) 인접 행렬 2차원 배열에 각 노드가 연결된 형태를 기록하는 방식이다. 파이썬에서는 리스트를 사용한다. 연결되어 있지 않은 노드끼리는 무한의 비용이라고 작성한다. 인접 행렬 방식 예제 INF=999999999 # 무한의 비용 선언 # 2차원 리스트를 이용해 인접 행렬 표현 graph=[ [0,7,5], [7,0,INF], [5,INF,0] ] 인접 리스트 각 노드..

재귀함수

재귀함수 스택을 함수에 적용시킨 개념이다. 자기 자신을 다시 호출하는 함수이다. def recursive_function(): print('재귀 함수를 호출합니다.') recursive_function() recursive_function() 그러나 위 코드처럼 재귀함수를 실행하면 무한 루프에 빠지게 되고 결국 재귀의 최대 깊이를 초과했다는 오류 메시지가 뜬다. 재귀함수는 컴퓨터 내부에서 스택을 통해 적재되기 때문에 메모리 한도치를 초과하게 되면 에러가 뜨는 것이다. 결국 재귀함수를 사용할 때는 다음과 같이 종료조건을 명시해주어야 한다. def recursive_function(i): if i==100: return print('재귀 함수를 호출합니다.') recursive_function(i+1) re..