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. 우선순위 큐 큐가 먼저 들어오는 데이터가 먼저 나가는 선입선출 형식의 자료구조라면, 우선순위 큐는 항상 우선순위가 가장 높은 데이터에만 관심이 있고 이 데이터만 먼저 나갈 수 있는 형태의 자료구조 힙을 이용할때 삽입, 삭제, 탐색시간을 O(logN)으로 맞출 수 있어서 힙으로 보통 구현한다. 자바에서는 PriorityQueue라는 클래스를 사용할 수 있다. import java.util.PriorityQueue; PriorityQueue (name) = new PriorityQueue(); 형태의 선언 필요 자바는 기본적으로 최솟값을 우선적으로 뽑아준다. 2. 핵심 메소드 2-1) add(E) 우선순위 큐에 데이터 E를 추가 2-2) size() 우선순위 큐에 들어있는 데이터 수를 반환 2-3) i..
1. HashMap 해싱을 기반으로 데이터들을 관리해주는 자료구조 파이썬에서 dict와 대응된다 HashMap은 (key,value) 쌍 형태로 들어가 있어서, key와 그 key에 따른 value값을 동시에 저장하는 형태 따라서 HashMap의 삽입, 삭제, 탐색 등 모든 함수의 시간복잡도는 O(1)이다. HashMap은 TreeMap보다 속도가 빠르며, 값 자체에만 관심이 있지, 그 순서에는 관심이 없는 자료구조 HashMap 사용을 위해서 import java.util.HashMap; HashMap (name) = new HashMap(); 형태의 선언이 필요하다. K,V는 key와 value에 해당하는 타입이다. import java.util.HashMap; public class Main { p..
1. Stack import java.util.Stack Stack (name) = new Stack(); 여기서 (type)은 reference type으로 스택 안에 들어갈 원소의 타입 import java.util.Stack; public class Main { public static void main(String[] args){ Stack s = new Stack(); } } 2. stack 핵심 메소드 2-1) push(E) 맨 위에 데이터 E를 추가 2-2) size() stack에 들어있는 데이터 수를 반환 2-3) isEmpty() stack이 비어있다면 true, 아니라면 false를 반환 2-4) peek() stack의 가장 위에 있는 데이터를 반환 2-5) pop() stack의 ..
1. 단일 연결리스트의 한계 단일 연결리스트는 결국 한방향으로만 이동할 수 있다는 한계점이 있어서 다른 방향으로 탐색하는 것이 불가능하다 때로는 다른 방향으로도 탐색하고 싶을 수 있는데 이런 문제를 해결하기 위해 next를 확장해서 특정 노드의 뒷 노드만 이어주는 것이 아니라, 앞 노드까지 이어질 수 있도록 한다. 2. 이중 연결리스트 단순히 단일 연결리스트에 새로운 노드로 prev를 추가한 것 뿐이다. 이중 연결리스트 역시 단일 연결리스트와 마찬가지로 삽입, 삭제, 탐색이 모두 가능하다. 탐색은 방향성이 양쪽에서 있다고는 하지만 어쨌든 일일이 확인해야하므로 O(N) 하지만 삽입, 삭제의 경우 해당하는 위치를 알고있다면 그냥 선을 끊고 연결해주는 작업만 하면 되므로 O(1) 이때 이중연결리스트는 한방향이..
1. 연결리스트(linked list) 배열의 시간복잡도는 삽입과 삭제가 O(N)이다. 삽입과 삭제가 자주 일어나는 상황에 배열에 들어있는 원소의 수가 매우 많다면 단순한 배열은 비효율적이다. 이런 문제를 해결하기 위해 등장한 자료구조가 연결리스트(linked list) 연결리스트는 탐색은 느리지만(O(N)) 삽입과 삭제 연산이 매우 빠르다(O(1)) 따라서 삽입과 삭제가 잦은 경우에 연결리스트를 이용하면 효과적으로 문제를 해결할 수 있다. 2. 노드(node) 노드는 데이터를 담는 곳이다. 연결리스트는 여러개의 노드들의 모임이다. 연결리스트에서 하나의 노드는 데이터와 다른 노드로 이동하는 경로를 갖는다. 노드를 정의하는 방법에 따라 앞 뒤로 이동할 수 있다. 3. 단일 연결리스트 단일 연결리스트는 연결..
딥러닝/머신러닝, 통계학, IT프로그래밍, 알고리즘을 좋아하는 사람 https://github.com/yundaehyuck
