유진's 공부로그

_로 시작하는 변수 (getter, setter) (참고: https://www.daleseo.com/python-property/) : 외부에서 직접 접근이 어려운 변수 (클래스 인스턴스의 내부 데이터를 보호하기 위함) class Person: def __init__(self, first_name, last_name, age): self.first_name = first_name self.last_name = last_name self.set_age(age) def get_age(self): ## getter return self._age # 외부에서 직접 접근을 하지 못하고, getter를 통해서만 가능 def set_age(self, age): ## setter if age < 0: raise Va..

수식이 포함되어 있는 글입니다. 원활한 이해를 위해 데스크탑 모드로 전환하실 것을 권합니다. Gradient Descent First-order iterative optimization algorithm for finding a local minimum of a differentiable function cf.) first-order optimization first-order optimization 같은 경우에는 최소 한 번 미분한 값을 활용하여 optimization을 하는 경우를 의미하고, second-order optimization과 같은 경우에는 두 번 미분한 값 (or gradient)를 활용하여 최적화를 하는 경우를 의미함. 일반적으로, nth optimization 같은 경우에는 rank..

백준이 프로그래머스나 리트코드에 비해 짜증나는 부분은 인풋이 들어가는 형태도 고려해줘야 한다는 점이다. 오랜만에 백준으로 문제를 풀려니까 입력을 어떻게 할지부터가 난관이어서 입력 형식을 정리해보고자 한다. (언어는 파이썬) 백준 예제 입력은 위와 같이 들어올 때가 종종(아니 대부분) 있다. 그럼 \n으로 split을 하면 되지 않나? 하는데 왜인지 모르게 계속 오류가 났다. 공백 기준으로 해도 똑같은 에러가 계속 발생한다. (나 이전까지는 어떻게 해온 거지..머리에 든 게 없는 것을 겸허히 받아들이고 정리하기로 했다..) 위의 에러가 발생하는 이유는 애초에 input이라는 함수 자체가 \n이 들어오면 아예 입력을 마치는 것처럼 동작하기 때문이다. 따라서 여러 개의 입력값을 받기 위해서는 반복문을 활용해야..

https://leetcode.com/problems/daily-temperatures/ 문제 설명 매일의 화씨 온도 리스트 T를 입력받아서, 더 따뜻한 날씨가 될 때까지 며칠을 더 기다려야 하는지 리스트로 리턴하라. 문제 접근 및 풀이 [1st Try] - 투 포인터 1) 현재를 가리키는 포인터를 left, 미래를 가리키는 포인터를 right으로 설정. 2) 미래의 기온이 현재의 기온보다 높지 않다면 right 포인터를 한 칸 옮긴다. 3) 미래의 온도가 현재의 온도보다 높다면 결과가 되는 리스트에 right과 left의 차이를 append하고, left 포인터를 한 칸 이동, right 포인터를 left의 바로 다음 칸으로 이동시킨다. 4) left가 마지막에서 두번째 원소를 가리킬 때까지 반복한다...

https://leetcode.com/problems/remove-duplicate-letters/ 문제 설명 주어진 문자열에서 중복된 문자를 제외한 후 사전식 순서가 가장 작은 문자열을 리턴하라. (즉, 원래 문자열에서의 문자 순서를 완벽히 무시할 수는 없다는 뜻. 중복조합처럼 자리를 정해주는 식으로 생각하면 좀 더 수월할 듯하다) 문제 접근 및 풀이 [1st try] 1) 중복을 제거한다는 것은, 각 글자가 있을 자리를 정해준다는 것 → 원래 있던 자리를 무시하는 게 아님 2) 사전식 순서로 가장 작은 것을 리턴해야하는 것 → 쉽게 생각하면 가장 작은 글자 앞으로, 가장 큰 글자 뒤로 → 그러나 문제가 되는 점은 원래 문자열에서의 각 글자의 자리는 보존되어야 한다는 점 → 뚜렷한 자료구조는 생각나지 ..

https://leetcode.com/problems/valid-parentheses 문제 설명 괄호로 된 입력값이 올바른지 판별 (기본기 점검으로 좋은 문제) 문제 풀이 접근 1) 각 여는 괄호는 짝이 맞는 닫는 괄호가 있다 2) 닫는 괄호의 순서는 여는 괄호의 순서와 반대로 이루어져야 한다. 가장 마지막에 오는 여는 괄호는 가장 처음에 오는 닫는 괄호와 만나게 되고, 이런 패턴이 계속 반복된다. → 스택으로 접근 (LIFO) → 여는 괄호는 스택에 넣고, 닫는 괄호를 만나면 pop해서 짝이 맞는지 대조하는 방식 → 짝이 맞는지 대조하는 데에 편리한 자료구조는 딕셔너리 문제 풀이 class Solution: def isValid(self, s: str) -> bool: parentheses = { "(..

