본문 바로가기

전체 글135

트리 구조 트리구조의 관한 내용은 힙정렬때 간략하게 공부한 탓인지 쉽게 이해하고 넘어갈 수 있었다. 책의 마지막 부분이 가까워지니까 내용이 한번 봤던 내용이여서 그런지 전보다는 쉽게 공부하는 것 같다. 트리구조는 데이터 사이의 계층이 존재한다. 따라서 값의 크고작음이 구조 자체에 나타나기 때문에 정렬하는 방법도 쉽게 나타낼 수 있다. 트리구조 데이터간의 계층관계를 표현하는 자료구조 용어 루트 : 트리의 가장 위쪽에 있는 노드 리프 (단말 노드): 트리의 가장 아래쪽에 있는 노드 비 단말 노드 (내부노드): 리프를 제외한 노드 레벨 : 루트에서 얼마나 떨어져 있는지를 나타내는 것 가지가 아래로 뻗어나갈 때마다 레벨이 1씩 증가 차수 : 각 노드가 갖는 자식의 수 형제 : 부모가 같은 노드 순서 트리 : 형제 노드의 .. 2022. 8. 10.
원형 이중 연결 리스트 이번 단원도 연결리스트이기 때문에 어려운 내용없이 잘 공부했던 것 같다. 중간중간 헷갈리는 부분도 있었지만 내가 궁금했던 질문을 적어놓고 다시 책을 읽어보니 쉽게 풀렸다. 이제 이 책도 내일이면 다 끝날 것 같은데 이제 곧 개강이기도 하니 조금 더 흥미를 가지고 있는 html를 공부 할 예정이다. 원형 이중 연결 리스트 꼬리노드의 다음이 다시 머리노드인 리스트 특징으로는 뒤쪽 노드를 찾기 쉬운 장점이 있는 반면 앞쪽 노드를 찾기 어렵다는 단점이 존재한다. 하지만 이런 단점을 보완한 방법이 이중 연결 리스트이다. 기존 연결리스트는 모두 자신의 다음 노드의 주소만 가지고 있을 뿐 이전 노드의 주소는 없었지만 이중 연결리스트는 양방향으로 이동이 가능하다. 다음은 원형 이중 연결리스트의 코드이다. from __.. 2022. 8. 8.
커서를 이용한 연결 리스트 이번 단원을 공부하며 내가 저번 단원을 잘못 이해했다는 것을 알았다. 포인터를 이용한 연결 리스트에서 포인터가 지금의 커서라고 생각했었는데 둘의 차이점을 잘 모르겠다. 저번 단원에서 원하는 위치에 데이터를 추가하려면 어떻게 해야할까 라는 생각을 하며 원하는 위치 앞, 뒤 위치의 노드 사이에 포인터 주소를 새로운 노드로 다르게 주면 되지 않을까 라는 결론을 내렸었다. 하지만 이번 단원에서 같은 내용이 나와버려서 내가 잘못 생각한 건가 라는 생각이 들어 검색을 해봤는데 결국 내가 내린 결론은 포인터와 커서는 비슷한 개념의 용어인것 같다. 일단 그렇게 이해하는게 지금 내가 공부하는데 혼란이 없을 것 같지만 나중에라도 확실히 짚고 넘어가야겠다. + 8.9 수정) 책의 앞부분에 나와있었는데 잊어버린것 같다. 책을.. 2022. 8. 7.
포인터를 이용한 연결 리스트 연결 리스트는 해시법을 공부하며 한번 공부했던 경험이 있어서 그런지 쉽게 느껴졌다, 나름 긴 코드도 술술 읽히고 책이 잘 읽혀진다는 느낌을 되게 오랜만에 느껴본 것 같아 뿌듯했다. 처음에는 연결리스트가 해시법과 뭐가 다른지 많이 헷갈렸지만 해시법과 연결 리스트는 애초에 비교를 할 수가 없는 다른 종류인 것 같다. 해시법은 검색을 하기 위한 알고리즘의 종류일 뿐이고 연결 리스트는 해시법과 같은 알고리즘을 위한 과정? 그 정도인것 같다. 연결리스트 데이터에 순서를 매겨놓은 자료구조 각 노드에는 다음 노드로 가기 위한 주소와 데이터가 담겨있다. 이 때 주소가 담겨있는 것을 포인터라고 한다. 포인터는 바로 다음 노드만을 가르키기 때문에 바로 뒷주소가 아닌 다른 주소로는 갈 수 없다. 노드를 구현하기 위한 가장 .. 2022. 8. 5.
문자열 검색 알고리즘 이번 단원은 검색 알고리즘 중 이전에 배웠던 숫자가 아닌 문자를 검색하는 내용이다. 나는 이전에 배웠었던 숫자의 검색 알고리즘을 떠올리며 문자를 모두 유니코드로 변환해 해시 법이나 선형 알고리즘으로 검색하는 줄 알았는데 내가 생각했었던 내용과는 다르게 문자 그대로를 비교하는 방법이었다. 따라서 수를 검색하는 알고리즘에서 선형 알고리즘이 문자열에서는 브루트 포스 법과 유사하다는 것도 알 수 있었다. 브루트포스법 앞서 말했듯이 숫자를 검색하는 가장 기초적인 알고리즘이 선형 알고리즘이라면 문자를 검색하는 알고리즘은 브루트 포스이다. 이때 찾으려는 문자열을 패턴이라 하고 검색되는 쪽의 문자열을 텍스트라고 한다. 브루트포스법의 원리는 다음과 같다. 텍스트와 패턴을 대조하여 첫 번째 문자가 같지 않으면 오른쪽으로 .. 2022. 8. 4.
정렬 알고리즘 (fin) - 도수정렬 이번 글은 전 단원과 함꼐 작성하려했지만 너무 길어질 것 같아서 나누어 쓴다. 도수정렬은 그동안 배웠던 알고리즘과 확실히 다른 느낌을 띄고있어서 이해하는데 많은 어려움이 있었고 오름/내림차순으로 정렬하는데 대소 구분을 하지 않는다는 점에서 신기했다. 하지만 정렬 알고리즘은 범위가 존재해야한다는 제약이 있기 때문에 사용할 때와 사용하지 못할 때의 구분을 확실히 해야한다. 도수 정렬 원소의 대소관계를 판단하지 않고 빠르게 정렬하는 알고리즘. 범위 조건이 있을 때 시간 복잡도는 O(n) 이며 매우 빠르다는 장점이 있음 처음에는 도수정렬에 대해 이해를 하지 못했는데 유튜버 '동빈나' 님의 강의를 듣고 바로 이해할 수 있게 되었다. 이 글을 읽어보아도 이해가 되질 않는다면 동빈나 님의 유튜브를 보는것도 추천한다... 2022. 8. 3.
정렬 알고리즘 (3) - 병합정렬, 힙정렬 지금까지 여러 검색 알고리즘을 배우며 그동안 배웠던 방법이 헷갈리기 시작했다. 그래서 지금까지 배웠던 내용을 다시 한 번 복습해봤다. 위 세가지 알고리즘은 간단하지만 비교적 좋지 못한 알고리즘이고 아래 알고리즘은 복잡하지만 효율적인 알고리즘이다. 버블정렬 : 두 이웃한 원소끼리 대소 비교 반복 단순 선택 정렬 : 배열의 가장 작은값을 0번 인덱스부터 채워나가는 것 단순 삽입 정렬 : 배열의 1번 인덱스를 기준으로 왼쪽의 (작은쪽) 값과 비교해나가며 맞는 자리를 찾아가는 방법 셸정렬 : 단순 삽입 정렬의 상위호환. 배열의 몇 칸 이라는 기준을 두어 값을 비교해 미리 어느정도 정렬을 해놓음 퀵정렬 : 피벗값을 기준으로 배열을 나누어 배열의 인덱스가 1개밖에 없을 때 까지 나눈 후 병합한다. 병합정렬 : 배열.. 2022. 8. 3.
정렬 알고리즘 (2) - 셸정렬, 퀵정렬 이번에 포스팅 할 내용도 정렬과 관련된 내용이다, 이전에 배웠던 알고리즘보다 더 성능이 뛰어나지만 그만큼 코드 구현이 어려웠다. 항상 드는 생각이지만 책을 보며 알고리즘의 작동 방식은 이해가 가지만 코드를 보며 해석하는건 너무 어려운것 같다. 그걸 내가 구현해내야한다는 것도 내가 넘어야 할 큰 산인것 같다. 셸정렬 셸정렬은 단순 삽입 정렬의 업그레이드 버전이라고 생각하면 쉽다. 단순 삽입 정렬은 옆 링크를 통해 알 수 있다. 여기 정렬 알고리즘 (1) - 버블정렬, 단순 선택/삽입 정렬 정렬 알고리즘은 정수의 배열을 오름/ 내림차순으로 정렬하기에 최적화 된 방법을 찾는 방식이다. 따라서 대소비교하는 수를 최소화 하는데에 초점을 두기 때문에 수식이 많아 코드를 이해하기 re-hwi.tistory.com 단.. 2022. 7. 30.
정렬 알고리즘 (1) - 버블정렬, 단순 선택/삽입 정렬 정렬 알고리즘은 정수의 배열을 오름/ 내림차순으로 정렬하기에 최적화 된 방법을 찾는 방식이다. 따라서 대소비교하는 수를 최소화 하는데에 초점을 두기 때문에 수식이 많아 코드를 이해하기 어려웠고 복잡했다. 유사한 방법의 알고리즘도 있어서 둘의 차이를 헷갈릴 때도 있었지만 그 속에서도 다른 점이 많았다. 정말 알고리즘이 늘기 위해선 문제를 많이 보고 직접 풀어보는 방법밖에는 없는 것 같다. 정렬 알고리즘 정렬이란 항목값의 대소에 따라 데이터 집합을 일정한 수서로 나열하는 작업이다. 값이 작은 데이터를 앞에 놓는것을 오름차순, 값이 큰 데이터를 앞에 놓는 것을 내림차순이라고 한다. 버블정렬 버블정렬은 이웃한 두 원소의 대소관계를 비교하여 교환을 반복하는 알고리즘이다. 총 대소구분을 하는 횟수는 (n - 1) .. 2022. 7. 28.

티스토리툴바