본문 바로가기
반응형

Algorithm29

브루트 포스법, 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.
정렬 알고리즘, 버블 정렬 Preface 이번 장에선 정렬 알고리즘이란 무엇인지에 관한 내용과 그 종류 중 하나인 버블 정렬 및 버블 정렬에 약간의 변화를 준 셰이커 정렬을 공부했다. 코드를 작성할 땐 아무 생각 없이 책에 나온 방식대로 진행하게 되지만, 해당 코드를 완성하면 기존의 코드에 능률성을 더한 새로운 코드 작성을 요구한다. 이전부터 코드를 작성할 때 어떻게 해야 더욱 효율적인 코드를 작성할 수 있을지를 고민하자고 생각은 하지만, 막상 공부를 하다 보면 그게 마음대로 되지 않는다. 내일부턴 책에 있는 코드를 그대로 따라 작성하기 전에 해당 문제를 해결할 방법을 미리 고민해 본 후 책과 비교하며 코드를 짤 생각이다. 또, 알고리즘 공부를 시작한 뒤로 진도를 나가는 데 시간이 너무 오래 걸리는데, 내 공부 방식이 맞는 것인지.. 2022. 1. 2.
하노이의 탑, 8퀸 문제 Preface 거의 두 달 만에 글을 작성한다. 개발 공부를 시작한 뒤로 이렇게 오래 공부를 쉬었던 적은 처음인 것 같다. 그동안 이런저런 일들이 있었다. 기말고사를 친 후 무사히 2학기를 마쳤고, 여자친구가 생겨 이곳 저곳 놀러다니며 데이트도 했다. 정말 오랜만에 사귄 여자친구인 탓인지 모든 정신이 팔려 시간 가는 줄도 모르고 두 달을 보낸 것 같다. 그런데 연말이 되고 주변에서 목표를 이루기 위해 노력하는 친구들을 보니 문득 정신이 들었고, 이렇게 허송세월을 보낼 수는 없다는 생각이 뇌리를 스쳤다. 이제 며칠 후면 스물 셋이 되고 졸업도 가까워졌다는 조바심에 서둘러 책을 펴 공부를 시작했지만, 너무 오랜만에 공부를 하는 탓인지, 내용 자체가 어려운 탓인지 이해가 잘 되지 않았고, 기본적인 내용도 기억.. 2021. 12. 29.
재귀 알고리즘의 기본, 재귀 알고리즘 분석 Preface 이번 장에선 재귀 알고리즘에 대해 공부했다. 재귀 알고리즘을 사용하면 코드를 보다 짧게 작성할 수 있다고 하는데, 나는 아직 재귀 알고리즘이 어떻게 작동하는 것인지 정확히 이해하지 못했다. 책에 수록되어 있는 그림을 보며 코드를 이해하려 해봐도 출력값을 예상할 수 없었다. 다음 장을 공부하기 전 모든 코드를 다시 한 번 살펴보며 완벽히 이해한 후 넘어갈 계획이다. 1. 재귀 알고리즘의 기본 - 재귀 : 어떠한 이벤트에서 자기 자신을 포함하고 다시 자기 자신을 사용하여 정의되는 경우 → 프로그램을 간결하고 효율성 좋게 작성할 수 있음 - 팩토리얼 코드 def factorial(n: int) -> int: if n > 0: return n * factorial(n - 1) else: retur.. 2021. 10. 25.
큐란? Preface 중간고사 이후 오랜만에 글을 업로드한다. 요즘엔 이런 저런 핑계를 대며 공부를 하지 않는 날이 많아진 것 같다. 저번 주만 해도 시험 공부를 한 뒤 한 두 시간 정도는 시간을 내 공부를 할 수 있었지만, 귀찮고 피곤하단 이유로 누워서 의미없는 시간을 보냈다. 매일 후회할 일을 하지 않고자 다짐해도 그게 말처럼 쉬운 일은 아닌 것 같다. 원하는 목표를 이루기 위해선 항상 초심을 잃지 말자. 이번 장에선 선입선출 자료구조인 큐에 대해 공부했는데, 코드 자체는 지난 번에 공부했던 스택과 크게 다른 부분이 없어 쉽게 이해하고 넘어갈 수 있었다. 또, 얼마 전까지만 해도 annotation과 enum의 사용이 헷갈리고 귀찮게 느껴졌지만, 여러 번 코드를 작성하다보니 나름 익숙해진 것 같다. - 큐(.. 2021. 10. 24.

티스토리툴바