Study for Backend (91) 썸네일형 리스트형 [Data Structure 기초연습] HashTable - 해시 충돌 해결 - 개방 주소법 ( 선형 탐사법 ) import java.util.Hashtable; import java.util.Map; //해시 충돌 해결 - 개방 주소법 ( 선형 탐사법 ) class MyHashTable2 extends MyHashTable{ MyHashTable2(int size){ super(size); } public void setValue(int key , int data){ int idx = this.getHash(key); if (this.elemCnt == this.table.length){ System.out.println("Hash table is full!"); return; }else if (this.table[idx] == null){ //데이터가 할당되지 않은 상태라면 this.table[idx] = da.. [Java 기초연습] 프로그래머스 - 행성 X3 https://www.acmicpc.net/problem/2830 import java.io.*; public class Main { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); int N = Integer.parseInt(br.readLine()); int[] binaryCnt = new int[20]; // 1,000,000의 이진 표현은 최대 20비트 필요 int name; long answer = 0L; for (int i = 0; i < N; i++) { name = Integer.parseInt(br... [Java 기초연습] 프로그래머스 - 짝수는 싫어요 프로그래머스 - 짝수는 싫어요 https://school.programmers.co.kr/learn/courses/30/lessons/120813?language=java //버전 01 class Solution { public int[] solution(int n) { int[] answer = {}; if(n % 2 == 0){ answer = new int[n/2]; }else{ answer = new int[(n/2)+1]; } int cnt = 0; for(int i=0; i [Data Structure 기초] HashTable HashTable(해쉬테이블) - key와 value를 대응시켜 저장하는 선형 데이터 구조 - key 를 통해 해당 데이터에 빠르게 접근 가능 - 키를 특정 계산식에 넣어 나온 결과를 사용하여 값에 접근하는 과정을 Hashing이라고 함 - 병렬 프로그래밍을 지원하여 병렬 처리를 하면서 자원의 동기화를 고려해야 하는 상황일 때 사용하기 적합 해시 충돌 해결 방법 1. 개방 주소법(Open Address) : 충돌 시, 테이블에서 비어있는 공간의 hash를 찾아 데이터를 저장하고 hash와 value가 1:1 관계 유지 비어있는 공간 탐색 방법에 따라 분류 - 선형 탐사법(Linear Probing) : 충돌 발생 지점부터 이후의 빈 공간을 순차적으로 탐사, 반복된 충돌 발생시 해당 지점 주변에 데이터가 .. [Java연습] 별 찍기 //for문 연습 - 별찍기 import java.util.Scanner; public class javaBasicPractice04 { public static void solution(int n , int type){ if(type == 1){ type1(n); }else if(type == 2){ type2(n); }else if(type == 3){ type3(n); }else if(type == 4){ type4(n); }else if(type == 5){ type5(n); } } public static void type1(int n){ System.out.println("=== Type1 ==="); for (int i = 0; i < n; i++) { for (int j = 0; j < n.. [Algorithm 기초] 투 포인터 Two Pointer (투 포인터) - 두 개의 포인터를 사용하여 문자열, 배열, List에서 원하는 값을 찾는 선형 구조 알고리즘 - 포인터 배치 방법 --> 같은 방향에서 시작 : 첫 번째 원소에 둘 다 배치 --> 서로 다른 방향에서 시작 : 첫 번째 원소와 마지막 원소에 배치 - 한 번의 반복으로 모든 요소를 처리하기에 효율적이며 다중 for문의 복잡도를 좀 더 선형적으로 풀 수 있음 알고리즘 복잡도 : O(n) 투 포인터의 종류 1. 고정 길이 슬라이딩 윈도우 - 고정된 길이의 윈도우를 사용하여 배열이나 리스트를 탐색 - 윈도우의 크기를 일정하게 유지하면서 왼쪽 포인터와 오른쪽 포인터를 이동시키며 필요한 계산을 수행 - 부분 배열의 합이나 평균을 계산하는 등의 문제에 사용 2. 가변 길이 슬라이.. [Algoritm 기초연습] 백준 1920 수 찾기 https://www.acmicpc.net/problem/1920 1920번: 수 찾기 첫째 줄에 자연수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 줄에는 N개의 정수 A[1], A[2], …, A[N]이 주어진다. 다음 줄에는 M(1 ≤ M ≤ 100,000)이 주어진다. 다음 줄에는 M개의 수들이 주어지는데, 이 수들 www.acmicpc.net //이진탐색 scanner 사용 버전 public class binarySearchPractice06 { public static int binarySearch(int[] array, int target){ if (array == null || array.length == 0){ return -1; } int left = 0; int right = .. [Algorithm 기초] 이진 탐색 이진 탐색 (Binary Search) - 정렬된 상태의 데이터에서 특정값을 빠르게 탐색하는 방법 - 찾고자 하는 값과 데이터 중앙에 있는 값과 비교 - 찾고자 하는 값이 더 작으면 데이터 왼쪽 부분에서 이진 탐색 - 찾고자 하는 값이 더 크면 데이터 오른쪽 부분에서 이진 탐색 알고리즘 복잡도 : O(logn) //이진탐색 사용예제01 //20240224 알고리즘 - 이진 탐색 public class binarySearch { //반복문 구조 버전 public static int binarySearch(int arr[] , int target){ int left = 0; int right = arr.length - 1; while (left right){ return -1; } int mid = (lef.. [Data Structure 기초] Heap Heap (힙) - 데이터에서 최대값과 최소값을 빠르게 찾기 위해 고안된 완전 이진 트리 - 반 정렬 상태이며 중복 값이 허용된다. Heap 시간복잡도 O(logn) import java.util.PriorityQueue; public class HeapExample { public static void main(String[] args) { // Integer를 저장하는 최소 힙 생성 PriorityQueue minHeap = new PriorityQueue(); // 요소 추가 minHeap.offer(5); minHeap.offer(2); minHeap.offer(8); minHeap.offer(1); // 최소값 확인 int minValue = minHeap.peek(); System.out.pr.. [Data Structure 기초] Deque Deque(덱 혹은 데크) - 양쪽에서 삽입과 삭제가 모두 가능한 자료구조 - 두 개의 포인터를 사용하여, 양쪽에서 삭제와 삽입을 발생시킬 수 있다. - 큐와 스택을 합친 형태로 생각할 수 있다. Stack 시간복잡도 삽입 : O(1) 삭제 : O(1) 탐색 : O(1) 연산 addFirst() 맨 앞에서 데이터를 삽입. 용량을 초과하는 경우 Exception 발생 offerFirst() 맨 앞에서 데이터를 삽입. 용량을 초과하는 경우 false 리턴 addLast() 맨 뒤에서 데이터를 삽입. 용량을 초과하는 경우 Exception 발생 offerLast() 맨 뒤에서 데이터를 삽입. 용량을 초과하는 경우 false 리턴 removeFirst() 맨 앞에서 데이터를 삭제. 비어있다면 Exception .. 이전 1 2 3 4 5 6 7 8 ··· 10 다음
