우노

B 트리란? B트리는 데이터베이스와 파일 시스템에서 널리 사용되는 자가 균형 이진 검색 트리의 일종입니다. B트리의 설계는 디스크 I/O 작업의 최소화를 목표로 하며, 이를 위해 트리의 높이를 가능한 낮게 유지합니다. 해당 포스팅에선 B트리의 규칙과 조회, 삽입, 삭제 방법에 대해서 다뤄보겠습니다. 규칙 노드 노드 차수(M): 각 노드가 가질 수 있는 자식 노드의 최대 개수 각 노드는 최소 M/2개에서 최대 M개의 자식 노드를 가질 수 있습니다. 루트 노드: 최소 2개의 자식 노드 (트리 생성/삭제 시 예외 가능) 내부 노드: 최소 ⌈M/2⌉개의 자식 노드 리프 노드: 모든 리프 노드는 동일한 레벨에 있어야 함 (데이터 접근 시간 균일화) 키 각 노드에 저장된 값입니다. 키 개수 범위: 최소 (M/2)-..

들어가기 앞서 투 포인터 알고리즘은 리스트에 순차적으로 접근해야 할 때, 2개의 점의 위치를 기록하면서 처리하는 알고리즘을 의미한다. ‘특정한 합을 가지는 부분 연속 수열 찾기’ 또는 ‘정렬되어 있는 두 리스트의 합집합’과 같은 문제에 사용된다. 특정한 합을 가지는 부분 연속 수열 찾기 투 포인터 알고리즘을 이용하여 ‘특정한 합을 가지는 부분 연속 수열 찾기’ 문제를 풀어보자. 해당 문제는, 양의 정수로만 구성된 리스트가 주어졌을 때, 그 부분 연속 수열 중에서 ‘특정한 합’을 갖는 수열의 개수를 출력하는 문제이다. 투 포인터 알고리즘의 특징은 2개의 변수를 이용해 리스트 상의 위치를 기록한다는 점이며, 해당 문제에서는 부분 연속 수열의 시작점(start)와 끝점(end)의 위치를 기록한다. 특정한 부분..

들어가기 앞서, 소수는 2보다 큰 자연수 중에서 1과 자기 자신을 제외한 자연수로는 나누어떨어지지 않는 자연수이다. 간혹 코딩 테스트에선, 어떠한 자연수가 소수인지 아닌지 판별하거나, 1부터 N까지의 모든 소수를 출력해야 하는 문제 등이 출제된다. 따라서, 해당 포스팅에선 두 가지 문제를 해결하는 효율적인 방법에 대해서 다뤄볼 것이다. 특정 자연수의 소수 판별 특정한 자연수 X가 소수인지 아닌지 효율적으로 확인하기 위해선, 자연수 X의 제곱근까지 나누어떨어지는 수가 있는지 없는지 확인하면 된다. 해당 알고리즘의 시간 복잡도는, 자연수 X의 제곱근까지만 확인하므로 O(X^1/2)이다. import math # 소수 판별 함수 def is_prime_number(x): # 2부터 x의 제곱근까지의 모든 수를..

표준 라이브러리란? 특정한 프로그래밍 언어에서 자주 사용되는 표준 소스코드를 미리 구현해 놓은 라이브러리를 의미한다. 코딩 테스트에서는 대부분 표준 라이브러리를 사용할 수 있도록 허용하므로, 표준 라이브러리를 사용하면 소스코드 작성량에 대한 부담을 줄일 수 있다. 파이썬에서 지원하는 표준 라이브러리는 굉장히 다양하지만, 코딩 테스트를 준비하며 반드시 알아야하는 라이브러리는 6가지 정도이다. PS 주요 라이브러리 with Python 내장 함수 print(), input()과 같은 기본 입출력 기능부터 sorted()와 같은 정렬 기능을 포함하고 있는 기본 내장 라이브러리이다. itertools 파이썬에서 반복되는 형태의 데이터를 처리하는 기능을 제공하는 라이브러리이다. 순열과 조합 라이브러리를 제공한다...

들어가기 앞서 PS 시 유용하게 사용되는 함수들을 정리합니다. 2차원 리스트를 왼쪽으로 90도 회전하기 def rotate_the_matrix_90_degree_to_the_left(a): n = len(a) # 행 길이 계산 m = len(a[0]) # 열 길이 계산 result = [[0] * n for _ in range(m)] # 회전된 결과 리스트 # 모든 요소값을 90도 회전 for i in range(n): for j in range(m): result[m-j-1][i] = a[i][j] return result 2차원 리스트를 오른쪽으로 90도 회전하기 def rotate_the_matrix_90_degree_to_the_right(a): n = len(a) # 행 길이 계산 m = len..

