개발 일기

📌 해시테이블이란? 키를 값에 매핑할 수 있는 구조인 연관 배열 추상 자료형(ADT)을 구현하는 자료구조로 시간 복잡도가 O(1)로 빠른 성능을 지니고 있다. 해싱: 해시 테이블을 인덱싱하기 위해 해시 함수를 사용하는 것 로드팩터 해시 테이블에 저장된 데이터 개수 n을 버킷의 개수 k로 나눈 것, 키들을 잘 분산해 주는지 효율성 측정에도 사용 로드 팩터 비율에 따라 해시 함수를 재작성해야 될지 해시 테이블의 크기를 조정해야 할지 결정한다. 자바 0.75 파이썬 0.66 루비 0.5 → 일반적으로 로드 팩터가 증가할수록 성능 감소, 로드 팩터를 넘어설 경우 동적 배열처럼 해시 테이블 공간 재할당 충돌 해결 방법 1. 개별 체이닝 충돌 발생 시 연결 리스트로 연결 보통 O(1)이지만 해시 충돌이 모두 발생하..

✅ 문제 - 일일 온도 현재 기온보다 더 높은 기온의 날을 며칠 더 기다려야 하는지 구하는 문제다. ✅ 풀이 def dailyTemperatures(self, temperatures: List[int]) -> List[int]: answer = [0]*len(temperatures) #[0,0,0,0] stack = [] #enumerate: 인덱스와 값의 쌍 생성 for i, cur in enumerate(temperatures): # stack에 값이 있고, 현재 온도가 스택에 담긴 인덱스에 해당하는 온도보다 높은 경우 while stack and cur > temperatures[stack[-1]]: last = stack.pop() answer[last] = i - last stack.append..

✅ 문제 문제 해석부터 해보자 1. 일반 프린터와 달리 중요도가 높은 순으로 문서 출력 2. 중요도가 높은 문서를 제일 앞에 배치 3. 앞에 있던 문서들은 순서대로 뒤에 배치 4. 주어진 인덱스에 위치한 문서의 출력 순서를 리턴함 그림을 그려서 이해해 보자면, 아래와 같다. 입출력 예시를 보면 첫 줄은 테스트 케이스 수로 3이다. 아래에는 두 줄씩 조건이 각 테스트케이스마다의 조건이 주어져있다. 예를 들어, 두번째 케이스는 아래와 같이 설명할 수 있다. ✅ 풀이 from collections import deque # 사용자에게 숫자 하나 입력 받아서 그 횟수만큼 테스트케이스 돌림(3) T = int(input()) for i in range(T): # 사용자가 입력한 수를 공백으로 나누어 N, M값 지..

✅ 문제 - 스택를 이용한 큐 구현 ✅ 풀이 💡 문제 이해하기 이 문제는 스택을 이용해서 큐를 구현해야 한다. 큐는 FIFO(First In First Out) 방식으로 먼저 삽입된 요소가 먼저 제거되며 쉽게 말해 선입선출의 개념이다. 요소를 가로로 놓고 봤을 때 삽입은 오른쪽으로, 제거는 왼쪽에서부터 된다. 스택은 LIFO(Last In First Out) 방식으로 삽입되는 방향은 큐와 같지만, pop연산에 있어서 방향이 반대다. MyQueue 클래스의 구현 내용 정의한 것을 보면 알고 있는 스택이 연산하는 방식과 조금 다르다. 1. push: 큐의 가장 끝에 요소 x를 삽입해야 한다. 2. pop, peek: 가장 첫 번째 자리 요소를 제거하거나 조회해야 한다. → 스택 방식으로 큐를 구현하여야 하기..

✅ 문제 - 큐를 이용한 스택 구현 ✅ 풀이 코드 💡 문제 이해하기 이 문제는 큐를 이용해서 스택을 구현해야 한다. 스택은 LIFO(Last In First Out) 방식으로, 요소를 가로로 놓고 봤을 때 사실상 마지막 요소만 가지고 연산을 한다. MyStack 클래스의 구현 내용 정의한 것을 보면 알고 있는 스택이 연산하는 방식과 조금 다르다. 1. push: 스택의 가장 첫 번째 자리에 요소 x를 삽입해야 한다. → stack은 요소 삽입 시 가장 마지막 자리에 요소가 삽입되므로 삽입 후 첫 번째 자리로 보내야 한다. 2. pop, top: 가장 첫 번째 자리 요소를 삭제하거나 반환해야 함 따라서 양 방향으로 연산이 가능하게끔 스택과 큐의 결합구조인 데크를 이용해서 이 문제를 풀어야 한다. class..

