Info-Tech

Scanner 쓰면 시간초과 날 경우 가 있음 100만개 입력할경우 Scanner 의 경우 약 2500ms가 걸림 (2.5초) 사용법 BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); String s = br.readLine(); // 입력받은 값이 스트링인 경우Int a = br.read(); //입력받은게 int일 때Int b = Integer.parsetInt(br.readLine()); // 엔터까지 입력받을 때 arr = new int[n+2]; StringTokenizer st = new StringTokenizer(br.readLine(), " "); int index = 1; while(st.hasMoreTo..

플로이드 와샬 변의 가중치가 음이거나 양인 가중 그래프에서 최단경로를 찾는 알고리즘 알고리즘 한번 수행시 모든 꼭짓점 쌍 간의 최단 경로의 길이(가중치의 합)을 찾는다. 1 let dist be a |V| × |V| array of minimum distances initialized to ∞ (infinity) 2 for each edge (u,v) 3 dist[u][v] ← w(u,v) // 변 (u,v)의 가중치 4 for each vertex v 5 dist[v][v] ← 06 for k from 1 to |V| 7 for i from 1 to |V| 8 for j from 1 to |V| 9 if dist[i][j] > dist[i][k] + dist[k][j] 10 dist[i][j] ← di..

동적 프로그래밍에서 지나치게 많이 일을 해서 좀 줄여보자는 취지로 만들어졌음. 미래를 생각하는게 아니라, 현재상황에서 최선을 택하는 기법이다. 활동선택문제와 백팩문제에서 쓰인다. 1.활동선택문제 이문제는 한 강의실에서 여러 수업을 진행한다고 했을 때, 가장 많이 할 수 있는 경우를 선택하는 문제이다. Si는 시작시간, Fi는 종료시간이다. 위 표를 보면 a1, a4와 a1,a2는 동시대에 진행되기 때문에 선택을 할 수 없다. 하지만 a1,a3은 선택이 가능하다. 즉 결과적으로 A1, a3, a6,a8 || A1, a3, a7, a9 이 후보지이다. G18을 a1이후, a8 이전으로 보면 선택 될수 있는 후보는 {a3,a5,a6,a7} 이다. 이중에서도 겹치지 않게 골라보면 {a3,a6} {a3,a7} {..

이 문제는 Union-find의 대표적인 문제이다 입력중에서 0인 경우 union을 해주면 되고, 1인 경우 find를 해주어서 루트가 똑같을 경우 YES, 아닐 경우 NO를 출력 해 주면 된다. 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.util.*;public class Main { static int parent[]; static int rank[]; public stati..

이진탐색을 하기 위해서는 데이터가 정렬이 먼저 되어 있어야 한다. 배열 { 1, 2, 4, 5, 6, 10,13,15 } 에서 4 ( = target값) 를 찾는다고 가정하자. 이진탐색의 기본 방법은 left의 Index와 해당 범위 내의 right Index를 2로 나뉘어 mid값을 찾아가는 가정이다. 처음의 mid = (0+7)/2arr[mid] = arr[3] = 5 즉, 우리가 찾고자 하는 값보다는 크다. 그럴 때는 right의 값을 현재 mid - 1을 해준다. 만약 target 값이 컸다면 left = mid+1을 해준다. 두번쨰 mid = (0+2)/2;(right = mid-1)을 해줬음.arr[mid] = arr[1] = 2, 즉 우리가 찾고자 하는 값보다는 작다 세번째 mid = (1+..

disjoint set 이라고도 불리며 서로소 집합이라고도 한다. 우선 서로소 집합이라는 표현부터 알아봐야 한다. 1 2 3 4 5 6 이처럼 각각의 서로다른 요소가 들어있다. 123 4 5 6 1과 2를 합친 상태이다. 123 456 4,5,6 을 합친 상태이다. 즉 이말은 4와 5를 합친 후에 5와 6을 합친 상황이다. 123 456 만약 1과 4를 합치면 이렇게 된다 -> 그 이유는 (1,2)하나의 집합이였고 (4,5,6)집합이 합쳐졌기 때문이다. 즉 두 집합에 속한 요소들을 합치게 되면 두 집합 자체가 합쳐지게 된다. 노드를 트리구조로 만들기 int parent[100];int size[100]for(int i=0; i

파이썬에서 urllib 혹은request를 보낼 때 간혹 이와 같은 오류를 접할 수 있다. 이때 ssl인증을 거쳐갈 임시의 context를 생성 할 수 있다. import ssl ssl._create_default_https_context = ssl._create_unverified_context 위의 구문을 추가해주면 된다. 자세한 원인과 해결 방법은 >> https://stackoverflow.com/questions/27835619/urllib-and-ssl-certificate-verify-failed-error

쇼핑몰에서 판매하는 상품을 ‘0’원에 뿌리는 이벤트로, 준비된 상품수에 맞추어 선착순으로 주문하는 이벤트였습니다. 당시 웹 서버를 담당하는 아키텍쳐 입니다. 회사에서는 모든 서비스가 AWS에서 돌아가는 환경이였습니다.  기존 서버 스택AWS 인스턴스 EC2 4대(2대 web 서버, 1대 db서버, 1대 Redis서버)  문제점이벤트 시작과 동시에 서버 터짐db connection connection error트랜잭션이 제대로 작동하지 않아 구매 가능한 상품보다 초과 구매가 된 상황CPU, Memory 만땅 (인스턴스 부족) 고민 위에서 발생한 문제점들을 하나하나 살펴보기 시작했습니다. 1. DB 서버현재 디비서버는 EC2에서 한대로 운영중이고 Master 한대로 운영중. Select 같은 query는 읽..