개발자 블로그

파이썬의 경우 가장 빠른 퀵솔트로 sort()함수가 구현이 되어있다. 퀵 솔트란? 기준 데이터를 설정하고 그 기준 보다 작은 데이터들을 왼쪽으로 큰 데이터들은 오른쪽으로 위치를 바꾸어 주며, 바뀐 데이터들 이와 같은 방법으로 재귀적으로 실행되며 정렬되는 방식. 평균적인 시간 복잡도는 O(nlogn)이고 최악의 경우, O(n**2)이 된다. 정렬 알고리즘 중 가장 빠른 시간을 자랑하지만, 기준 데이터에 따라 최악의 시간 복잡도를 가질 수 있다. 따라서, 적절한 pivot(기준)을 정해주는 것이 중요하겠다. python 또한, 내부적으로 항상 nlogn으로 pivot을 설정하여 작동하게 끔 구현이 되어있다. def quick_sort(array: list) -> list: if len(array)

문제 설명 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):..

문제 설명 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..

문제 설명 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..

문제 설명 1697번: 숨바꼭질 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 www.acmicpc.net 나의 풀이 from collections import deque, defaultdict def bfs(start_number, target_number): q = deque() q.append(start_number) distance_dict = defaultdict(int) distance_dict[start_number] = 0 dx = [-1, 1] while q: cur_num = q.popleft() if cur_n..

문제 설명 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 나의 풀이 # 2*7=14, 4*10=40 -> 40 # 3*7=21, 3*10=30 -> 30 # 4*7=28, 2*10=20 -> 28 # 5*7=35, 1*10=10 -> 35 # x0*times[0], x1*times[1], ... xn*times[n] -> 값들 중 최대가 되는 값, x0+x1+...xn = n def solution(n, times): answer = 0 left = 1 right = max(times) * n while left = n: answer = mid right..

문제 설명 2468번: 안전 영역 재난방재청에서는 많은 비가 내리는 장마철에 대비해서 다음과 같은 일을 계획하고 있다. 먼저 어떤 지역의 높이 정보를 파악한다. 그 다음에 그 지역에 많은 비가 내렸을 때 물에 잠기지 않는 www.acmicpc.net 나의 풀이 from collections import deque def changing_graph_zero_one(graph, rain_amount): safety_graph = [[1]*len(graph[0]) for _ in range(len(graph))] for i in range(len(graph)): for j in range(len(graph[0])): if graph[i][j]

문제 설명 7576번: 토마토 첫 줄에는 상자의 크기를 나타내는 두 정수 M,N이 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M,N ≤ 1,000 이다. 둘째 줄부터는 하나의 상자에 저장된 토마토 www.acmicpc.net 나의 풀이 from collections import deque def bfs(graph, q): dx = [-1,1,0,0] dy = [0,0,-1,1] while q: y, x = q.popleft() for i in range(4): nx = x + dx[i] ny = y + dy[i] if 0

문제 설명 1012번: 유기농 배추 차세대 영농인 한나는 강원도 고랭지에서 유기농 배추를 재배하기로 하였다. 농약을 쓰지 않고 배추를 재배하려면 배추를 해충으로부터 보호하는 것이 중요하기 때문에, 한나는 해충 방지에 www.acmicpc.net 나의 풀이 from collections import deque def bfs(graph, start_node): if not graph[start_node[0]][start_node[1]]: return False q = deque() q.append(start_node) graph[start_node[0]][start_node[1]] = 0 dx = [-1,1,0,0] dy = [0,0,-1,1] while q: current_y, current_x = q.p..