✅ 문제 💡 사용자에게 정수 하나를 입력받아 그 수만큼 문자열을 입력받고 괄호가 모두 쌍이 있는 경우 YES 출력(VPS에 해당), 괄호가 남는 경우 NO 출력 ✅ 첫 번째 시도 - 실패 # 파이썬에서 사용자로부터 정수를 입력받아 변수 T에 할당하는 코드 # 예를 들어 사용자가 3을 입력하면 T는 3이 됨 T = int(input()) # () 괄호 한 쌍 딕셔너리 방식으로 지정 # key ')', value '(' pair = {')': '('} for i in range(T): # T번 for문 돌림 stack = [] # 괄호를 담아둘 리스트 s=input() #T가 3이라면 문자열을 세번 입력받아 s에 할당 for char in s: # pair의 key값에 해당하는게 없을 경우(열림 괄호일 경우..

✅ 문제 - 유효한 괄호 이 문제는 s의 괄호 짝이 맞는 경우 true, 맞지 않는 경우 false 반환하는 문제이다. ✅ 풀이 코드 이 문제는 전형적인 스택 구조이다. 예를 들어, s가 {[]} 라면 [ 가 나중에 들어갔기 때문에 ] 가 먼저 나와야하고, 그다음에 처음 들어간 { 에 맞는 } 가 나와야 한다. 방법1) class Solution: def isValid(self, s: str) -> bool: # 괄호 짝 dict로 만들기(key-value) pair = { ')' : '(', '}' : '{', ']' : '[', } #opener를 담을 리스트 stack = [] opener = "({[" for item in s: # opener는 stack에 넣기 if item in opener:..

✅ 문제 - 세 수의 합💡 숫자로 이루어진 리스트의 값 3개를 더했을 때 0이 되는 세 수를 구하는 문제 ✅ 첫 번째 시도 - 런타임 초과class Solution: def threeSum(self, nums: List[int]) -> List[List[int]]: results = [] nums.sort() #i,j,k 세 수의 합 for i in range(len(nums)-2): # 중복값 제외 if i>0 and nums[i] == nums[i-1]: continue for j in range(i+1, len(nums)-1): if j > i+1 and nums[j] == nums[j-1]: continue for k in range(j+1, len(nums)): if k > j+1 and num..

✅ 문제 - 가장 긴 팰린드롬 부분 문자열 구하기💡 팰린드롬이란? 토마토 기러기 스위스처럼 앞으로 읽어도 거꾸로 읽어도 같은 문자열을 지닌 단어를 말한다. 주어진 문자열 s에서 앞뒤가 똑같은 문자열을 추출하여 가장 긴 것만 반환하는 것이 이 문제의 포인트이다. 주어진 문자열의 길이가 짝수인 경우 연달아 겹쳐있는 문자도 팰린드롬에 포함된다. ✅ 첫 번째 시도 - 실패class Solution: def longestPalindrome(self, s: str) -> str: #한 글자일 경우, s를 뒤집었을 때 s와 같은 경우 s 그대로 반환 if len(s) == 1 or s == s[::-1]: return s #팰린드롬 담을 리스트 선언 p_list = [] for i in range(len(s)): f..

✅ 문제 - 그룹 애너그램 💡 애너그램이란? 문자를 재배열하여 다른 단어로 바꾸는 것이다. 예를들어 eat의 경우 eat, ate, tea 등으로 바꿀 수 있다. 이 문제는 주어진 문자열을 이용하여 동일한 문자를 지닌 문자열들을 그룹핑해서 반환하여야 한다. ✅ 풀이 코드from typing import List import collections class Solution: def groupAnagrams(self, strs: List[str]) -> List[List[str]]: #기본적으로 빈 리스트를 값으로 가지는 딕셔너리 anagrams = collections.defaultdict(list) #str 리스트 요소에 대해 반복 #단어를 정렬, 해당 단어를 키로 하여 word를 추가함 for word..