평범한 연구소

해시 (Hash) key, value 쌍으로 이루어진 데이터 구조 키를 이용해 값을 O(1) 시간 복잡도로 찾을 수 있다. 해시 충돌 (Hash Collision)다른 key를 사용해도 같은 결과가 나오는 경우를 해시 충돌이라고 한다.해시 충돌을 완화하기 위한 접근 방법개방 주소법분리 연결법 개방 주소법 (Open Addressing)특정 값이 들어가야하는 자리(버킷)가 이미 사용되고 있는 경우, 다른 빈 공간을 탐색하여 버킷에 데이터를 삽입한다.대표적인 3가지 방식이 있다.선형 탐사 (Liner Probing)고정된 크기만큼 한 칸씩 옮기면서 빈 버킷을 찾는 방법해시 자료 구조 전체에서 해시 충돌이 균등하게 발생하는 경우 유리한 탐색법이다.구현이 간단하고 캐시 적중률이 높으나 특정 버킷 주변이 모두 채..

동시성한 CPU에서 동시에 여러 작업을 하는 것처럼 보이는 것예시하나의 CPU에서 2개의 프로세스가 있다고 가정해보자.두 개의 프로세스는 아주 짧은 시간에 컨텍스트 스위칭으로 번갈아 실행된다. 이 과정이 우리가 볼 때 동시에 동작하는 것처럼 보이는 것! 경쟁 상태 (Race Condition) 두 개 이상의 스레드가 공유 자원에 동시에 접근할 때, 스레드 간의 실행 순서에 따라 결과가 달라지는 현상경쟁 상태가 발생했다면 원자성과 가시성 모두 보장하지 못했기 때문동시성 문제의 발생을 파악하기 어렵고, 발생하더라도 결함이 아닌 일시적 버그로 여겨질 수 있음 (재현이 안되기 때문)Java에서는 synchronized, Atomic Type, Concurrent Collection 등으로 해결 가능 원자성 (..

합 배열합 배열은 원본 배열을 전처리한 배열합 배열 S 공식 (S=합배열, A=원본배열)S[i] = A[0] + A[1] + A[2] + ... + A[i-1] A[i] ~ A[j] 까지의 합(구간합)을 합 배열 없이 구하는 경우, 시간 복잡도는 O(N)코딩테스트에서 시간 복잡도는 생명🏄‍♀️ 구간 합합 배열을 이용하여 시간 복잡도를 줄이기 위해 사용하는 알고리즘구간 합 공식 (S=합배열)S[j] + S[i-1]  // i ~ j 까지 구간의 합 1차원 배열의 구간 합1. 배열의 구간 합을 구하는 작업을 선행한다.2. 구간 합 공식을 대입하여 결과를 도출한다.백준 11659번 예제로 공부해보자.https://jeongsoyeon.tistory.com/157 2차원 배열의 구간 합나는 2차원 배열의 경우..

package src.main.java.boj;import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.util.StringTokenizer;public class Ex11660 { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); StringTokenizer st = new StringTokenizer(br.readLine()); int size = ..

package src.main.java.boj;import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.util.StringTokenizer;public class Ex11659 { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); StringTokenizer st = new StringTokenizer(br.readLine()); // 배열 size와..

프로젝트 진행 중 디폴트 생성자 관련 버그를 해결하며... 기본 개념을 복습하고자 작성한다!  1. 생성자 Constructor객체가 생성될 때 초기화를 담당하는 메서드new 키워드를 사용2. 생성자의 특징클래스명과 동일한 이름을 가진다반환 타입이 없다 (void도 아님)객체가 생성될 때 자동으로 한 번 호출된다3. 생성자의 종류 3-1. 디폴트 생성자 (Default Constructor)매개변수가 없는 생성자클래스에 생성자가 없으면 컴파일러가 자동으로 기본 생성자를 만든다. public class Student { private String name; private String email; private int age; public Student() { thi..