공부하는 블로그 ✍️

중복되는 연산을 줄이자 - 우리는 연산 속도와 메모리 공간을 최대한으로 활용할 수 있는 알고리즙을 작성해야 한다 - 어떤 문제는 메모리 공간을 약간만 더 사용하여 연산 속도를 비약적으로 증가시킬 수 있다 - 대표적인 방법이 다이나믹 프로그래밍(Dynamic Programming) 기법으로, 동적 계획법이라고도 부른다 - 다이나믹 프로그래밍의 기본 아이디어를 알아보고, 탑다운 방식과 보텀업 방식에 대해 알아보자 - 추가로 다이나믹 프로그래밍을 위해 자주 사용되는 메모이제이션 기법까지 알아보자 다이나믹 프로그래밍 - 피보나치 수열 - 다이나믹 프로그래밍으로 해결할 수 있는 대표적인 예시로 피보나치 수열이 있다 - 피보나치수열은 이전 두 항의 합을 현재의 항으로 설정한다 - 수학자들은 수열의 항이 이어지는 형..

기출문제 (3) 문자열 뒤집기 다솜이는 0과 1로만 이루어진 문자열 S를 가지고 있다. 다솜이는 이 문자열 S에 있는 모든 숫자를 전부 같게 만들려고 한다. 다솜이가 할 수 있는 행동은 S에서 연속된 하나 이상의 숫자를 잡고 모두 뒤집는 것이다. 뒤집는 것은 1을 0으로, 0을 1로 바꾸는 것을 의미한다. 예를 들어 S=0001100 일 때, 전체를 뒤집으면 1110011이 된다. 4번째 문자부터 5번째 문자까지 뒤집으면 1111111이 되어서 2번 만에 모두 같은 숫자로 만들 수 있다. 하지만, 처음부터 4번째 문자부터 5번째 문자까지 문자를 뒤집으면 한 번에 0000000이 되어서 1번 만에 모두 같은 숫자로 만들 수 있다. 문자열 S가 주어졌을 때, 다솜이가 해야 하는 행동의 최소 횟수를 출력하시오..

import from queue import PriorityQueue 생성 que1 = PriorityQueue() # que1.qsize() = 무한대 que2 = PriorityQueue(maxsize=10) # que2.qsize() = 10 우선순위 큐의 기본 사이즈는 무한대로, 만약 최대 크기를 지정하고자 한다면 maxsize 속성을 사용해 지정한다 데이터 삽입 que.put(7) que.put(3) que.put(5) 데이터 삭제 print(que.get()) # 3 print(que.get()) # 5 print(que.get()) # 7 get() 메서드를 사용해 오름차순으로 데이터를 삭제하고, 삭제한 값은 반환한다 우선순위 지정 que.put((5, 'FIVE')) que.put((1, ..

힙(Heap)의 삭제 연산 과정 루트 노드의 값이 가장 먼저 삭제된다. 최대 힙의 경우 최대값부터, 최소 힙의 경우 최솟값부터 삭제된다 최대 힙을 예로 들어 힙의 삭제 연산에 대해 알아보자 루트 노드를 삭제하고, 마지막 노드를 루트 노드의 자리로 이동한다 최대 힙은 루트 노드에 최대값이 와야 한다. 삭제 연산 후 루트 노드의 값은 전체 노드 중 최댓값이 아니므로 재구조화 과정이 필요하다. 루트 노드의 자식 노드 중, 더 큰 값(6)과 루트 노드의 값(2)을 비교하고 swap한다 부모 노드의 값(2)이 자식 노드의 값(5) 보다 작으므로 swap을 진행해주어 최대 힙의 구조를 완성시킨다

힙의 삽입 연산 2 → 5 → 3 → 4 → 6 → 1 → 7의 순서로 최대 힙에 값을 삽입하는 과정을 살펴보자 비어있는 노드에 값을 넣고, 부모 노드와의 대소 관계를 비교하며 swap과 insert를 반복한다 루트 노드에 2를 삽입한다 5을 삽입한다. 부모 노드(2) 보다 자식 노드(5)가 크기 때문에, swap을 진행한다 더 이상 대소 관계를 비교할 부모 노드가 없으므로 swap을 멈춘다 3을 삽입한다. 부모 노드(5)와 자식 노드(3)의 대소 관계가 성립한다 4을 삽입한다. 부모 노드(2) 보다 자식 노드(4)가 크기 때문에, swap을 진행한다 swap을 진행한 후 부모 노드(5) 와 자식 노드 (4)의 대소 관계가 성립하므로 swap을 멈춘다 6을 삽입한다. 부모 노드(4) 보다 자식 노드(6)..

