정말 정말 풀기 싫은 레벨3 를 풀었습니다레벨 2를 다 풀고 하면 되지 않나, 문제도 길고 조건이 많잖아ㅠ이 마인드로 하다가 고득점 kit 에 더이상 풀 레벨2 가 없어서 눈물을 머금고 도전,,,이것저것 해보다가 한시간 좀 넘게 걸렸는데 할만한데 뭔가 다른 사람 풀이 보니까 다들 잘혀~,,,,,좀 fansy 하게 풀지를 못했고,, 코드 좀 길긴해..그래도 중간중간 chatgpt 키고 싶은 마음 꾹 참으면서 일요일 아침을 잘 보냈네요..https://school.programmers.co.kr/learn/courses/30/lessons/42579 프로그래머스SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr 배운 것그..
자료구조 알고리즘
문제 설명초 단위로 기록된 주식가격이 담긴 배열 prices가 매개변수로 주어질 때, 가격이 떨어지지 않은 기간은 몇 초인지를 return 하도록 solution 함수를 완성하세요.제한사항prices의 각 가격은 1 이상 10,000 이하인 자연수입니다.prices의 길이는 2 이상 100,000 이하입니다.입출력 예pricesreturn[1, 2, 3, 2, 3][4, 3, 1, 1, 0]입출력 예 설명1초 시점의 ₩1은 끝까지 가격이 떨어지지 않았습니다.2초 시점의 ₩2은 끝까지 가격이 떨어지지 않았습니다.3초 시점의 ₩3은 1초뒤에 가격이 떨어집니다. 따라서 1초간 가격이 떨어지지 않은 것으로 봅니다.4초 시점의 ₩2은 1초간 가격이 떨어지지 않았습니다.5초 시점의 ₩3은 0초간 가격이 떨어지지 않..
두번째 자료부터 시작, 그 앞 자료들과 비교하여 삽입 위치를 지정한 후 자료를 뒤로 옮기고 지정한 자리에 자료를 삽입하여 정렬하는 알고리즘 def insertionSort(arr): for i in range(1, len(arr)): key = arr[i] j = i - 1 while j >= 0 and key < arr[j]: arr[j+1] = arr[j] j -= 1 arr[j+1] = key 시간복잡도 최선: O(n), 평균/최악: O(n^2) 공간복잡도 O(n) 장점 단순 이미 정렬되어 있을 경우 효율적 제자리 정렬 안정 정렬 단점 비효율적 배열의 길이가 길어질수록 비효율적 References https://github.com/GimunLee/tech-refrigerator/blob/master..
해당 순서에 원소를 넣을 위치는 이미 정해져 있고, 어떤 원소를 넣을지 선택하는 알고리즘 최소값을 찾고 위치 값과 교환. 나머지도 같은 방법으로 교체. A = [64, 25, 12, 22, 11] for i in range(len(A)): min_idx = i for j in range(i+1, len(A)): if A[min_idx] > A[j]: min_idx = j A[i], A[min_idx] = A[min_idx], A[i] 시간복잡도 O(n^2) 공간복잡도 O(n), swap을 주어진 배열 안에서 수행 장점 단순한 알고리즘 제자리 정렬(in-place sorting) 정렬을 위한 비교횟수는 많으나 bubble sort에 비해 실제 교환횟수는 적음 단점 비효율적. 시간 복잡도 O(n^2) 불안정..
서로 인접한 두 원소의 대소를 비교, 조건에 맞지 않으면 자리를 교환하며 정렬하는 알고리즘 void bubbleSort(int arr[], int n) { int i, j; for(i = 0; i arr[j+1]) swap(arr[j], arr[j+1]); def bubbleSort(arr): n = len(arr) for i in range(n): for j in range(0, n-i-1): if arr[i] > arr[j+1]: arr[j], arr[j+1] = arr[j+1], arr[j] 시간복잡도 모두 O(n^2) 공간복잡도 O(n), 주어진 배열 안에서 swap 사용으로 장점 구현 간단, 직..
B-Tree의 노드의 추가적인 생성관 연산을 최소화하기 위해 삽입, 삭제 시 발생하는 노드 분리를 줄이려고 고안됨 노드가 가득찰 경우 분열 대신 형제 노드로 재배치 정렬되어있고 중복 X 모든 leaf node는 같은 레벨 root node는 leaf node가 아닌 경우 적어도 2개 이상의 자식 노드를 가짐 root node, leaf node 가 아닌 내부 노드는 2((M-2)/3) + 1 ~ M 개의 자식 노드를 가지고 있음 References https://ssocoit.tistory.com/217 [자료구조] 간단히 알아보는 B-Tree, B+Tree, B*Tree 위 글을 보고 정리를 하지 않을 수 없었습니다. 가슴이 시키네요;; 그렇다면 바로 B-Tree, B*Tree, B+Tree의 특징에 ..
같은 레벨의 모든 키값들이 정렬됨 같은 레벨의 sibling node는 연결리스트 형태로 연결되어있음 모든 leaf node는 연결리스트로 연결되어 있음 키값 중복 X, 탐색 유리 블럭 사이즈를 더 많이 이동할 수 있음(key 값에 대한 하드디스크 주소 X) 그러나 무조건 leaf node 까지 내려가야함 삽입, 삭제 모두 leaf node에서 이루어짐 모든 leaf node는 같은 레벨 leaf node가 아닌 node의 키 값의 수는 그 노드의 서브트리수-1 단말 노드 비단말 노드 인덱스 노드 : leaf node가 아닌 자료, value값에 다음 노드를 가리키는 포인터 주소 존재 데이터 노드 : lead node 자료, value값에 데이터가 존재 References https://ssocoit.t..
정렬된 균형이진트리 하나의 노드에 많은 정보를 가지거나, 두 개 이상의 자식을 가질 수 있음 중복없음 모든 leaf node는 같은 레벨에 있음 root node는 자신이 leaf node가 아닌 이상 최소 2개 이상의 자식을 가짐 내부 노드(root, leaf node 이외) M/2 ~ M개의 자식을 가짐 노드는 M/2 - 1 ~ M - 1 개의 데이터(키)가 포함될 수 있음 자식 수의 하한값이 t, M = 2t - 1 데이터가 k, 자식 노드의 수는 k+1 검색은 O(logn) 구조 유지를 위해 추가적인 연산이 수행되거나 새로운 노드를 생성함 -> 최소화를 위해 B*Tree 등장 탐색을 위해서 노드를 찾아서 이동해야함 -> 해소를 위해 B+Tree 등장 아래의 조건 위반 시 재구조화 내부노드는 M/2..
