빠르게 성장하는 개발자

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

문제N×N 크기의 공간에 물고기 M마리와 아기 상어 1마리가 있다. 공간은 1×1 크기의 정사각형 칸으로 나누어져 있다. 한 칸에는 물고기가 최대 1마리 존재한다.아기 상어와 물고기는 모두 크기를 가지고 있고, 이 크기는 자연수이다. 가장 처음에 아기 상어의 크기는 2이고, 아기 상어는 1초에 상하좌우로 인접한 한 칸씩 이동한다.아기 상어는 자신의 크기보다 큰 물고기가 있는 칸은 지나갈 수 없고, 나머지 칸은 모두 지나갈 수 있다. 아기 상어는 자신의 크기보다 작은 물고기만 먹을 수 있다. 따라서, 크기가 같은 물고기는 먹을 수 없지만, 그 물고기가 있는 칸은 지나갈 수 있다.아기 상어가 어디로 이동할지 결정하는 방법은 아래와 같다.더 이상 먹을 수 있는 물고기가 공간에 없다면 아기 상어는 엄마 상어에게..

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

문제수식은 일반적으로 3가지 표기법으로 표현할 수 있다. 연산자가 피연산자 가운데 위치하는 중위 표기법(일반적으로 우리가 쓰는 방법이다), 연산자가 피연산자 앞에 위치하는 전위 표기법(prefix notation), 연산자가 피연산자 뒤에 위치하는 후위 표기법(postfix notation)이 그것이다. 예를 들어 중위 표기법으로 표현된 a+b는 전위 표기법으로는 +ab이고, 후위 표기법으로는 ab+가 된다.이 문제에서 우리가 다룰 표기법은 후위 표기법이다. 후위 표기법은 위에서 말한 법과 같이 연산자가 피연산자 뒤에 위치하는 방법이다. 이 방법의 장점은 다음과 같다. 우리가 흔히 쓰는 중위 표기식 같은 경우에는 덧셈과 곱셈의 우선순위에 차이가 있어 왼쪽부터 차례로 계산할 수 없지만 후위 표기식을 사용하..

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 +=..

비선형구조인 그래프 구조는 그래프로 표현된 자료를 빠짐 없이 검색하는 것이 중요하다.DFS (깊이 우선 탐색)BFS (너비 우선 탐색) 1. DFS란?시작 정점의 한 방향으로 갈 수 있는 경로가 있는 곳까지 깊이 탐색해 가다가 더이상 갈 곳이 없으면, 가장 마지막에 만났던 갈림길 갈선이 있는 정점으로 되돌아와서 다른 방향의 정점으로 탐색을 계속 반복하여 결국 모든 정점을 반복하는 순회방법 → 가장 마지막에 만났던 갈림길의 정점으로 돌아가기 위해서 “스택” 을 사용한다. 2. DFS의 기본 구조(출처: 관광이 블로그)DFS를 구하기 위한 준비물은 다음과 같다… 현재 노드와 인접한 노드의 정보를 담은 인접리스트 혹은 인접 행렬방문했는지 여부를 체크할 수 있는 리스트마지막 방문 위치를 담을 수 있는 스택2-1..