본문 바로가기

스터디IT🌼41

[ 파이썬 ] DFS - 깊이 우선 탐색 / BFS - 넓이 우선 탐색 (Feat. 음료수 얼려 먹기, 미로 탈출 ) DFS와 BFS는 그래프를 탐색하기 위한 가장 대표적인 알고리즘이다. 이번 글에서는 DFS와 BFS에 대해 정리해보고자 한다. 1. DFS - DFS ( Depth-First Search ) 는 깊이 우선탐색으로, 그래프에서 깊은 부분을 우선적으로 탐색하는 알고리즘이다. - Stack 자료 구조를 사용한다. ( LIFO - 먼저 들어온 것이 가장 늦게 나감 ) - 그래프 아래까지 내려갔다가 와서 위에것들이 빠져야하기에 STACK 자료구조 사용! - LIFO 자료구조를 갖고 있는 것이 컴퓨터의 재귀함수 처리 방식! - 스택을 사용한 DFS의 순서는 다음과 같다 1. 탐색 시작 노드를 스택에 삽입하고 방문 처리한다. 2. 스택의 최상단 노드에 방문하지 않은 인접 노드가 있으면 그 인접 노드를 스택에 넣고 방.. 2022. 2. 17.
[ 파이썬 ] 파이썬 자료형 별 시간 복잡도 ( BIG - O ) * 알고리즘 풀이에 있어 시간 복잡도를 고려해야하는 부분이 많다 * * 알고리즘 풀이에 도움이 될 만한 파이썬 주요 함수, 자료형 별 시간 복잡도에 대해 간단히 정리해보고자 한다 * List 연산 예시 Big - O 기타 Index list[i] O(1) 인덱스로 값 찾기 Store list[i] = 1 O(1) 인덱스로 데이터 저장 Length len(list) O(1) 리스트 길이 Append list.append(3) O(1) 리스트 뒤에 데이터 저장 Pop list.pop() O(1) list.pop(-1) 과 동일 Slice list[ a: b ] O( b-a ) list[:] -> O(N) Clear list.clear() O(1) list = [ ] Extend list.extend(..) .. 2022. 2. 7.
[ 파이썬 알고리즘 인터뷰 ] 일일 온도 문제1. 매일의 화씨온도 리스트 T를 입력받아서, 더 따뜻한 날씨를 위해서는 며칠을 더 기다려야 하는지를 출력하라. EX1_입력 ] T = [ 73,74,75,71,69,72,76,73 ] EX1_출력 ] [ 1,1,4,2,1,1,0,0 ] 해당 문제를 푸는 방법 ?! 1. 스택을 이용한 값 비교 1. 스택을 이용한 값 비교 def DailyTemperature(list): answer = [0] * len(list) stack = [] for i, cur in enumerate(list): while stack and cur > list[stack[-1]]: last = stack.pop() answer[last] = i-last stack.append(i) print(answer) DailyTempe.. 2022. 2. 6.
[ 파이썬 알고리즘 인터뷰 ] 중복 문자 제거 문제1. 중복된 문자를 제외하고 사전식 순서로 나열하라. EX1_입력 ] "bcabc" EX1_출력 ] "abc" EX2_입력 ] "cbacdcbc" EX2_출력 ] "acdb" EX3_입력 ] "ebcabc" EX3_출력 ] "eabc" EX4_입력 ] "ebcabce" EX4_출력 ] "abce" 해당 문제를 푸는 방법 ?! 1. 스택을 이용한 문자 제거 2. 스택과 Collection.Counter를 이용한 문자제거 1. 스택을 이용한 문자 제거 def removeDuplicateLetters(s:str)->str: d = { char : indx for indx, char in enumerate(s)} res = [] for indx, char in enumerate(s): if char not .. 2022. 2. 3.
[ 파이썬 알고리즘 인터뷰 ] 유효한 괄호 문제 1. 괄호로 입력된 값이 올바른지 판별하라. EX1_입력 ] ()[]{} EX1_출력 ] true 해당 문제를 푸는 방법?! - 스택 일치 여부 판별 ( 딕셔너리 테이블 사용 ) 1. 스택 일치 여부 판별 def isValid( s) : table ={ ')':'(', ']': '[', '}': '{', } stack = [] for char in s : if char not in table : # 키값응로 검색 stack.append(char) elif not stack or table[char]!= stack.pop(): #스택이 비었거나 닫는 괄호와 여는 괄호가 일치하지 않을 시 return False return len(stack)==0 #알맞은 입력일 경우 스택이 비어서 종료 print(i.. 2022. 2. 3.
[ 파이썬 알고리즘 인터뷰 ] 가장 긴 팰린드롬 부분 문자열 문제1. 가장 긴 팰린드롬 부분 문자열 Q. 가장 긴 팰린드롬 부분 문자열을 출력하라. EX1_입력 ] "babad" EX1_출력 ] "bab" 또는 "aba" EX2_입력 ] "cbbd" EX2_출력 ] "bb" 해당 문제를 푸는 아이디어?! - 슬라이딩 윈도우 기반 투 포인터! - 중앙을 중심으로 확장 아이디어 1. 슬라이딩 윈도우 기반 투 포인터! - 2칸, 3칸으로 구성된 투 포인터가 슬라이딩 윈도우 처럼 전진한다. bb 또는 bab 등 중심을 기준으로 앞뒤 문자열이 같기에 2,3칸으로 구성된 포인터를 사용하면 팰린드롬을 찾아낼 수 있다. 문자열이 끝날 때까지 포인터가 앞으로 전진해나가며 팰린드롬을 찾는다. 2칸짜리 포인터는 짝수용 팰린드롬을, 3칸 짜리 포인터는 홀수용 팰린드롬을 찾기위함이다. .. 2022. 1. 19.

티스토리툴바