빠르게 성장하는 개발자

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

문제한 개의 회의실이 있는데 이를 사용하고자 하는 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],..

1. 완전 이진트리 (Complete Binary Tree)높이가 h이고, 노드 수가 n개 일 때, 포화 이진트리의 노드 번호 1번부터 n번까지 빈자리가 없는 트리 2. 이진 탐색 트리왼쪽 서브트리 < key (루트노드) < 오른쪽 서브트리왼쪽 서브트리와 오른쪽 서브트리도 이진 탐색 트리다.‘중위 순회’ 하면 오름차순으로 정렬된 값을 얻을 수 있다.def binary(node): global k # 왼쪽이 비어있으면 왼쪽으로 이동 if 2*node 부모이면, # 자리를 변경하고 갱신한다. # 그렇지 않다면, 반복문을 중단한다. Uploaded by N2T

1. DFS vs BFSDFS : 탐색 시작점을 기준으로 갈 수 있는 곳까지 방문한 후에, 더이상 갈 수 없으면 마지막으로 방문했던 곳으로 되돌아가서 다시 탐색을 진행하는 방식 ⇒ ‘스택’ 을 활용한다.BFS : 탐색 시작점의 인접한 정점을 모두 차례로 방문한 후에, 방문했던 정점을 시작점으로 하여 다시 인접한 정점들을 차례로 방문하는 방식 ⇒ ‘큐’ 를 활용한다. 2. 코드로 구현해보기인접행렬을 구하는 것은 DFS 를 참고한다. (https://mummur.tistory.com/37)기본적인 흐름은 다음과 같다.참고로 백준에서는 그냥 list로 진행하면 타임에러가 났다. deque로 진행해야 time error가 나지 않는다.# 준비물 : 인접행렬, 방문했는지 기록할 visited, 방문할 곳을 담은 ..

스택 다음에 배울 자료구조는 큐! (이미지 출처: 위키백과) 1. 큐의 특징큐와 스택의 공통점 : 삽입과 삭제의 위치가 제한적인 자료구조이다.차이점 : 선입-선출 (FIFO). 가장 먼저 삽입된 원소는 가장 먼저 삭제된다. 2. 큐의 구현선형큐초기 공백 큐 생성 ( front와 rear을 모두 -1로 초기화)삽입 (enQueue) : rear += 1을 한 후, 배열원소를 저장한다.삭제 (deQueue) : front += 1을 하여 큐에 남아있게 될 첫번째 원소로 이동하고 값을 리턴한다.공백상태 검사(isEmpty()) : front == rear 일 경우에 공백상태이다포화상태 검사(isFull()) : rear ==n-1 (n:배열의 크기, n-1:마지막인덱스)검색(Qpeek()) : front +=..