반응형

* 핵심

PriorityQueue를 이용하여 pq에 있는 값중 작은 두를 곱해가는 방식


* 문제

문제

안녕? 내 이름은 ntopia!

나는 원래 지구에 살고 있던 평범한 20대 청년이었어. 어느 날 길을 걷다가 괴한의 칼에 찔려 죽어버렸어. 그런데 이게 무슨 일이람! 정신을 차려보니 이세계에 떨어져 버렸지 뭐야. 여기에서 나는 슬라임을 전문으로 연구하는 슬라임 연구자가 되어버린 것 같아. 나는 지금 아주 중요한 연구를 진행하고 있어. 이 연구가 성공하면 나는 내가 살던 세계로 돌아갈 수 있게 될 거야. 이 연구를 도와주지 않겠니?

이곳의 슬라임은 모두 슬라임 에너지라는 것을 갖고 있고 그 양은 2 이상의 자연수로 표현돼. 나는 슬라임을 합성했을 때 슬라임 에너지가 어떻게 변화하는지에 대해 연구하고 있어.

슬라임 합성 과정은 2마리를 합성해서 1마리를 만들어내는 식으로 이루어져. A만큼의 슬라임 에너지를 가진 슬라임과 B만큼의 슬라임 에너지를 갖고 있는 슬라임이 있었다고 해보자. 이 슬라임 2마리를 합성하면 슬라임 에너지가 A × B 인 슬라임을 만들 수 있어.

그리고 슬라임 합성 기술이 아직 완벽하지 않아서 슬라임을 합성할 때마다 크나큰 전기 에너지가 필요해. 구체적으로, A만큼의 슬라임 에너지를 가진 슬라임과 B만큼의 슬라임 에너지를 가진 슬라임을 합성하려면 A × B 만큼의 전기 에너지가 필요해.

에너지가 4인 슬라임과 에너지가 6인 슬라임을 합성한 모습. 4 × 6의 전기 에너지를 사용해 슬라임 에너지가 24인 슬라임이 합성되었다.

나에겐 지금 N마리의 슬라임이 있어. 이 슬라임들을 모두 적절히 합성해서 1마리의 슬라임으로 만들려고 해. 그런데 내가 소속된 연구소에서 각 합성 단계마다 필요한 전기 에너지들을 모두 곱한 값을 나에게 비용으로 청구하겠다고 했지 뭐야. 그래서 이 값이 최소가 되도록 합성을 적절히 수행하는 것이 내 연구의 목표야.

내 연구를 도와줘! 부탁이야!!

입력

첫 번째 줄에 테스트 케이스의 수 T 가 주어지고, 이어서 T 개의 테스트 케이스가 주어진다.

각 테스트 케이스의 첫 번째 줄에는 슬라임의 수 N (1 ≤ N ≤ 60)이 주어지고, 두 번째 줄에는 N 개의 자연수가 주어진다. i번째 자연수 Ci (2 ≤ Ci ≤ 2 × 1018) 는 i번째 슬라임의 슬라임 에너지를 나타낸다. 끝까지 합성하고 난 후에 생기는 슬라임의 에너지의 양이 2 × 1018 이하라는 것이 보장된다.

모든 테스트 케이스에 대한 N 의 총합이 1, 000, 000을 넘지 않음이 보장된다.

출력

각 테스트 케이스마다 슬라임을 끝까지 합성했을 때 청구될 비용의 최솟값을 1, 000, 000, 007로 나눈 나머지를 출력한다. 전기 에너지가 전혀 필요하지 않은 경우엔 1 을 출력한다.


* 소스코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
import java.io.*;
import java.util.*;
 
