자료구조&알고리즘

Hash란? 임의의 데이터를 해시 함수를 통해 고정된 크기의 고유한 값으로 매핑하는 것을 말한다. 해시 함수는 주어진 입력에 대해 항상 동일한 출력을 생성하고, 최대한 서로 다른 입력에 다른 출력을 만들어 충돌을 최소화 한다. Hash Map이란? 해시 맵이란 해시를 사용해서 데이터를 저장하는 자료 구조 이다. 각 키에 해당하는 해시 값을 계산하여 해당 위치에 데이터를 저장한다. 따라서 해시 맵은 평균적으로 검색, 삽입 삭제 연산의 시간 복잡도가 O(1)이다.

1. 선택 정렬 (Selection Sort) 선택 정렬은 가장 간단 하면서 비효율적인 정렬 알고리즘이다. 1. 배열에서 최소값(또는 최대값)을 찾는다. 2. 최소값(또는 최대값)을 배열의 맨 앞의 원소와 교환한다. 3. 정렬된 부분의 배열을 제외하고 나머지 배열에서 위 과정을 반복한다. 자바로 구현하기 import java.util.Scanner; public class SelectionSort { public static void main(String[] args) { Scanner scanner = new Scanner(System.in); int num = Integer.parseInt(scanner.nextLine()); int[] arr = new int[num]; for (int i = 0;..

Stack이란? Stack은 LIFO(Last-in, First-out) 의 특성을 가지고 있는 자료구조이다. 즉, 나중에 들어온 것이 먼저 나가는, 바닥부터 차곡차곡 쌓고 제일 위를 꺼내는 특성을 가지고 있다! Stack의 시간 복잡도는 다음과 같다. 삽입(push) O(1) 삭제(pop) O(1) 읽기(peek) O(1) 탐색(search) O(n) Java로 코테에서 Stack 활용하기 java에서는 Stack클래스를 제공하고 있다. 하지만 오라클 공식 문서에 따르면 Stack 클래스 보다는 ArrayDeque를 활용하는 것을 추천한다. (https://docs.oracle.com/en/java/javase/11/docs/api/java.base/java/util/ArrayDeque.html) Th..

문제 이해 1부터 n까지 오름차순으로 스택에 push할수 있다. 입력된 숫자가 스택에 있는 숫자 보다 클 경우 push를 해준다. 스택을 pop했을때 입력된 숫자와 pop된 숫자가 동일해야 한다. 동일하지 않거나 스택이 비어있는 경우, 실패이다. 풀이 import java.io.*; import java.util.Stack; public class Solution { void solution() throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); int num = Integer.parseInt(br.readLine()); Stack stack = new Stack(); StringBuil..