공부공간

www.acmicpc.net/problem/1766 1766번: 문제집 첫째 줄에 문제의 수 N(1 ≤ N ≤ 32,000)과 먼저 푸는 것이 좋은 문제에 대한 정보의 개수 M(1 ≤ M ≤ 100,000)이 주어진다. 둘째 줄부터 M개의 줄에 걸쳐 두 정수의 순서쌍 A,B가 빈칸을 사이에 두고 주 www.acmicpc.net 문제집에서 순서가 존재하기때문에 차수를 고려한 위상정렬을 진행해준다. 다만, 문제 번호가 1-N 까지 문제중에서 차수가 0 이되었을때에 우선순위를 부여해야한다 ( 쉬운문제 부터 푼다 ) 따라서, 우선순위큐에 문제번호가 낮은 차수가 0 인 노드부터 처리해주자 import java.io.BufferedReader; import java.io.InputStreamReader; impor..

www.acmicpc.net/problem/10282 1717번: 집합의 표현 첫째 줄에 n(1≤n≤1,000,000), m(1≤m≤100,000)이 주어진다. m은 입력으로 주어지는 연산의 개수이다. 다음 m개의 줄에는 각각의 연산이 주어진다. 합집합은 0 a b의 형태로 입력이 주어진다. 이는 a가 www.acmicpc.net 해킹당하는 컴퓨터의 개수와 시간을 구하기위해 다익스트라 알고리즘을 사용한다. 컴퓨터의 개수는 다익스트라알고리즘을 돌면서 만나는 노드의 개수이고, 시간은 다익스트라로 구한 최단경로중 길이가 가장 큰 것이다. 반례로, 아무컴퓨터와 연결되어있지 않은경우, 1대만 감염되어야 한다. 시간은 0초 import java.io.BufferedReader; import java.io.Input..

www.acmicpc.net/problem/6549 6549번: 히스토그램에서 가장 큰 직사각형 입력은 테스트 케이스 여러 개로 이루어져 있다. 각 테스트 케이스는 한 줄로 이루어져 있고, 직사각형의 수 n이 가장 처음으로 주어진다. (1 ≤ n ≤ 100,000) 그 다음 n개의 정수 h1, ..., hn (0 ≤ hi ≤ www.acmicpc.net N이 10만이기때문에 일반적인 모든구간을 탐색하는 N^2풀이시 시간초과를 만나게된다. 복잡도를 줄이기위해 어떤 직사각형을 생각해보면 그 높이는 입력으로 들어온 것들중 한개일 것이다. 너비는 적당한 구간일 것이고, 따라서 높이를 N개 탐색하는데, 구간에 대해서 최솟값을 반환해주는 함수가있다면, 높이를 최소부터 최대까지 탐색할수 있을것이다. 그러면 구간 점 ..

www.acmicpc.net/problem/14719 14719번: 빗물 첫 번째 줄에는 2차원 세계의 세로 길이 H과 2차원 세계의 가로 길이 W가 주어진다. (1 ≤ H, W ≤ 500) 두 번째 줄에는 블록이 쌓인 높이를 의미하는 0이상 H이하의 정수가 2차원 세계의 맨 왼쪽 위치 www.acmicpc.net 모 기업 코딩테스트에서 출제되었던 문제이다. 배열의 앞,뒤로 탐색하면서 나보다 큰 벽을 만났을때, 그 중간 벽들과의 차이를 더해준다. 시간복잡도 O(2*500)으로 처리가능하다 import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.StringTokenizer; public class 빗물 { publi..

www.acmicpc.net/problem/1167 1167번: 트리의 지름 트리가 입력으로 주어진다. 먼저 첫 번째 줄에서는 트리의 정점의 개수 V가 주어지고 (2≤V≤100,000)둘째 줄부터 V개의 줄에 걸쳐 간선의 정보가 다음과 같이 주어진다. (정점 번호는 1부터 V까지 www.acmicpc.net 트리의 지름을 구하는 알고리즘(?)은 특정점 ( 아무점 ) 에서 가장 먼 하나의 노드를 선택하고 그 노드에서 가장 먼점을 선택하면 된다. ( 증명은 생략 ) 최장거리계산을 위해, 다익스트라 알고리즘을 사용하여서 각 노드까지의 최단거리 중 큰값을 찾고, 그 노드부터 다시 최단거리중 최장거리를 찾는다. import java.io.BufferedReader; import java.io.InputStream..

www.acmicpc.net/problem/1783717837번: 새로운 게임 2재현이는 주변을 살펴보던 중 체스판과 말을 이용해서 새로운 게임을 만들기로 했다. 새로운 게임은 크기가 N×N인 체스판에서 진행되고, 사용하는 말의 개수는 K개이다. 말은 원판모양이고, 하�www.acmicpc.net3 가지를 나누어서 생각해보면, 움직이는 다음 좌표가 흰색인경우잠깐 TEMP 리스트에 담고 진행한다. 빨간색인경우 TEMP 리스트를 뒤집고 진행한다. 파랑색인경우, 또 3가지로 나뉜다.파랑 -> 흰 이면 현재값만 방향을 바꾸어주고 흰색처리파랑 -> 빨 이면 현재값만 방향을 바꾸어주고 빨강색처리파->파이면 이동하지 않는다. 매턴중간에 4개가 쌓였는지 체크하기위해 좌표를 가지고다닌다.import java.io.Buf..

요즘은 싸피에서 Django기반의 RESTful API를 제작하면서 DB부하를 줄이기 위한 노력을 하고있다. 간단하면서도, 강력한 Caching기법을 이용하여 시간을 줄여보고자한다. Redis는 Key-Value 쌍으로 Caching을 지원한다 -> 시간복잡도도 O(1)에 처리하면서 상당히 쉽다. 먼저 Docker Image를 이용하여 Redis 서버를 띄우고 Django에서 연결해서 구현해보고자 한다. (사실방법은 여러가지겠지만, 가장간단하게..) Docker에서 Redis 설치하고 Redis-net 띄우기 cmd 창을 열고.. ( docker는 v19.03.8입니다 ) 1 ) docker pull redis:alpine -> docker images 입력후 " redis " 확인 2 ) docker ..

www.acmicpc.net/problem/8983 8983번: 사냥꾼 입력의 첫 줄에는 사대의 수 M (1 ≤ M ≤ 100,000), 동물의 수 N (1 ≤ N ≤ 100,000), 사정거리 L (1 ≤ L ≤ 1,000,000,000)이 빈칸을 사이에 두고 주어진다. 두 번째 줄에는 사대의 위치를 나타내는 M개의 x-좌 www.acmicpc.net 사냥꾼의 사정거리를 계산할 때에, 동물에서 가장가짜운 사대의 왼쪽 오른쪽만 보면된다. 전체탐색 x 이분탐색으로 사대의 위치를 찾고, 정확히 찾는다면 L값이 Y값보다 같거나 큰지의 여부를 파악하고, 찾지못했다면, 양옆의 사대의 X값의 차이 + y 값이 L사정거리보다 같거나 작으면 범위안에 있는 것이다. import java.io.BufferedReader;..