본 게시글은 학부 강의 '자료구조', 온라인 강의 'Honglab Data Structure(https://www.honglab.ai/)' 그리고 강의 교재 '자바와 함께하는 자료구조의 이해'의 내용들을 바탕으로 이해한 내용을 정리하였습니다. 배열이 이진 탐색 트리보다 더 낫지 않나? 배열의 성능이 O(1)인데 배열을 응용하면 이진 탐색 트리처럼 찾는 것보다 훨씬 더 빠를 수 있지 않을까 하는 생각이 들었다.배열의 O(1) 성능은 무적이다. 이걸 이용해보는거다. 상수 시간에 데이터를 찾아내는 마법의 자료구조 해싱 등 용어가 낯설 뿐 결국 배열이다.아이템의 key를 index number로 사용한다는 것. 아이템 key를 인덱스 번호로 쓰고 그 인덱스 자리에 아이템을 저장한다.해시라는 ..

본 게시글은 학부 강의 '자료구조', 온라인 강의 'Honglab Data Structure(https://www.honglab.ai/)' 그리고 강의 교재 '자바와 함께하는 자료구조의 이해'의 내용들을 바탕으로 이해한 내용을 정리하였습니다. 데이터를 더 많이 담고 싶은데... 노드를 더 크게 만들어 보는거야 레드 블랙 트리나 B-트리 모두 2-3트리에서 나온 개념이다. 아무래도 대용량의 데이터를 다루기 위해 나온 자료구조이기 때문에 데이터베이스 분야에서 많이 쓰이는 형태라 할 수 있겠다. B-트리 다수의 키를 가진 노드로 구성되어 다방향 탐색(Multiway Search)이 가능한 균형 트리2-3 트리는 B-트리의 일종으로 노드에 키가 2개까지 있을 수 있는 트리B-트리는 대용량..

본 게시글은 학부 강의 '컴퓨터 프로그래밍 1'과 강의 교재 '파워 유저를 위한 파이썬 Express'를 토대로 이해한 내용을 정리하였습니다. 객체지향 프로그래밍을 배웠다. 직접 클래스를 만들고, 객체를 만들고, 함수를 직접 만들기도 했다. 그러기에 이제 우리는 예술가의 창작의 고통을 조금이나마 이해할 수 있게 되었다. 무에서 유를 창조하는 일은 너무나도 허들이 높다는 것. 그렇다면 우리는 앞으로 프로그래밍을 할 때 항상 아무것도 없는 무의 세계에서 하나하나 우리가 만들어 나가야 하는걸까? 너무 막막한데? 내장 함수파이썬 인터프리터에는 항상 사용할 수 있는 많은 함수가 준비되어 있다. 이러한 함수를 내장 함수라고 한다. 직접 인수에 숫자 넣어보면서 어떤 결과가 나오는 지 확인하자 ..

본 게시글은 학부 강의 '컴퓨터 프로그래밍 1'과 강의 교재 '파워 유저를 위한 파이썬 Express'를 토대로 이해한 내용을 정리하였습니다. 꼭 개발자라고 해서 모든 걸 개발, 직접 만들어낼 필요는 없다. 누군가 만들어 놓은 것을 가져다 써도 된다. 아니면 전에 내가 만들어 놓았던 것을 불러와 사용해도 된다.한 때 컴퓨터로 CD게임을 할 때 누군가 클리어 해놓은 세이브 파일을 구해와 순식간에 만렙을 찍고 시작한 적이 있다. 우리는 개발자이지만 이용자이기도 하다. 파일 입출력# 파일 객체 = open(파일 이름, 파일 모드)# 파일 객체.close()infile = open("input.txt", "r")#......infile.close()# infile 이 파일 객체# input.tx..

