Study Log

문제 https://www.acmicpc.net/problem/11286 11286번: 절댓값 힙 첫째 줄에 연산의 개수 N(1≤N≤100,000)이 주어진다. 다음 N개의 줄에는 연산에 대한 정보를 나타내는 정수 x가 주어진다. 만약 x가 0이 아니라면 배열에 x라는 값을 넣는(추가하는) 연산이고, x가 0 www.acmicpc.net 설계 주어진 입력의 개수는 최대 100,000개이고, 주어진 시간은 1초이다. 따라서 이 문제는 최소 $ O(n \mathrm{log}n) $의 시간복잡도로 해결해야 한다. 입력을 하는 과정에서 n번의 연산을 하는 것은 어쩔 수 없으니, 저번과 같이 답을 구하는 과정에서 $O(1)$의 시간이 걸리는 큐나 덱을 사용해보자. 여기서 포인트는 데이터를 절댓값 순으로 정렬해야한..

문제 https://www.acmicpc.net/problem/11003 11003번: 최솟값 찾기 N개의 수 A1, A2, ..., AN과 L이 주어진다. Di = Ai-L+1 ~ Ai 중의 최솟값이라고 할 때, D에 저장된 수를 출력하는 프로그램을 작성하시오. 이때, i ≤ 0 인 Ai는 무시하고 D를 구해야 한다. www.acmicpc.net 설계 N개의 수가 주어지고, 숫자 L이 주어지며 주어진 $D_{i}$ 의 최솟값들을 출력하는 문제이다. 기본적인 구성은 위의 그림과 같다. L = 2일 때, $D_{i}$ 는 $A_{i-1}$ ~ $A_{i}$ 의 범위 중 최솟값이 되고, L = 3일 때, $D_{i}$ 는 $A_{i-2}$ ~ $A_{i}$ 의 범위 중 최솟값이 된다. 이를 알아보기 쉽게 표..

덱 덱(Double Ended QUEue)는 앞서 이야기한 스택(Stack)과 큐(Queue)의 특성을 모두 가지고 있는 자료구조이다. 두 가지의 특성을 모두 가지고 있는 자료구조답게 덱의 앞과 뒤 모두에서 삽입과 삭제가 이루어진다. 또한 덱을 잘 이용하면 효율적으로 시간복잡도를 줄이거나, 정렬 효과를 얻을 수 있으니 잘 알아두도록 하자. 스택(Stack)과 큐(Queue)가 뭔지 잘 모르겠다면, 아래 게시글을 참고하자. https://pink-saurus.tistory.com/entry/%EC%9E%90%EB%A3%8C%EA%B5%AC%EC%A1%B0python-%EC%8A%A4%ED%83%9D-Stack [자료구조][Python] 스택 (Stack) 스택이란? 스택(Stack)은 후입선출(Last I..

큐 큐(Queue)는 선입선출(First In First Out)의 규칙을 따르는 자료구조이다. 스택과 마찬가지로 리스트 자료구조의 연장형이며, 큐의 앞 부분에서 삭제가, 뒷 부분에서 삽입이 이루어진다. 큐의 import 와 연산 큐를 import 하는 주된 방법은 크게 두 가지가 존재한다. import 한 방식에 따라서 사용 가능한 함수에 약간의 차이가 있으니 주의하자. from queue import Queue from queue import Queue Q = Queue() print(type(Q)) # class - 큐에서의 삽입(put) Q.put(data): 큐에 data를 삽입한다. 이때, 삽입되는 data의 위치는 큐의 뒷 부분이다. - 큐에서의 삭제(get) Q.get(): 큐의 맨 앞 원..

스택이란? 스택(Stack)은 후입선출(Last In First Out)의 규칙을 따르는 자료구조이다. 리스트 자료구조의 연장형이며, 가장 나중에 들어온 값(top)을 기준으로 삽입과 삭제와 같은 연산이 진행된다. 스택의 연산 스택의 연산은 삽입(append)과 삭제(pop)가 있다. - 스택에서의 삽입(append) S.append(data): 스택에 data를 삽입한다. 이때, 삽입되는 data의 위치는 스택의 가장 마지막 인덱스이다. - 스택에서의 삭제(pop) S.pop(): 스택의 top 인덱스의 원소를 스택에서 삭제한다. 이때, 삭제되는 원소가 리턴된다. 주의사항: top은 단순히 연산이 이루어지는 위치를 의미하며, 실질적인 원소값을 얻기 위해서는 S [-1]을 통해 얻어야 한다.

