Data Structure 🛠️28 [면접을 위한 CS 전공지식 노트] 5-2 선형 자료구조 / 비선형 자료구조 1. 선형 자료구조 선형 자료구조란 요소가 일렬로 나열되어 있는 자료구조를 의미한다. 1-1. 연결 리스트 연결리스트란 ? 데이터를 감싼 노드를 포인터(Pointer)로 연결해서 공간 효율성을 극대화시킨 자료구조 삽입과 삭제가 O(1)이 걸리며, 탐색에는 O(n)이 걸린다. 싱글 연결 리스트 이중 연결 리스트 원형 이중 연결 리스트 1-2. 배열 배열이란 ? 여러 개의 데이터를 연속적인 공간에 저장한 자료구조 삽입과 삭제에는 O(n)이 걸리지만, 탐색에는 O(1)이 걸린다. 👉🏻 따라서 데이터 추가와 삭제가 많은 경우에는 '연결 리스트'를, 탐색을 많이 하는 경우에는 '배열'을 사용하는 것이 좋다. 1-3. 스택 스택이란 ? 마지막에 들어간 데이터가 가장 먼저 나오는 후입선출(LIFO) 구조을 가진 자료.. 2023. 11. 26. [프로그래머스 PCCP 모의고사 3번] 카페 확장 from collections import deque def solution(menu, order, k): answer = 0 queue = deque() for i in order: queue.append(menu[i]) answer = max(answer,len(queue)) time = k while queue: # queue[0]과 time을 비교(걸리는 시간과 남은 시간) if queue[0] time: queue[0] -= time break else: queue.popleft() break return answer 이번 문제는 Queue 자료구조를 사용하여 푸는 문제인데 문제의 조건이 조금 .. 2023. 11. 11. [프로그래머스 PCCP 모의고사 2번] 신입사원 교육 import heapq def solution(ability,number): # 신입사원 2명 선발, 선발 후 같이 공부시킴 # 모든 신입사원의 능력치는 정수로 표현 # 2명이 같이 공부하면 서로의 능력을 흡수하여 두 신입사원의 능력치는 # '공부하기 전 두 사람의 능력치의 합'이 됨 # 교육 후 모든 신입사원의 능력치의 합을 최소화 # 최솟값을 pop하는 시간복잡도를 최소화 하기위해 heapq 사용 q = [] for item in ability: heapq.heappush(q,item) for i in range(number): a = heapq.heappop(q) b = heapq.heappop(q) heapq.heappush(q,a+b) heapq.heappush(q,a+b) return sum(q) 2023. 11. 11. [백준 1406번] 에디터 1406번: 에디터 첫째 줄에는 초기에 편집기에 입력되어 있는 문자열이 주어진다. 이 문자열은 길이가 N이고, 영어 소문자로만 이루어져 있으며, 길이는 100,000을 넘지 않는다. 둘째 줄에는 입력할 명령어의 개수 www.acmicpc.net import sys input = sys.stdin.readline string = list(input().rstrip()) m = int(input().rstrip()) command_list = [tuple(input().rstrip().split()) for _ in range(m)] stack = [] for command in command_list: if len(command) == 1: # L / D / B인 경우 if command[0] == 'L'.. 2023. 10. 18. [백준 9935번] 문자열 폭발 9935번: 문자열 폭발 첫째 줄에 문자열이 주어진다. 문자열의 길이는 1보다 크거나 같고, 1,000,000보다 작거나 같다. 둘째 줄에 폭발 문자열이 주어진다. 길이는 1보다 크거나 같고, 36보다 작거나 같다. 두 문자열은 모 www.acmicpc.net string = list(input()) boom = input() boom_length = len(boom) stack = [] for i,value in enumerate(string): stack.append(value) if value == boom[-1] and len(stack) >= boom_length: if ''.join(stack[-boom_length:]) == boom: for j in range(boom_length): st.. 2023. 10. 18. [백준 2812번] 크게 만들기 2812번: 크게 만들기 N자리 숫자가 주어졌을 때, 여기서 숫자 K개를 지워서 얻을 수 있는 가장 큰 수를 구하는 프로그램을 작성하시오. www.acmicpc.net n, k = map(int,input().split()) number = list(input()) stack = [] for i in range(n): while stack and number[i] > stack[-1] and k > 0: # 현재 숫자가 stack에 있는 숫자보다 크면 stack.pop() # 가장 큰 숫자를 앞 쪽에 위치시키기 위함 ! # k개 까지만 지워야 하므로 k > 0이상일 때만 수행 stack.pop() k -= 1 stack.append(number[i]) # 만일 k개 미만으로 숫자를 지웠다면 뒤에 있는 숫.. 2023. 10. 18. 이전 1 2 3 4 5 다음
