Jun's TID

보통 어떤 알고리즘에서 최대 값을 계속해서 갱신하기 위해서 max = 0 과 같은 방법을 자주 사용한다. 이 경우 딱히 문제가 되는 경우가 없지만, input pool이 음수를 포함할 수 있거나 최대값이 아닌 최소값을 계속 갱신해야 하는 경우 문제는 조금 복잡해진다. 이럴 때 사용할 수 있는 것이 시스템이 가질 수 있는 가장 큰 or 작은 값을 가지도록 초기값을 선언해주는 것이다. 파이썬에서는 보통 두가지 방법을 이용하여 구현할 수 있다. # 첫번째 방법(sys 모듈 사용) mx = sys.maxsize # 시스템이 가질 수 있는 가장 큰 값 mn = -sys.maxsize # 시스템이 가질 수 있는 가장 작은 값 # 두번째 방법(float 사용, 이 경우 값은 무한대이다) mx = float('inf'..

제약 조건이 없다면 미리 값들을 모두 곱한 다음에 이터레이터가 되는 값을 나눠서 간단하게 구할 수 있지만... 제약조건이 있기 때문에 시간 복잡도를 맞추기 위해서는 이터레이터가 되는 값의 왼쪽을 모두 곱한 결과에 오른쪽 값을 모두 곱한 값을 곱해줘서 구해볼 수 있다. (이것도 한참 고민하다가 모범 답안을 본 건데, 진짜 미친 풀이인 거 같다...) from typing import List def multiply(nums_list: List[int]) -> List[int]: result = [] left_p = 1 right_p = 1 # 이터레이터 기준 왼쪽 값들의 곱을 저장 for i in range(0, len(nums_list)): result.append(left_p) left_p *= num..

