1. 문제 배열에 다음과 같은 연산을 할 수 있습니다. 배열에 정수 x (x ≠ 0) 를 넣습니다. 배열에서 절댓값이 가장 작은 값을 출력하고, 그 값을 배열에서 제거합니다. ( 절댓값이 가장 작은 값이 여러개일 때는, 그 중 가장 작은 수를 출력하고, 그 값을 배열에서 제거합니다. ) 비어있는 배열에서 시작하여 입력된 연산을 실행하는 프로그램을 작성해보세요. 2. 풀이 자바하면 클래스 어렵게 생각하지 말고 필요하다면 클래스를 구현해서 사용하라 절댓값을 만드는 클래스를 구현해야하는데, 문제는 절댓값을 기준으로 오름차순 정렬을 할 수 있어야하고 중요한건 절댓값만 저장하는게 아니라 원본도 저장해야한다. 그래야 우선순위 큐에서 출력할때 원본값을 출력할 수 있으니까 import java.util.Scanner;..
1. running median 우선순위 큐로 중앙값을 빠르게 구하는 방법 - running median (tistory.com) 우선순위 큐로 중앙값을 빠르게 구하는 방법 - running median 1. 개요 수열이 계속 변화할때, 이 수열의 중앙값을 어떻게 빠르게 구할 수 있을까 매번 정렬해서 중간의 값을 찾아야하는가? 최대 힙과 최소 힙을 이용하면 중앙값을 아주 쉽게 찾을 수 있다 결 deepdata.tistory.com 1) 최대힙과 최소힙 2개를 초기화 2) 최대힙의 원소의 수와 최소힙의 원소의 수가 동일하다면, 최대힙에 수를 넣어주고 3) 최대힙의 원소의 수가 최소힙의 원소의 수 + 1이라면, 최소힙에 수를 넣어준다. 즉 최대힙 > 최소힙 > 최대힙 > 최소힙 >....으로 번갈아가면서 수..
1. 문제 N개의 정수들이 있습니다. 이 중 정확히 앞에서부터 K개를 삭제하고 난 후, 남아있는 정수 중 가장 작은 숫자 하나를 제외한 평균을 구한다 했을 때 이 평균값이 최대가 될 때의 값을 구하는 프로그램을 작성해보세요. 단, K는 1이상 N - 2 이하까지만 고려하도록 합니다. 아니 쉬운문제 같은데 메모리,시간제한 도저히 안되는데..? 2. 풀이 K=1부터 시작해서, 배열에서 1개 지우고 나머지 N-1개에서 최솟값을 찾아 지우고, 평균을 구하고 K=2이면, 2개 지우고 나머지 N-2개에서 최솟값을 찾아 지우고, 평균을 구하고. ... K=N-2이면, N-2개 지우고 나머지 2개에서 최솟값 찾아 지우고, 평균 구하고 이렇게하면, 최솟값 찾는 과정에서 우선순위 큐에 매번 N-1개의 원소넣고 최솟값 찾고..
1. 원하는 우선순위 기준에 맞는, 우선순위 큐 만들기 [(1, 7), (3, 2), (3, 1), (6, 2)] 와 같이 2차 평면상의 점들의 위치가 순서대로 주어졌을 때, 각각의 점의 위치가 주어질 때 마다 지금까지 주어진 점 들 중 x, y의 곱이 가장 큰 경우를 출력하는 프로그램을 작성해보세요. 위와 같은 문제는 어떻게 해결할 수 있을까? 무작정 코드를 작성한다면 점의 위치가 주어질때마다, x*y를 계산하여 최대가 되는 경우를 골라야하므로, $O(N^{2})$이 된다. 하지만 PriorityQueue를 이용한다면 순간 최댓값을 찾는 과정이 O(logN)이 되어, 시간복잡도가 O(NlogN)이 된다. 그런데, 우선순위 큐를 어떻게 만들어야할까? 두 수의 곱이 최대가 되는 특별한 경우를 원하므로, 이..
1. 수식 트리(expression binary tree) 수식을 표현하는 이진 트리 수식 이진 트리라고도 부른다 연산자는 루트 노드이거나 가지 노드 루트와 잎 사이의 중간 노드들을 가지 노드라고 하나봐 피연산자는 모두 잎 노드에 존재함 전위, 중위, 후위순회를 이용해서 순회하면 수식의 전위표기법, 중위표기법, 후위표기법이 된다 2. 예시 다음과 같은 트리를 전위, 중위, 후위순회 해서 전위표기법, 중위표기법, 후위표기법을 구해보면? 2-1) 구현 예시 #class 정의 class Node: def __init__(self,data): self.data = data self.left = None self.right = None #tree 정의 root = Node('+') root.left = Node(..
딥러닝/머신러닝, 통계학, IT프로그래밍, 알고리즘을 좋아하는 사람 https://github.com/yundaehyuck
