Algorithm/알고리즘 공부노트24 함수형 프로그래밍에 대하여 0. 개요 - 언어와 상관없이, 알고리즘 공부를 하다 보면 내가 10줄로 짠 코드를 누군가는 3줄로 짜는 것을 보며 현타가 올 때가 많다. - 이 7줄의 차이는 언어에 대한 이해도의 차이에서 온다고 생각한다. - 최근 파이썬과 자바스크립트 같은 함수형 프로그래밍 언어가 주목을 받으면서, 파이썬을 파이썬답게 쓰자는 말이 많이 들린다. - 어떻게 해야 사용하는 언어답게, 그 언어에 최적화된 기술들을 이용하여 코드를 짤 수 있을까? - 그 시작은 언어에 대한 특성을 이해하는 것에서 시작된다고 생각하여 이번 포스팅을 준비했다. 1. 함수형 프로그래밍이란? - 함수형 프로그래밍은 절차 지향적 언어보다 시대적으로 앞서 등장한 언어의 형태다. - 함수형 언어는 수학적 사고방식을 필요로 하기에, 사람의 사고방식에 가까.. 2021. 12. 29. 파이썬 - packing/unpacking 1. Packing - packing은 여러개의 객체를 하나의 객체로 합쳐주는 기능이다. - packing에는 2가지가 존재한다. a) 위치인자(*) packing - print('a', 'b', 'c') - print 함수는 매개변수의 갯수에 대한 제약이 없다. 이것이 가능한 이유가 packing이다. - 즉, 함수의 인자(=매개변수)의 갯수를 유연하게 지정할 때 사용한다. - 위치인자(*)를 매개변수 앞에 붙이면 packing을 사용한다. - 위치인자를 사용하면 다수의 값들을 tuple로 관리한다. 예시 - 위치인자) def test_packing(*args): print(type(args)) print(args) test_packing(1,2,3,4,5) b) 키워드인자(**) packing - 키.. 2021. 12. 26. 알고리즘 개념 총정리 - 탐색 및 기타 1. 탐색 (Search) a) 너비우선탐색(Breadth First Search, BFS) - Graph의 모든 노드를 탐색하는 알고리즘으로, 완전탐색에 포함된다. - 동일한 level의 형제노드를 우선적으로 탐색하는 방법 - need_visit Queue와 visited Queue를 이용하여 방문할 노드와 방문한 노드의 정보를 관리한다. - Vertex와 Arc의 수에 따라 O(V + A)의 시간복잡도를 가진다. b) 깊이우선탐색(Deapth First Search, DFS) - Graph의 모든 노드를 탐색하는 알고리즘으로, 완전탐색에 포함된다. - 하나의 노드를 시작으로 자식노드를 순차적으로 말단노드까지 탐색한다. - 말단노드까지 탐색을 했다면, 시작노드의 위치로 돌아와 동일한 방법으로 다른 형제.. 2021. 12. 23. 알고리즘 개념 총정리 - 정렬 a) 버블 정렬(Bubble Sort) - 인접한 요소끼리 크기 비교를 하며 swap과정을 통해 정렬한다. - 더이상 swap이 발생하지 않는 상태까지 정렬과정을 반복한다. - O(n^2)의 시간복잡도를 가진다. b) 삽입 정렬(Insertion Sort) - 가장 좌측의 요소를 기준으로 다른 요소와 비교하며 swap과정을 통해 정렬한다. - 기준 요소보다 작은 요소들은 기준요소의 좌측에, 큰 요소들은 기준요소의 우측에 정리하는 과정을 반복한다. - O(n^2)의 시간복잡도를 가진다. c) 선택 정렬(Selection Sort) - 가장 좌측 요소의 위치를 포인터로, 포인터가 가리키는 요소보다 작은 요소를 찾아 swap하며 정렬한다. - swap이 한번 일어날 때마다, 포인터의 위치는 오른쪽으로 한칸씩 .. 2021. 12. 23. Return에 대하여 - 알고리즘을 공부하면서, 다른사람이 작성한 다양한 코드를 접하고 분석하게 된다. - 그러다 보니 내가 알고있다고 생각한 것들도 완전히 알지 못했다는 것을 깨닫게 되었다. - 최근에 이런 경험을 한 것이 Return이다. 1. Return의 기능 - return은 메소드를 구현할 때 굉장히 자주 사용되는 명령어다. - 단순히 함수를 종료하거나 값을 반환한다는 이해보다 한 단계 깊게 알아보자. a) Return은 함수를 종료하기만 하는걸까? - return은 함수를 종료한다. - 아무런 반환값 또는 함수 내부의 지역변수 없이 return만 덩그러니 사용되는 경우가 여기에 해당한다. - 그러나 생각해보면 return이 수행되고 난 후에, 다음 코드가 실행된다. - 즉, return은 함수를 종료하고나서 ma.. 2021. 11. 28. 파이썬 클래스와 self의 의미 1. Class 개념 클래스를 생성한다는 것은 새로운 데이터 타입을 만든다는 의미다. 위의 스크린샷을 살펴보자. 4라는 값을 test 라는 변수에 담았다. 4와 test의 type을 출력해보면 int 클래스 라는 것을 확인할 수 있다. 즉, int 클래스의 객체이고 int 자료형을 사용한다는 의미다. 그렇다면 간단하게 class를 만들어서 객체를 생성하여 해당 객체의 type을 출력해보자. 위의 스크린샷에서 확인할 수 있듯이, 클래스는 새로운 자료형을 나타낸다. 즉, 클래스를 만드는 것은 새로운 자료형을 생성하는 것이다. 2. Self 개념 파이썬에서 클래스를 만들고, 클래스 내부에 메소드를 선언할 때에는 반드시 self라는 변수가 첫번째로 들어가야 한다. 이는 다음과 같이 이해할 수 있다. person.. 2021. 11. 6. 12. String Match(KPM, Rabin-Karp, Palindrome) 0. 시작하기전에 - 한동안 알고리즘 공부를 하며 깨달은게 있다. - 알고리즘을 얼마나 외우고 있느냐는 코딩테스트에서는 중요하지 않다는 점이다. - 결국 이론적인 이해도와 지식에 대한 소화시간을 충분히 갖고, 이를 기반으로 응용적인 사고가 가능하냐는 부분이 가장 중요하다. - 그러므로 코드를 외우려 노력하지말고, 그 안의 규칙성과 논리를 이해하기 위해 더 시간을 투자하기를 바란다. 1. String Match - 문자열을 탐색하는 방법론이다. - 대표적으로 KMP 알고리즘과 Rolling Hash를 사용하여 구현한 Rabin Karp 알고리즘이 있다. - 일반적으로 String Match 알고리즘은 O(n)의 시간복잡도를 갖는다. a) 시간복잡도 - 문자열 탐색은 다음과 같은 과정을 거친다. string.. 2021. 10. 20. 11. Array(배열) - Radix Sort 0. 시작하기 전에 - Radix Sort는 Counting Sort를 기반하기 때문에, Counting Sort를 알아야 한다. - 다음 포스팅에서 Counting Sort에 대해 익히기를 바란다. https://devraphy.tistory.com/438 10. Array(배열) - Counting Sort 0. 시작하기 전에 - 지금까지 배운 알고리즘은 O(n^2) 또는 O(n log n)의 시간복잡도를 갖는다. ▶ O(n^2): bubble, insertion ▶ O(n log n): merge, quick - Counting Sort는 O(n + alpha)의 시간복잡도를.. devraphy.tistory.com 1. Radix Sort(기수 정렬) a) Radix Sort를 사용하는 이유 - .. 2021. 10. 8. 10. Array(배열) - Counting Sort 0. 시작하기 전에 - 지금까지 배운 알고리즘은 O(n^2) 또는 O(n log n)의 시간복잡도를 갖는다. ▶ O(n^2): bubble, insertion ▶ O(n log n): merge, quick - Counting Sort는 O(n + k)의 시간복잡도를 가진다. - Counting Sort를 이해하며 k의 의미가 무엇인지 알아보자. 1. Counting Sort(계수정렬) - Counting Sort는 주어진 array의 요소를 counting하여 정렬하는 알고리즘이다. a) Counting Sort의 정렬과정 2. 코드 구현 - 위에서 진행한 과정을 코드로 그대로 구현하면 Counting Sort 알고리즘이 완성된다. - 다음 코드를 확인해보자. from typing import List.. 2021. 10. 5. 이전 1 2 3 다음