이진 탐색 (Binary Search) 이진탐색은 배열의 중앙값(median)을 조사하여 찾고자 하는 항목이 왼쪽 또는 오른쪽 부분 배열에 있는지를 알아내어 탐색의 범위를 대략 반으로 줄여가며 재귀적으로 진행하는 알고리즘이다(물론 반복으로도 구현 가능하다). 정렬된 배열에서의 탐색에 적합한 알고리즘이다(연결리스트에서는 부적합함. 가운데 지점을 빠르게 찾을 수 없기 때문이다). 시간복잡도는 $O(\log_2{n})$ 으로 빠른 수행시간을 보여준다. 이진 탐색 알고리즘 1) 재귀 구현 2) 반복 구현 투 포인터를 어떻게 활용하느냐의 차이로 투 포인터의 응용이라고 볼 수도 있을 듯하다. 이진 탐색 in Python bisect 모듈에 구현이 되어 있으며, bisect_left를 사용하면 된다. 원래는 정렬된 ..

삽입정렬 삽입정렬이란 정렬되어 있는 앞 부분에 새로운 레코드를 올바른 위치에 삽입하는 과정을 반복하며 정렬하는 알고리즘이다. 1) 삽입정렬 과정 초기 상태는 첫번째 원소를 정렬이 되어있다고 가정하고 시작함. 이후, 정렬된 부분 바로 뒷원소(a)와 정렬된 부분의 모든 원소를 비교하며 a의 제자리를 찾아 넣어줌. 예를 들어, 아래 그림에서의 2를 보면 1,3,5,8의 정렬된 부분 리스트와 비교를 시작하여 1보다 크고 3보다 작으므로 1과 3 사이에 삽입해주고, 탐색을 마친다. 2) 삽입정렬 알고리즘 이중 반복문 구조를 가진 알고리즘 1. 배열의 길이만큼 반복 2. key = 삽입할 원소 3. j는 배열의 오른쪽에서 왼쪽으로 이동한다. 4. 삽입할 원소를 정렬된 부분의 원소와 하나씩 비교하면서 한 칸씩 밀어냄..

스택(Stack) 스택은 후입선출(LIFO)로 처리되는 자료구조이다. 즉, 스택에 가장 마지막에 들어간 요소가 가장 처음으로 꺼내진다. Stack은 무엇인가가 쌓여있는 걸 지칭한다는 점을 생각해보면 가장 마지막에 쌓여진 것이 가장 처음으로 꺼내진다는 것의 개념은 쉽게 이해될 것이다. 스택은 흔히 연결리스트로 구현된다. 이 경우에 스택 선언을 위해 메모리 내의 연속된 공간을 할당할 필요가 없어지며, 실제로 스택 내의 요소 간 순서가 메모리 내의 물리적 순서와는 무관하게 될 것이다. 그러나 파이썬에서는 리스트가 스택으로 충분히 기능할 수 있기 때문에 연결리스트로 스택을 구현하지 않아도 된다. 스택의 주 연산은 삽입(push)와 제거(pop)이다. 삽입은 스택의 가장 마지막 자리에 요소가 추가되는 것이고, 제..

트라이 검색 트리의 일종으로 일반적으로 키가 문자열인, 동적 배열 혹은 연관 배열을 저장하는 데 사용되는 정렬된 트리 자료구조. 자연어 처리 분야에서 문자열 탐색을 위한 자료구조로 널리 쓰인다. 주로 문자열이 키인 경우가 많고, 이진 탐색 트리와 달리 트리의 어떤 노드도 그 노드 자체와 연관된 키는 저장하지 않는다. 대신 노드가 트리에서 차지하는 위치가 연관된 키를 정의한다. 즉, 키의 값은 자료 구조 전체에 분산된다. 트라이는 트리와 유사하지만, 우리가 주로 살펴본 이진 트리의 모습이 아닌 전형적인 다진 트리(m-ary Tree)의 형태를 띤다. 도식을 참고하면, 노드의 모든 자손은 노드에 연관된 문자열의 공통 접두사를 공유한다. 루트는 빈 문자열에 연관된다. (이 부분은 어떻게 구현하냐의 차이인 것 ..