자료구조 (10) 썸네일형 리스트형 <스택> 9935번 문자열 폭발 with 파이썬 문제 상근이는 문자열에 폭발 문자열을 심어 놓았다. 폭발 문자열이 폭발하면 그 문자는 문자열에서 사라지며, 남은 문자열은 합쳐지게 된다. 폭발은 다음과 같은 과정으로 진행된다. 문자열이 폭발 문자열을 포함하고 있는 경우에, 모든 폭발 문자열이 폭발하게 된다. 남은 문자열을 순서대로 이어 붙여 새로운 문자열을 만든다. 새로 생긴 문자열에 폭발 문자열이 포함되어 있을 수도 있다. 폭발은 폭발 문자열이 문자열에 없을 때까지 계속된다. 상근이는 모든 폭발이 끝난 후에 어떤 문자열이 남는지 구해보려고 한다. 남아있는 문자가 없는 경우가 있다. 이때는 "FRULA"를 출력한다. 폭발 문자열은 같은 문자를 두 개 이상 포함하지 않는다. 입력 첫째 줄에 문자열이 주어진다. 문자열의 길이는 1보다 크거나 같고, 1,00.. <자료구조> 우선순위 큐 1. 우선순위 큐(Priority Queue) * 우선순위 큐 - 우선순위 큐는 큐와 달리 우선순위가 높은 것부터 Dequeue를 시키는 자료구조를 의미한다. - 이 장에서는 파이썬 모듈 heapq를 이용하여 구현해보자. * 힙(heap) - 힙은 완전이진트리(complete binary tree)를 기본으로 하는 자료구조이다. - 힙은 부모-자식 노드의 키값 대소 관계가 일정하게 유지된다. - 최대 힙 : 자식 노드의 키 값보다 부모 노드의 키 값이 항상 크다. - 최소 힙 : 자식 노드의 키 값보다 부모 노드의 키 값이 항상 작다. - 참고로 파이썬에서 heapq모듈은 최소 힙 자료구조만 제공한다. 2. 구현하기 * 생성 - 먼저 모듈을 불러와야 한다. import heapq heap = [] - 모.. <자료구조> 해시 테이블과 트라이 * 해시 테이블 - 연결리스트와 트리구조에서 검색시간이 O(n)과 O(log n)이 걸렸다. 그러나 컴퓨터 공학자들은 이 시간을 더 단축시켜서 O(1)에 가깝게 만들기를 원했다. - 위를 가능하게 해주는 구조 중 하나가 바로 해시 테이블이다. - 해시테이블은 연결리스트를 원소로 가지는 배열이다. - 이름표를 바구니에 담는다고 가정하자. 단순히 바구니 하나에 여러 이름표를 담으면 사람들이 찾는 데 오랜 시간이 걸릴 것이다. - 그렇다면 바구니를 여러개로 한다면 어떨까. 이 때 바구니를 무슨 기준으로 나누는 것이 좋을까. - 이 때의 기준이 해시 함수이다. 이름표이므로 해시함수를 이름의 가장 첫 글자로 시도해보자. 알파벳이라면 총 16개의 포인터들이 생기고, 그 알파벳은 각각 연결리스트를 가리키게 된다. -.. <알고리즘> 재귀 알고리즘 (1) 1. 재귀 알고리즘의 기본 * 재귀란 - 재귀 : 어떤 사건에서 자기 자신을 포함하고 다시 자신을 사용하여 정의되는 것. * 팩토리얼 구현 - n! 정의 ① 0! = 1 ② n > 0 이면 n! = n x (n-1)! 이 경우 n이 0이 아닌 수일 경우 ②를 실행하고 이는 또 다시 그 보다 1작은 수의 ②를 시행함을 알 수 있다. def factorial(n: int) -> int : if n > 0: return n * factorial(n - 1) else: return 1 x = int(input()) print(factorial(x)) # 5 # 120 : 매개 변수 5를 먼저 받고, 5 * factorial(4)을 계산해야한다. 이 때 이 곱셈을 위해 factorial(4)를 호출한다. 차례로 .. <자료구조> 스택과 큐(2) 1. 큐란 * 큐 - 스택과 같이 데이터를 임시 저장하는 자료구조이지만 가장 먼저 넣은 데이터를 가장 먼저 꺼낸다는 차이가 있다. (선입선출구조) - 인큐(enqueue) : 큐에 데이터를 추가하는 행위 - 디큐(dequeue) : 큐에서 데이터를 꺼내는 행위 - 프론트(front) : 데이터가 빠지는 가장 앞쪽 부분 - 리어(rear) : 데이터를 넣는 부분 2. 배열과 큐 - 인큐 : 맨 끝 데이터의 다음 인덱스에 원소를 저장하여 처리의 복잡도는 O(1)이고 cost가 적다. - 디큐 : que[0]에 저장된 원소를 꺼내면서 이후의 원소를 모두 앞쪽으로 옮겨야한다. 따라서 복잡도는 O(n)이고 매우 비효율적이다. ※ 우선순위 큐 : 인큐할 때 데이터에 우선순위를 부여하고 디큐할 때 우선순위대로 꺼내는.. <자료구조> 스택과 큐(1) 1. 스택이란 * 스택 - 데이터를 임시 저장할 때 사용하는 자료구조이다. 후입선출 방식의 입출력 순서를 가진다. - 푸시(Push) : 스택에 데이터를 쌓아 넣는 일 - 팝(Pop) : 스택에서 데이터를 꺼내는 일 - 데이터는 겹겹이 쌓이는 방식으로 푸시하면 top에 쌓이고 pop하면 top에서부터 꺼낸다. 2. 스택의 구현 - 스택을 구현하기 위해 크기가 결정된 고정길이 스택을 클래스를 이용하여 만드려면 어떤 요소들이 필요할까. * 스택 구현 - 스택을 구현하기 위해서는 다음과 같은 요소들이 필요하다. - 스택 배열 : 푸시한 데이터를 list형 배열에 저장하도록 하면 첫번째 푸시한 데이터는 list[0]에 저장된다. - 스택포인터 : 스택에 쌓여있는 데이터의 갯수이다. 가장 마지막에 푸시한 데이터는.. <알고리즘> 검색 알고리즘(2) 1. 해시법 이번 장은 검색뿐 아니라 데이터의 추가·삭제도 효율적으로 수행할 수 있는 해시법을 알아보자. * 해시법 - 데이터를 저장할 위치인 인덱스를 새로 구하는 것이다. 이를 통해 원소의 검색과 추가·삭제를 효율적으로 수행한다. 위의 배열을 11로 나눈 나머지를 정리해보자. 위에서 나온 해시값을 인덱스로 새로 배열을 해보자. - 위를 해시테이블이라 하며 새로운 원소 37을 추가하더라도 다른원소의 이동이 없는 것을 알 수 있다. 이는 기존의 배열에서 37을 추가하려면 뒤의 원소들을 모두 한칸씩 옮겨야 했던 것보다 효율적임을 알 수 있다. - 해시함수 : 위와 같이 키를 해시값으로 변환하는 과정 - 버킷(bucket) : 해시테이블에서 만들어진 원소 * 해시충돌 - 위의 예시에서 33을 추가하려면 버킷[.. <알고리즘> 검색 알고리즘 (1) 1. 검색 알고리즘이란 * 검색 : 어떤 조건을 만족하는 데이터를 찾는 행위 - 검색과 키 ex) 전공이 경제학과인 학생을 찾아라. : 위 예시의 조건은 전공이라는 항목이다. 이렇게 조건에서 주목되는 것이 '키'이다. * 배열검색 - 선형검색 : 무작위로 늘어놓은 데이터의 집합에서 검색 수행 - 이진검색 : 일정한 규칙의 데이터 집합에서 빠른 검색 수행 - 해시법 : 추가와 삭제가 자주 일어나는 데이터의 집합에서 빠른 검색을 수행. 체인법과 오픈주소법이 있음. * 검색 알고리즘의 선택 - 단순히 검색만 잘되면 좋다고 생각한다면 계산시간이 짧은 검색 알고리즘을 선택할 수 있다. - but, 검색 뿐 아니라 데이터의 추가·삭제도 수행한다면 검색이외에 작업에 들어가는 비용을 종합적으로 평가해야한다. - 따라서.. <자료구조> 자료구조와 배열 1. 자료구조와 배열 * 배열이란 - 하나의 값이 아닌 묶음 단위의 값을 저장하는 자료구조 - 원소 : 배열에 저장된 객체 한 단위 - 파이썬에서는 주로 리스트와 튜플로 배열을 표현함. * 객체 - 파이썬은 데이터, 함수, 클래스, 모듈 등 전부 객체로 취급하기때문에 변수는 값을 갖는 것이 아니다. - 모든 객체는 메모리를 차지하며 식별번호가 따로 존재한다. - 따라서 변수는 객체를 참조하는 별명이라고 보는 것이 좋다. 예를 들어 10의 고유번호를 19991010 이라고 하자. 이 때 x = 10 이라고 선언하고 x의 식별번호를 확인하면 19991010이 나타난다. ※ 값을 비교할 때 연산자로 == 을 사용하지만 두 객체의 값과 식별번호를 함께 비교할 경우에는 is 를 사용한다. * 리스트와 튜플 - 리.. <알고리즘> 알고리즘 기초 1. 알고리즘이란 * 기초용어 먼저 두 숫자중 더 큰 숫자를 구하는 간단한 프로그램을 구현해보자. a = int(input('첫 번째 숫자를 입력하세요. :')) b = int(input('두 번째 숫자를 입력하세요. :')) large = a if b > large : large = b print(f'더 큰 숫자는 {large}입니다.') # 첫 번째 숫자를 입력하세요. : 10 # 두 번째 숫자를 입력하세요. : 25 # 더 큰 숫자는 25입니다. - 순차구조 : 위와 같이 순서대로 처리되는 구조 - 복합문 : if문과 같이 복합적으로 이루어진 구문 - 대입문 : large = a 와 같은 단순한 구문 - 조건식 : if문 바로 뒤에 따라오는 조건 - 선택구조 : 조건식으로 평가된 결과에 따라 흐름이.. 이전 1 다음
