본문 바로가기

Study for Backend

 (91)
[Data Structure 기초] Linked List Linked List (연결 리스트) - 각 노드가 데이터와 포인터를 가지고 한 줄로 연결되어 있는 방식으로 데이터를 저장하는 자료구조. - 데이터를 담고 있는 노드들이 연결되어있는데, 노드의 포인터가 이전이나 다음의 노드와의 연결을 담당하게 된다. - 키와 값은 모두 객체이다. 값은 중복 저장될 수 있지만 키는 중복 저장될 수 없다. - 만약 기존에 저장된 키와 동일한 키로 값을 저장하면 기존의 값은 없어지고 새로운 값으로 대치된다. - 실제 데이터를 저장시킬 때는 Node 타입의 배열에 저장된다. HashMap에 선언된 Node 타입 변수 및 클래스이다. Hashmap 시간복잡도 접근, 탐색 : O(n) 추가 , 삭제 : O(1) 연산 void addFirst(Object obj) 맨 앞에 객체(ob..
[Java 연습] Queue를 이용한 요세프스 순열 문제 import java.util.ArrayList; import java.util.LinkedList; import java.util.Queue; import java.util.stream.IntStream; //20240222 /* 요세프스 순열 문제 N과 K가 주어졌을 때 (N,K) 요세프스 순열을 구하시오. N과 K는 N >= K를 만족하는 양의 정수이다. 1부터 N번 까지 N명이 순서대로 원을 이루어 모여있다. 이 모임에서 원을 따라 순서대로 K번째 사람을 제외한다. 모든 사람이 제외될 때까지 반복하며 이 때, 제외되는 순서가 요세푸스 순열이다. */ public class queuePractice03 { public static ArrayList getJosephusPermutation(int N..
[Java 연습] Queue를 이용한 카드 섞기 import java.util.*; import java.util.stream.IntStream; //20240222 카드 섞기 /* 1부터 N까지 번호로 구성된 N장의 카드가 있다. 1번 카드가 가장 위에 그리고 N번 카드는 가장 아래의 상태로 카드가 순서대로 쌓여있다. 아래의 동작을 카드 한 장만 남을 때가지 반복했을 때 가장 마지막 남는 카드 번호를 출력하시오. 1.가장 위의 카드는 버린다. 2.그 다음위의 카드는 쌓여 있는 카드의 가장 아래에 다시 넣는다. */ public class queuePractice02 { public static int findLastCard(int N){ Queue queue = new LinkedList(); IntStream.range(1, N + 1).forEa..
[Algorithm 기초] 기수 정렬, 계수 정렬, 셀 정렬 기수 정렬 (Radix Sort) 낮은 자리수 부터 정렬하는 방식. 각 원소 간의 비교 연산을 하지 않아 빠른 대신, 기수 테이블(queue)을 위한 메모리 필요 알고리즘 복잡도 : O(dn) 기수정렬구현 의사코드 (Pseudocode) RadixSort(a[], n): // Finding the maximum element max=a[0] For (i=1 to n-1): If (a[i]>max): max=a[i] // Calling countingSort for // k times using For loop. For (div=1 to max/div>0): countingSort(a, n, div) div=div*10 계수 정렬(Counting Sort) 숫자끼리 비교하지 않고 카운트를 세서 정렬하는 방..
[Algorithm 기초연습] 백준 2750 수 정렬하기 https://www.acmicpc.net/problem/2750 2750번: 수 정렬하기 첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 수가 주어진다. 이 수는 절댓값이 1,000보다 작거나 같은 정수이다. 수는 중복되지 않는다. www.acmicpc.net //버전01 import java.util.*; public class Main{ public static void main(String[] args){ Scanner sc = new Scanner(System.in); int cnt = sc.nextInt(); int[] arr = new int[cnt]; for(int i = 0; i < cnt; i++){ arr[i] = sc.nextInt(); }..
[Data Structure 기초] Hashmap Hashmap(해쉬맵) - Map 인터페이스를 상속받아 만들어진 클래스로 Map의 특성을 그대로 갖고있다. - Map은 Key & Value 한 쌍으로 구성된 Entry 객체를 저장하는 자료구조이다. - 키와 값은 모두 객체이다. 값은 중복 저장될 수 있지만 키는 중복 저장될 수 없다. - 만약 기존에 저장된 키와 동일한 키로 값을 저장하면 기존의 값은 없어지고 새로운 값으로 대치된다. - 실제 데이터를 저장시킬 때는 Node 타입의 배열에 저장된다. HashMap에 선언된 Node 타입 변수 및 클래스이다. Hashmap 시간복잡도 접근, 탐색 , 추가 , 삭제 : O(1) 연산 put(K key, V value) key와 value를 저장 remove(Object key) key와 일치하는 기존 데이..
[Data Structure 기초] Array Array(어레이) - 동일한 타임의 연관 데이터를 메모리에 연속적으로 저장하여 하나의 변수에 묶어서 관리하기 위한 자료 구조, 선형 자료구조 - 처음 생성할 때 지정한 자료형만 넣을 수 있다 - 배열의 길이는 고정적이고 먼저 할당해줘야 한다. 따라서 메모리 사용에 효율적이다. Stack 시간복잡도 접근, 탐색 : O(1) 추가 1. 추가하려는 데이터가 맨 뒤가 아니라면, 추가되는 데이터 위치 이후에 있는 모든 데이터들을 한 칸씩 미뤄야 하므로 O(n)의 시간복잡도를 가진다. 2. 추가하려는 데이터의 위치가 맨 뒤이고 배열에 공간이 남아있다면, O(1)의 시간복잡도를 가진다. 삭제 1. 삭제하려는 데이터의 위치가 맨 뒤가 아니라면, O(n)의 시간복잡도를 가진다. 2. 삭제하려는 데이터의 위치가 맨 뒤이..
[Algorithm기초] 합병 정렬, 힙 정렬, 퀵 정렬, 트리 정렬 합병 정렬 (Merge Sort) 배열을 계속 분할해서 길이가 1이 되도록 만들고 인접한 부분끼리 정렬하면서 합병 알고리즘 복잡도 : O(nlogn) 합병정렬구현 의사코드 (Pseudocode) mergeSort(A[], p, r) ▷ A[p...r]을 정렬한다{ if (p < r) then { q ← (p+q)/2; ----------------- ① ▷ p, q의 중간 지점 계산 mergeSort(A, p, q); ---------- ② ▷ 전반부 정렬 mergeSort(A, q+1, r); -------- ③ ▷ 후반부 정렬 merge(A, p, q, r);------------ ④ ▷ 합병 } } merge(A[], p, q, r){ 정렬되어 있는 두 배열 A[p...q]와 A[q+1...r]을 ..
[Data Structure기초] Queue Queue(큐) - 줄을 지어 순서대로 처리되는 자료구조 - 먼저 들어온 데이터가 가장 먼저 나감 (First In First Out , 선입선출) - 마트의 재고관리 부터 운영체제의 프로세스 관리, 너비 우선 탐색(BFS) , 캐시 메모리, 버퍼 등에서 사용됨 Stack 시간복잡도 삽입( enqueue ) : O(1) 삭제( dequeue ) : O(1) 연산 enqueue(Object data) 데이터를 넣는 함수 ( add(data), offer(data) ) dequeue() 데이터를 꺼내는 함수( remove(), poll() ) peek() 요소를 읽어옴, 비어있으면 null isEmpty() 큐가 비어있는지 확인 isFull() 큐가 꽉 차있는지 확인 element() 큐가 비었을 때 요소를..
[Java연습] 스택 두 개의 문자열 비교 import java.util.Stack; //20240220 두 문자열 비교 // - 단 #은 백스페이스로 바로 이전의 문자를 삭제한다고 가정 public class stackPractice05 { public static boolean stringCompare(String s1, String s2){ String s1After = doBackSpace(s1); String s2After = doBackSpace(s2); return s1After.equals(s2After); } public static String doBackSpace(String s){ Stack stack = new Stack(); for (char c : s.toCharArray()) { if(c == '#' && !stack..

티스토리툴바