CS 공부/알고리즘8 큐(Queue) 두 개로 스택(Stack) 구현하기 Push - queue1의 enqueue()를 통하여 데이터를 저장 Pop a. queue1의 데이터 갯수가 1개 이하로 남을 때까지 dequeue를 한 후, 해당 데이터를 queue2에 enqueue()하여 옮김. 이 결과로 가장 나중에 들어온 데이터를 제외한 모든 데이터가 queue2로 옮겨짐. b. queue1에 남아있는 하나의 데이터를 dequeue()하여 가장 최근에 저장된 데이터를 반환(LIFO) c. ★ 다음에 진행될 pop()을 마찬가지로 진행하기 위해 queue1과 queue2를 swap 코드 작성 import queue class Stack(object): def __init__(self): self.q1 = queue.Queue() self.q2 = queue.Queue() def p.. 2023. 8. 8. 스택(Stack) 두 개로 큐(Queue) 구현하기 구현방법 큐를 입력할 때에는 하나의 스택의 push()를 통하여 데이터를 넣고, 큐를 추출할 때에는 다른 스택의 pop()를 통하여 선입선출을 만족시키는 방법 Enqueue - 첫번째 스택 stack1에 push를 하여 데이터 저장 Dequeue - 두번째 스택 stack2 이용 a. stack2가 비어있다면 stack1이 비어질 때까지 pop()하여 모든 데이터를 옮겨넣음. 이 결과로 stack1에서 가장 먼저 있었던 데이터는 stack2의 top에 위치하게 됨 b. stack2.pop()을 하면 가장 먼저 있었던 데이터가 가장 먼저 추출됨(FIFO) 코드 작성 class Queue(object): def __init__(self): self.instack=[] self.outstack=[] def e.. 2023. 8. 8. 동적 계획법 (Dynamic Programming) 개념 요약 복잡한 문제를 간단한 여러 개의 문제로 나누어 푸는 방법 구체적 개념 흔히 말하는 DP가 바로 '동적 계획법' 이다. 한 가지 문제에 대해서, 단 한 번만 풀도록 만들어주는 알고리즘이다. 즉, 똑같은 연산을 반복하지 않도록 만들어준다. 실행 시간을 줄이기 위해 많이 이용되는 수학적 접근 방식의 알고리즘이라고 할 수 있다. 동적 계획법은 Optimal Substructure에서 효과를 발휘한다. Optimal Substructure : 답을 구하기 위해 이미 했던 똑같은 계산을 계속 반복하는 문제 구조 접근 방식 커다란 문제를 쉽게 해결하기 위해 작게 쪼개서 해결하는 방법인 분할 정복과 매우 유사하다. 하지만 간단한 문제로 만드는 과정에서 중복 여부에 대한 차이점이 존재한다. 즉, 동적 계획법은.. 2022. 8. 28. 계수 정렬(Counting Sort) 계수 정렬(Counting Sort) 의 개념 요약 각 원소의 개수를 세어 저장해두고, 그에 따라서 적절한 위치에 정렬하는 알고리즘이다. 구체적인 개념 원소들의 순서를 결정하기 위해 배열에 각 원소가 몇 개씩 있는지 세어서 적절한 위치에 선형 시간에 정렬하는 방법이다. 각 원소의 개수를 기록하기 위해 정수로 인덱스 또는 카운트 리스트를 사용하기 때문에 정수나 정수로 표현할 수 있는 자료에만 적용할 수 있는 정렬 알고리즘이다. 카운트 리스트를 위한 충분한 공간을 할당하려면 배열 내의 가장 큰 정수를 알아야 한다. 예제 step 0. 가장 작은 데이터(0)부터 가장 큰 데이터(9)까지의 범위가 모두 담길 수 있도록 리스트를 생성한다. step 1. 데이터를 하나씩 확인하며 데이터의 값과 동일한 인덱스의 데이.. 2022. 8. 21. 해시 테이블 (Hash Table) 해시 테이블이란? 해시 테이블은 (Key, Value)로 데이터를 저장하는 자료구조 중 하나로 빠르게 데이터를 검색할 수 있는 효율적인 탐색(빠른 탐색)을 위한 자료구조이다. 해시 테이블이 빠른 검색속도를 제공하는 이유는 내부적으로 배열(버킷)을 사용하여 데이터를 저장하기 때문이다. 해시 테이블은 각각의 Key값에 해시함수를 적용해 배열의 고유한 index를 생성하고, 이 index를 활용해 값을 저장하거나 검색하게 된다. 여기서 실제 값이 저장되는 장소를 버킷 또는 슬롯이라고 한다. 저장, 삭제, 검색의 시간복잡도는 모두 O(1)이다. 직접 주소화 테이블? 해시 테이블와는 다르게 직접 주소화 테이블(Direct-address Table)이라는 key값으로 k를 갖는 데이터를 index k에 저장하는 방.. 2022. 8. 20. 기수 정렬 (Radix Sort) 기수 정렬(Radix Sort) 의 개념 요약 자릿수를 기준으로 차례대로 데이터를 정렬하는 정렬 알고리즘이다. 여기서 '기수' 라는 것은 '자릿수' 를 의미한다. 구체적 개념 낮은 자리수부터 비교하여 정렬해 간다는 것을 기본 개념으로 하는 알고리즘이다. 비교 연산을 하지 않아서 정렬 속도가 빠르지만 데이터 전체 크기에 기수 테이블의 크기만한 메모리가 더 필요하다. 이 메모리는 기수 정렬에서 '버킷' 이라고 불리는데 숫자에 알맞게 새로운 공간에 값을 임시적으로 저장해주는 것이라고 생각하면 된다. 밑에서 더 자세히 설명하겠다. 가장 작은 자리수부터 비교하는 방법을 LSD(Least-Significant-Digit)라고 한다. 가장 큰 자리수부터 비교하는 방법은 MSD(Most-Significant-Dig.. 2022. 8. 13. 이전 1 2 다음
