Programming
-
[python]버블 정렬Programming/python 2019. 10. 20. 00:17
버블 정렬(Bubble sort)이란? 버블 정렬이란, 두 인접한 원소를 검사하여 정렬하는 방법이다. 거품 정렬이라고도 불리며 원소의 이동하는 모습이 거품이 수면으로 올라오는 듯한 것처럼 보이기 때문에 지어진 이름이다. 버블정렬의 특징 장점 구현이 간단하다. 단점 하나의 요소가 가장 왼쪽에서 가장 오른쪽으로 이동하려면 배열의 모든 다른 요소들과 교환해야하는 필요 이상의 교환이 생긴다 시간 복잡도 시간 복잡도가 O(n²)로 상당히 느린편이지만 코드가 단순하기 때문에 자주 사용된다. 코드 #버블 정렬 #리스트 a를 버블 정렬로 정렬함 def bubble_sort(a): n = len(a) for i in range(0,n-1): for j in range(n-1): if a[j] > a[j+1]: a[j],..
-
[python]퀵 정렬Programming/python 2019. 10. 18. 22:46
퀵 정렬(Quick Sort)이란? 퀵 정렬은 기준(Pivot)을 먼저 정하고 그 기준으로 두 개의 비균등한 크기로 분할하고 분할된 부분 리스트들을 기준과 비교해 정렬한 다음 정렬된 부분을 합하는 방법. 그룹을 둘로 나누어서 재귀 호출한다는 방식은 병합 정렬과 비슷하지만 그룹을 나눌 때 미리 기준과 비교해서 나눈다는 점이 다르다. 분할단계(divide): 입력 배열을 피벗을 기준으로 비균등하게 2개의 부분 배열(피벗을 중심으로 왼쪽은 피벗보다 작은 요소들을 배치하고, 오른쪽은 피벗보다 큰 요소를 배치)로 분할한다. 정복단계(Conquer): 부분 배열을 정렬한다. 배열 크기가 충분히 작지 않다면 재귀 호출을 이용해서 다시 분할 정복 방법 적용(재귀는 리스트가 1이하가 될 때까지 반복된다) 결합단계(Com..
-
[python]합병 정렬Programming/python 2019. 10. 18. 01:52
합병정렬(Merge sort)이란? 합병정렬 또는 병합정렬이라고도 부르며, 먼저 절반으로 분할하고 합치면서 정렬하는 방법. 존 폰 노이만이 제안한 방법이며, 분할 정복 알고리즘의 하나이다. 리스트 길이가 1이하이면 이미 정렬된 것으로 본고 그렇지 않은 경우에는 분할단계(divide): 정렬되지 않은 리스트를 타노스 손가락 튕기듯이 절반을 잘라 비슷한 크기의 두 부분 리스트로 나눈다. 마블 MCU로 생각하면 인피니트 워 단계 정복단계(conquer): 각 부분 리스트를 재귀적으로 합병 정렬을 이용해 정렬한다. 결합단계(combine): 두 부분 리스트를 다시 하나의 정렬된 리스트로 합병한다. 마블 MCU로 치면 앤드 게임에 해당한다. 오른쪽과 같이 [6,5,3,1,8,7,2,4]라는 정렬되지 않은 배열이 ..
-
관점 지향 프로그래밍 AOPProgramming 2019. 10. 17. 19:30
지난 포스팅에서 프로그래밍 패러다임인 객체 지향와 절차형 프로그래밍에 대해서 알아보았다. 그런데 스프링을 공부하다보면 튀어나오는 AOP, 즉 관점 지향 프로그래밍이라는 개념. 객체 지향을 알고있으니 뭔가 프로그래밍 패러다임이라는 것은 알고 있는데 정확히 관점 지향 프로그래밍은 명령형인지 선언형인지 그리고 무엇인지 도통 알 수가 없다. AOP의 개요 프로그래밍 언어에서 절차적은 프로시저를 통해, 그리고 OOP는 클래스를 통해서 분리된 관심과 개념들을 통해 모듈로 분해했다. 앞선 포스팅에서 OOP를 현대에 들어 수 많이 늘어나고 복잡해진 상호작용들과 대응하기 위해서 등장한 개념이라고 설명했다. 하지만 OOP를 적용한다고 할지라도 충분히 분리해 낼 수 없는 부분이 있다는 문제 제기에서 부터 AOP의 개념이 들..
-
객체 지향 프로그래밍이란 무엇인가Programming 2019. 10. 17. 01:45
프로그래밍 패러다임 프로그래밍 패러다임이란 프로그래머가 코드를 짤 때 어떤 관점을 가지고 짜느냐에 결정적인 역할을 한다. 가장 크게는 선언형과 명령형으로 나눌 수 있고, 이안에 우리가 중점적으로 알아볼 객체 지향과 절차 지향, 함수형 프로그래밍이 포함되어있다. 대략적으로 카테고리를 나누어본다면 다음과 같다. 명령형 프로그래밍 - 절차적 프로그래밍(PP) : C - 객체 지향 프로그래밍(OOP) :C++,JAVA,python 선언형 프로그래밍 - 함수형 프로그래밍 : SQL, HTML,Python 명령형 프로그래밍이란 프로그래밍의 상태와 상태를 변경시키는 구문의 관점에서 연산을 설명하는 방식이고, 선언형 프로그래밍은 어떤 방법으로 해야하는지 나타내기보다 무엇과 같은지를 설명하는 방식이다. 절차 지향 프로그..
-
[python]삽입 정렬Programming/python 2019. 10. 16. 01:39
삽입 정렬(Insertion sort)이란? 앞에 요소를 살펴보고 그 값보다 작은 지 큰 지를 비교해 적당한 위치에 삽입해서 정렬하는 방법. 리스트 중에 두 번째 요소를 key값으로 한다. 그 앞에 값과 키값을 비교한 뒤 작으면 그 앞, 크면 그 뒤에 넣는다. 그 다음 요소(세 번째)를 key값으로 한다. 그 앞에 값(두번째 요소)와 키 값을 비교한 뒤 작으면 앞 크면 그 뒤에 넣는다. 계속해서 반복한다. 직관적으로 이미지를 보면서 예를 들어보자면 다음과 같다. (a)옆에 [3,7,2,5,1,4]라는 배열이 있다. 가장 앞에 값인 3을 제외하고 두 번째 값인 7을 키 값으로 설정한다. 빨간색 박스는 key값이라는 뜻이다. 이 key값인 7은 3과 비교해서 더 큰 값이므로 3 뒤에 위치하게 된다. (b)다..
-
[python]선택 정렬Programming/python 2019. 10. 15. 00:16
선택 정렬(Selection sort)이란? 리스트 중에서 가장 작은 걸 선택한 뒤에 가장 앞으로 보내면서 정렬하는 방법. 리스트 중에 최소값을 찾는다. 그 값을 맨 앞에 값과 교체한다. 맨 앞의 값을 제외하고 다시 검색해서 최소값을 찾는다. 맨 앞의 값 뒤에 값과 최소값을 교체한다. 차례로 반복 직관적으로 애니메이션 이미지를 보면서 예를들어보자. 옆에 [8,5,2,6,9,3,1,4,0,7]이라는 배열이 있다. 가장 처음에 앞에서부터 찾아가며 최소값 0을 찾아내고 이를 맨 앞에 있는 0과 교환한다. [0,5,2,6,9,3,1,4,8,7] 그 다음에 0을 제외하고 검색을 시작하고 최소값 1을 찾아낸 뒤에 5와 1을 교환한다. [0,1,2,6,9,3,5,4,8,7] 그 다음에 0,1을 제외하고 검색을 시작하..
-
프레임워크와 라이브러리의 차이점Programming 2019. 10. 12. 02:00
프레임워크도 알고있고, 라이브러리도 알고있지만 이 둘의 차이점에 대해서는 잘 알지 못하고 넘어가는 경우가 많다. 단순히 API를 모은 게 라이브러리고 라이브러리가 모여서 프레임워크가 되는거 아니야? 라고 말할 수 있지만 사실 그렇게 쉽게 설명되지 않는 문제이다. 프레임워크를 설명할 때 등장하는 다른 여러 개념들이 있기 때문에 이 개념들과 함께 프레임워크를 알아보도록 하자. 프레임워크의 개요 프로그램 개발에 투입되는 개발자들이 늘어남에 따라서(특히 객체 지향 프로그래밍이 늘어남에 따라서) 다양성 또한 비례되어 늘어나고, 전체 시스템의 통합성, 일관성이 부족함을 느끼게 되었다. 그래서 개발자의 자유를 제한하는 대신에 일정한 테두리 안에서 일관되고 유지 보수를 쉽게 개발할 수 있는 환경인 프레임워크를 도입했다..