aeightchill

깊이 우선 탐색 (Depth-First Search, DFS)루트 노드 혹은 임의 노드에서 다음 브랜치로 넘어가기 전에 해당 브랜치를 모두 탐색하는 방법 (스택 or 재귀함수를 통해 구현) 가능한 한 깊이 내려가면서 탐색을 진행한다.특정 경로를 찾거나, 그래프의 모든 노드를 방문하는 데 유용하다. def dfs(graph, v, visited): visited[v] = True for i in graph[v]: if not visited[i]: dfs(graph, i, visited)visited = [False] * ndfs(graph, 1, visited)      너비 우선 탐색 (Breadth-First Search, BFS)루트 노드 또는 임의 노드에서 인접한 노드부터 먼저 탐색하는 방법 ..

계수 정렬 (Counting Sort)계수 정렬은 비교하지 않는 정렬 알고리즘으로 데이터의 개수를 세서 정렬하는 방식. 정렬하려는 데이터의 범위를 인덱스로 갖는 빈 배열을 생성한다.데이터 범위가 0 ~ 99까지라면 크기가 100인 빈 배열을 생성한다.정렬하려는 배열을 순회하면서 데이터에 해당하는 인덱스의 값을 1씩 증가한다. 제약 조건데이터의 범위가 0 또는 양의 정수여야 한다. 예시배열 [8, 3, 9, 2, 3, 4, 0, 5]를 계수 정렬하는 과정. 정렬하려는 배열 : 83923405계수 배열 :1012110011인덱스 ↑0123456789최종 배열 : 02334589 시간 복잡도  :  O(n + k)   * 데이터의 개수 : n , 데이터의 최댓값 : k  (데이터의 최댓값이 무한대에 수렴하면 ..

기수 정렬 (Radix Sort)기수 정렬은 비교하지 않는 정렬 알고리즘으로 낮은 자릿수부터 정렬을 수행. 숫자별로 버킷(bucket)이라는 queue를 생성정렬하려는 숫자들의 각 자릿수에 해당하는 숫자를 각각의 버킷에 넣어 정렬이를 자릿수만큼 반복한다.   단점버킷을 구성하기 위한 추가 메모리가 필요정렬할 수 있는 데이터 타입이 한정적 예시숫자 배열 [73, 21, 56, 13, 16, 35, 41, 69]를 기수 정렬을 이용해 오름차순으로 정렬하는 과정7321561316354169버킷          0123456789 버킷 4121 1373 351656  690123456789  2141731335561669버킷 1613213541566973  0123456789  1316213541566973 시..

병합 정렬 (Merge Sort)병합 정렬은 재귀를 이용하는 분할 정복 알고리즘. 분할  →   배열을 쪼개는 것.정복  →   분할한 배열을 정렬하면서 하나로 합병하는 것.   작동 방식정렬하려는 배열을 크기가 0 또는 1이 될 때까지 절반씩 분할.분할된 배열은 다시 하나의 배열로 합쳐지면서 정렬.예시배열 [8, 3, 2, 1, 7, 6, 4, 5]가 있을 때 다음과 같은 과정으로 정렬한다. (오름차순)분할8 3 2 1 7 6 4 58 3 2 1  |  7 6 4 58 3  |  2 1  |  7 6  |  4 58  |  3  |  2  |  1  |  7  |  6  |  4  |  5정렬6 7  |  4 5  |  _ _ _ _6 7  |  _ 5  |  4 _ _ _6 7  |  _ _  |  ..

퀵 정렬 (Quick Sort)퀵 정렬은 피봇보다 작은 값으로 구성된 배열과 피봇보다 큰 값으로 구성된 배열로 분할해 정렬하는 알고리즘.   작동 방식변수 : low low배열의 첫 번째 요소에서 시작피봇보다 작으면 오른쪽으로 한 칸 이동피봇보다 크면 이동 Xhigh배열의 마지막 요소에서 시작피봇보다 크면 왼쪽으로 한 칸 이동피봇보다 작으면 이동 Xlow와 high 둘 다 이동하지 않을 때 두 변수가 가리키는 값을 교환예시배열 [4, 3, 2, 6, 7, 1, 5]가 있을 때 다음과 같은 과정으로 분할한다.분할은 배열의 크기가 1이하가 될 때까지 반복해서 수행한다.1.4326715 pivotlow    high2.4326715 pivotlow    high3.4326715 pivot low  high(이..

삽입 정렬 (Insertion Sort)삽입 정렬은 배열을 앞에서부터 순회하면서 정렬된 부분의 적절한 위치에 값을 삽입하는 방식으로 정렬하는 알고리즘.   작동 방식인덱스 i에 있는 a를 정렬할 차례일 때, 인덱스 0부터 i-1까지는 이미 정렬된 상태배열의 정렬된 부분에서 a보다 작거나 같은 수와 a보다 큰 수 사이에 a를 삽입한다.예시배열 [5, 3, 8, 1, 2]가 있을 때 다음과 같은 과정으로 정렬된다.5 3 8 1 23 5 8 1 23 5 8 1 21 3 5 8 21 2 3 5 8시간 복잡도 : O(n^2)    * 1 + 2 + ... + (n-2) + (n-1) = n(n-1) / 2   def insertion_sort(arr): n = len(arr) for i in range..

선택 정렬 (Selection Sort)선택 정렬은 배열을 순회하면서 배열의 앞에서부터 차례대로 각 인덱스에 들어갈 값을 선택해 위치시키며 정렬하는 알고리즘   작동 방식인덱스 i에 들어갈 값은 인덱스 i부터 N(마지막 인덱스)까지 중 최소값이 된다.예시배열 [5, 3, 8, 1, 2]가 있을 때 다음과 같은 과정으로 정렬된다.5 3 8 1 21 3 8 5 21 2 8 5 31 2 3 5 81 2 3 5 8시간 복잡도 : O(n^2)        * (n-1) + (n-2) + ... + 2 + 1 = n(n-1) / 2   def selection_sort(arr): for i in range(len(arr)): min_idx = i for j in range(i+1, l..

버블 정렬 (Bubble Sort)버블 정렬은 선택 정렬과 유사한 알고리즘으로 서로 인접한 두 원소의 대소를 비교하고, 조건에 맞지 않다면 자리를 교환하며 정렬하는 알고리즘. 버블 정렬하면 배열의 뒤에서부터 정렬된다.배열의 첫 번째 요소부터 n번째 요소까지 오름차순으로 버블 정렬을 수행하면 해당 범위의 최댓값이 n번째에 위치하게 된다.  배열의 n번째 요소를 정렬하는데 n-1번을 비교하므로 배열의 모든 요소를 정렬하려면 (n-1) + (n-2) + ... + 2 + 1 = n(n-1) / 2 만큼 연산을 수행한다. 시간 복잡도 : O(n^2)  def bubble_sort(arr): for i in range(len(arr)): for j in range(len(arr) - i - 1)..

🗂️  문제[SQL50] 550. Game Play Analysis IV (AGGREGATE)✍🏻  풀이 문제 해석유저가 첫 로그인한 다음날 다시 로그인한 비율을 구하는 문제 📌  Table : ActivityColumn NameType설명player_idint유저의 고유 IDdevice_idint유저가 로그인한 장치의 IDevent_datedate로그인 날짜games_playedint해당 로그인 동안 플레이한 게임 수 (0일 수도 있음) PRIMARY KEY  :  (player_id, event_date)한 유저(player_id)가 같은 날(event_date)에 여러 번 로그인한 기록은 없다. 📌  요구 사항각 유저의 첫 로그인 날짜(first_login)를 찾는다.첫 로그인 날짜의 다음날..

이상 현상 (Anomaly) 이상 현상이란?이상 현상은 불필요한 데이터 중복으로 인해 Relation에서 데이터를 삽입, 수정, 삭제할 때 발생하는 부작용을 의미한다.  이상 현상의 종류삽입 이상 (Insertion Anomaly)새로운 데이터를 추가하려면 불필요한 데이터까지 함께 삽입해야 하는 문제갱신 이상 (Update Anomaly)중복된 튜플 중 일부만 수정하면 데이터 불일치가 발생하는 문제삭제 이상 (Delete Anomaly)특정 데이터를 삭제할 때 필요한 정보까지 함께 삭제되는 문제  📎  삽입 이상 (Insertion Anomaly)새로운 데이터를 삽입하려면 관계없는 정보도 함께 입력해야 하는 문제불필요한 데이터가 강제로 포함되므로 데이터 정합성 유지가 어려움  📎  갱신 이상 (Upd..