Sean :: Dev

Two Pointer 2개의 지점(포인터)을 옮겨가며 답을 구한다. 순차적 접근 등이 요구되는 특수한 상황에서 사용된다. ex) 정렬된 두 배열을 하나의 정렬된 배열로 합칠 때(Merge Sort에서 사용됨), 어떤 배열의 연속 부분집합의 원소합이 k인 경우를 찾는 경우 등 ... 자세한 내용은 Merge Sort 부분 참고 Sliding Window Two pointer와 비슷하지만, 두 포인터 사이의 길이가 고정되어있다는 차이가 있다. Input Output 첫 번째 줄에는 배열 D의 원소의 개수 N과 윈도우 사이즈 K 가 주어지고, 두 번째 줄에는 배열의 원소 Di가 주어집니다. (Di 는 자연수) 배열 D의 길이가 K인 연속부분집합의 원소 합의 최대값을 출력합니다. import java.util...

Hash (해시) Input Output 첫 줄에 명령어의 개수 N이 주어집니다. (1 ≤ V ≤ 100,000) 두번째 줄부터 N개의 줄에 걸쳐 아래와 같은 형태로 명령어가 주어집니다. 1 s: 입력받은 문자열 s를 set에 추가합니다. 이미 set에 존재한다면 추가하지 않습니다. 2 s: 입력받은 문자열 s를 set에서 제거합니다. 존재하지 않는다면 아무 동작도 하지 않습니다. 3 s: 입력받은 문자열 s가 set에 있다면 1을, 없다면 0을 출력합니다. 각 명령어에 알맞은 결과를 한줄씩 출력합니다. import java.util.*; public class Test { public static void main(String args[]) { Scanner sc = new Scanner(System...

Stack (스택) LIFO (Last In First Out) push, pop(반환,제거), peek(반환), search ... 배열 or 연결리스트를 이용한 구현 > 자바는 기본 라이브러리로 스택 제공 이용) 역순 문자열 만들기, 시스템 스택(함수 호출,복귀 관리), 수식의 괄호검사, 수식의 후위표기법 등 .. InputOutput첫 줄에 명령어의 개수 N이 주어집니다. (1 ≤ N ≤ 1,000,000)두번째 줄부터 N개의 줄에 걸쳐 아래의 명령어가 입력됩니다.push x : x를 스택에 삽입합니다.pop : 가장 마지막에 들어온 인자를 반환합니다.size : 큐의 크기를 출력합니다.top : 큐의 맨 앞 인자 값을 출력합니다.각 명령 순서에 따라 값을 출력합니다. import java.util..

데이터 표현방식 순차 자료구조 선형 리스트 (Linear/Ordered List) 연결 자료구조 단순 연결리스트 (Linear/Singly Linked List) 원형 연결리스트 (Circular Linked List) 이중 연결리스트 (Doubly Linked List) 이중 원형 연결리스트 (Doubly Circular Linked List) => 그리고 이 자료구조들을 활용한 표현 (다행식, 행렬 등...) Linked List (연결 리스트) 랜덤접근이 가능한 배열과 다른, 순차적 자료구조. 저장할 값과 다음 노트를 가리키는 포인터로 이뤄진 '노드'로 구성. Linked List Doubly Linked List Circular Linked List 배열 vs 리스트 배열 리스트 index로 무작..

# Heap Sort (힙 정렬) # Tree Sort (트리 정렬)

Shell Sort (셸 정렬) https://gmlwjd9405.github.io/2018/05/08/algorithm-shell-sort.html 일정간격으로 부분집합을 구성하고, 각 부분집합에 대해 삽입정렬을 수행. 간격을 줄여가며 반복. 부분집합을 만드는 기준이 되는 간격 값에 따라 성능 좌우 일반적으로 시간 복잡도는 O(n1.25~1.5)로 측정 삽입정렬보다는 개선된 방법 import java.lang.Math; import java.util.Scanner;; public class Test { public static void printArray(int[] arr) { for(int i=0; i

Quick Sort (퀵 정렬) 기준값(pivot)을 잡고, pivot보다 작은수는 좌partition으로 큰수는 우partition으로 보낸다. 다시 좌/우partition에서 각각 pivot을 설정하고 좌/우partition으로 나눈다. 이러한 과정 반복 divide & conquer pivot을 설정하는 방법이 다양하고, 이에 따라 성능이 결정된다. (pivot을 좌우끝값 또는 중앙값으로 등등..) 평균 시간 복잡도 : O(nlog2n) 최악 시간 복잡도 : O(n2) 구현방법이 제각각, 다양하다 import java.lang.Math; import java.util.Scanner;; public class Test { public static void printArray(int[] arr) { f..

Selection Sort (선택 정렬) 0번째 자리와 '1번째-N-1번째 중에서 가장 작은 값'을 교환, 1번째 자리와 '2번째-N-1번째 중에서 가장 작은 값'을 교환, ... 평균/최악 시간 복잡도 : O(n2) import java.lang.Math; import java.util.Scanner;; public class Test { public static void printArray(int[] arr) { for(int i=0; i