개요이진검색(Binary Search) 알고리즘은 정렬된 배열의 중간값과 찾고자 하는 키 값을 비교하여 배열의 절반만 확인하는 과정을 반복하여 키 값이 배열에 있는지 확인하는 검색 알고리즘이다.검색을 진행하면서 생길 수 있는 경우의 수는 다음과 같다. 1. 키 값이 배열에 있을 경우 1-1. key값과 mid값이 같을 때 : "찾았습니다!" 출력 후 종료 1-2. key값이 mid값보다 클 때 : start = mid + 1 로 설정 후 함수 재호출 1-3. key값이 mid값보다 작을 때 : end = mid - 1 로 설정 후 함수 재호출 2. 키 값이 배열에 없을 경우 이러한 경우에는 배열에 원소가 한 개 남을 때까지 검색이 진행된다. 즉, 함수의 맨 처음에 배열에 원소가 한 개 남았을 때 key값..

개요 병합정렬 알고리즘은 배열을 하나의 원소가 될 때까지 분할하여 정렬 후 정렬된 부분 배열을 병합, 병합된 부분 배열끼리 다시 정렬 후 병합하는 과정을 반복하여 전체 배열을 정렬하는 알고리즘이다. 위의 자료와 같이 분할하고 병합하는 과정이 똑같이 반복되기 때문에 재귀함수로 구현이 가능하다. 코드 void Merge_Sort(int A[], int p, int r) { if (p < r) { int q = (p + r) / 2; Merge_Sort(A, p, q);// 분할 Merge_Sort(A, q + 1, r);// 분할 Merge(A, p, q, r);// 정렬 } } 위의 코드는 배열을 분할하고 정렬하는 함수를 재귀적으로 수행하는 Merge_Sort 함수이다. 여기서 p와 r은 정렬할 배열의 각..

개요 선택정렬 알고리즘은 정렬되지 않은 부분배열에서 가장 작은 원소를 찾아 알맞은 위치에 삽입하고 이를 반복하여 배열 전체를 정렬하는 알고리즘이다. 위의 자료에서 정렬된 부분배열은 빨간색, 정렬되지 않은 부분배열은 검은색으로 표시했다. 정렬되지 않은 부분배열을 순회해 가장 작은 key 값을 찾아, 알맞은 위치의 원소와 위치를 바꾼다. 이를 반복하면 전체 배열을 정렬할 수 있다. 코드 void Selection_Sort(int arr[], int size){ int key, index; for(int i=0;i

문제 원소가 n개인 두 배열 A, B에 저장된 두 개의 n비트 이진수를 더하고 원소가 n+1개인 배열 C에 저장해 그 결과를 출력하라. 설계 1. 배열 A, B에 이진수를 저장하고 그 값을 더해 배열 C에 그림과 같이 저장한다. 2. 배열 C의 $ 2^{0} $ 자리부터 받아올림을 시작한다. 이때, 배열 C의 원소에 가능한 수는 0, 1, 2, 3 뿐이다. 2-1. 배열 C의 원소가 0, 1이면 continue 2-2. 배열 C의 원소가 2면 해당 인덱스의 원소값을 0으로 바꾸고, 다음 자리 + 1 2-3. 배열 C의 원소가 3이면 해당 인덱스의 원소값을 1로 바꾸고, 다음 자리 + 1 코드 두 이진수를 더한 값을 배열 C에 저장하는 코드는 다음과 같다. for(int i=0;i=0;i--){ if(C[..

개요 선형검색(Linear Search) 알고리즘은 배열을 처음부터 끝까지 읽어보고 찾고자 하는 키 값을 찾는 간단한 알고리즘이다. 코드 void Linear_Search(int arr[], int size, int key){ int find = 0; for(int i=0;i