pythaac의 개발노트

이 글은 "파이썬 알고리즘 인터뷰 (박상길 지음)"을 읽고 주관적으로 요약한 글입니다. 문제 정의 주식 가격이 시간순으로 주어질 때 최대 이익 출력 책에서 구현된 코드 from typing import List class Solution: def maxProfit(self, prices: List[int]) -> int: # 0보다 크면 무조건 합산 return sum(max(prices[i + 1] - prices[i], 0) for i in range(len(prices) - 1)) 기억해야할 기법 "그리디 알고리즘으로 접근해야한다"는 힌트를 어디서 얻을 수 있을까 문제를 잘 해석하면 모든 이익의 합산이다 sell & buy를 동시에 할 수 있다는 것을 캐치하면 쉬운 문제였다 나는 나중에 팔았을 때 ..

이 글은 "파이썬 알고리즘 인터뷰 (박상길 지음)"을 읽고 주관적으로 요약한 글입니다. 요약 글로벌 최적을 찾기 위해 각 단계에서 로컬 최적의 선택을 하는 휴리스틱 문제 해결 알고리즘 (코딩 테스트에서의 정의를 의미하는듯? -> 항상 글로벌 최적을 찾기는 어려울 듯) 그리디 알고리즘 드물게 최적해를 보장하는 경우도 있음 보통 주어진 시간 내에 그런대로 괜찮은 해를 찾는 것을 목표로 삼음 최적해를 찾을 수 있는 두 가지 조건 탐욕 선택 속성 (Greedy Choice Property) - 앞의 선택이 이후 선택에 영향을 주지 않음 - 즉, 문제 해결 과정 중 substructure마다 독립적인 문제 해결 최적 부분 구조 (Optimal Substructure) - 문제의 최적 해결 방법이 부분 문제에 대한..

이 글은 "Java의 정석 (남궁 성 지음)"을 읽고 주관적으로 요약한 글입니다. 1. 다형성 1) 다형성 다형성 상속과 함께 객체지향개념의 중요한 특징 중 하나 상속과 깊은 관계 정의 여러 가지 형태를 가질 수 있는 능력 한 타입의 참조 변수로 여러 타입의 객체를 참조할 수 있도록 함으로써 다형성을 프로그램적으로 구현 - 조상클래스 타입의 참조변수로 자손 클래스의 인스턴스를 참조할 수 있음 조건 참조변수의 타입에 따라 사용할 수 있는 멤버가 달라짐 참조변수가 사용할 수 있는 멤버는 인스턴스의 멤버 수보다 같거나 적어야 함 - 즉, super 클래스만 sub 클래스를 참조 가능 2) 참조변수와 인스턴스의 타입 불일치 참조변수의 형변환 서로 상속관계에 있는 클래스만 사용 가능 자료형은 작은 타입이 큰 타입..

이 글은 "쉽게 배우는 데이터 통신과 컴퓨터 네트워크 (박기현 지음)"을 읽고 주관적으로 요약한 글입니다. ※ 요약 MAC 계층 WAN 환경과 달리 LAN 환경에서는 데이터링크 계층의 기능을 나누어 처리 LLC 계층 (Logical Link Control) OSI 7계층 모델에서 정의한 데이터링크 계층의 기본 기능 MAC 계층 (Medium Access Control) 물리적인 전송 선로의 특징과 매체간의 연결 방식에 따른 제어 부분 물리적인 특성을 반영하므로 LAN 종류에 따라 특성이 구분됨 LAN 환경에 따라 종류가 다양하며, 대표적으로 공유 버스 방식의 이더넷과 링 구조 방식의 토큰 링이 대표적 IEEE 802 시리즈 국제 표준화 단체인 IEEE에서 데이터링크 계층과 관련된 다양한 LAN 표준안 연..

