본문 바로가기

Algorithm120

LeetCode 53(Maximum Subarray, java) 0. 문제 https://leetcode.com/problems/maximum-subarray/ Maximum Subarray - LeetCode Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview. leetcode.com 1. 문제 설명 - 위의 문제의 핵심은 연속적인 배열 요소의 합 중에서 가장 큰 값을 찾는 것이다. - 이 문제에서 생각해야 할 것은 어떻게 연속적인 배열의 시작 요소를 어떻게 찾을 것이냐는 것이다. - 다음 예시를 보자. nums = [-2,1,-3,4,-1,2,1,-5,4] - 위의 .. 2022. 4. 11.
LeetCode 217(Contains Duplicate, java) 0. 문제 https://leetcode.com/problems/contains-duplicate/ Contains Duplicate - LeetCode Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview. leetcode.com 1. 문제 설명 - 이 문제의 핵심은 배열 요소의 중복 유무를 검사하는 것이다. - 배열 요소의 중복 검사를 위해서는 for문을 이용해 배열의 요소를 HashSet에 삽입한다. - HashSet.add() 메서드는 boolean을 반환하기 때문에, 해당 메서드가 false를 반환하.. 2022. 4. 11.
재귀 함수의 개념 및 문제 접근방식 0. 개요 - 최근 Tree 문제를 풀기 시작하면서 재귀 함수를 사용한 풀이를 많이 접했다. - 재귀 함수(= Recursion)를 사용하면 연산 속도도 빠르고 작성하는 코드 또한 간결해진다. - 그래서 Recursion을 제대로 알고 사용하고 싶지만, 감이 잡힐 것 같으면서도 잡히지 않는다. - 이와 같은 이유로 Recursion을 정복하고 싶다는 생각에 이번 포스팅을 작성한다. - 나와 같이 Recursion에 어려움을 겪는 분들에게 도움이 되기를 바란다. 1. Recursion 이란? - Recursion은 함수 내부에서 자기 자신을 다시 호출하는 형태를 가진 함수를 말한다. 2. 재귀 함수 작성 규칙 - 재귀 함수를 작성할 때 지켜야 하는 2가지 규칙이 있다. a) Base case(반복을 멈추는.. 2022. 3. 11.
함수형 프로그래밍에 대하여 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.

티스토리툴바