notcherry

에라토스테네스의 체 원리 1. 주어진 범위까지 배열을 생성하고 2부터 탐색 시작. 2. 선택한 수의 모든 배수를 삭제한다. 3. 다음 지워지지 않는 수를 선택하여 배수를 모두 삭제한다. 3. 앞의 과정을 반복한다. 시간 복잡도는 일반적으로 O(nlogn)이다. 뒤로 갈 수록 삭제된 데이터가 많아 탐색할 수가 적어지기 때문이다. 백준 1929에서 에라토스테네스의 체 적용해보기 public class 소수_구하기 { public static void main(String[] args) { Scanner sc = new Scanner(System.in); int m = sc.nextInt(); int n = sc.nextInt(); int[] a = new int[n+1]; for (int i = 1; i

errors.EADDRINUSE: 로컬에서 로컬로 요청을 넣는 상황에서, 로컬이 사용할 수 있는 포트 개수가 모두 찼을 때 값이 나온다.(서버가 죽은 상태는 아) 포트가 같은 (내가 내 컴퓨터에 요청을 보내는 경우와 같은) 경우 제대로 측정하기 어렵다. 따라서 가용 포트번호가 없을 때 파란색 막대 그래프가 생기는 것이라고 볼 수 있겠다! 데드락이 걸리는 이유 1초에 10개를 처리할 수 있는 상황에 20개씩 요청이 들어온다면, 10개는 처리되지만 10개는 쌓이는 상황이온다. 10초 후, 더 이상 요청을 받지 않는다고 해도 쌓인 100개의 요청을 처리하느라 10초가 더 필요한 상황인데 이렇게 기존 요청도 처리하면서 새 요청까지 받아야 하는 상황이 오면 데드락에 걸린다. 서버 입장에서 이것을 방지하기 위해 타..

그리디 알고리즘이란 현재 상태에서 보는 선택지 중 최선의 선택지가 전체 선택지 중 최선의 선택지라고 가정하는 알고리즘이다. 수행 과정 1. 해 선택 : 최선의 선택지를 해로 선택한다. 2. 적절성 검사 : 전체 문제의 제약 조건에 벗어나지 않는지 검사한다. 3. 1~2 반복 백준 11047에서 그리디를 적용하기 위해 살펴보면, 최대한 큰 금액의 동전으로 구성하는 것이 최선의 선택지임을 알 수 있다. public class 동전개수의_최솟값_구하기 { public static void main(String[] args) { Scanner sc = new Scanner(System.in); int n = sc.nextInt(); int k = sc.nextInt(); int a[] = new int[n]; ..

[너비 우선 탐색 BFS] 도 그래프를 완전 탐색하는 방법 중 하나로 시작 노드에서 출발해 시작노드를 기준으로 가까운 노드를 먼저 방문하면서 탐색하는 알고리즘(FIFO) 입니다. 선입선출 방식으로 탐색하므로 큐를 이용해 구현합니다. 너비 우선 탐색의 핵심 이론 1.BFS를 시작할 노드를 정한 후 사용할 자료구조 초기화 하기 (DFS와 동일하지만 스택대신 큐를 사용한다는 점에서 다름) 2. 큐에서 노드를 꺼낸 후 꺼낸 노드의 인접 노드를 다시 큐에 삽입하기 3. 큐 자료구조에 값이 없을 때 까지 반복 백준 2178 미로 찾기 문제에 적용해보기 public class 미로탐색 { static int[] dx = {0,1,0,-1}; static int[] dy = {1,0,-1,0}; //각각 위, 오른쪽,..