Coding Story

AWS 리전 물리적으로 위치가 다른 나라들을 대상으로 동일 서버를 사용하게 되면 재해 등으로 서버가 정지되었을 때 대처가 어렵다.이러한 이유로 아마존은 주요 국가에 리전을 구축하여 해당 위치에서 가장 가까운 곳에서 클라우드 서비스를 이용할 수 있도록 서비스를 제공한다. 리전이란 AWS가 전 세계에서 데이터 센터를 클러스터링하는 물리적 위치 리전끼리는 aws 백본 네트워크로 연결되어 있음 2개 이상의 가용 영역으로 구성 각 AWS 리전은 완전한 이중화 및 네트워크 연결 제공 가용영역 AZ 각 리전에는 다수의 가용 영역이 있음 AZ(가용 영역)는 AWS 리전의 중복 전력, 네트워킹 및 연결이 제공되는 하나 이상의 개별 데이터 센터로 구성 가용영역과 외부(인터넷) 연결을 위한 이중화된 트랜짓 센터(엣지) 가 ..

https://www.acmicpc.net/problem/2089 2089번: -2진수 -2진법은 부호 없는 2진수로 표현이 된다. 2진법에서는 20, 21, 22, 23이 표현 되지만 -2진법에서는 (-2)0 = 1, (-2)1 = -2, (-2)2 = 4, (-2)3 = -8을 표현한다. 10진수로 1부터 표현하자면 1, 110, 111, 100, 101, 11010, 110 www.acmicpc.net import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; public class Main{ public static void main(String[] args) throws IOExceptio..

https://www.acmicpc.net/problem/17103 17103번: 골드바흐 파티션 첫째 줄에 테스트 케이스의 개수 T (1 ≤ T ≤ 100)가 주어진다. 각 테스트 케이스는 한 줄로 이루어져 있고, 정수 N은 짝수이고, 2 < N ≤ 1,000,000을 만족한다. www.acmicpc.net import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; public class Main{ static int[] arr = new int[1000001]; public static int partition(int n){ int answer = 0; // 골든바흐 파티션 찾기 for(int ..

https://www.acmicpc.net/problem/1373 1373번: 2진수 8진수 첫째 줄에 2진수가 주어진다. 주어지는 수의 길이는 1,000,000을 넘지 않는다. www.acmicpc.net import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; public class Main{ public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); String str = br.readLine(); StringBu..

https://www.acmicpc.net/problem/17087 17087번: 숨바꼭질 6 수빈이는 동생 N명과 숨바꼭질을 하고 있다. 수빈이는 현재 점 S에 있고, 동생은 A1, A2, ..., AN에 있다. 수빈이는 걸어서 이동을 할 수 있다. 수빈이의 위치가 X일때 걷는다면 1초 후에 X+D나 X-D로 이 www.acmicpc.net import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.ArrayList; import java.util.StringTokenizer; public class Main{ public static int gcd(int a, in..

https://www.acmicpc.net/problem/9613 9613번: GCD 합 첫째 줄에 테스트 케이스의 개수 t (1 ≤ t ≤ 100)이 주어진다. 각 테스트 케이스는 한 줄로 이루어져 있다. 각 테스트 케이스는 수의 개수 n (1 < n ≤ 100)가 주어지고, 다음에는 n개의 수가 주어진 www.acmicpc.net import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.ArrayList; import java.util.StringTokenizer; public class Main{ public static int gcd(int a, int b){..

자료구조와 알고리즘 자료구조의 필요성 컴퓨터에서 처리할 자료들을 효율적으로 관리하기 위해 구조화 자료의 특성에 따라 자료의 형태를 구성하고 처리하고 저장 자료구조란? 자료를 효율적으로 처리할 수 있도록 자료를 조직화하고 체계적으로 구조화하여 표현한 것이다. 프로그램 = 자료구조 + 알고리즘 알고리즘이란? 해야 할 일을 컴퓨터가 수행하여야 할 단계적인 절차를 자세히 기술하는 것 컴퓨터로 문제를 풀기 위한 단계적인 절차 문제와 컴퓨터가 주어진 상태에서 문제를 해결하는 방법을 정밀하게 장치가 이해할 수 있는 언어로 기술한 것 특정한 일을 수행하는 명령어들의 집합(명령어란 컴퓨터에서 수행되는 문장들) 알고리즘의 조건 입력 : 0개 이상의 입력이 존재하여야 한다. 출력 : 1개 이상의 출력이 존재하여야 한다. 명..

그래프 탐색 알고리즘 그래프 탐색은 하나의 정점으로부터 시작하여 차례대로 모든 정점을 한 번씩 방문하는 것이다. 많은 문제들이 단순히 그래프의 노드를 탐색하는 것으로 해결된다. 그래프의 탐색 방법은 깊이 우선 탐색(DFS)과 너비 우선 탐색(BFS)의 두가지가 있다. 깊이 우선 탐색(DFS: depth first search) 그래프의 시작 정점에서 한 방향으로 계속 가다가 더 이상 갈 수 없게 되면 다시 가장 가까운 갈림길로 돌아와서 다른 방향으로 다시 탐색을 진행한다. 알고리즘 자기 자신을 다시 호출하는 순환 알고리즘의 형태를 띈다. 그래프의 시작 정점에서 출발하여 시작 정점 v를 방문하였다고 표시한다. v에 인접한 정점들 중에서 아직 방문하지 않은 정점 u를 선택하여 깊이 우선 탐색을 다시 시작한다..

그래프 그래프의 개념 객체 사이의 연결 관계를 표현할 수 있는 자료구조 정점(vertex)과 간선(edge)으로 이루어진 자료구조 그래프와 관련된 용어 정점(vertex): 노드(node)라고도 불리며, 여러가지 특성을 가질 수 있는 객체 간선(edge): 링크(link)라고도 불리며, 정점을 연결하는 선 인접 정점(adjecent vertex): 간선에 의해 직접 연결된 정점 정점의 차수(degree): 무방향 그래프에서 하나의 정점에 인접한 정점의 수 진입 차수(in-degree): 방향 그래프에서 외부에서 오는 간선의 수 진출 차수(out-degree): 방향 그래프에서 외부로 향하는 간선의 수 경로 길이(path length): 경로를 구성하는 데 사용된 간선의 수 단순 경로(simple path..

머신 스케줄링 어떤 작업을 처리하는 동일한 기계가 m개 존재하고 처리해야 할 작업이 n개 있다고 하자. 이 기계를 풀가동하여 가장 최소의 시간에 작업들을 끝내고자 한다. 이것을 머신 스케줄링이라한다. 이 문제의 최적의 해를 찾는것은 어렵지만 LPT(longest processing time first) 방법을 통해 근사의 해를 찾을 수 있다. LPT(Longest Processing Time first) LPT는 가장 긴 작업을 우선적으로 가장 먼저 사용가능하게 되는 기계에 할당하는 것이다. 맨 위의 표는 각 작업의 기계 사용 시간이다. 미리 정렬되어 있다고 가정한다. 최소 힙은 모든 기계의 종료시간을 저장하고 있다. 초기의 모든 기계의 종료시간은 0이고, 힙에서 최소 종료시간을 가지는 기계를 삭제하여 ..