💡 Stack을 이용한 오큰수 구현 for문으로 오큰수를 찾으면 시간복잡도가 높아 제한시간을 초과할 우려가 있으므로, 스택을 이용하여 오큰수를 구현한다. 입출력 예시 입력 int N = 수열의 크기 int[] M = 수열' 출력 5 7 7 -1 풀이 스택에 새로 들어오는 수가 top에 존재하는 수보다 크면 그 수는 오큰수가 된다. 오큰수를 구한 후, 수열에서 오큰수가 존재하지 않는 숫자에 -1을 출력해야 한다. 풀이 순서 스택에 채워져 있거나 A[index] > A[top]인 경우 pop한 인덱스를 이용해 정답 수열에 오큰수 저장. (pop은 조건을 만족하는 동안 계속 반복) 현재 인덱스를 스택에 push하고 다음 인덱스로 넘어간다. 위의 과정을 수열의 길이만큼 반복하고 현재 스택에 남아있는 인덱스에 -..

💡 오름차순 수열 구현 임의의 수열을 스택에 넣었다가 출력하는 방식으로 오름차순 수열을 출력할 수 있는지 확인. 출력할 수 있다면 push와 pop 연산을 어떤 순서로 수행해야 하는지 알아내는 프로그램 작성. push 연산은 +, pop 연산은 -, 불가능 할 때는 NO 출력. static int AA = 5; static int[] BB = {3,4,5,6,7}; public static void main(String[] args) { // average(A, B); stack(AA, BB); } // Stack의 오름차순 수열 구현 // 수열의 개수 a, 수열[] b public static String stack(int a, int[] b) { int[] A = new int[a]; for (int..

💡 DFS Depth-First Search의 약자이며 깊이 우선 탐색을 하는 알고리즘이다. 동작방식 스택을 이용하므로 재귀를 이용했을때 간결한 구현이 가능하며 시간복잡도는 O(N)이다. 탐색 시작 노드에 스택일 삽입하고 방문 처리한다. 스택의 최상단 노드에 방문하지 않은 인접 노드가 있으면 그 인접 노드를 스택에 넣어 방문 처리하고, 방문하지 않은 인접 노드가 없으면 스택에서 최상단 노드를 꺼낸다. 위의 과정을 더 이상 수행할 수 없을 때까지 반복한다. 방문처리란? 스택에 한번 삽입되어 처리된 노드가 다시 삽입되지 않게 체크하는 것을 의미한다. 이를 통해 각 노드를 한 번씩만 처리할 수 있다. 재귀 함수를 이용한 DFS 구현 노드들은 호출을 받으면 하위의 노드를 재귀 호출 하기 전, 자기 자신을 출력한..

💡 ArrayList로 구현 public class Implementation_Queue { private ArrayList listQueue = new ArrayList(); public void add(Integer data) { listQueue.add(data); } public Integer poll() { if (listQueue.size() == 0) { return null; } else { return listQueue.remove(0); } } public int size() { return listQueue.size(); } public Integer peek() { if (listQueue.size() == 0) { return null; } else { return listQueu..

💡 ArrayList로 스택 구현 public class Implementation_Stack { private ArrayList listStack = new ArrayList(); public void push(Integer data) { listStack.add(data); } public Integer pop() { if (listStack.size() == 0) { return null; } else { return listStack.remove(listStack.size()-1); } } public int size() { return listStack.size(); } public Integer peek() { if (listStack.size() == 0) { return null; } el..

💡 Hash Chaining 가장 안정적이며 보편적으로 사용되는 자료구조 중 하나이다. 파이썬의 딕셔너리도 이것을 기반으로 만들어졌으며 자바에서도 쉽게 해시를 만들 수 있게 API를 제공한다. 펄에서도 이 방법으로 연상 배열과 해시를 만든다. 해시는 사실상 배열 1개로 구성되어 있으며, 요소들이 들어가야 할 위치에 추가되면서 배열은 점점 채워진다. 그래서 배열의 위치마다 새로운 자료구조를 만들면서 수많은 데이터를 수용할 수 있도록 만드는것이다. 즉, Hash 배열의 각 요소에 자료구조인 LinkedList를 사용하며 각 요소는 테이블의 크기보다 클 수 있다. 어떤 자료구조가 가장 적합할까? 정답은 LinkedList 이다. 체인을 만들기 위해 배열의 각 위치마다 LinkedList를 만들어 주는 방법이며..

💡 선형조사법 (Linear Probing) 채우려는 공간이 이미 차 있다면, 비어있는 칸을 찾을 때까지 다음 칸을 확인하는 방법이다. 비어있는 칸을 찾아 그 곳에 채운 후 위치가 바뀌었다는 사실을 알려야 한다. 예시 객체 x 객체 x의 hashCode 값인 h를 구한다. h를 양수로 변환 -> h & 0x7FFFFFFF; 테이블의 크기와 % 연산 -> h % table.size(); h를 가지고 x를 적절한 위치로 저장, 이 때 위치는 hashCode의 값에 따라 다름 객체 y 위와 동일한 방법으로 h를 구한다. x의 위치와 동일한 값이 나오면 x의 위치에 y를 저장해야 한다. 이런 상황을 충돌이라고 한다. 해결 x의 다음 칸에 y를 저장 y의 위치가 바뀌었다는 사실을 알려야 한다.\ 삭제의 경우 데이..