본 게시글은 학부 강의 '자료구조' 그리고 강의 교재 '자바와 함께하는 자료구조의 이해'의 내용들을 바탕으로 이해한 내용을 정리하였습니다. 2-3 트리의 구현이 너무 복잡해..2-3 트리를 이진 트리처럼 만들어 보는거야!! BST에 융통성이 생긴 2-3 트리. 성능도 좋았지만 노드가 많아지면서 노드 구조가 복잡해졌다. 그러기에 경우의 수가 너무 많아지는게 문제였다.2-노드와 3-노드를 처리해야 하고삽입, 삭제 시 너무나도 다양한 케이스들이 존재했다.메모리 효율성 측면에서도 항상 3개의 자식 포인터 공간이 필요했다. 그래서 2-노드일 때 하나는 낭비가 된다. 그래서 좀 더 나은 방법은 없을까? 레드 블랙 트리노드에 색을 부여하여 트리의 균형을 유지탐색, 삽입, 삭제 연산의 수행 시간이 각각 O(lo..

본 게시글은 학부 강의 '자료구조', 온라인 강의 'Honglab Data Structure(https://www.honglab.ai/)' 그리고 강의 교재 '자바와 함께하는 자료구조의 이해'의 내용들을 바탕으로 이해한 내용을 정리하였습니다. 이진 트리가 아니어도 괜찮아! 노드에 키를 2개까지 넣어보자!! 자료구조 등의 여러 컴퓨터 과학 과목을 듣다보면 모든 테크닉에는 장단점이 명확하게 존재했다. 그래서 단점을 보완한 새로운 테크닉이 등장해도 거기에는 또 다른 단점이 생겼고 보완되기 위해 지금도 새로운 방법론들이 계속 제시되고 있다. 2-3 트리도 아이디어와 함께 이전 트리의 단점을 보완하기 위해 탄생했을 것이다. 앞서 작성한 이진 탐색 트리에는 단점이 존재했다. 일반적인 BST에는 최악의 경우..

본 게시글은 학부 강의 '자료구조', 온라인 강의 'Honglab Data Structure(https://www.honglab.ai/)' 그리고 강의 교재 '자바와 함께하는 자료구조의 이해'의 내용들을 바탕으로 이해한 내용을 정리하였습니다. AVL 트리(Hight Balanced Binary Trees)AVL 트리는 Adelson-Velskii & Landis Tree 라고도 한다. 만든 사람의 이름을 땄다.AVL 트리는 트리가 한쪽으로 치우치는 것을 방지하여 트리 높이의 균형을 유지균형(Balanced) 이진 트리 : 탐색, 삽입, 삭제 연산의 수행 시간 O(logn) 보장 AVL 트리는 삽입이나 삭제로 인해 균형이 어긋나면 회전 연산을 통해 트리의 균형을 유지한다. AVL 트리는 임의의 노..

본 강의는 학부 강의 '컴퓨터 프로그래밍 1'과 강의 교재 '파워 유저를 위한 파이썬 Express' 의 내용을 바탕으로 이해한 내용을 작성하였습니다. 리스트가 어떤 친구인지 알았으니, 이제 리스트를 잘 이용할 수 있도록 고급 스킬들을 알아보도록 하자.추후에 리스트에 등장하는 인덱스 개념은 전공 자료구조에 정말 흔히 쓰이는 단어이니 나와 물아일체가 되도록 체득하자. 리스트 합병과 복제 heroes1 = ["Ironman", "Thor"]heroes2 = ["Hulk", "Hawkeye"]avengers = heroes1 + heroes2# avengers의 리스트는 ["Ironman", "Thor", "Hulk", "Hawkeye"] 가 된다.# numbers = [5, 6, 7, 8] * 3#..

본 게시글은 학부 강의 '자료구조', 온라인 강의 'Honglab Data Structure(https://www.honglab.ai/)' 그리고 강의 교재 '자바와 함께하는 자료구조의 이해'의 내용들을 바탕으로 이해한 내용을 정리하였습니다. 사전(Dictionary)저장된 데이터에 대해 탐색, 삽입, 삭제, 갱신 등의 연산을 수행할 수 있는 자료구조어찌보면 파이썬의 딕셔너리와 일맥상통. Key와 Value가 존재한다는 것. 탐색 트리저장된 데이터에 대해 접근, 탐색, 삽입, 삭제, 갱신 등의 연산을 수행할 수 있는 자료구조배열, 연결 리스트 : O(n) 시간스택, 큐 : 특정 응용에 적합한 자료구조이진 탐색 트리, AVL 트리, 2-3 트리, 2-3-4 트리, RB 트리, B-트리 이진..

본 게시글은 학부 강의 '컴퓨터 프로그래밍 1', 강의 교재 '파워 유저를 위한 파이썬 Express'의 내용들을 바탕으로 이해한 내용을 정리하였습니다. 집 앞 롯데리아만 가도 우리는 키오스크를 접할 수 있다. 필자는 착한점심을 좋아한다.그리고 나는 다른 곳에서도, 생각지도 못한 곳에서도 키오스크를 발견한 적이 있었다. 그리고 술집에 갔을 때 이제는 종업원이 아닌 작은 화면의 키오스크 화면이 나를 반겨준다. 나와 같은 I를 가진 사람에게는 더 이상 귀가 빨개져 가면서까지 메뉴를 초조해하며 고르지 않아도 되는 시대를 살아가고 있었다.우리가 사소하지만 익숙함에 속아 늘 사용하고 있는 것. 전자제품이 생겨나기 전에도 액정 화면이 아닌 종이로도 보고 있었던 것. 바로 목록. 리스트이다. 우리 생활 속에서 느..

본 게시글은 학부 강의 '자료구조', 온라인 강의 'Honglab Data Structure(https://www.honglab.ai/)' 그리고 강의 교재 '자바와 함께하는 자료구조의 이해'의 내용들을 바탕으로 이해한 내용을 정리하였습니다. 스택(Stack)한쪽 끝에서만 항목 삽입 / 삭제하는 자료구조새 항목을 저장하는 연산 : pushTop 항목을 삭제하는 연산 : pop후입 선출(Last-In First-Out, LIFO) 배열로 구현한 스택마지막 index를 top에 가지고 있다.A[++top;] = "망고"A[top++;] = "망고"는 틀린 문법! 주의할 것 단순 연결 리스트로 구현한 스택정의된 스택대로 사용하는게 제일 효율적이다. 배열로 구현한 ArrayStack class..

본 게시글은 학부 강의 '자료구조', 온라인 강의 'Honglab Data Structure(https://www.honglab.ai/)' 그리고 강의 교재 '자바와 함께하는 자료구조의 이해'의 내용들을 바탕으로 이해한 내용을 정리하였습니다. 배열(Array) 동일한 타입의 원소들이 연속적인 메모리 공간에 할당되어 각 항목이 하나의 원소에 저장되는 기본적인 자료구조특정 원소에 접근할 때에는 배열의 인덱스로 O(1) 시간에 접근새 항목을 배열 중간에 삽입하거나 중간에 있는 항목을 삭제하면, 뒤따르는 항목들을 1칸씩 뒤로 또는 앞으로 이동 : O(n) 시간 a는 배열 이름인 동시에 배열의 첫번째 원소의 레퍼런스를 저장a[i]는 인덱스 i를 가지는 원소를 가리키는 레퍼런스a[i]는 a가..