public class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int t = Integer.parseInt(br.readLine());
        while (t-- > 0) {
            int n = Integer.parseInt(br.readLine());
            StringTokenizer stk = new StringTokenizer(br.readLine());
            PriorityQueue<Long> pq = new PriorityQueue<>(new Comparator<Long>() {
                @Override
                public int compare(Long o1, Long o2) {
                    return Long.compare(o1,o2); //오름차순
                    //return o1-o2;   //오름차순
                }
            });
            for (int i = 0; i < n; i++) {
                pq.add(Long.parseLong(stk.nextToken()));
            }
            long sum = 1;
            final int mod = 1000000007;
            while (pq.size() >= 2) {
                Long tmp = (pq.poll() * pq.poll());
                pq.add(tmp);        //O(logN)
                sum = sum * (tmp % mod) % mod;
            }
            System.out.println(sum);
        }
    } // End of Main
}
cs





반응형
저작자표시 비영리 변경금지

'∙Algorithm' 카테고리의 다른 글

[Algorithm] 백준/11724 :: 연결 요소의 개수  (0) 2018.12.29
[Algorithm] 백준/1181 :: 단어 정렬  (0) 2018.12.29
[Algorithm] 백준/1620 :: 나는야 포켓몬 마스터 이다솜  (0) 2018.12.27
[Algorithm] 백준/2750 :: 수 정렬하기  (0) 2018.12.27
반응형

* ArrayList vs LinkedList

ArrayList와 LinktedList 둘다 모두 Java에서 제공하는 List 인터페이스를 구현한 Collection 구현체이다.

하지만 내부적으로 작동하는 방식은 다르다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
import java.io.*;
import java.util.*;
 
public class Main {
    public static void main(String[] args) throws Exception {
        ArrayList<String> alist = new ArrayList<>();
        alist.add(0,"First");           //O(1)
        alist.add("Second");            //O(1)
        alist.add(2, "Third");          //O(1)
        alist.remove(1);                //O(n)
 
        alist.get(1);                   //O(1)
 
        LinkedList<String> nlist = new LinkedList<>();
        nlist.addFirst("First");        //O(1)
        nlist.add("Second");            //O(1)
        nlist.addLast("Third");         //O(1)
        nlist.pollFirst();              //O(1)
        nlist.pollLast();               //O(1)
 
        nlist.get(0);                   //O(n)
    }
}
 
cs

알고리즘 문제를 풀면서 가장 중요한 ArrayList와 LinkedList의 차이점은 시간복잡도의 차이라고 볼 수 있다.

ArrayList는 동적으로 Array를 생성한다고 생각하면 배열과 비슷한 점이 많다.

ArrayList는 remove 시에 O(n)의 시간복잡도를 가진다.

i번째 배열을 지우고 최대 n만큼 앞으로 이동해야 하기 때문이다.

삽입 또한 맨 뒤에삽입과 중간삽입으로 나눌 수 있는데, 중간에 삽입하는 경우 O(n), 맨 뒤에 삽입하는 경우 O(1)의 시간복잡도를 가진다.

하지만 get 메소드는 해당 index를 바로 가져오기 때문에 O(1)의 시간복잡도를 가진다.


이에 비해, LinkedList는 Node를 사용하기 때문에 add, poll 시에 O(1)의 시간복잡도를 가진다.

하지만 get 메소드 사용시에 앞에서부터 찾기 때문에 O(n)의 시간복잡도를 가진다.

이를 정리하면 다음과 같다.

 

 ArrayList

 LinkedList

삽입

 add  >> O(1) or O(n)

add, addFirst, addLast >> O(1)

삭제 

 remove >> O(n)

poll, pollFirst, pollLast >> O(1)

get 

 get(index) >> O(1)

get(index) >> O(n) 

반응형
저작자표시 비영리 변경금지

'∙Data Structure' 카테고리의 다른 글

[Data Structure] Heap (힙)  (0) 2019.01.17
[Data Structure] Stack (스텍)  (0) 2019.01.17
[Data Structure] Queue (큐)  (0) 2019.01.17
[Data Structure] LinkedList (연결리스트)  (0) 2019.01.17
반응형

* 핵심

HashMap으로 중복 제거한다.

<key, value> 에 <포켓몬 이름, 포켓몬 번호> 를 저장하고

str[포켓몬 번호] = 포켓몬 이름 을 저장한다.


* 문제

입력

