빠르게 성장하는 개발자

1. 퀵 소트?퀵소트는 주어진 배열을 분할하고 - 각각은 정렬한다.분할한다는 점에서 merge sort와 닮아 보이지만, 다른 점은 ‘병합’ 과정이 필요하지 않다는 것이다!!why? ⇒ merge sort는 각각을 분할하고 끝! 이지만, quick sort는 pivot을 중심으로 작은 것은 왼편, 큰것은 오른편에 두는 과정을 거치기 때문이다. 2. pivot 고르기결국 quick sort의 핵심은 pivot 고르기! 라고 할 수 있겠다.시간복잡도는 O(nlogn)O(nlogn)O(nlogn) 이지만, 최악의 경우 O(n2)O(n^2)O(n2) 가 될 수 있다.예를 들어 이미 정렬이 되어있는 리스트에, 리스트의 첫 원소를 pivot으로 설정하면?? → 최악의 경우가 발생하여 문제 풀이시에 시간초과를 경..

1. 합병 정렬의 기본적인 idealist가 주어지면 → 길이가 1일 때까지 나눈다 분할 → 병합 merge ! 2. 분할 → python 으로 구현하기def merge_sort(unordered_list): if len(unordered_list)

🍨 제목은 귀엽지만 풀이과정은 사악했던 디저트 카페 문제를 데려왔다.https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV5VwAr6APYDFAWudfs 라는 것은 알겠는데 도저히 생각나지 않아서 약간 검색의 힘을 빌렸다. 1. 문제의 특징이동할 수 있는 방향의 순서가 정해져 있다. 직사각형을 이루려면 시계방향 혹은 반시계방향으로 돌면서 탐색이 이뤄저야 한다. 지금 내가 갈 수 있는 방향은 이전의 방향, 그리고 시계방향으로 돌아간 방향 2가지로 제한되어있다는 뜻이다.⇒ 함수의 인자에 방향을 나타내는(d)를 추가하여 기존에 오고 있는 방향으로 이동할 수 있다면 이동하고, 그렇지 않다면 그 다음 방향으로 탐색하는 코드를 ..

1. 완전 탐색의 기본기억하자 for 문을 돌려야 될 수도? → 언제나 for 문에 대한 열린 생각!!2. 기본적인 순열 & back-tracking 문제완전 탐색을 하면 ⇒ 시간초과 에러가 발생하였다!back-tracking을 통해서 중간까지의 합이 현재의 최솟값보다 크면(앞으로는 더해야 하므로 가망이 없기 때문에) 리턴하는 방식으로 가지치기를 진행해주었다.→ 이를 위해서 함수에 tmp 라는 인자를 가지고 다닌다.이 테크닉을 이후에 유용하게 잘 써먹고 있다!# 각 줄에 대해서 하나씩 선택하는 함수를 만든다 def select(i, k, tmp): global min_V if tmp > min_V: return if i == k: min_V = min(min_V, tmp) return else: for ..

문제한 개의 회의실이 있는데 이를 사용하고자 하는 N개의 회의에 대하여 회의실 사용표를 만들려고 한다. 각 회의 I에 대해 시작시간과 끝나는 시간이 주어져 있고, 각 회의가 겹치지 않게 하면서 회의실을 사용할 수 있는 회의의 최대 개수를 찾아보자. 단, 회의는 한번 시작하면 중간에 중단될 수 없으며 한 회의가 끝나는 것과 동시에 다음 회의가 시작될 수 있다. 회의의 시작시간과 끝나는 시간이 같을 수도 있다. 이 경우에는 시작하자마자 끝나는 것으로 생각하면 된다.입력첫째 줄에 회의의 수 N(1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N+1 줄까지 각 회의의 정보가 주어지는데 이것은 공백을 사이에 두고 회의의 시작시간과 끝나는 시간이 주어진다. 시작 시간과 끝나는 시간은 231-1보다 작거나 같..

1. 조합(Combination) nCr=n−1Cr−1+n−1CrnCr = n-1Cr-1 + n-1CrnCr=n−1Cr−1+n−1CrN = 5 for i in range(N-2): for j in range(i+1, N-1): for k in range(j+1, N): print(i,j,k)# output 0 1 2 0 1 3 0 1 4 0 2 3 0 2 4 0 3 4 1 2 3 1 2 4 1 3 4 2 3 42. 재귀를 이용해서 구현해보기! def nCr(n, r, s): # n개의 원소에서 r개를 순서없이 뽑늗다. s는 시작하는 범위 if r == 0: print(*comb) else: for i in range(s, n-r+1): comb[r-1] = A[i] #n-1Cr-1 (A의 i번째 원소를..

1. 비트연산자를 이용해서 부분집합 구하기이 방법은 저번 포스팅에서 다뤘으니, 자세한 설명은 아래 링크를 참고하면 된다.arr = [3,6,7,1,5,4] n = len(arr) for i in range(0, (1

1. 순열(Permutation) 이란?서로 다른 것들 중 몇 개를 뽑아서 한 줄로 나열하는 것 (순서 고려)nPrnPrnPr 이라고 표현한다.nPr=n∗(n−1)∗(n−2)∗…∗(n−r+1)nPr = n*(n-1)*(n-2)*…*(n-r+1)nPr=n∗(n−1)∗(n−2)∗…∗(n−r+1)nPn=n!=n∗(n−1)∗….∗2∗1nPn = n! = n*(n-1)*….*2*1nPn=n!=n∗(n−1)∗….∗2∗112! 이상으로 넘어가면 숫자가 폭발적으로 증가한다!→ n > 12 이상인 경우에는 잘 사용하지 않는다. 2. python을 이용해서 순열 생성해보기!예를 들어 [1,2,3] 으로 만들 수 있는 모든 순열의 가지수는 어떻게 될까?→ [1,2,3], [1,3,2], [2,1,3], [2,3,1],..