위상 정렬 알고리즘이란? 사이클이 없는 방향 그래프의 모든 노드를 방향성에 거스르지 않도록 순서대로 나열하는 것을 의미합니다. 예시) 선수과목을 고려한 학습 순서 설정 위 세 과목을 모두 듣기 위한 적절한 순서는? 자료구조 → 알고리즘 → 고급 알고리즘 (o) 자료구조 → 고급 알고리즘 → 알고리즘 (x) 진입차수와 진출 차수 진입 차수(Indegree) 특정한 노드로 들어오는 간선의 개수 진출 차수(Outdegree) 특정한 노드에서 나가는 간선의 개수 위상 정렬 알고리즘 세부 동작 과정 진입차수가 0인 모든 노드를 큐에 넣습니다. 큐가 빌 때까지 다음 과정을 반복합니다. 큐에서 원소를 꺼내, 해당 노드에서 나가는 모든 간선을 그래프에서 제거합니다. 새롭게 진입차수가 0이 된 노드를 큐에 넣습니다. 결..

신장 트리란? 신장 트리는 그래프 알고리즘 문제로 자주 출제되는 문제 유형입니다. 신장 트리란, 하나의 그래프가 있을 때, 모든 노드를 포함하면서 사이클이 존재하지 않는 부분 그래프를 의미합니다. 이때 모든 노드가 포함되어 서로 연결되면서 사이클이 존재하지 않는다는 조건은 트리의 성립 조건이기도 합니다. 따라서, 이러한 그래프를 신장 트리라고 부릅니다. 크루스칼 알고리즘이란? 예를 들어, N개의 도시가 존재하는 상황에서, 각각의 도시 사이에 도로를 놓아, 전체 도시가 서로 연결될 수 있도록 도로를 설치할 때, 최소한의 비용으로 모든 도시를 연결하기 위해선 어떤 알고리즘이 사용되어야할까요? 최소 비용으로 만들 수 있는 신장 트리를 찾는 알고리즘을 ‘최소 신장 트리 알고리즘' 이라고 하며, 대표적인 ..

주요 개념 서로소 집합은 크루스칼 알고리즘에 핵심 개념으로 사용됩니다. 서로소 집합은 공통 원소가 없는 두 집합을 의미합니다. 예를 들어, 집합 {1, 2} 와 {3, 4} 는 서로소 관계입니다. 서로소 집합은 2가지 연산(union, find)으로 조작할 수 있습니다. union 연산은 2개의 부분 집합을 하나의 집합으로 합치는 연산입니다. find 연산은 특정한 원소가 어떤 집합에 속해있는지 알려주는 연산입니다. 따라서, 전체 요소들이 주어졌을 때, 전체 요소들이 어떤 형태의 부분 집합으로 나누어지는지 확인하고 싶을 때 사용하는 개념입니다. 서로소 집합 자료구조의 동작 과정 여러 개의 Union(A, B) 연산이 주어집니다. 순서대로 Union(A, B) 연산을 진행합니다. find 를 사용해, A와..

트리와 그래프의 구조 트리 방향성 : 방향 그래프 순환성 : 비순환 루트 노드 존재 여부 : 존재함 노드간 관계성 : 부모와 자식 관계 있음 모델의 종류 : 계층 모델 그래프 방향성 : 방향 그래프 혹은 무방향 그래프 순환성 : 순환 및 비순환 루트 노드 존재 여부 : 존재하지 않음 노드간 관계성 : 부모와 자식 관계 없음 모델의 종류 : 네트워크 모델 참고 이것이 취업을 위한 코딩테스트다. with Python https://kangworld.tistory.com/37

플로이드 워셜(Floyd-Warshall) 알고리즘이란? 플로이드 워셜 알고리즘은 ‘모든 지점에서 다른 모든 지점까지의 최단 경로를 모두 구해야 하는 경우'에 사용할 수 있는 알고리즘입니다. 해당 알고리즘은 매 단계마다 ‘현재 노드를 거쳐 가는 노드'를 기준으로 알고리즘을 수행합니다. 노드의 개수가 N개일 때, 알고리즘상으로 N번의 단계를 통해 현재 노드를 선택하며, 단계마다 O(N^2)의 연산을 통해 ‘현재 노드를 거쳐 가는' 모든 경로를 고려합니다. 따라서, 플로이드 워셜 알고리즘의 총 시간 복잡도는 O(N^3)입니다. 해당 알고리즘은 2차원 리스트에 ‘최단 거리' 정보를 저장한다는 특징이 있습니다. 모든 노드가 다른 모든 노드로 가는 최단 거리 정보를 담아야 하기 때문입..