첫째 줄에는 도감에 수록되어 있는 포켓몬의 개수 N이랑 내가 맞춰야 하는 문제의 개수 M이 주어져. N과 M은 1보다 크거나 같고, 100,000보다 작거나 같은 자연수인데, 자연수가 뭔지는 알지? 모르면 물어봐도 괜찮아. 나는 언제든지 질문에 답해줄 준비가 되어있어.

둘째 줄부터 N개의 줄에 포켓몬의 번호가 1번인 포켓몬부터 N번에 해당하는 포켓몬까지 한 줄에 하나씩 입력으로 들어와. 포켓몬의 이름은 모두 영어로만 이루어져있고, 또, 음... 첫 글자만 대문자이고, 나머지 문자는 소문자로만 이루어져 있어. 포켓몬 이름의 최대 길이는 20이야. 그 다음 줄부터 총 M개의 줄에 내가 맞춰야하는 문제가 입력으로 들어와. 문제가 알파벳으로만 들어오면 포켓몬 번호를 말해야 하고, 숫자로만 들어오면, 포켓몬 번호에 해당하는 문자를 출력해야해. 입력으로 들어오는 숫자는 반드시 1보다 크거나 같고, N보다 작거나 같고, 입력으로 들어오는 문자는 반드시 도감에 있는 포켓몬의 이름만 주어져. 그럼 화이팅!!!

출력

첫째 줄부터 차례대로 M개의 줄에 각각의 문제에 대한 답을 말해줬으면 좋겠어!!!. 입력으로 숫자가 들어왔다면 그 숫자에 해당하는 포켓몬의 이름을, 문자가 들어왔으면 그 포켓몬의 이름에 해당하는 번호를 출력하면 돼. 그럼 땡큐~

* 소스코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
import java.io.*;
import java.util.*;
 
public class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer stk = new StringTokenizer(br.readLine());
        StringBuilder sb = new StringBuilder();
 
        HashMap<String, Integer> hm = new HashMap<>();
 
        int n = Integer.parseInt(stk.nextToken());
        int m = Integer.parseInt(stk.nextToken());
 
        String[] str = new String[n];
 
        for (int i = 0; i < n; i++) {
            stk = new StringTokenizer(br.readLine());
            String a = stk.nextToken();
            hm.put(a, i+1);
            str[i] = a;
        }
        for (int i = 0; i < m; i++) {
            stk = new StringTokenizer(br.readLine());
            String a = stk.nextToken();
            try {
                Integer.parseInt(a);
                sb.append(str[Integer.parseInt(a)-1]).append("\n");
            } catch (Exception e) {
                sb.append(hm.get(a)).append("\n");
            }
        }
        System.out.println(sb);
    }
}
 
cs


반응형
저작자표시 비영리 변경금지

'∙Algorithm' 카테고리의 다른 글

[Algorithm] 백준/11724 :: 연결 요소의 개수  (0) 2018.12.29
[Algorithm] 백준/1181 :: 단어 정렬  (0) 2018.12.29
[Algorithm] 백준/14698 :: 전생했더니 슬라임 연구자였던 건에 대하여 (Hard)  (0) 2018.12.28
[Algorithm] 백준/2750 :: 수 정렬하기  (0) 2018.12.27
반응형

*핵심

Arrays.sort 사용


* 문제

 

* 소스코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
import java.io.*;
import java.util.*;
public class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer stk = new StringTokenizer(br.readLine());
        StringBuilder sb = new StringBuilder();
        int n = Integer.parseInt(stk.nextToken());
        int[] arr = new int[n];
        for (int i = 0; i < n; i++) {
            stk = new StringTokenizer(br.readLine());
            arr[i] = Integer.parseInt(stk.nextToken());
        }
        Arrays.sort(arr);    // O(n*logN)
        for (int i = 0; i < n; i++) {
            sb.append(arr[i]).append("\n");
        }
        System.out.println(sb);
    }
}
cs


반응형
저작자표시 비영리 변경금지

'∙Algorithm' 카테고리의 다른 글

