Dev/Algorithm (5) 썸네일형 리스트형 [Algorithm] 선택, 삽입, 버블 정렬 본 포스팅에서는 선택, 삽입 버블 정렬에 대한 포스팅입니다. 구현 언어는 Python입니다. 이 세 가지 정렬 방식은 다른 알고리즘에 비해 성능이 떨어지지만 구현이 쉽고 코드 읽기가 쉽다는 장점이 있습니다. (선택과 버블 정렬은 데이터의 상태와 관계없이 O(n²)의 시간 복잡도를 가지고 삽입 정렬은 데이터의 상태에 따라 O(n)의 이상적인 시간 복잡도를 가지지만 최악의 경우 O(n²)의 시간 복잡도를 갖는다고 합니다. 우선 본 포스팅을 위해 위 3가지 정렬 기능을 하나의 스크립트로 미리 작성해두었습니다. import copy class Sorts: def __init__(self, array): self.array = array #결과 출력용 함수 def print_result(self, name, ar.. [Algorithm] 에라토스테네스의 체 저는 학창 시절 배웠던 교과목 중 제일 흥미를 가지지 못했던 과목이 수학입니다. 성적도 다른 과목에 비해 제일 낮았고 소위 말하는 수포자였죠. 그런 와중에 프로그래머를 업으로 시작하고 현재에 이르러서 수학적 지식의 필요성을 느껴 뒤늦게 다시 수학책을 펼쳐보고 있습니다. (중학교 수학 지식 조차 잊어버려 지금은 상당히 애를 먹고 있습니다.) 공부하던 중 에라토스테네스의 체라는 소수를 걸러내는 알고리즘을 알게 되었습니다. 소수란 1과 자기 자신 외에 다른 약수가 없는 수를 뜻합니다. 이를 걸러내는 방법으로는 에라토스테네스의 체가 흔히 쓰인다고 합니다. 에라토스테네스의 체는 여러 숫자들 중 체로 치듯 걸러서 소수만 남기는 방법으로 과정은 아래와 같습니다. 1. 찾을 범위까지의 수를 나열하고, 소수가 아닌 1을.. [Algorithm] Binary Search(이진 탐색) 이번 포스팅은 Binary Search(이진 탐색)에 대한 기록입니다. 이진 탐색 알고리즘은 배열과 Target을 가지고 특정 값의 위치를 찾는 알고리즘입니다. 주어진 배열의 시작점, 끝점을 기준으로 정 가운데 값과 Target 값을 비교하며 같은 값이 나올 때까지 시작점, 끝점의 범위를 대폭 좁혀가며 Target의 위치값을 찾는 것이 이 알고리즘의 핵심입니다. 사람이 사전에서 특정 단어를 찾기 위해 앞 뒤 페이지를 뒤지는 것과 유사한 원리입니다. 이 과정을 그림으로 표현한 것이 상단에 있는 이미지입니다. 이 알고리즘을 적용하기 위해서는 주어지는 값이 반드시 오름차순 정렬된 상태여만 합니다. 따라서 정렬되지 않은 데이터 묶음에 대해서는 적용하기 어려운 알고리즘입니다. 아래의 코드는 Python으로 작성된.. [Algorithm] 정렬 - 가장 큰 수 programmers에 등록되어있는 정렬 - 가장 큰 수 구하기 알고리즘에 대한 풀이입니다. 개인적인 공부를 위해 작성하는 개인적인 해석으로 경우에 따라 틀린 해석일 수도 있음을 상술합니다. 알고리즘 코딩 테스트는 간편하고 빠르게 구현할 수 있는 언어인 파이썬으로 응시하는 경향이 강하다고 합니다. 따라서 알고리즘 포스팅 또한 파이썬을 기준으로 풀어보도록 하겠습니다. 코드 링크는 아래 첨부합니다. https://programmers.co.kr/learn/courses/30/lessons/42746 본격적인 포스팅을 하기에 앞서 일러두자면, 후술 할 설명들은 최대한 자세하게 코드의 흐름을 설명하고자 하였으므로, 숙달된 분들에게는 불필요한 서술이 많습니다. 만약 코드 자체만으로 분석이 가능하신 분들은 위에서 .. [Algorithm] 정렬 - K번째 수 programmers에 등록되어있는 정렬 - K번째 수 구하기 알고리즘에 대한 풀이입니다. 개인적인 공부를 위해 작성하는 개인적인 해석으로 경우에 따라 틀린 해석일 수도 있음을 상술합니다. 알고리즘 코딩 테스트는 간편하고 빠르게 구현할 수 있는 언어인 파이썬으로 응시하는 경향이 강하다고 합니다. 따라서 알고리즘 포스팅 또한 파이썬을 기준으로 풀어보도록 하겠습니다. 코드 링크는 아래 첨부합니다. https://programmers.co.kr/learn/courses/30/lessons/42748 본격적인 포스팅을 하기에 앞서 일러두자면, 후술할 설명들은 최대한 자세하게 코드의 흐름을 설명하고자 하였으므로, 숙달된 분들에게는 불필요한 서술이 많습니다. 만약 코드 자체만으로 분석이 가능하신 분들은 위에서 두 .. 이전 1 다음
