목록전체 글 (142)
개발자 블로그
파이썬의 경우 가장 빠른 퀵솔트로 sort()함수가 구현이 되어있다. 퀵 솔트란? 기준 데이터를 설정하고 그 기준 보다 작은 데이터들을 왼쪽으로 큰 데이터들은 오른쪽으로 위치를 바꾸어 주며, 바뀐 데이터들 이와 같은 방법으로 재귀적으로 실행되며 정렬되는 방식. 평균적인 시간 복잡도는 O(nlogn)이고 최악의 경우, O(n**2)이 된다. 정렬 알고리즘 중 가장 빠른 시간을 자랑하지만, 기준 데이터에 따라 최악의 시간 복잡도를 가질 수 있다. 따라서, 적절한 pivot(기준)을 정해주는 것이 중요하겠다. python 또한, 내부적으로 항상 nlogn으로 pivot을 설정하여 작동하게 끔 구현이 되어있다. def quick_sort(array: list) -> list: if len(array)
![](http://i1.daumcdn.net/thumb/C150x150.fwebp.q85/?fname=https://blog.kakaocdn.net/dn/ZzTFu/btrJRDM8VLa/YUJk4GFEh7Y5XJC9OwDDgK/img.png)
함수가 호출되어 저장되어 사용되는 곳이 스택 메모리 영역이다. 재귀함수는 함수가 호출 되면서 함수 자기 자신을 또 다시 호출하는 방식으로 재귀함수 호출 시 스택 메모리에 호출 된 함수들이 계속 쌓이게 된다. 스택은 LIFO(선입선출) 구조이기 때문에 가장 마지막에 호출된 함수 factorial(1)를 먼저 완료하고, 값을 아래로 전달하여 최초로 호출된 함수 factorial(3)가 최종 값을 계산한다. 따라서, 재귀함수를 호출할 때 스택 메모리 공간이 초과되는 스택 오버플로우가 발생되는 오류를 주의하며, 과도한 스택 메모리가 사용되지 않도록 조심하며 사용해야한다.
![](http://i1.daumcdn.net/thumb/C150x150.fwebp.q85/?fname=https://blog.kakaocdn.net/dn/rVIn5/btrJREL0zXv/M5m1xjdKa2JEehjfRHDZck/img.png)
컴퓨터에서 숫자를 기억하는 방식은 2진수 즉, 0과 1로만 모든 것을 표현한다. 이 때문에 오는 오차가 있어 사용 시 주의해야할 상황이 있는데 이는 float 타입을 사용할 때이다. 예를들어, 0.1이라는 숫자를 컴퓨터가 저장하는 방식은 이진수로 나타낸다면, 무한히 반복되는 숫자가 되버린다. 하지만 컴퓨터는 이러한 수를 근삿값으로 저장한다. 떄문에 정확한 값을 저장하지 않는다는 말! 이러한 문제를 해결하기 위해 파이썬에서는 decimal.Decimal, round() 등 여러가지 메소드를 통해 부동소수의 한계를 해결하는 방법 등이 있긴하다. 하지만, 이 또한, 완벽히 문제를 해결하는 방법이 아닐 수도 있으니, 사용할 시 주의하고 상황에 맞는 방법을 활용하도록 하자! 결론, 정확한 소수점 계산을 해야할 때..
![](http://i1.daumcdn.net/thumb/C150x150.fwebp.q85/?fname=https://blog.kakaocdn.net/dn/b2Spm5/btrJRX5zfg9/kqTcKLp9atzELWYIUKEzHk/img.png)
함수를 정의하고, 파라미터의 기본값을 정의를 하는 경우가 많다. 하지만, 사용 시 주의 사항이 있다. mutable 한 객체를 함수의 디폴트 파라미터로 사용하지 말라는 것이다. 예제를 통해 살펴보자! def add_sharp(s = []): s.append('#') return s s = [1, 2, 3] print(add_sharp(s)) # [1, 2, 3, '#'] print(add_sharp()) # ['#'] print(add_sharp()) # ['#'] print(add_sharp()) # ['#'] 우리가 예상한 결과값은 주석 처리를 한 값이다. 하지만, 실제 결과값은 그렇지 않다. 파이썬에서 함수의 디폴트 인자들은 __defaults__ 또는 __kwdefaults__ 어트리뷰트의 저장된..
get methhod는 조회나 검색에 활용되는 http method이다. 따라서 클라이언트에서 서버로 데이터를 보낼 때, 다른 방식과 다르게 request body에 실어 보내지 않는다. 따라서 get method에서 데이터를 서버에 보내기 위해선 QueryString을 사용하거나 path parameter로 데이터를 보내야 합니다. QueryString: /endpoint?key1=value1&ket2=value2 path parameter: /endpoint// 두 가지 쓰임이 있기에 상황에 따라 두가지를 사용하면 되겠다. 우선 쿼리 스트링의 경우, Id와 같이 정확한 데이터의 정보가 아닌 경우에 쓰이며, 조건에 맞는 쿼리셋을 사용자에게 보여줄 때 사용된다. 반면, 경로 인자는 객체의 id값과 같은..
문제 설명 1389번: 케빈 베이컨의 6단계 법칙 첫째 줄에 유저의 수 N (2 ≤ N ≤ 100)과 친구 관계의 수 M (1 ≤ M ≤ 5,000)이 주어진다. 둘째 줄부터 M개의 줄에는 친구 관계가 주어진다. 친구 관계는 A와 B로 이루어져 있으며, A와 B가 친구라는 뜻 www.acmicpc.net 나의 풀이 from collections import deque, defaultdict # 기준이 되는 start_num을 기준으로 너비 탐색을 통해 kavin_bacon리스트의 인덱스 정보를 # 나를 기준으로 얼마나 떨어져있는지 카운트 정보를 담는다. # 현재 숫자가 tartget_num이라면, kavin_bacon의 해당 값을 반환 def bfs(graph, start_num, target_num):..
![](http://i1.daumcdn.net/thumb/C150x150.fwebp.q85/?fname=https://blog.kakaocdn.net/dn/oVg8r/btrIyw91iYL/zvj0E1KrARpKqqP95PzbgK/img.png)
datetime객체는 naive datetime(without timezone)과 aware datetime(with timezone) 객체가 있습니다. 현재 timezone이 활성화되어있는 데(use_TZ = True, in setting), created_at 필드에 timezone이 없는 naive datetime 객체를 대입하셔서 발생하는 "경고" 입니다. 이를 timezone이 있는 aware datetime으로 변환하셔서 대입하시면 해당 경고는 사라진다. 참고로 서비스가 여러 timezone의 유저에게 서비스를 제공한다면 timezone 설정을 살려두시는 것(use_TZ=True)이 좋습니다. 대한민국은 하나의 시간대만 있지만, 해외에서는 국내 서비스라 하더라도 여러 시간대가 있는 나라가 많고..
문제 설명 10451번: 순열 사이클 1부터 N까지 정수 N개로 이루어진 순열을 나타내는 방법은 여러 가지가 있다. 예를 들어, 8개의 수로 이루어진 순열 (3, 2, 7, 8, 1, 4, 5, 6)을 배열을 이용해 표현하면 \(\begin{pmatrix} 1 & 2 &3&4&5&6&7&8 \\ 3 www.acmicpc.net 나의 풀이 from collections import deque def find_cycle(graph, start_num, visited): q = deque() q.append(start_num) while q: cur_num = q.popleft() next_num = graph[cur_num] if next_num not in visited: visited.append(nex..
![](http://i1.daumcdn.net/thumb/C150x150.fwebp.q85/?fname=https://blog.kakaocdn.net/dn/le5C8/btrIlw4NTJ8/DP5hqd2u8m1qeqWI6BtWn0/img.png)
문제 설명 1525번: 퍼즐 세 줄에 걸쳐서 표에 채워져 있는 아홉 개의 수가 주어진다. 한 줄에 세 개의 수가 주어지며, 빈 칸은 0으로 나타낸다. www.acmicpc.net 나의 풀이 from collections import deque, defaultdict def bfs(start_num): cnt_dict = defaultdict(int) q = deque() q.append(start_num) dx = [-1,1,0,0] dy = [0,0,-1,1] while q: cur_num = q.popleft() if cur_num == '123456780': return cnt_dict[cur_num] zero_idx = cur_num.find('0') zero_x = zero_idx // 3 ze..
문제 설명 2644번: 촌수계산 사람들은 1, 2, 3, …, n (1 ≤ n ≤ 100)의 연속된 번호로 각각 표시된다. 입력 파일의 첫째 줄에는 전체 사람의 수 n이 주어지고, 둘째 줄에는 촌수를 계산해야 하는 서로 다른 두 사람의 번호가 주어 www.acmicpc.net 나의 풀이 from collections import deque, defaultdict def relation_people(people, start_person, relation_graph): q = deque() q.append(start_person) chon_list = [-1] * (people + 1) chon_list[start_person] = 0 while q: cur_person = q.popleft() for pe..