자료구조

투 포인터 (two pointer) 알고리즘이란?

투 포인터란? '투 포인터'라는 기법은 문자열 string 또는 배열 array 기반의 알고리즘 문제에서 자주 사용할 수 있는 효과적인 기법입니다. 구체적으로 투 포인터도 여러 가지 방식이 있지만, 대개는 시작점과 끝점 또는 왼쪽 포인터와 오른쪽 포인터 두 지점을 기준으로 하는 문제 풀이 전략으로 볼 수 있습니다. 알고리즘 문제를 풀 때, 일반적인 반복문 접근 또는 브루트 포스 방식을 활용하다 보면 타임아웃에 직면하게 되는 경우가 종종 있습니다. 투 포인터 방식을 활용하면 복잡도를 한단계 낮출 수 있습니다. ==> $O(N^k)$ --> $O(N^{k-1})$ 투 포인터는 크게 두가지 방법으로 응용할 수 있습니다. 앞쪽 첫번째에서 시작하는 포인터 & 뒤쪽 끝에서 시작하는 포인터 빠른 포인터가 느린 포인터..

[leetcode 42] Trapping Rain Water - hard

오늘은 리트코드(leetcode) 42번 문제 trapping rain water에 관해 풀어보겠습니다. (링크: https://leetcode.com/problems/trapping-rain-water/description/) 문제는 높이를 입력받아 비 온 뒤 얼마나 많은 물이 쌓일 수 있는지 계산을 요구하는 문제입니다. 이 문제는 높이와 너비 모든 공간을 차례대로 살펴보면서 풀어나간다면 $O(n^2)$만큼의 시간 복잡도로 풀이가 가능합니다. 하지만 시간 복잡도가 높기 때문에, 더 효율적인 풀이를 찾는 것이 권장됩니다. 풀이: 투 포인터 활용 투 포인터를 활용하면 $O(n)$의 시간 복잡도로 문제를 풀 수 있다고 생각했습니다. 우선 다음 그림을 보겠습니다. 위 그림에서 주목할 부분은 '가장 높은 막대..

[python] 등차수열과 등차수열의 합

알고리즘 및 코딩 테스트를 진행하다보면, 이따금 수학적 공식을 알고 있다면 생각보다 쉽게 풀리는 문제들이 있습니다. 수많은 공식들을 모두 외울 수도 없지만, 기본적인 내용은 짚고 넘어가면 도움이 될 수 있습니다. 그 중에서도 오늘은 등차수열에 관해 다뤄보려고 합니다. 등차수열의 기본 공식: n 번째 항 구하기 등차수열에서 n번째 항을 구하는 공식은 다음과 같습니다. $$ a_n = a_1 + (n-1)d $$ 여기서 각 기호는 다음을 의미합니다. $a_n$: $n$번째 항 $a_1$: 첫번째 항 $d$: 공차 $n$: 항의 순서 이 공식은 등차수열의 어느 항이든지 첫 번째 항과 그 항의 순서를 통해 계산할 수 있게 해줍니다. 등차수열의 기본 공식은 주로 수열의 특정 항을 찾을 때 사용되는데, 간단..

[python] stack 구현 (고정길이 스택 fixed stack, class 활용)

(본 포스팅은 Do It! 시리즈의 '자료구조와 함께 배우는 알고리즘 입문 - 파이썬편'을 참고하여 작성하였습니다.) 데이터를 임시 저장하는 기본 자료 구조는 대표적으로 두 가지가 있는데, 스택(stack)과 큐(queue)이다. 스택은 일반적으로 데이터 입력과 출력 순서가 후입선출(Last in First Out)인 것이 특징이다. 이 기능을 구현하기 위해서 우리가 생각해봐야할 부분은 어떤 것이 있을까? 크게 살펴보자면 첫째로, 데이터를 집어 넣는 push 기능 둘째로, 데이터를 꺼내는 pop 기능 셋째로, 스택의 길이를 알려주는 len 기능 넷째로, 스택이 비었는지 확인하는 기능 다섯번 째로, 스택이 가득 차 있는지 확인하는 기능 여섯번 째로, 특정 값이 스택 어디에 위치해있는지 확인하는 기능 일곱번..

[python] 함수 활용 시 매개변수가 뮤터블 vs 이뮤터블 일때..

파이썬에서는 매개변수에 실제 인수가 대입된다. 복사가 아니라는 점을 명심해야한다. 파이썬에서 인수 전달은 실제 인수인 객체에 대한 참조를 값으로 전달하여 매개변수에 대입되는 방식이다. 다른 프로그래밍 언어에서는 실제 인수의 값을 매개변수에 복사하는 값에 의한 호출(call by value)를 사용하거나, 실제 인수의 참조를 매개변수에 복사하여 매개변수가 실제 인수와 같아지는 참조에 의한 호출 (call by reference)를 사용한다. 하지만 python은 객체 참조에 의한 전달(call by object reference)를 활용하는데, 위 2가지 호출의 중간 방식으로 인지하면 된다. 따라서 함수 생성 시, 1. 인수가 immutable 일 때: 함수 안에서 매개변수의 값을 변경하면 다른 객체를 생..