[Algorithm] 백준/11724 :: 연결 요소의 개수  (0) 2018.12.29
[Algorithm] 백준/1181 :: 단어 정렬  (0) 2018.12.29
[Algorithm] 백준/14698 :: 전생했더니 슬라임 연구자였던 건에 대하여 (Hard)  (0) 2018.12.28
[Algorithm] 백준/1620 :: 나는야 포켓몬 마스터 이다솜  (0) 2018.12.27
반응형

시간복잡도 -> N범위에 따라서 다르다.


O(nlogN) = 10만~50만 

O(n^2) = 0~5천 


1억에 1초로 생각하면 되지만, 정확한 값은 아니다.


BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

StringTokenizer stk = new StringTokenizer(br.readLine());

StringBuilder sb = new StringBuilder();


System.out.print    >> 여러번 출력시 오래 걸림

-> 이를 방지하기 위해 StringBuilder 사용

ex)  sb.append(arr[i]).append("\n");



* 참고 라이브러리

Arrays.sort = O(n*logN)     이므로 자주 사용해도 괜찮음

Arrays.fill(채울 1차원배열, 채울 값)

반응형
저작자표시 비영리 변경금지

'∙Algorithm Tech' 카테고리의 다른 글

[Algorithm Tech] Bitmask(비트마스크)  (0) 2019.01.08
[Algorithm Tech] BackTracking  (0) 2019.01.03
[Algorithm Tech] BFS vs DFS  (0) 2018.12.29
[Algorithm Tech] Stack & Queue & PriorityQueue  (0) 2018.12.13
반응형

* Stack

FILO 방식 (First In Last Out) 

// Stack 선언

Stack<String> st = new Stack<String>();


push(x) : 해당 스택의 제일 상단에 전달된 요소를 삽입함.

pop() : 해당 스택의 제일 상단에 있는(제일 마지막으로 저장된) 요소를 반환하고, 해당 요소를 스택에서 제거함.

size() : 해당 스택에 들어있는 정수의 개수를 출력함.

empty() : 해당 스택이 비어 있으면 true를, 비어 있지 않으면 false를 반환함.

peek() : 해당 스택의 제일 상단에 있는(제일 마지막으로 저장된) 요소를 반환함.



* Queue

FIFO 방식 (First In First Out)

// Queue 선언

Queue<String> q = new LinkedList<String>();


add(E e), offer(E e) : 해당 큐의 맨 뒤에 전달된 요소를 삽입함.

element() : 해당 큐의 맨 앞에 있는(제일 먼저 저장된) 요소를 반환함.

peek() : 해당 큐의 맨 앞에 있는(제일 먼저 저장된) 요소를 반환함.

poll() : 해당 큐의 맨 앞에 있는(제일 먼저 저장된) 요소를 반환하고, 해당 요소를 큐에서 제거함.

remove() : 해당 큐의 맨 앞에 있는(제일 먼저 저장된) 요소를 제거함.


* 우선순위 Queue

Heap Sort 알고리즘 사용

// 우선순위 Queue 선언

PriorityQueue<Integer> pq = new PriorityQueue<>();


우선순위 큐에 저장될 때, Heap Sort의 방식을 거쳐 저장된다. O(nlogn)

Heap Sort는 완전 이진 트리의 일종으로 최댓값, 최솟값을 쉽게 추출할 수 있는 자료구조이다.


우선순위 큐는 큐에서 뺄 때, 우선순위 순서대로 가져온다. 

Default 는 최소 힙(작은 값이 루트 노드)이다. 즉, 숫자가 작을 수록 우선순위가 높다. 

우선순위를 변경하고 싶으면 Comparator 를 사용하면 된다.

pq.add 시에 자동으로 최소/최대 힙을 만족하도록 수정하여 저장되며 이때의 시간복잡도는 O(logN)이다.

1
2
3
4
5
6
7
8
9
PriorityQueue<Integer> pq = new PriorityQueue<>();
 
pq.add(1);
pq.add(3);
pq.add(2);
 
