공부하는 블로그 ✍️

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

📌 20291. 파일 정리 친구로부터 노트북을 중고로 산 스브러스는 노트북을 켜자마자 경악할 수밖에 없었다. 바탕화면에 온갖 파일들이 정리도 안 된 채 가득했기 때문이다. 그리고 화면의 구석에서 친구의 메시지를 확인할 수 있었다. 바탕화면의 파일들에는 값진 보물에 대한 정보가 들어 있어. 하나라도 지우게 된다면 보물은 물론이고 다시는 노트북을 쓸 수 없게 될 거야. 파일들을 잘 분석해서 보물의 주인공이 될 수 있길 바랄게. 힌트는 “확장자”야. 화가 났던 스브러스는 보물 이야기에 금세 화가 풀렸고 보물의 정보를 알아내려고 애썼다. 하지만 파일이 너무 많은 탓에 이내 포기했고 보물의 절반을 보상으로 파일의 정리를 요청해왔다. 스브러스의 요청은 다음과 같다. 파일을 확장자 별로 정리해서 몇 개씩 있는지 알려..

📌 10989. 수 정렬하기3 N개의 수가 주어졌을 때, 이를 오름차순으로 정렬하는 프로그램을 작성하시오. ✏️ 입력. 첫째 줄에 수의 개수 N(1 ≤ N ≤ 10,000,000)이 주어진다. 둘째 줄부터 N개의 줄에는 수가 주어진다. 이 수는 10,000보다 작거나 같은 자연수이다. 📋 출력. 첫째 줄부터 N개의 줄에 오름차순으로 정렬한 결과를 한 줄에 하나씩 출력한다. # 메모리 초과 import sys def counting_sort(arr): res = [0] *(max(arr) + 1) for i in range(len(arr)): res[arr[i]] += 1 for i in range(len(res)): for j in range(res[j]): print(i) input = sys.stdi..

📌 1431. 시리얼 번호 다솜이는 기타를 많이 가지고 있다. 그리고 각각의 기타는 모두 다른 시리얼 번호를 가지고 있다. 다솜이는 기타를 빨리 찾아서 빨리 사람들에게 연주해주기 위해서 기타를 시리얼 번호 순서대로 정렬하고자 한다. 모든 시리얼 번호는 알파벳 대문자 (A-Z)와 숫자 (0-9)로 이루어져 있다. 시리얼번호 A가 시리얼번호 B의 앞에 오는 경우는 다음과 같다. A와 B의 길이가 다르면, 짧은 것이 먼저 온다. 만약 서로 길이가 같다면, A의 모든 자리수의 합과 B의 모든 자리수의 합을 비교해서 작은 합을 가지는 것이 먼저온다. (숫자인 것만 더한다) 만약 1,2번 둘 조건으로도 비교할 수 없으면, 사전순으로 비교한다. 숫자가 알파벳보다 사전순으로 작다. 시리얼이 주어졌을 때, 정렬해서 출력..