이 글은 "쉽게 배우는 데이터 통신과 컴퓨터 네트워크 (박기현 지음)"을 읽고 주관적으로 요약한 글입니다. ※ 요약 전송과 교환 전송 - 물리 매체에 의해 일대일로 직접 연결된 두 시스템간의 신뢰성 있는 데이터 전송 - 라우팅이 포함되지 않음 교환 - 전달 경로가 둘 이상일 때 라우터에서 데이터를 전달하는 방향을 선택하는 기능 - 데이터를 올바른 경로로 전달해줌 전송 방식의 종류 네트워크에 연결된 호스트의 지리적 분포에 따른 구분 방식 LAN MAN WAN 데이터 전송/교환 기술에 따른 네트워크 분류 방식 점대점 방식 - 송신 호스트가 중개 호스트와 일대일로 연결되어 다른 호스트에는 데이터가 전달되지 않는 구성 - 최종 목적지 호스트까지 인접 호스트에 전송하는 과정이 단계적으로 반복됨 - 성능면에서 유리..

이 글은 "파이썬 알고리즘 인터뷰 (박상길 지음)"을 읽고 주관적으로 요약한 글입니다. 문제 정의 문자열 s에 대해 k개를 변경하여 만들 수 있는 가장 긴 반복문자열의 길이 출력 책에서 구현된 코드 class Solution: def characterReplacement(self, s: str, k: int) -> int: left = right = 0 counts = collections.Counter() for right in range(1, len(s) + 1): counts[s[right - 1]] += 1 # 가장 흔하게 등장하는 문자 탐색 max_char_n = counts.most_common(1)[0][1] # k 초과시 왼쪽 포인터 이동 if right - left - max_char_n..

이 글은 "파이썬 알고리즘 인터뷰 (박상길 지음)"을 읽고 주관적으로 요약한 글입니다. 문제 정의 t의 모든 문자, 개수가 포함된 s의 최소 윈도우 출력 책에서 구현된 코드 import collections class Solution: def minWindow(self, s: str, t: str) -> str: need = collections.Counter(t) missing = len(t) left = start = end = 0 # 오른쪽 포인터 이동 for right, char in enumerate(s, 1): missing -= need[char] > 0 need[char] -= 1 # 필요 문자가 0이면 왼쪽 포인터 이동 판단 if missing == 0: while left < right..

이 글은 "파이썬 알고리즘 인터뷰 (박상길 지음)"을 읽고 주관적으로 요약한 글입니다. 문제 정의 k개의 슬라이드마다 최대값을 담아 출력 책에서 구현된 코드 # 테스트케이스 변경으로 현재 책의 방식으로 통과되지 않음 (책에도 이슈관련 내용이 적혀있음) # github에 다른 분이 작성하신 수정된 방식 from collections import deque from typing import List class Solution: def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]: deq, ans = deque(), [] for i in range(len(nums)): # 앞에서부터 out of window -> 제거 if deq and i-de..

이 글은 "파이썬 알고리즘 인터뷰 (박상길 지음)"을 읽고 주관적으로 요약한 글입니다. 슬라이딩 윈도우 고정 사이즈의 윈도우가 이동하면서 윈도우 내에 있는 데이터를 이용하는 문제를 풀이하는 알고리즘 네트워크에 사용되던 용어 (MAC 계층에서 본 적 있음) 알고리즘 문제 풀이에 매우 유용하게 사용되는 중요한 기법 투포인터와의 차이점 고정 사이즈 윈도우를 사용함 정렬 여부에 관계없이 활용 좌->우로만 이동

이 글은 "파이썬 알고리즘 인터뷰 (박상길 지음)"을 읽고 주관적으로 요약한 글입니다. 문제 정의 unsigned int 입력의 1비트 개수 출력 책에서 구현된 코드 # 문자열 사용 class Solution: def hammingWeight(self, n: int) -> int: return bin(n).count('1') # 문자열 없이 구현 class Solution: def hammingWeight(self, n: int) -> int: count = 0 while n: # 1을 뺀 값과 AND 연산 횟수 측정 n &= n - 1 count += 1 return count 기억해야할 기법 내가 구현한 코드 # 문자열 사용 class Solution: def hammingWeight(self, n:..