나만의 개발 블로그

🙆‍♂️ 후위표현식으로 변환하기 """ 스택 클래스 Stack def emt : 스택에 값이 없다면 True를 반환 있다면 False를 반환 def size : 스택의 현재 길이를 반환 def clear : 스택 값을 초기화 def push : 입력 요소 ch를 스택에 입력 def pop : 스택의 최상단 값을 삭제 def peek : 스택의 최상단 값 반환 def disply : 스택의 상태를 출력 """ class Stack: def __init__(self): self.stack=[] def emt(self): return len(self.stack)==0 def size(self): return len(self.stack) def clear(self): self.stack=[] def push(s..

🙆‍♂️ 괄호 검사 알고리즘 """ 괄호 검사 알고리즘 """ def checkB(string): stack = [] for i in string: if i in ['(','{','[']: stack.append(i) elif i in [')','}',']']: if len(stack) == 0: return "Wrong String!" else: if (( stack[-1] == '(' and i==')' or stack[-1] == '{' and i=='}' or stack[-1] == '[' and i==']' )): stack.pop(-1) else: return "Wrong String!" if len(stack) != 0: return "Wrong String!" else: return "Go..

🙆‍♂️스택 """ 스택 클래스 Stack def emt : 스택에 값이 없다면 True를 반환 있다면 False를 반환 def size : 스택의 현재 길이를 반환 def clear : 스택 값을 초기화 def push : 입력 요소 ch를 스택에 입력 def pop : 스택의 최상단 값을 삭제 def peek : 스택의 최상단 값 반환 def disply : 스택의 상태를 출력 """ class Stack: def __init__(self): self.stack=[] def emt(self): return len(self.stack)==0 def size(self): return len(self.stack) def clear(self): self.stack=[] def push(self,ch): se..

🙆‍♂️ List class ArrayList: def __init__(self): self.items=[] #O(n) def insert(self,pos,elem): self.items.insert(pos,elem) #O(n) def delete(self, pos): self.items.pop(pos) def isEmpty(self): return self.size == 0 #O(1) def getEntry(self,pos): return self.items[pos] def size(self): return len(self.items) def clear(self): self.items=[] def find(self,item): return self.items.index(item) def replace(..

🙆‍♂️Stack First in Last out인 자료구조 입니다. 데이터가 쌓여져 가는 구조인데 PUSH라는 명령어로 데이터를 Stack의 가장 위에 올리고 POP이라는 명령어로 Stack의 가장 위의 명령어를 뺍니다. TOP이라는 명령어는 가장 위의 명령어에 접근합니다. 코딩테스트에서는 배열을 사용하여 스택이라고 가정하여 접근합니다. 🙋‍♂️문제 🚀 valid parentheses 괄호 열리고 닫힌 것을 구분하는 문제들은 stack 문제로 보고 풀 수 있습니다. PUSH를 해서 괄호를 열어주고 POP을 해서 매칭이되면 괄호를 닫아줍니다. 매칭이 안되면 invalid하다는 것을 출력하는 것입니다. >관련 문제

🙆‍♂️계수 정렬 주어진 배열의 값 범위가 작은 경우 빠른 속도로 정렬하는 알고리즘 입니다. 원소의 개수와 원소 최대 값이 수행시간에 영향을 줍니다. 🙋‍♂️방식 arr = [4,0,6,2,0,6] 이런 배열을 정렬할 때 🚀count 배열 값 2 0 1 0 1 0 2 인덱스 0 1 2 3 4 5 6 먼저 배열의 요소들을 카운팅을 하고 각 인덱스에 카운팅 값들을 갖는 count 배열을 만듭니다. count 배열을 만들 때 0,2,4,6만 있으니 이에 대한 수만 세는 것이 아니라 가장 작은 수(0)부터 가장 큰 수(6)까지의 수를 전부 계수합니다. 🚀누적 count 배열 값 2 2 3 3 4 4 6 인덱스 0 1 2 3 4 5 6 그리고 누적 카운트 배열을 만듭니다. 🚀최종 index 배열 값 1 1 2 2..

🙆‍♂️병합 정렬 병합정렬은 분활하고 정렬하고 합병하는 그런 정렬입니다. 🙋‍♂️방식 먼저 이렇게 배열이 있따면 배열의 길이가 1이 될 때 까지 나눕니다. 그리고 정렬과 합병을 반복하면 됩니다. 시간 복잡도는 O(n log n) 입니다. def merge(arr): if len(arr) == 1: return arr #####나누는 구간##### middle = len(arr)//2 left_arr = arr[:middle] right_arr = arr[middle:] leftArrSort = merge(left_arr) rightArrSort = merge(right_arr) leftIdx = 0 rightIdx = 0 #####합치는 구간##### sortArr = [] while leftIdx < ..

🙆‍♂️선택 정렬 각 칸에 들어갈 요소를 선택해서 정렬하는 방법입니다. 🙋‍♂️방식 arr = [6,4,2,8] 이렇게 배열이 있을 때 오름차순으로 선택정렬을 한다면 #level1 arr = [2,4,6,8] 첫 번째 자리에 들어갈 가장 작은 2와 6을 바꿔줍니다. 그러면 정렬이 완성됩니다. 시간 복잡도는 O(n^2)입니다. 그리고 stable하지 않은 정렬입니다.

🙆‍♂️삽입 정렬 삽입 정렬은 앞에서부터 이미 정렬된 요소와 비교하여 자신의 위치에 삽입하는 정렬입니다. 🙋‍♂️방식 arr = [8,6,2,4] 이 배열을 오름차순으로 삽입정렬하려 하면 #level 1 arr = [6,8,2,4] 01. 8과 6을 비교하여 삽입 #level 2 #first arr = [6,2,8,4] #second arr = [2,6,8,4] 02. 2와 8, 2와 6을 비교하면서 적절한 위치에 삽입 #level 3 #first arr = [2,6,4,8] #second arr = [2,4,6,8] 03. 4와 8, 4와 6 4와 2를 비교해서 적절한 위치에 삽입 시간 복잡도는 O(n^2)입니다. 그리고 stable한 정렬입니다. def select(arr): for i in rang..

🙆‍♂️버블 정렬 서로 인접한 두 원소의 대소를 비교해서 조건에 따라 교환을 수행하여 정렬하는 방법입니다. 직관적인 정렬 방식입니다. 🙋‍♂️방식 a=[7,3,1,6,2] 이렇게 배열이 있을 때 버블 정렬을 사용해서 오름차순 정렬을 한다고 했을 때 a[0]과 a[1]을 비교해서 a[0]의 크기가 작다면 가만히 있고 크다면 a[1]과 자리를 바꿔줍니다. #1단계의 첫 번째 스위칭 a=[3,7,1,6,2] #1단계의 두 번째 스위칭 a=[3,1,7,6,2] #1단계의 세 번째 스위칭 a=[3,1,6,7,2] #1단계의 네 번째 스위칭 a=[3,1,6,2,7] 첫 번째 단계를 수행하면 이런식으로 수행되어 가장 큰 수인 7이 뒤로 옮겨지고 그 다음 계속적으로 수행하면 큰 수 부터 우측에 쌓이게 됩니다. 버블 정..