pq.poll();  //1
pq.poll();  //2
pq.poll();  //3
cs


1
2
3
4
5
6
7
8
9
10
11
12
13
PriorityQueue<Integer> pq = new PriorityQueue<>(new Comparator<Integer>() {
    @Override
    public int compare(Integer o1, Integer o2) {
        return Integer.compare(o2, o1);     //내림차순
    }
});
pq.add(1);
pq.add(3);
pq.add(2);
 
pq.poll();  //3
pq.poll();  //2
pq.poll();  //1
cs



반응형
저작자표시 비영리 변경금지

'∙Algorithm Tech' 카테고리의 다른 글

[Algorithm Tech] Bitmask(비트마스크)  (0) 2019.01.08
[Algorithm Tech] BackTracking  (0) 2019.01.03
[Algorithm Tech] BFS vs DFS  (0) 2018.12.29
[Algorithm Tech] 알고리즘 기본 지식  (0) 2018.12.27
반응형

WEB 동작 원리

주소창에 www.naver.com을 입력하면 어떤 일이 일어날까?

면접 질문에서도 종종 나오는 이 방식은 생각보다 간단하다.

방식에 대해 이해하기 전에 IP 주소, 도메인에 대한 사전 지식이 필요하다.


* IP 주소

IP 주소란 많은 컴퓨터들이 인터넷 상에서 서로를 인식하기 위해 지정받은 식별용 번호라고 생각하면 된다.

현재는 IPv4 버전(32비트)로 구성되어 있으며 한번씩은 들어봤을 법한 127.0.0.1 같은 주소를 말한다.

시간이 갈수록 IPv4 주소의 부족으로 IPv6가 생겼는데, 128비트로 구성되어있기 때문에 IP 주소가 부족하지 않다는 특징이 있다.


* 도메인 네임(Domain Name)

IP주소는 12자리의 숫자로 되어있기 때문에 사람이 외우기 힘들다는 단점이 있다.

그렇기 때문에 12자리의 IP 주소를 문자로 표현한 주소를 도메인 네임이라고 한다.

다시 말해서, 도메인 네임은 'naver.com'처럼 몇 개의 의미있는 문자들과 점(.)의 조합으로 구성된다.


도메인 네임은 사람의 편의성을 위해 만든 주소이므로 실제로는 컴퓨터가 이해할 수 있는 IP 주소로 변환하는 작업이 필요하다.

이때 사용할 수 있도록 미리 도메인 네임과 함께 해당하는 IP 주소값을 한 쌍으로 저장하고 있는 데이터베이스를 DNS(Domain Name System) 이라고 부른다.

다시 말해 사람이 도메인 네임으로 입력하면 DNS를 이용해 컴퓨터는 IP 주소를 받아 찾아갈 수 있는 것이다.


* 작동 방식

  1. 사용자가 브라우저에 도메인 네임(www.naver.com)을 입력한다.
  2. 사용자가 입력한 URL 주소 중에서 도메인 네임(domain name) 부분을 DNS 서버에서 검색하고, DNS 서버에서 해당 도메인 네임에 해당하는 IP 주소를 찾아 사용자가 입력한 URL 정보와 함께 전달한다.
  3. 페이지 URL 정보와 전달받은 IP 주소는 HTTP 프로토콜을 사용하여 HTTP 요청 메시지를 생성하고, 이렇게 생성된 HTTP 요청 메시지는 TCP 프로토콜을 사용하여 인터넷을 거쳐 해당 IP 주소의 컴퓨터로 전송된다.
  4. 이렇게 도착한 HTTP 요청 메시지는 HTTP 프로토콜을 사용하여 웹 페이지 URL 정보로 변환되어 웹 페이지 URL 정보에 해당하는 데이터를 검색한다.
  5. 검색된 웹 페이지 데이터는 또 다시 HTTP 프로토콜을 사용하여 HTTP 응답 메시지를 생성하고 TCP 프로토콜을 사용하여 인터넷을 거쳐 원래 컴퓨터로 전송된다.
  6. 도착한 HTTP 응답 메시지는 HTTP 프로토콜을 사용하여 웹 페이지 데이터로 변환되어 웹 브라우저에 의해 출력되어 사용자가 볼 수 있게 된다.


