Jeff's Inovation Lab Jeff's Inovation Lab

목차 삽입정렬 삽입정렬 구현 단계 알고리즘 분석 1.삽입정렬 삽입 정렬은 두 번째 인덱스부터 시작 해당 인덱스(key 값) 앞에 있는 데이터(B)부터 비교해서 key 값이 더 작으면, B값을 뒤 인덱스로 복사 이를 key 값이 더 큰 데이터를 만날때까지 반복, 그리고 큰 데이터를 만난 위치 바로 뒤에 key 값을 이동 2.삽입정렬 구현단계 데이터가 네 개 일때 (데이터 갯수에 따라 복잡도가 떨어지는 것은 아니므로, 네 개로 바로 로직을 이해해보자.) 예: data_list = [9, 3, 2, 5] 처음 한번 실행하면, key값은 9, 인덱스(0) - 1 은 0보다 작으므로 끝: [9, 3, 2, 5] 두 번째 실행하면, key값은 3, 9보다 3이 작으므로 자리 바꾸고, 끝: [3, 9, 2, 5] 세..

목차 선택정렬 선택정렬 구현 단계 알고리즘 분석 1.선택정렬 주어진 데이터 중, 최소값을 찾음 해당 최소값을 데이터 맨 앞에 위치한 값과 교체함 맨 앞의 위치를 뺀 나머지 데이터를 동일한 방법으로 반복함 2.삽입정렬 구현단계 데이터가 두 개 일때 예: dataList = [9, 1] data_list[0] > data_list[1] 이므로 data_list[0] 값과 data_ list[1] 값을 교환 데이터가 세 개 일때 예: data_list = [9, 1, 7] 처음 한번 실행하면, 1, 9, 7 이 됨 두 번째 실행하면, 1, 7, 9 가 됨 데이터가 네 개 일때 예: data_list = [9, 3, 2, 1] 처음 한번 실행하면, 1, 3, 2, 9 가 됨 두 번째 실행하면, 1, 2, 3, ..

