빠르게 성장하는 개발자

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

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

1. 스택의 특징선형구조를 갖는다. (자료간의 관계가 1:1이다.)마지막에 삽입한 자료를 가장 먼저 꺼낸다. (LIFO:Last-In-First-Out)자료구조 : 자료를 선형으로 저장할 저장소배열을 사용할 수 있다.스택에서 마지막 삽입된 원소의 위치를 top이라고 부른다. 혹은 stack pointercf ) 1차원 배열을 사용하여 구현할 경우, 구현이 용이하지만 스택의 크기를 변경하기 어렵다는 단점이 있다. → 저장소를 동적으로 할당하여 구현하는 방법이 있다. (복잡하지만 메모리를 효율적으로 사용) 스택의 활용 : 괄호검사, function call 2. 재귀호출function call을 생각해보자. 예를 들어def f(n): if n > 5: return else: print(f"{n} in") f..

1. 최소공배수, 최대공약수, 소수최대공약수를 구하는 방법💡유클리드 호제법2개의 자연수 a, b(a>b)에 대해서 a % b = r 일 때, a와 b의 최대공약수는 b와 r의 최대공약수와 같다.이 과정을 반복해서 나머지가 0이 되었을 때, 이 때 나누는 수가 a 와 b의 최대 공약수 이다.# 공통인 약수 중 가장 큰 수 (GCD) # gcd : greatest common divisor # a > b def gcd(a,b) : r = 0 # 나머지 # a를 나누어 떨어질 때까지 나눈다. while b != 0: r = a % b a = b b = r return a 2. 최소공배수를 구하는 방법# 두 수에 서로 공통으로 존재하는 배수 중 제일 작은 수 # 최소 공배수의 성질 # 두 수 a,b의 최소공배수..

패턴매칭 1️⃣고지식한 패턴 검색 알고리즘 (Brute Force)def search_in_text(s, p): n = len(s) m = len(p) i = 0 j = 0 while i < n and j < m: if s[i] != p[j]: i = i - j j = -1 j = j+ 1 i = i + 1 if j == m: # 검색에 성공했을 때 index 반환 return i-m else : # 검색에 실패했을 때 -1 반환 return -1 s = "This is a book!" p = "is" print(search_in_text(s,p)) # 22️⃣ 카프-라빈 알고리즘3️⃣ KMP 알고리즘kmp 알고리즘은 텍스트에서 패턴을 찾을 때 주로 쓰이는데, 특히 패턴에서 반복되는 부분이 있을 경우, ..

1. 컴퓨터에서의 문자표현컴퓨터에서 문자 ‘A’는 어떻게 메모리에 저장할까?네트워크가 발전되기 전, 미국에서는 각 지역 별로 코드체계를 정해놓고 사용했지만, 네트워크의 발전 이후 서로간 정보를 주고 받을 때 정보를 달리 해석한다는 문제가 생겼다. → 이러한 목적으로 ASCII (American Standard Code for Information Interchange)라는 문자 인코딩 표준이 제정되었다. 표준 아스키 코드 vs 확장 아스키코드표준 아스키 코드확장 아스키 코드사용 비트7bit7bit표현가능표준 문자표준 문자, 악센트 문자, 도형 문자, 특수 문자, 특수 기호 … 등 128개교환서로 다른 프로그램이나 컴퓨터 사이에 교환 가능교환 불가마이크로컴퓨터 하드웨어 및 소프트웨어 사이에서 세계적으로 통..