반응형 Algorithm/자료구조와 함께 배우는 알고리즘(Python)23 (Fin) 트리 구조, 이진 트리와 이진 검색 트리 Preface 오늘 공부한 트리 구조를 끝으로 자료구조와 알고리즘 책을 모두 마쳤다. 트리 구조와 이진 트리는 힙 정렬 알고리즘에서 이미 한 번 봤던 내용이라 쉽게 이해하며 넘어갈 수 있었고, 코드 자체도 선형 검색 방법을 따르므로 큰 어려움 없이 금방 작성할 수 있었다. 처음 알고리즘 공부를 시작했을 땐 간단한 코드만 이해할 수 있었을 뿐, 조금만 길고 복잡한 코드를 접하면 겁부터 났었는데, 몇 달 간 다양한 코드를 눈으로 보고 직접 작성해 본 탓인지 그래도 이전보다 조금은 성장한 것 같다고 느껴 나름의 성취감이 생긴다. 이번 주말엔 그동안 업로드했던 코드들을 천천히 복습하며 푹 쉰 후, 다음주부터 데이터베이스 공부를 시작할 생각이다. 1. 트리 구조 - 루트 : 트리의 가장 위쪽에 있는 노드 - 리프.. 2022. 1. 21. 원형 이중 연결 리스트 Preface 이번 장에선 연결 리스트의 단점을 보완한 원형 이중 연결 리스트를 공부했다. 코드의 구성 면에선 포인터와 커서를 이용한 연결 리스트와 크게 다른 부분이 없어 손쉽게 코드를 작성할 수 있었다. 나는 왜 지금껏 연결 리스트를 공부하며 노드를 역순으로 스캔할 생각을 하지 않았을까? 코드의 효율성은 단순히 얻어지는 것이 아니라 끝없이 더 나은 방법을 모색해야만 떠올릴 수 있는 것인데, 나는 책에 나온 방법에 한해서만 고민하는 것 같다. 아마도 '우물 안의 개구리'는 이럴 때 쓰는 말이 아닐까 싶다. 더 넓게 더 멀리 봐야 하는데 주어진 내용이 전부라 생각하고 그 이상은 생각하지 않게 된다. 공부를 하면 할 수록 책에 나온 내용만을 공부하는 것이 아닌, 개인 프로젝트를 통해 나만의 코드를 작성하며 .. 2022. 1. 18. 커서를 이용한 연결 리스트 Preface 이번 장에선 커서를 이용한 연결 리스트를 공부했다. 이는 연결 리스트를 사용하는 방법 중 하나이므로 지난 장에서 공부했던 포인터를 이용한 연결 리스트와 크게 다른 부분이 없었다. 한 가지 다른 점이라면 프리 리스트를 사용한다는 것인데, 이 또한 배열의 빈 공간 인덱스를 특정 변수에 저장한다는 개념일 뿐 특별한 점은 없어 어렵지 않게 이해할 수 있었다. - 커서(cursor) : 인덱스로 나타낸 뒤쪽 포인터 - 커서를 이용한 연결 리스트 : 데이터 개수가 크게 변하지 않거나 데이터 최대 개수를 예측할 수 있는 경우 프리 리스트를 사용하여 메모리를 확보하는 구조 - 커서를 이용한 연결 리스트 코드 # 커서로 연결 리스트 구현하기 from __future__ import annotations f.. 2022. 1. 15. 연결 리스트, 포인터를 이용한 연결 리스트 Preface 이번 장에선 리스트의 종류들 중 포인터를 통해 효율성을 향상시킨 연결 리스트에 대해 공부했다. 만들어야 할 함수가 많아 코드가 생각보다 길어졌지만, 클래스를 통해 선언하는 단순한 함수들을 나열한 것이므로 크게 어려운 부분은 없었다. 며칠 간 책에 있는 내용들을 이해하기 어려워 스트레스를 많이 받았었는데, 이번 장은 쉽게 이해할 수 있었던 탓인지 숨통이 조금 트인 것 같다. 1. 연결 리스트 - 리스트 : 순서가 있는 데이터를 늘어놓은 자료구조 1) 선형 리스트 : 데이터의 논리적인 순서와 기억 장소에 저장되는 물리적인 순서가 일치하는 구조 2) 연결 리스트 : 각 노드가 데이터와 포인터를 가지고 한 줄로 연결되어 있는 구조 - 연결 리스트 용어 1) 노드 : 각각의 원소 2) 머리 노드 :.. 2022. 1. 13. 브루트 포스법, KMP법, 보이어·무어법 Preface 이번 장에선 문자열 검색 알고리즘을 공부했다. 코드 자체는 어렵지 않았지만, 각 방법의 작동 방식이 복잡하게 설명되어 있어 이해하기 어려웠다. 처음 책을 읽을 때부터 코드를 작성하면서까지 계속 이상하다고 생각했던 부분이 있다. 대부분의 ide나 브라우저에서 이미 문자열 검색 기능을 제공하는데, 왜 굳이 검색 알고리즘을 사용할까? 나는 번거롭게 코드를 작성하는 것 보다 기존의 기능을 사용하는 것이 훨씬 효율적일 것 같다고 생각한다. 1. 브루트 포스법 - 문자열 검색 : 어떤 문자열 안에 다른 문자열이 포함되어 있는지 검사하고, 그 위치를 찾아내는 작업 1) 텍스트 : 검색되는 쪽의 문자열 2) 패턴 : 찾아내는 문자열 - 브루트 포스법(단순법) : 선형 검색을 단순 확장한 알고리즘 → 이미.. 2022. 1. 12. 힙 정렬, 도수 정렬 Preface 오늘 배운 힙 정렬과 도수 정렬을 끝으로 드디어 정렬 알고리즘을 모두 마쳤다. 두 방법 모두 글로 쓰여진 설명은 복잡했지만, 실제 코드는 생각보다 간단하여 쉽게 작성할 수 있었다. 다만 힙 정렬은 정렬 과정마다 배열을 힙으로 만들어야 하므로 불필요한 계산이 많음에도 불구하고 사용되는 이유가 무엇인지 이해할 수 없었는데, 여러 블로그를 찾아본 결과 힙 정렬은 전체 배열을 정리하는 것이 아니라 가장 큰 값 몇 개만을 필요로 할 때 사용한다고 한다. 요즘 들어 공부를 할 때마다 머리를 복잡하게 하는 한 가지 걱정이 있다. 책에 쓰여진 코드를 천천히 분석하며 계산해보면 분명 이해는 할 수 있지만, 막상 나에게 동일한 문제가 주여졌을 때 내가 해당 코드를 작성할 수 있을 거란 확신이 들지 않는다는 .. 2022. 1. 10. 병합 정렬 Preface 오늘은 병합 정렬을 공부했는데, 어제 배운 퀵 정렬과 크게 다른 점이 없는 것 같다. 퀵 정렬은 배열을 1개의 원소만이 남을 때 까지 두 그룹으로 나누는 작업을 반복하는데, 병합 정렬 역시 배열을 마지막 원소까지 나눈 후 오름차순으로 병합하는 작업을 반복한다. 한 가지 차이점이 있다면 퀵 정렬은 피벗을 중심으로 배열을 나누지만, 병합 정렬은 무작위로 그룹을 반으로 나눈다는 것이다. 나는 나누어진 원소들을 병합할 때마다 비교하여 정렬하는 병합 정렬보단 한 번 피벗을 설정한 후 나누면서 정렬을 수행하는 퀵 정렬이 훨씬 효율적이라고 생각한다. 마지막으로 본문의 첫 번 째 코드에서 a, b 배열의 남은 원소들을 c에 복사할 때 남은 원소들 중 다른 배열의 마지막 원소보다 작은 배열이 있을 경우 정.. 2022. 1. 9. 퀵 정렬 Preface 오늘은 퀵 정렬을 공부했다. 일반적인 퀵 정렬에서부터 스택을 사용한 비재귀적 정렬, 특정한 규칙을 적용한 퀵 정렬까지 다양한 방식으로 퀵 정렬을 구현해봤다. 한 번 공부할 때 모든 것을 완벽히 이해할 정도는 아니어도 다시 봤을 때 배웠던 것들을 금방 떠올릴 수 있을 정도로 공부했던 탓인지 3개월 전 업로드했던 스택 관련 코드들은 큰 어려움 없이 사용할 수 있었다. 그러나 배열의 맨 앞, 중간, 맨 끝 원소의 중앙값을 정렬한 후 원소의 수가 9개 미만일 땐 단순 선택 정렬, 10개 이상일 땐 퀵 정렬을 사용하여 결과를 출력하는 코드는 생각할 것도 너무 많고 이것 저것 계산해볼 값들도 다양해서 머리가 너무 복잡했다. 앞으로는 직접 계산하지 않고 종단점을 설정한 후 디버깅을 실행하여 계산 과정을.. 2022. 1. 8. 셸 정렬 Preface 오늘은 다음날 공부할 시간이 없을 것 같아 한 파트를 추가로 업로드한다. 이번 파트에선 셸 정렬에 대해 공부했다. 불과 몇 시간 전 단순 삽입 정렬을 직접 계산할 땐 계산할 부분이 너무 많아서 복잡하게 느껴진다는 생각을 했었는데, 셸 정렬을 사용하여 계산을 하자 확실히 원소들을 정렬하기 쉬워졌다는 것을 느낄 수 있었다. 또한, 셸 정렬의 앞 부분을 읽어보며 아무리 원소들을 그룹으로 나누어 정렬한다고 한들 이들이 순서 없이 다시 합쳐지면 결국 단순 삽입 정렬과 동일해질 것 같다는 생각이 들어 직접 두 가지 방법으로 계산을 해보기도 했는데, 뒷 부분에 이러한 문제점을 완화시킬 수 있는 수열을 사용한 셸 정렬이 소개되어 있어 셸 정렬의 효율성을 인정할 수 있었다. 처음 정렬 알고리즘을 공부할 땐.. 2022. 1. 6. 단순 선택 정렬, 단순 삽입 정렬 Preface 오늘은 지난 포스팅에 이어 정렬 알고리즘의 종류 중 하나인 단순 선택 정렬과 단순 삽입 정렬, 이진 삽입 정렬을 공부했다. 단순 선택 정렬은 내가 예상했던 방식으로 코드를 작성하여 큰 어려움 없이 이해할 수 있었지만, 단순 삽입 정렬은 그렇지 않았다. 어떠한 방식으로 정렬이 진행되는 것인지는 금방 이해할 수 있었지만, 이 내용을 코드화하자 생각보다 복잡하여 코드를 한 줄 한 줄 분석한 후 직접 노트에 적어 계산해 본 후에야 코드의 작동 방식을 알 수 있었다. 이진 삽입 정렬도 마찬가지이다. 이진 검색을 하는 부분에서 검색 범위의 맨 끝 원소 인덱스를 i가 아닌 i - 1로 설정한 이유부터 시작하여 j의 값을 굳이 범위로 설정하는 이유 등 곧바로 이해되지 않는 부분들이 있어 한 시간 이상을 .. 2022. 1. 5. 이전 1 2 3 다음
