Algorithm/자료구조와 함께 배우는 알고리즘20 정렬 알고리즘 (3) - 병합정렬, 힙정렬 지금까지 여러 검색 알고리즘을 배우며 그동안 배웠던 방법이 헷갈리기 시작했다. 그래서 지금까지 배웠던 내용을 다시 한 번 복습해봤다. 위 세가지 알고리즘은 간단하지만 비교적 좋지 못한 알고리즘이고 아래 알고리즘은 복잡하지만 효율적인 알고리즘이다. 버블정렬 : 두 이웃한 원소끼리 대소 비교 반복 단순 선택 정렬 : 배열의 가장 작은값을 0번 인덱스부터 채워나가는 것 단순 삽입 정렬 : 배열의 1번 인덱스를 기준으로 왼쪽의 (작은쪽) 값과 비교해나가며 맞는 자리를 찾아가는 방법 셸정렬 : 단순 삽입 정렬의 상위호환. 배열의 몇 칸 이라는 기준을 두어 값을 비교해 미리 어느정도 정렬을 해놓음 퀵정렬 : 피벗값을 기준으로 배열을 나누어 배열의 인덱스가 1개밖에 없을 때 까지 나눈 후 병합한다. 병합정렬 : 배열.. 2022. 8. 3. 정렬 알고리즘 (2) - 셸정렬, 퀵정렬 이번에 포스팅 할 내용도 정렬과 관련된 내용이다, 이전에 배웠던 알고리즘보다 더 성능이 뛰어나지만 그만큼 코드 구현이 어려웠다. 항상 드는 생각이지만 책을 보며 알고리즘의 작동 방식은 이해가 가지만 코드를 보며 해석하는건 너무 어려운것 같다. 그걸 내가 구현해내야한다는 것도 내가 넘어야 할 큰 산인것 같다. 셸정렬 셸정렬은 단순 삽입 정렬의 업그레이드 버전이라고 생각하면 쉽다. 단순 삽입 정렬은 옆 링크를 통해 알 수 있다. 여기 정렬 알고리즘 (1) - 버블정렬, 단순 선택/삽입 정렬 정렬 알고리즘은 정수의 배열을 오름/ 내림차순으로 정렬하기에 최적화 된 방법을 찾는 방식이다. 따라서 대소비교하는 수를 최소화 하는데에 초점을 두기 때문에 수식이 많아 코드를 이해하기 re-hwi.tistory.com 단.. 2022. 7. 30. 정렬 알고리즘 (1) - 버블정렬, 단순 선택/삽입 정렬 정렬 알고리즘은 정수의 배열을 오름/ 내림차순으로 정렬하기에 최적화 된 방법을 찾는 방식이다. 따라서 대소비교하는 수를 최소화 하는데에 초점을 두기 때문에 수식이 많아 코드를 이해하기 어려웠고 복잡했다. 유사한 방법의 알고리즘도 있어서 둘의 차이를 헷갈릴 때도 있었지만 그 속에서도 다른 점이 많았다. 정말 알고리즘이 늘기 위해선 문제를 많이 보고 직접 풀어보는 방법밖에는 없는 것 같다. 정렬 알고리즘 정렬이란 항목값의 대소에 따라 데이터 집합을 일정한 수서로 나열하는 작업이다. 값이 작은 데이터를 앞에 놓는것을 오름차순, 값이 큰 데이터를 앞에 놓는 것을 내림차순이라고 한다. 버블정렬 버블정렬은 이웃한 두 원소의 대소관계를 비교하여 교환을 반복하는 알고리즘이다. 총 대소구분을 하는 횟수는 (n - 1) .. 2022. 7. 28. 재귀 알고리즘 (2) - (하노이의 탑, 8퀸 문제) 하노이의 탑 하노이의 탑은 큰 원판이 작은 원판 위로 올 수 없다는 규칙을 가지고 있으며 모든 원판을 지정한 기둥으로 옮기면 되는 문제이다. 이 문제의 해결법은 아래 그림과 같이 가장 큰 원판을 제외한 모든 원판을 2번째 기둥에 놓고 가장 큰 원판을 목표 기둥에 놓으면 된다. 그렇게 된다면 중간 기둥에 큰 원판을 제외한 다른 원판을 쌓는 과정이 문제가 된다. 하지만 다시 생각해보면 이 과정도 중간 기둥을 목표 기둥이라 놓고 가장 큰 원판을 목표기둥(2번째 기둥) 에 놓기만 하면 된다. 이렇게 점차 줄여나가면 결국 하노이의 탑 문제를 풀 수 있는 것이다. 아래는 하노이의 탑 코드이다. def move (no, start, target): if no > 1: move(no - 1, start, 6 - sta.. 2022. 7. 27. 재귀 알고리즘 (1) 이번 단원은 정말 생각보다 많이 어려웠다. 어제 나름 집중도 잘하고 열심히 공부했다고 생각이 들었음에도 완벽히 이해하지 못해 오늘까지 시간이 필요했다. 재귀의 개념을 이해하더라도 코드를 어떻게 구현하는지, 실행과정이 어떻게 되는지를 알아야하기 때문에 상당한 시간이 필요했지만 앞서 먼저 공부한 친구의 도움을 빌려 어찌어찌 잘 해낸것 같다. 재귀 알고리즘 재귀란 어떠한 함수 또는 행동에서 자기 자신을 포함하고 다시 자기 자신을 사용하며 그로 인해 작업을 수행하는 것을 말한다. 하지만 자기 자신을 무한히 참조하기 때문에 무한 루프에 빠지지 않으려면 반드시 제어문이 필요하다. 일상생활 속에서 컴퓨터 화면이 자신의 화면을 출력한다면 그 출력물에서도 아래 사진과 같이 또 다른 자신의 화면을 호출할 것이다. 이것이 .. 2022. 7. 27. 스택과 큐 이번 단원은 OS 에서 배웠던 기초 지식이 있었던 탓인지 코드가 길어도 이해하기 쉬웠고, 코드를 읽으며 이해가 바로바로 되니까 재미가 붙었던 단원이다. 그랬던 탓인지 딱히 궁금증이 생기거나 막히는 부분 없이 무난하게 잘 공부했던 것 같다. 스택 스택이란 데이터를 임시저장하는 자료구조로서 후입선출 (LIFO : Last In First Out) 방식을 띄고있다. 한마디로 가장 먼저 들어간 데이터가 가장 마지막에 나온다는 뜻이다. 스택에서 데이터를 넣을 때 쓰는 용어는 푸시 (PUSH), 데이터를 꺼낼때는 팝 (POP) 이라고 한다. 스택을 구성하는 코드는 다음과 같다. from typing import Any class FixedStack: class Empty(Exception): # 비어있는 스택에 팝.. 2022. 7. 25. 이전 1 2 3 4 다음
