공부하는 블로그 ✍️

힙(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..

1874. 스택 수열 스택 (stack)은 기본적인 자료구조 중 하나로, 컴퓨터 프로그램을 작성할 때 자주 이용되는 개념이다. 스택은 자료를 넣는 (push) 입구와 자료를 뽑는 (pop) 입구가 같아 제일 나중에 들어간 자료가 제일 먼저 나오는 (LIFO, Last in First out) 특성을 가지고 있다. 1부터 n까지의 수를 스택에 넣었다가 뽑아 늘어놓음으로써, 하나의 수열을 만들 수 있다. 이때, 스택에 push하는 순서는 반드시 오름차순을 지키도록 한다고 하자. 임의의 수열이 주어졌을 때 스택을 이용해 그 수열을 만들 수 있는지 없는지, 있다면 어떤 순서로 push와 pop 연산을 수행해야 하는지를 알아낼 수 있다. 이를 계산하는 프로그램을 작성하라. 입력. 첫 줄에 n (1 ≤ n ≤ 10..

💬 문제 설명 스트리밍 사이트에서 장르 별로 가장 많이 재생된 노래를 두 개씩 모아 베스트 앨범을 출시하려 합니다. 노래는 고유 번호로 구분하며, 노래를 수록하는 기준은 다음과 같습니다. 속한 노래가 많이 재생된 장르를 먼저 수록합니다. 장르 내에서 많이 재생된 노래를 먼저 수록합니다. 장르 내에서 재생 횟수가 같은 노래 중에서는 고유 번호가 낮은 노래를 먼저 수록합니다. 노래의 장르를 나타내는 문자열 배열 genres와 노래별 재생 횟수를 나타내는 정수 배열 plays가 주어질 때, 베스트 앨범에 들어갈 노래의 고유 번호를 순서대로 return 하도록 solution 함수를 완성하세요. 💡제한사항 genres[i]는 고유번호가 i인 노래의 장르입니다. plays[i]는 고유번호가 i인 노래가 재생된 횟..

📌 11004. K번째 수 수 N개 A1, A2, ..., AN이 주어진다. A를 오름차순 정렬했을 때, 앞에서부터 K번째 있는 수를 구하는 프로그램을 작성하시오 ✏️ 입력. 첫째 줄에 N(1 ≤ N ≤ 5,000,000)과 K (1 ≤ K ≤ N)이 주어진다. 둘째에는 A1, A2, ..., AN이 주어진다. (-109 ≤ Ai ≤ 109) 📋 출력. A를 정렬했을 때, 앞에서부터 K번째 있는 수를 출력한다. import sys n, m = map(int, sys.stdin.readline().split()) arr = list(map(int, sys.stdin.readline().split())) arr.sort() print(arr[m-1]) 내장 함수를 사용하면 간단하게 풀 수 있는 문제다 imp..

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

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

순차 탐색 (Sequential Search) 이진 탐색을 알아보기 전에 가장 기본적인 탐색 방법인 순차 탐색을 알아보자 리스트 안에 있는 특정한 데이터를 찾기 위해 가장 앞에서부터 데이터를 하나씩 확인하는 방법이다 정렬되어 있지 않은 리스트에서 특정 값을 찾을 때 주로 사용한다 리스트 내에 많은 데이터가 있더라도 시간만 있다면, 원하는 데이터를 찾을 수 있다 따라서 데이터의 개수가 N개일 때, 최대 N번의 비교 연산이 필요하므로, 최악의 경우 시간 복잡도는 O(N)이다 위와 같은 리스트에서 짱구를 찾을 때, 순차 탐색에서는 먼저 첫 번째 순서인 유리를 확인한다 짱구가 아니므로 그다음인 철수를 확인하고, 그다음으로 넘어가 짱구를 찾는다 순차 탐색 구현 # 순차 탐색 구현 # n:arr길이 # target..

실전문제 01) 위에서 아래로 하나의 수열에는 다양한 수가 존재한다. 수는 크기에 상관없이 나열되어 있다 이 수열의 수들을 큰수부터 작은 수의 순서로 정렬해야한다. 수열을 내림차순으로 정렬하는 프로그램을 만드시오 ✏️ 입력 조건 - 첫번째 줄에 수열에 속해 있는 수의 개수 N이 주어진다 - 두번째 줄부터 N+1 번째 줄에는 N개의 수가 입력된다. 수의 범위는 1 이상 100,000 이하의 자연수이다 - 입력 예시 3 15 27 12 🖨 출력 조건 - 입력으로 주어진 수열이 내림차순으로 정렬된 결과를 공백으로 구분하여 출력한다 - 동일한 수의 순서는 자유롭게 출력해도 된다 - 출력 예시 27 15 12 💡 풀이 방법 - 파이썬의 sorted() 함수를 사용해 배열의 요소를 정렬한 뒤 순서대로 출력한다 n ..