목차 버블정렬 구현 단계 1.버블정렬 구현 단계 데이터가 네 개 일때 (데이터 갯수에 따라 복잡도가 떨어지는 것은 아니므로, 네 개로 바로 로직을 이해해보자.) 예: data_list = [1, 9, 3, 2] 1차 로직 적용 1 와 9 비교, 자리바꿈없음 [1, 9, 3, 2] 9 와 3 비교, 자리바꿈 [1, 3, 9, 2] 9 와 2 비교, 자리바꿈 [1, 3, 2, 9] 2차 로직 적용 1 와 3 비교, 자리바꿈없음 [1, 3, 2, 9] 3 과 2 비교, 자리바꿈 [1, 2, 3, 9] 3 와 9 비교, 자리바꿈없음 [1, 2, 3, 9] 3차 로직 적용 1 과 2 비교, 자리바꿈없음 [1, 2, 3, 9] 2 과 3 비교, 자리바꿈없음 [1, 2, 3, 9] 3 과 9 비교, 자리바꿈없음 [1..

목차 정렬 버블정렬 1.정렬 정렬 (sorting): 어떤 데이터들이 주어졌을 때 이를 정해진 순서대로 나열하는 것 정렬은 프로그램 작성시 빈번하게 필요로 함 다양한 알고리즘이 고안되었으며, 알고리즘 학습의 필수다양한 정렬 알고리즘 이해를 통해, 동일한 문제에 대해 다양한 알고리즘이 고안될 수 있음을 이해하고, 각 알고리즘간 성능 비교를 통해, 알고리즘 성능 분석에 대해서도 이해할 수 있음 2.버블정렬 정렬 (sorting): 어떤 데이터들이 주어졌을 때 이를 정해진 순서대로 나열하는 것 정렬은 프로그램 작성시 빈번하게 필요로 함 다양한 알고리즘이 고안되었으며, 알고리즘 학습의 필수 다양한 정렬 알고리즘 이해를 통해, 동일한 문제에 대해 다양한 알고리즘이 고안될 수 있음을 이해하고, 각 알고리즘간 성능 ..

목차 알고리즘 연습 방법 1.알고리즘 연습 방법 연습장과 펜을 준비한다. 알고리즘 문제를 읽고 분석한다. 간단하게 테스트용으로 매우 간단한 경우부터 복잡한 경우를 순서대로 생각해보면서 연습장과 펜을 이용하여 알고리즘을 생각해본다. 가능한 알고리즘이 보인다면 구현할 알고리즘을 세부 항목으로 나누고 문장으로 세부 항목을 나누어서 적어본다. 코드화 하기 위해 데이터 구조 또는 사용할 변수를 정리한다. 각 문장을 코드 레벨로 적는다. 데이터 구조 또는 사용할 변수가 코드에 따라 어떻게 변하는지를 손으로 적으면서 임의 데이터로 코드가 정상 동작하는지를 연습장과 펜으로 검증한다. https://bit.ly/37BpXiC

목차 Heap의 pop Heap의 구현(pop) 시간 복잡도 1.Heap의 Insert 보통 삭제는 최상단 노드 (root 노드)를 삭제하는 것이 일반적임 힙의 용도는 최대값 또는 최소값을 root 노드에 놓아서, 최대값과 최소값을 바로 꺼내 쓸 수 있도록 하는 것임 상단의 데이터 삭제시, 가장 최하단부 왼쪽에 위치한 노드 (일반적으로 가장 마지막에 추가한 노드) 를 root 노드로 이동 root 노드의 값이 child node 보다 작을 경우, root 노드의 child node 중 가장 큰 값을 가진 노드와 root 노드 위치를 바꿔주는 작업을 반복함 (swap) 특정 노드의 관련 노드 위치 알아내기 부모 노드 인덱스 번호 (parent node's index) = 자식 노드 인덱스 번호 (child..

목차 Heap의 Insert Heap의 구현(Insert) 1.Heap의 Insert 일반적으로 힙 구현시 배열 자료구조를 활용함 배열은 인덱스가 0번부터 시작하지만, 힙 구현의 편의를 위해, root 노드 인덱스 번호를 1로 지정하면, 구현이 좀더 수월함 인덱스 번호는 1번부터 시작하도록 변경 삽입한 노드가 부모 노드의 값보다 클 경우, 부모 노드와 삽입한 노드 위치를 바꿈 삽입한 노드가 루트 노드가 되거나, 부모 노드보다 값이 작거나 같을 경우까지 반복 특정 노드의 관련 노드 위치 알아내기 부모 노드 인덱스 번호 (parent node's index) = 자식 노드 인덱스 번호 (child node's index) // 2 왼쪽 자식 노드 인덱스 번호 (left child node's index) =..

목차 Heap의 삽입 Heap의 삭제 1.Heap의 삽입 힙은 완전 이진 트리이므로, 삽입할 노드는 기본적으로 왼쪽 최하단부 노드부터 채워지는 형태로 삽입 삽입할 데이터가 힙의 데이터보다 클 경우 (Max Heap의 예) 먼저 삽입된 데이터는 완전 이진 트리 구조에 맞추어, 최하단부 왼쪽 노드부터 채워짐 채워진 노드 위치에서, 부모 노드보다 값이 클 경우, 부모 노드와 위치를 바꿔주는 작업을 반복함 (swap) 2.Heap의 삭제(Max Heap) 보통 삭제는 최상단 노드 (root 노드)를 삭제하는 것이 일반적임 힙의 용도는 최대값 또는 최소값을 root 노드에 놓아서, 최대값과 최소값을 바로 꺼내 쓸 수 있도록 하는 것임 상단의 데이터 삭제시, 가장 최하단부 왼쪽에 위치한 노드 (일반적으로 가장 마지..