포인터를 정해놓고 리스트 인덱스를 옮겨가며, 연산 후 비교하는 로직을 구성하면 쉽게 풀 수 있으나, 문제는 세 수의 합이기 때문에 자칫 삼중 for문을 사용하는 불상사가 발생할 수 도 있다. 이 문제 역시 두 개의 포인터를 사용하여 쉽게 풀이가 가능하다. 1 씩 증가하는 리스트 인덱스 i를 만들어 놓은 뒤, i 뒤쪽의 나머지 배열의 양 끝을 left와 right로 나눈다. 이때, i, left, right 위치의 값들을 더하여 0과 비교하고, 0보다 작다면 right를 감소, 크다면 left를 증가시키는 방식으로 풀이할 수 있다. from typing import List def sum_of_three(nums_list: List[int]) -> List[List[int]]: nums_list.sort(..

리스트를 사용하는 조금 난이도 있는 문제를 가지고 왔다. 벽들의 높이를 리스트로 입력받아, 빗물이 쌓일 수 있는 면적을 구하는 문제이다. 처음에는 한개의 포인터로, 더 높은 벽을 만날 때마다 포인터를 높은 벽의 높이로 갱신하며, 이전 포인터 까지의 격차를 더하여 푸려고 계획했다. 그러나, 포인터를 한개만 사용하면, 가장 높은 벽(예시에서는 3)을 만난 뒤에는 포인터를 갱신할 수 없는 문제가 발생하고, 이 문제를 해결하려면 꽤나 복잡한 로직이 동반된다. 그래서, 가장 높은 벽을 기준으로 양 끝, 두개의 포인터를 이용하여 풀이를 작성했다. 1. 두개의 포인터를 이용하여 풀이 from typing import List def trap(rain: List[int]) -> int: sum = 0 left = 0 ..

선형 자료구조를 다루는 가장 기초적인 문제로, 리트 코드의 1번 문제라서 한번 가져와 봤다. 문제는 단순 비교하여 값을 리턴한다고 구성하면 아마 초등학생도 풀 수 있는 정도의 난이도의 문제이지만, 의외로 최적화할 수 있는 방법이 많아서 다뤄보려고 한다. 1. 무차별 대입 방식 from typing import List def twoSum(nums: List[int], target: int) -> List[int]: for i in range(len(nums)): for j in range(i+1, len(nums)): if nums[i] + nums[j] == target: return [i, j] if __name__ == '__main__': nums = [2, 5, 7, 9] target = 9 p..

단순 문자열 조작 파트의 마지막 문제이다. 입력으로 어떤 문자열이 주어졌을 때, 해당 문자열에서 가장 긴 부분 팰린드롬을 찾으라는 문제이다. 입출력 예제는 다음과 같다. 문제는 두개의 포인터가 중앙을 중심으로 확장하는 형태로 풀 수 있다. 두개의 포인터는 처음엔 문자열 2자리, 3자리로 작은 규모로 시작하여 팰린드롬을 발견했을 때, 중앙을 중심으로 이를 확장하는 방식이다. def longestPalindrome(s: str) -> str: #팰린드롬 판별 및 투 포인터 확장 def expand(left: int, right: int) -> str: while left >= 0 and right < len(s) and s[left] == s[right]: left -= 1 right += 1 return ..

Python의 Thread도 자바와 동일하게 동시에 여러 함수나 프로그램을 실행할 수 있도록 해주며, 이는 Python을 활용한 대부분의 응용 프로그램에서 유용하게 사용이 가능하다. 파이썬에서 멀티 스레딩이나 타이머 기능을 사용하기 위해서는 우선 threading 모듈을 import 해줘야한다. 바로 예제를 하나 보도록 하자 import threading def count(start, end): for i in range(start,end): print(i) thread = threading.Thread(target=count, args=(1, 10)) thread.start() print('hey! my name is main') 위와 같이 간단한 스레딩 예제 코드를 적어봤다. 실행해보면, 이렇게, 메..

문제: 금지된 단어를 제외한 가장 흔하게 등장하는 단어를 출력하라. 대소문자를 구분하지 않으며, 구두점 또한 무시한다. 풀이는 리스트 컴프리헨션과 Counter를 이용한다. 그렇게 어려운 문제는 아니다. 정규 표현식을 이용하여 단어가 아닌 모든 문자를 공백으로 치환한 뒤에 banned 리스트 내에 있는 단어를 제외한 단어의 리스트를 따로 만들어 주고, 그 개수를 세주기만 하면 끝난다. import collections import re from typing import List def mostCommonWord(paragraph: str, banned: List[str]) -> str: words = [word for word in re.sub('[^\w]', ' ', paragraph).lower()...

그냥 기초를 짚고 넘어가자는 의미에서 아주 간단한, 문자열을 뒤집어서 리턴하는 함수를 작성해보려고 한다. 1) 투 포인터를 이용 from typing import List def reverseString(s: List[str]): left = 0 right = len(s) - 1 temp = 0 while left < right: temp = s[left] s[left] = s[right] s[right] = temp left += 1 right -= 1 if __name__ == '__main__': s = ["1", "2", "3", "4"] reverseString(s) print(s) 혹은 temp를 사용하지 않고도 다음과 같이 작성할 수 있다. (파이썬은 진짜 미친 거 같다) from typin..

문자열 조작에 있어서 아주 편리하게 사용할 수 있는 정규표현식에 대하여 알아보자. 정규표현식은 반드시 typing의 re 모듈을 import 해야 사용할 수 있다. 1. 메타 문자 메타 문자는 보통 어떤 문자열 안에 와일드 문자로써 사용되는 경우가 많기 때문에 백슬레시와 같은 문자를 사용할 때는 반드시 백슬레시를 한번 더 사용하여 이스케이프 처리를 해야한다. 1) [ ] [ ] 내부 문자열과 매치되는 것 import re test = re.compile('[abc]') print(test.findall('a abc ccc aaa bbb')) >>> ['a', 'a', 'b', 'c', 'c', 'c', 'c', 'a', 'a', 'a', 'b', 'b', 'b'] 또한 [] 를 이용하여 특정 패턴을 모두..