힙(Heap) - 최댓값 및 최솟값을 찾아내는 연산을 빠르게 하기 위해 고안된 완전 이진트리를 기본으로 한 자료구조 - 키 값의 대소 관계는 오로지 부모노드와 자식 노드 간에만 성립하며, 형제 사이에는 대소 관계가 정해지지 않는다 - 각 노드의 자식 노드의 최대개수는 힙의 종류에 따라 다르지만, 대부분의 자식 노드의 개수가 최대 2개인 이진 힙을 사용한다 - 힙에서는 가장 높은(혹은 가장 낮은) 우선순위를 가지는 노드가 항상 루트노드에 오게 되는 특징을 갖는다 - 루트 노드에는 항상 데이터들 중 가장 큰 값(혹은 가장 작은 값)이 저장되어 있다 - 따라서 힙 구조에서의 최댓값(혹은 최솟값)을 찾을 때의 시간복잡도는 O(1)이다 - 데이터의 삽입과 삭제는 모두 O(logN)이 소요된다 - 이를 응용하면 우..

큐(Queue) - 큐는 스택과 마찬가지로 데이터를 일시적으로 쌓아두기 위한 자료구조이다 - 스택과 달리 가장 먼저 넣은 데이터를 가장 먼저 꺼내는 선입선출(First In First Out / FIFO) 구조를 갖는다 - 큐에 데이터를 넣는 작업은 인큐(enQueue), 꺼내는 작업은 디큐(deQueue)라고 한다 - 그리고 데이터를 꺼내는 쪽을 Front, 넣는 쪽은 Rear라 부른다 선형 큐 - 기본적인 큐의 형태로 선형으로 구현된 큐를 말한다 - 선형 큐는 인덱스의 감소 없이 증가만이 이루어지는 방식이기 때문에, 큐의 앞부분에는 데이터가 없는 경우가 발생한다 - 이러한 방식은 front의 앞부분을 다시 활용 못하기 때문에 메모리를 낭비한다는 단점이 있다 - 메모리 낭비를 하지않고, 앞의 빈 공간을..

스택 (Stack) - 스택은 박스 쌓기처럼 먼저 쌓은 박스를 마지막에 꺼낼 수 있다 - 이러한 구조를 선입 후출(First In Last Out / FILO) 혹은 후입 선출(Last In First Out) 구조라고 말한다 - 스택은 데이터를 일시적으로 저장하기위한 데이터 구조이다 - 스택에 데이터를 넣는 작업은 push, 스택에서 데이터를 꺼내는 작업은 pop이라고 말한다 - 박스쌓기와 같은 스택은, 데이터를 넣는 작업과 꺼내는 작업 모두 위쪽으로부터 수행된다 - 스택에서 푸시와 팝을 하는 위치를 꼭대기(top), 스택의 가장 아래부분은 바닥(Bottom)이라고 부른다 - 자바는 메서드를 호출하고 실행할 때 프로그램 내부에서는 스택을 사용한다 public class Test { public stat..

실전문제 (1) 부품 찾기 동빈이네 전자매장에는 부품이 N개 있다. 각 부품은 정수 형태의 고유한 번호가 있다. 어느날 손님이 M개 종류의 부품을 대량으로 구매하겠다며 당일 날 견적서를 요청했다. 동빈이는 때를 놓치지 않고 손님이 문의한 부품 M개 종류를 모두 확인해서 견적서를 작성해야 한다. 이때 가게 안에서 부품이 모두 있는지 확인하는 프로그램을 작성해보자. ✏️ 입력 조건 - 첫째 줄에 정수 N이 주어진다. (1

이진 탐색 트리 모든 트리가 다 이진 탐색 트리는 아니다 이진 탐색 트리는 부모 노드보다 왼쪽 자식 노드가 작고, 오른쪽 자식 노드가 크다는 특징을 갖는다 간단하게 표현하면 왼쪽 자식 노드 < 부모 노드 < 오른쪽 자식 노드 가 성립해야 이진 탐색 트리라고 말할 수 있다 37을 찾는 탐색을 이진 탐색 트리로 진행해보자 이진 탐색은 루트 노드부터 방문한다. 루트 노드는 30이고, 찾는 원소 값은 37이다 이진 탐색 트리의 특징에 의해, 찾는 원소값인 37은 루트 노드보다 크기 때문에 왼쪽 노드는 확인할 필요가 없다 따라서 오른쪽 노드를 방문한다. 오른쪽 노드의 값은 48이다 찾는 원소값인 37은 48보다 작으므로, 왼쪽 노드를 방문한다 현재 방문한 노드의 값이 찾는 원소 값과 동일하므로 탐색을 종료한다. ..