자료구조 (6) 썸네일형 리스트형 [백준] 2493 - 탑 교수님이 어렵다고 하셔서 쫄아있었는데 정말 어렵다 ,, ^^!; 야구 문제가 여러 알고리즘들이 섞이고, 야구의 룰에 따라 값들을 관리해줘서 어렵다면 이 문제는 나오는 자료구조는 스택 하나 뿐인데 그 스택을 단순한 LIFO + 다른 기능을 추가적으로 생각해봐야한다. 사실 스택문제라는 걸 알기 전까진 이 문제가 스택으로 풀릴 수 있을 거란 생각조차 못했고, 브루트포스인가 하고 생각했었다. 하지만 완전탐색이라고 하기엔 입력 범위가 너무 컸으며, 완전탐색으로 코드를 짰더니 백준에선 틀렸다고 하고, 정올에선 시간초과 에러가 났다.. 이때부터 ㄹㅇ 멘붕 시작ㅋㅋㅋㅋㅋㅋㅋㅋㅋ 한시간 가량 짠 코드가 아까웠지만... 이럴 땐 과감히 버려야 한다는 교수님의 말씀이 기억나서 과감히 버리고 스택으로 접근을 시도해보았다. 각.. 힙(Heap) - 특정한 조건을 갖춘 이진트리 - 특정한 조건이란? 1) root 노드가 언제나 전체 트리 중 최댓값(max heap) 혹은 최솟값(min heap) -> 자신의 서브트리 (왼쪽이건 오른쪽이건)보다 무조건 크거나(max heap), 무조건 작다 (min heap) -> 재귀적정의 2) 완전 이진 트리 -> 0~level-1 까진 포화, level 번째 에선 포화는 아니더라도 왼쪽부터 순차적으로 데이터가 있음 3) 오른쪽 서브트리와 왼쪽 서브트리 사이의 순서는 정의되지 않았다. - 이진 탐색 트리와 달리 완전 이진 트리이지만, 노드의 자식 사이의 배치가 정해진 바 없어 이진 탐색 트리처럼 검색 기능을 제공하지 않는다. - 순회도 제공하지 않는다. [ Max Heap의 추상적 자료구조 ] 1) __init.. 이진 탐색 트리 (Binary Search Trees) - 왼쪽 서브트리의 모든 값 bfs/dfs로 탐색, 찾은 노드+부모노드 함께 반환 -> 다른 함수에서 쓰.. 후위 표기법 (Postfix Notation) 중위표기법 (infix notation) - 연산자가 피연산자들 사이에 위치 예) (a+b)*(c+d) 후위표기법 (postfix notation) - 연산자가 피연산자들의 뒤에 위치 예) ab+cd+* [중위 표현식을 후위 표현식으로 변경하기 (feat.스택)] a*b+c => ab*c+ a+b*c =>abc*+ //문자는 그 순서 그대로, (피연산자1)(피연산자2)(연산종류) 이 형태 유지 1) 스택에 넣기 피연산자인 경우 바로 print 연산자는 stack 에 push ->우선순위가 더 높(거나같 - 먼저나온게 우선임)은게 들어있다면(지금 넣는 것보다 먼저 해야 하니까), pop 하고나서 push ->우선순위가 더 낮은게 들어있다면, 지금 있는 것보다 위에 있어야 하므로 push 수식의 끝까지 왔을.. 스택(Stack) in Python [ 스택이란? ] - 자료를 보관할 수 있는 선형 구조. 한쪽 끝에서 밀어넣고(push) 같은 쪽에서부터 뽑아쓴다.(pull) - 후입선출(LIFO - Last In, First Out) [ 스택 언더플로우 & 스택 오버플로우 ] - 스택 언더플로우(stack underflow): 비어있는 스택에서 데이터 원소를 꺼내려고 할 때 발생하는 에러 - 스택 오버플로우(stack overflow): 꽉 찬 스택에 데이터 원소를 넣으려 할 때 발생하는 에러 [ 스택의 추상적 자료구조 구현 ] 1. 구현 방법 1) 배열 이용 - Python의 리스트와 메서드를 이용하여 스택을 구현한다. 2) 연결리스트 이용 - 양방향 연결리스트를 이용하여 스택을 구현한다. 2. 연산의 정의 1) size() - 현재 스택에 들어있.. 연결리스트 (Linked List) in Python 연결리스트는 말 그대로 연결된 리스트이다. 리스트(배열)자료구조에서 각 원소들이 호텔의 방에 하나씩 들어가 있었다면, 연결리스트에서 그 방들은 호텔에 갇힌것이 아닌, 독립적인 캠핑카가 된다. 그리고 서로의 꽁무늬에 'link'라는 연결고리를 달고 다니는데, 이 꼬리엔 아무것도 오지 않을 수도, 혹은 또 다른 캠핑카 한 대가 연결되어 기차같은 모양을 이룰수도 있다. [자료 구조 정의] 1. Node (캠핑카) class Node: def __init__(self,item): self.data = item #캠핑카에 탑승한 운전자 self.next = None #꽁무늬 (link 가 여기선 next) 초기화 item, next 는 각자 캠핑카에 탑승한 자료, 캠핑카의 뒤에 붙은 꽁무늬와 같다. 노드를 초기화.. 이전 1 다음
