본문 바로가기
반응형

자료구조7

[자료구조] 큐(queue)의 이해 - python을 통한 실습 (6) 큐(queue) - 큐(queue)는 스택(Stack)처럼 일종의 리스트 - 단 데이터의 삽입은 한쪽 끝에서, 삭제는 반대쪽 끝에서만 일어남 - 삽입이 일어나는 쪽을 rear, 삭제가 일어나는 쪽을 front - FIFO (First-In, First-Out) 큐의 연산 - insert, enqueue,offer, push : 큐의 rear에 새로운 원소를 삽입하는 연산 - remove, dequeue, poll, pop : 큐의 front에 있는 원소를 큐로부터 삭제하고 반환하는 연산 - element, front, peek : 큐의 front에 있는 원소를 제거하지 않고 반환 - empty : 큐가 비었는지 검사 #Python 예제 queue = [1,2,3] queue.append(4) #queue.. 2022. 11. 23.
[자료구조] 스택(Stack)을 이용한 미로찾기 (5) 미로찾기 - 이미 방문한 위치는 표시를 해서 무한루프를 방지한다. - 현재 위치에서 일정한 규칙으로 다음 위치로 이동한다. ㄴ 북, 동 남, 서의 순으로 검사하여 그 방향으로 갈 수 있다면 Tip. 즉 방문하지 않은 위치면서 벽이 아니면 그 방향으로 간다. - 아무 방향으로도 갈 수 없으면 그 위치에 오기 직전 위치로 회귀한다. # 프로그램의 구조로 표현 1. 현재 위치는 출발점(0, 0)이다. 2. 다음을 반복한다. 1) 현재 위치에 방문했다는 표시를 한다. 2) 현재 위치가 출구라면 종료한다. 3) 현재 위치에서 북, 동, 남, 서 4방향에 대해서 순서대로 이동할 수 있는지(벽 x, 외부 x, 방문한 위치 x) 검사 4) 갈 수 있다면 현재 위치를 스택에 push 후 그 방향으로 이동 5) 3번에서 .. 2022. 11. 23.
[자료구조] 스택(Stack)의 후위표기식으로 변환(괄호가 있는 경우) (5) 중위 표기식을 후위 표기식으로 변환 (괄호가 있는 경우) e.g ) (2+10)/(9-6) 1. 여는 괄호는 무조건 스택에 push (Tip.이때 스택 내의 어떤 연산자도 pop 하지 않는다) 2. 어떤 연산자를 스택에 push할 때 스택의 top에 여는 괄호가 있으면 아무것도 pop하지 않고 push 3. 입력에 닫는 괄호가 나오면 스택에서 여는 괄호가 나올 때 까지 pop하여 출력한다. 4. 닫는 괄호는 스택에 push 하지 않는다. (stack의 여는 괄호도 pop 한다.) # 괄호가 있는 중위 표기식을 후위 표기식으로 변환 # 입력 : 3 + ( ( 4 * 7 ) / 2 ) # 기대 출력 : [3, 4, 7, '*', 2, '/', '+'] OPERATORS = "+-*/()" PRECEDENCE.. 2022. 11. 14.
[자료구조] 스택(Stack)의 응용 중위표기식 -> 후위표기식 (4) 중위 표기식을 후위 표기식으로 변환 e.g ) 2 - 10 / 5 * 6 + 4 1. 중위 표기식을 처음부터 순서대로 읽음 2. 피연산자의 경우에는 바로 출력 가능 3. 연산자의 경우 일단 스택에 stack에 push하여 우선 순위 확인 필요 (LIFO 구조이기 때문) 4. Tip. 스택의 우선순위 보다 더 높은 연산자가 있으면 pop하여 출력한 후에 push (우선순위가 높은 연사자는 모두 pop 해야함) 5. 수식이 종료되면 스택에 있는 모든 연산자를 pop하여 출력 #Python 코드 # 괄호가 없는 중위 표기식을 후위 표기식으로 변환 # 입력 : 2 - 10 / 5 * 6 + 4 # 기대 출력 : [2, 10, 5, '/', 6, '*', '-', 4, '+'] OPERATORS = '+-*/' .. 2022. 11. 11.
[자료구조] 스택(Stack)의 응용 후위표기식 - python을 통한 실습 (3) 후위 표기식(postfix expression) - 일반적으로 사용하는 수식의 표기법은 중위 표기식(infix expression) ㄴ 연산자(+, - *, /)가 피연산자의 사이에 들어감 - 후위 표기식(postfix expression) ㄴ 연산자가 피연산자 뒤에 나옴 - 괄호가 필요없음 후위 표기식을 스택으로 구현 (입력 : 후위 표기식, 출력 : 계산 값) 1. 피연산자를 stack에 넣는다 2. 연산자가 나오면 stack에서 pop()을 두번하여 연산자를 꺼낸 후 적용 ㄴ Tip. 먼저 꺼낸 값이 오른쪽 피연산자가 되고, 나중에 꺼낸 값이 왼쪽 피연산자가 된다! 3. 결과값을 다시 stack에 push() 4. 반복 후 stack에는 하나의 값만 남아 있어야하며 그 값이 계산 결과가 된다. # .. 2022. 11. 11.
[자료구조] 스택(Stack)의 이해 - python을 통한 실습 (2) 스택(Stack) - 스택은 일종의 리스트 - 데이터의 삽입과 삭제가 한쪽의 끝에서만 이루어진다 - LIFO (Last-In, First-Out) - 삽입/삭제가 일어나는 쪽을 스택의 top이라고 부름 스택의 연산 - push : 스택에 새로운 원소를 삽입하는 연산 - pop : 스택의 top에 있는 원소를 스택에서 제거하고 반환 - peek : 스택 top의 원소를 제거하지 않고 반환 - empty : 스택이 비었는지 검사 #Python 예제 stack = [1,2,3] stack.append(4) #stack push print(stack) # [1,2,3,4] top = stack.pop() #stack pop print(top) #4 print(stack) #[1,2,3] top = stack[-.. 2022. 11. 9.

티스토리툴바