어려운 개념은 아니니 재미삼아 읽어봐도 좋을 것 같다.


출처 : http://tcpschool.com/webbasic/works

반응형
저작자표시 비영리 변경금지

'∙Network' 카테고리의 다른 글

[정보처리기사]TCP/IP  (0) 2020.06.30
[Network] TCP/UDP란?  (0) 2019.03.22
[Network] OSI 7 Layer란?  (0) 2019.03.22
[Network] HTTP와 REST API  (0) 2019.02.13
반응형

대부분의 시중은행은 ‘Oracle DB’라는 제품을 이용해서 데이터, 즉 고객의 돈을 관리한다. 

Oracle DB는 안정성과 성능은 이미 인정받았다. 하지만 비용이 비싸서 큰 회사가 아니면 사용하기 힘들다.


특히, Oracle DB를 쓰는 가장 큰 이유는 RAC(Real application clusters)라는 기능 때문인데, 

RAC는 간단히 말하면 하나의 DB를 여러 서버가 공유하는 기술이다.


하나의 DB를 여러 서버가 공유하기 때문에 서버 하나가 장애가 나도 데이터 정합성이 유지된다. 

즉, 서버 장애 때문에 고객의 돈이 사라지지 않는다는 의미다.



그러나 MySQL은 서버들이 DB를 공유하지 않고 서버마다 다른 DB가 있다. 

이 때문에 MySQL은 마스터와 슬레이브라는 구조의 시스템을 운용한다. 

마스터 서버로 시스템을 운용하면서 슬레이브 서버는 마스터 서버의 데이터를 특정 시점마다 복제한다. 

마스터에 장애가 나도 복제된 데이터를 가지고 있는 슬레이브로 대체해서 운용하면 된다는 이론이다.



그러나 마스터와 슬레이브가 완전 동기화 되지 않는 것이 문제다. 

마스터 서버에서 데이터가 발생한 후 슬레이브에 복제되기 전에 장애가 발생한다면 그 데이터는 유실된다. 

은행의 경우 데이터는 돈이기  때문에 고객의 돈이 사라진다. 은행이 MySQL과 같은 DB를 사용하지 않는 이유다.


카카오뱅크는 MySQL을 사용하면서 이 문제를 해결했다.

슬레이브가 마스터의 데이터를 비동기 방식으로 복제해도 데이터가 유실될 가능성을 막았다는 것이다.



카카오뱅크는 로스리스 리플리케이션(Lossless Replication)이라는 기능과 MHA(Master High Availability)라는 기능을 조합해 데이터 무손실을 유지한다.


로스리스 리플리케이션은 마스터에 변경이 생기면 ‘릴레이 로그’라는 것을 슬레이브에 남긴다. 

슬레이브가 마스터를 복제하기 전에도 릴레이 로그가 남는다. 

이는 마스터가 슬레이브에 데이터를 넘기기 전에 셧다운 된다고 해도, 슬레이브에 남아있는 릴레이 로그를 활용해서 마스터와 똑같은 데이터를 생성할 수 있다는 것이다.

MHA는 이를 기반으로 재빨리 복구하는 역할을 한다.


참고할 레퍼런스가 턱없이 부족함에도 불구하고, 금융업에 MySQL을 도입하였다는 것 자체가 신기한 도전인 것 같다.

반응형
저작자표시 비영리 변경금지

'∙Databases' 카테고리의 다른 글

[정보처리기사]관계 데이터베이스 모델과 언어  (0) 2020.06.30
[정보처리기사]데이터베이스 개념 및 모델링  (0) 2020.06.30
[Databases] Database Sharding(샤딩)이란?  (0) 2019.01.29
[Databases] Oracle ANSI SQL과 INNER/OUTER JOIN 차이  (1) 2018.12.13

티스토리툴바