개발 블로그

[Elastic Search란?]

간단히 말하면, 다양한 데이터를 위한 검색 엔진이다. 

검색엔진이란 무엇일까? 우리가 흔하게 알고 있는 관계형DB와 비교해서 생각해보자.

관계형 DB는 테이블 안에 행, 열에 맞게 데이터를 쪼개서 넣고 쿼리문으로 데이터를 선별한다.

이와 비교해서 검색엔진은 보다 유연하게 데이터를 넣고, 검색할 수 있다. 

[Elastic Search의 필요성]

시스템을 운영하다 보면, 운영 안정성 향상 및 이슈 대응을 위해 로그를 수집하고 분석해야 하는 일이 잦다.  

그러나 발생하는 로그는 비정형 데이터인 경우가 많으며, 그 양도 많아 많은 양의 로그에서 인사이트를 도출하는 것이 필요한데

이 때 유용하게 사용할 수 있는 것이 Elastic Search 툴이다. 

[ELK Stack이란?]

- Elasticserach : Storage 역할 - 데이터 저장/분석/관리

- Logstash : Data Processing 역할 - 서버 내 로그, 웹 등 다양한 소스에서 데이터 수집하여 입력, 데이터 변환/구조 구척, 데이터 출력/송신

- Kibana : Visualize 역할 - Dashboard를 이용한 탐색

[Elastic Search의 핵심 기능]

=> Inverted Index(역색인) & 형태소 분석 

: 빠르게 문서 탐색 가능

* 역색인의 단점 : 대다수의 문서에서 등장하는 단어라면, 오히려 속도가 떨어짐 -> Stopword(불용어)로 등록하면 인덱스에서도 제겋하고 검색어에 등장해도 무시하도록 되어 있음. 

[RDBMS 와 Elastic serach 비교]

1. 문법

참고 1) 6.0이하 버전의 엘라스틱서치에서는 하나의 인덱스 내부 기능에 따라 데이터 분류 후에 여러 개의 타입을 만들어 사용했지만 현재는 하나의 인덱스에 하나의 타입만을 구성해야 합니다.

참고 2) 매핑은 필드의 구조와 제약조건에 대한 명세를 말하며 관계형 DB의 스키마와 같습니다.

참고 3) 관계형 DB와 엘라스틱서치는 인덱스라는 개념을 다르게 사용하는데, 관계형 DB에서 인덱스는 그저 Where절의 쿼리와 Join을 빠르게 만들어주는 보조데이터의 도구로 사용됩니다.

[Elastic Search 설치]

https://www.elastic.co/kr/downloads/elasticsearch

24.04.21 기준으로 가장 최신 버젼은 8.13.2 버젼이다.

그러나 해당 버젼 설치 시 아래 파일이 실행되지 않는 문제가 있었다. 재설치 / 시스템 환경 설정 - 보안 및 개인정보 보호 / Control + 열기를 해도 실행이 되지 않아, 8.11.2 로 다시 재설치하니 오류가 해결되었다. (Monterey 의 버그인가?)

무튼 위 파일을 실행하고 정상 여부를 확인하기 위해서는 localhost:9200로 접속을 해야한다.

최신 버젼의 elastic은 http가 아닌 https://localhost:9200 으로 접속해야 한다!

위 링크로 접속을 하게 되면 ID와 PW를 입력해야 하는데, 아래 파일일 열리지 않아서 그냥 yml 파일을 수정해버렸다. 

elasticsearch-8.11.2/config/elasticsearch.yml을 실행시키고

xpack.security.enabled: false

xpack.security.enrollment.enabled: false

true -> false 로 바꿔준다. 

그리고나서 elastic search를 재시작 후 localhost 로 접속하면 아래와 같이 정상 접속을 확인할 수 있다. 

[Kibana 설치]

아래 링크에서 Kibana를 다운한다. 

https://www.elastic.co/kr/downloads/past-releases/elasticsearch-8-11-2

설치 후 아래 경로에서 Contol을 누르고 열기를 클릭하여 파일을 실행한다. 

bin/kibana

*주의 ) Elastic Searh와 버젼이 다르면 아래와 같이 뜬다. 버젼을 맞추도록 하자. 

[2024-04-21T13:47:26.658+09:00][ERROR][elasticsearch-service] This version of Kibana (v8.13.2) is incompatible with the following Elasticsearch nodes in your cluster: v8.11.2 @ 192.168.0.2:9200 (127.0.0.1)

실행 후, http://localhost:5601 로 접속해보자. 

[실습]

Sample Data를 활용해보자. 이커머스 주문 데이터를 Add 해보았다. 

View Data > Discover 를 클릭한다. 

확장 버튼을 누르면 세부 내용을 볼 수 있다. Field(RDBMS의 열) 를 확인할 수 있고, 각 Field 값의 Value도 확인 가능하다.

RDBMS에서는 하나의 열에 하나의 데이터 타입만 가질 수 있었지만, Elastic에서의 필드는 동적이라, 여러개의 데이터 타입을 가질 수 있다. 

JSON 데이터도 확인 가능하다. 

{
  "_index": "kibana_sample_data_ecommerce",
  "_id": "G8JI_44BBQw1fKj0hGME",
  "_version": 1,
  "_score": 0,
  "_source": {
    "category": [
      "Men's Accessories",
      "Men's Shoes"
    ],
    "currency": "EUR",
    "customer_first_name": "Samir",
    "customer_full_name": "Samir Moss",
    "customer_gender": "MALE",
    "customer_id": 34,
    "customer_last_name": "Moss",
    "customer_phone": "",
    "day_of_week": "Sunday",
    "day_of_week_i": 6,
    "email": "samir@moss-family.zzz",
    "manufacturer": [
      "Oceanavigations",
      "Low Tide Media"
    ],
    "order_date": "2024-04-21T05:35:31+00:00",
    "order_id": 564237,
    "products": [
      {
        "base_price": 20.99,
        "discount_percentage": 0,
        "quantity": 1,
        "manufacturer": "Oceanavigations",
        "tax_amount": 0,
        "product_id": 19840,
        "category": "Men's Accessories",
        "sku": "ZO0311203112",
        "taxless_price": 20.99,
        "unit_discount_amount": 0,
        "min_price": 10.29,
        "_id": "sold_product_564237_19840",
        "discount_amount": 0,
        "created_on": "2016-12-11T05:35:31+00:00",
        "product_name": "Watch - black",
        "price": 20.99,
        "taxful_price": 20.99,
        "base_unit_price": 20.99
      },
      {
        "base_price": 32.99,
        "discount_percentage": 0,
        "quantity": 1,
        "manufacturer": "Low Tide Media",
        "tax_amount": 0,
        "product_id": 13857,
        "category": "Men's Shoes",
        "sku": "ZO0395703957",
        "taxless_price": 32.99,
        "unit_discount_amount": 0,
        "min_price": 17.15,
        "_id": "sold_product_564237_13857",
        "discount_amount": 0,
        "created_on": "2016-12-11T05:35:31+00:00",
        "product_name": "Trainers - beige",
        "price": 32.99,
        "taxful_price": 32.99,
        "base_unit_price": 32.99
      }
    ],
    "sku": [
      "ZO0311203112",
      "ZO0395703957"
    ],
    "taxful_total_price": 53.98,
    "taxless_total_price": 53.98,
    "total_quantity": 2,
    "total_unique_products": 2,
    "type": "order",
    "user": "samir",
    "geoip": {
      "country_iso_code": "AE",
      "location": {
        "lon": 55.3,
        "lat": 25.3
      },
      "region_name": "Dubai",
      "continent_name": "Asia",
      "city_name": "Dubai"
    },
    "event": {
      "dataset": "sample_ecommerce"
    }
  },
  "fields": {
    "products.manufacturer": [
      "Oceanavigations",
      "Low Tide Media"
    ],
    "products.base_unit_price": [
      20.984375,
      33
    ],
    "products.discount_amount": [
      0,
      0
    ],
    "type": [
      "order"
    ],
    "products.discount_percentage": [
      0,
      0
    ],
    "products._id.keyword": [
      "sold_product_564237_19840",
      "sold_product_564237_13857"
    ],
    "day_of_week_i": [
      6
    ],
    "total_quantity": [
      2
    ],
    "taxless_total_price": [
      53.96875
    ],
    "total_unique_products": [
      2
    ],
    "geoip.continent_name": [
      "Asia"
    ],
    "sku": [
      "ZO0311203112",
      "ZO0395703957"
    ],
    "customer_full_name.keyword": [
      "Samir Moss"
    ],
    "category.keyword": [
      "Men's Accessories",
      "Men's Shoes"
    ],
    "products.taxless_price": [
      20.984375,
      33
    ],
    "products.quantity": [
      1,
      1
    ],
    "customer_first_name": [
      "Samir"
    ],
    "products.price": [
      20.984375,
      33
    ],
    "customer_phone": [
      ""
    ],
    "geoip.region_name": [
      "Dubai"
    ],
    "customer_full_name": [
      "Samir Moss"
    ],
    "geoip.country_iso_code": [
      "AE"
    ],
    "order_id": [
      "564237"
    ],
    "products._id": [
      "sold_product_564237_19840",
      "sold_product_564237_13857"
    ],
    "products.product_name.keyword": [
      "Watch - black",
      "Trainers - beige"
    ],
    "products.product_id": [
      19840,
      13857
    ],
    "products.category": [
      "Men's Accessories",
      "Men's Shoes"
    ],
    "products.manufacturer.keyword": [
      "Oceanavigations",
      "Low Tide Media"
    ],
    "manufacturer": [
      "Oceanavigations",
      "Low Tide Media"
    ],
    "products.unit_discount_amount": [
      0,
      0
    ],
    "customer_last_name": [
      "Moss"
    ],
    "geoip.location": [
      {
        "coordinates": [
          55.3,
          25.3
        ],
        "type": "Point"
      }
    ],
    "products.product_name": [
      "Watch - black",
      "Trainers - beige"
    ],
    "products.tax_amount": [
      0,
      0
    ],
    "manufacturer.keyword": [
      "Oceanavigations",
      "Low Tide Media"
    ],
    "products.min_price": [
      10.2890625,
      17.15625
    ],
    "currency": [
      "EUR"
    ],
    "products.taxful_price": [
      20.984375,
      33
    ],
    "products.base_price": [
      20.984375,
      33
    ],
    "email": [
      "samir@moss-family.zzz"
    ],
    "day_of_week": [
      "Sunday"
    ],
    "customer_last_name.keyword": [
      "Moss"
    ],
    "products.sku": [
      "ZO0311203112",
      "ZO0395703957"
    ],
    "products.category.keyword": [
      "Men's Accessories",
      "Men's Shoes"
    ],
    "geoip.city_name": [
      "Dubai"
    ],
    "customer_first_name.keyword": [
      "Samir"
    ],
    "order_date": [
      "2024-04-21T05:35:31.000Z"
    ],
    "products.created_on": [
      "2016-12-11T05:35:31.000Z",
      "2016-12-11T05:35:31.000Z"
    ],
    "category": [
      "Men's Accessories",
      "Men's Shoes"
    ],
    "customer_id": [
      "34"
    ],
    "user": [
      "samir"
    ],
    "customer_gender": [
      "MALE"
    ],
    "event.dataset": [
      "sample_ecommerce"
    ],
    "taxful_total_price": [
      53.96875
    ]
  }
}

Dashboard 에서 다양한 Summary 데이터를 확인할 수 있다. 

이제 실습을 해보자. 

• took : 검색 응답 시간
• time_out : 검색이 time out 되었는지 여부
• _shards : 검색을 수행한 샤드 정보
• total : 검색을 수행한 총 샤드 수
• successful : 검색 수행을 성공한 샤드 수
• failed : 검색 수행을 실패한 샤드 수
• hits
• total : 검색 매칭에 성공한 도큐먼트 수
• max_score : 매칭에 성공한 도큐먼트중 가장 높은 점수

=======================

참고

- https://velog.io/@jakeseo_me/%EC%97%98%EB%9D%BC%EC%8A%A4%ED%8B%B1%EC%84%9C%EC%B9%98-%EC%95%8C%EC%95%84%EB%B3%B4%EA%B8%B0-2-DB%EB%A7%8C-%EC%9E%88%EC%9C%BC%EB%A9%B4-%EB%90%98%EB%8A%94%EB%8D%B0-%EC%99%9C-%EA%B5%B3%EC%9D%B4-%EA%B2%80%EC%83%89%EC%97%94%EC%A7%84

https://kok202.tistory.com/100

문제 링크 : https://acmicpc.net/problem/15989

3
4
7
10

4
8
14

풀이 방법

[1]

1

=> 1가지

(0가지 일 수도 있는지?...)

[2] 

1 + 1

=> 1가지

[3]

1 + 1 + 1

2 + 1

=> 2가지

[4]

1 + 1 + 1 + 1

2 + 1 + 1 , 2 + 2

3 + 1

=> 4가지

[5]

1 + 1 + 1 + 1 + 1

2 + 1 + 1 + 1 , 2 + 2 + 1

3 + 1 + 1, 3 + 2

=> 5가지

[6]

1 + 1 + 1 + 1 + 1 + 1

2 + 1 + 1 + 1 + 1 , 2 + 2 + 1 + 1, 2 + 2 + 2

3 + 1 + 1 + 1, 3 + 2 + 1

3 + 3

=> 7가지

[7]

1 + 1 + 1 + 1 + 1 + 1 + 1

2 + 1 + 1 + 1 + 1 + 1 , 2 + 2 + 1 + 1 + 1, 2 + 2 + 2 + 1

3 + 1 + 1 + 1 + 1, 3 + 2 + 1 + 1, 3 + 2 + 2, 

3 + 3 + 1

=> 8가지

[8]

1 + 1 + 1 + 1 + 1 + 1 + 1 + 1

(2 + 1 + 1 + 1 + 1 + 1 + 1), (2 + 2 + 1 + 1 + 1 + 1), (2 + 2 + 2 + 1 + 1), (2 + 2 + 2+ 2)

(3 + 1 + 1 + 1 + 1 + 1), (3 + 2 + 1 + 1 + 1), (3 + 2 + 2 + 1)

(3 + 3 + 1 + 1), (3 + 3 + 2)

=> 10가지

 [9]

1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1

(2 + 1 + 1 + 1 + 1 + 1 + 1 + 1), (2 + 2 + 1 + 1 + 1 + 1 + 1), (2 + 2 + 2 + 1 + 1 + 1), (2 + 2 + 2+ 2 + 1)

(3 + 1 + 1 + 1 + 1 + 1 + 1), (3 + 2 + 1 + 1 + 1 + 1), (3 + 2 + 2 + 1 + 1), (3 + 2 + 2 + 2)

(3 + 3 + 1 + 1 + 1), (3 + 3 + 2 + 1)

(3 + 3 + 3)

=> 12가지

 [10]

1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1

(2 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1), (2 + 2 + 1 + 1 + 1 + 1 + 1 + 1), (2 + 2 + 2 + 1 + 1 + 1 + 1), (2 + 2 + 2+ 2 + 1 + 1), (2 + 2 + 2+ 2 + 2)

(3 + 1 + 1 + 1 + 1 + 1 + 1 + 1), (3 + 2 + 1 + 1 + 1 + 1 + 1), (3 + 2 + 2 + 1 + 1 + 1), (3 + 2 + 2 + 2 + 1)

(3 + 3 + 1 + 1 + 1 + 1), (3 + 3 + 2 + 1 + 1), (3 + 3 + 2 + 2)

(3 + 3 + 3 + 1)

=> 14가지

 [11]

1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1

(2 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1), (2 + 2 + 1 + 1 + 1 + 1 + 1 + 1 + 1), (2 + 2 + 2 + 1 + 1 + 1 + 1 + 1), (2 + 2 + 2+ 2 + 1 + 1 + 1), (2 + 2 + 2+ 2 + 2 + 1)

(3 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1), (3 + 2 + 1 + 1 + 1 + 1 + 1 + 1), (3 + 2 + 2 + 1 + 1 + 1 + 1), (3 + 2 + 2 + 2 + 1 + 1), (3 + 2 + 2 + 2 + 2)

(3 + 3 + 1 + 1 + 1 + 1 + 1), (3 + 3 + 2 + 1 + 1 + 1), (3 + 3 + 2 + 2 + 1)

(3 + 3 + 3 + 1 + 1), (3 + 3 + 3 + 2)

=> 16가지

6부터 2씩 증가-> fail!!!

==========================

dp[n,k] : 1,,,k 를 활용해 n을 만드는 방법의 수로 가정하고 각 값을 구해보자. 

===========================================

• dp[n,1] = 1
• dp[n,2] = n/2(몫만) + 1
• dp[n-3] = dp[n-1, 1] +dp[n-2, 2] + dp[n-3, 3]   = 1 + {(n-2)/2} + 1 + dp[n-3,3]

import java.util.Scanner;

public class BOJ_15989_123더하기4 {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int T = sc.nextInt();
        int[][] dp= new int[10001][4];

        for(int n = 0; n<=10000; n++){
            dp[n][0] = 0;
            dp[n][1] = 1;
            dp[n][2] = n/2 + 1;
        }
        dp[1][2] = 1; dp[1][3] = 1;
        dp[2][2] = 1; dp[2][3] = 2;
        dp[3][2] = 2; dp[3][3] = 3;
        dp[4][2] = 3; dp[4][3] = 4;
        
        for(int i = 5; i<=10000; i++){
            dp[i][3] = 2 + (i-2)/2 + dp[i-3][3];
        }


        int n;
        for(int i = 0; i<T; i++){
            n = sc.nextInt();
            System.out.println(dp[n][3]);

        }
    }
}

출처 : https://www.youtube.com/watch?v=yR8_v58kN2c&list=PLvbX4wFD7b734CdVXEgCW5uU91gUX_RVu

1. 자동 채우기

• 매출 채우기 : 드래그 또는 더블클릭
• 날짜 채우기 : 격일 단위 또는 평일만 (옵션 사용)

2. 빠른 채우기

• 단축키 : Ctrl + E
• Ex. 치즈크러스트 - 페퍼로니 피자

3. 가로 표 글자 크기 맞추기 

• 셀 너비 맞추기 : 범위의 머리글 클릭 -> 셀 세로 선 위에 마우스 놓고 너비 전체 셀 조정 가능
• 글자 크기 맞추기 : 해당 셀 전체 선택 -> 셀 서식(Ctrl + 1) ->  맞춤 탭 -> 텍스트 조정 -> 셀에 맞춤 

4. 그룹 (숨기기 대신)

• 숨기고 싶은 열 드래그 -> 데이터 탭 -> 그룹 클릭
• 단축키 : 드래그 후 Alt + Shift + -> (그룹 삭제는 Alt + Shift + <- )

5. 테두리 채우기

• 단축키 : 드래그 후 ALT + HBA (각각 누름)
• 태두리 빼기 :Ctrl + Shift + (-)

6. 하이퍼링크 /  한/영 바뀜 설정 변경

• 파일 -> 옵션 -> 언어교정 ->

1. 자동교정 옵션 -> 입력할 때 자동 서식 -> 하이퍼링크 해제
2. 자동고침 -> 한/영 자동교청 해제
3. 문장의 첫 글자를 대문자로 해제

7. 빠른 실행 도구모음

• 안 보이면 상단 타이틀 우 클릭 후 빠른 실행 도구 모음 표시 클릭
• 잘 쓰는 오름차순/내림차순 등 추가 가능
• ALT 누르면 번호가 뜨면서 단축키 확인 가능
• 화살표 클릭 후 기타 명령에서 개인에 맞게 잘 쓰는 기능 추가 (셀 병합.. 등)

8. 값 빠르게 편집하는 F2

• 더블클릭 할  필요 없음

9. 행 위치 교체 Shift

 
10. 인접 셀 전체 선택
단축키 : 범위 내 셀 하나 클릭 후 Ctrl + A  
 
11. 표 전체 복사 후 너비 조절
단축키 : Ctrl 누르고 나서 떼고 W 누르기 
 
12. 상태 표시줄
실시간으로 평균 /선택 행 개수 / 합계 손쉽게 확인 가능
화살표 클릭하여 원하는 값 (Min, Max 등) 추가 가능

13. 셀 병합 문제 해결
셀 병합 시 컬럼 선택하면 병합된 머리글 셀 때문에 열 선택 안 되는 문제 있음
-> 셀 병합 해제 후 다시 셀 범위 선택하고 셀 서식-> 맞춤 -> 선택한 영역의 가운데로 클릭
(겉으로는 병합되는 것처럼 보임)

가상화란?

• 물리적인 컴퓨터 하드웨어를 효율적으로 활용할 수 있도록 해주는 과정.
• 가상화는 소프트웨어를 사용하여 단일 컴퓨터의 하드웨어 요소(프로세서, 메모리, 스토리지)를 다수의 가상 컴퓨터(VM)로 분할해서 사용할 수 있도록 해줌
• 각각의 VM은 자체의 OS를 실행해서 마치 독립적인 컴퓨터처럼 동작함.

가상화의 장점

1. 리소스 효율성 향상

• 가상화 전에는 각 app서버에 물리적인 cpu 가 필요했음 (신뢰성 측면에서 App과 OS/CPU가 1:1 구성)
• 물리 서버는 항상 Full로 사용되지 않기 때문에 효율적으로 Capa를 사용하지 못했음
• 가상화 이후에는 각 VM에서 각자의 OS를 가지고 App을 실행할 수 있어 효율성 및 신뢰성 모두 만족할 수 잇음
• 물리적 하드웨어에 각 VM이 여러개 떠 있는 구조로 유동적으로 자원을 나눠 사용 가능하므로 리소스 효율성도 만족함

2. 가동 중단 시간 최소화

• 여러개의 가상 머신을 띄워서 관리함
• 그 중 하나의 가상 머신 내에서 문제가 발생할 경우 다른 가상 머신을 활용해서 서비스 무중단을 제공함

3.  빠른 자원 제공 

• 물리 서버인 경우 구매, 설치, 구성에는 많은 시간 소요됨
• 가상 머신 활용 시 (하드웨어가 이미 구성되어 있다는 전제 하에) App 실행을 위한 자원을 빠르게 제공 가능
• 전용 SW 사용하여 자원 제공을 자동화하고, 기존 워크플로우에 빌드함으로써 관리의 용이성 제공

가상화의 종류

• 데스크탑 가상화
• 네트워크 가상화
• 스토리지 가상화
• 데이터 가상화
• 애플리케이션 가상화
• 데이터 센터 가상화
• CPU 가상화
• GPU 가상화
• Linux 가상화
• 클라우드 가상화

서버 가상화

• 서버 가상화는 SW를 통해 하나의 물리적인 서버를 여러개의 분리된 가상 서버로 나누는 과정
• 각 가상 서버는 자체 OS를 독립적으로 실행 가능

서버 가상화의 장점

• 서버 가용성 증가
• 운영 비용 절감
• 서버 복잡성 제거
• 애플리케이션 성능 향상
• 더욱 빠른 워크로드 배포

하이퍼바이저란

• 하이퍼바이저는 가상머신을 생성하고 구동하는 SW
• 물리적 리소스를 분리해서 각각의 가상 환경을 만들어주는 역할을 함
• 사용자 또는 프로그램이 물리적 환경의 추가 리소스 요구 시 -> 하이퍼바이저는 그 요청을 물리적 시스템에 전달하고 변경사항을 저장함

하이퍼바이저의 종류

Type 1. Bare-Metal / Native

• 호스트 하드웨어에 직접 설치하여 구동함
• 즉 하드웨어 바로 위에 위치해서 OS역할(하드웨어 제어)을 하고 VM을 관리하는 역할을 함
• 호스트 OS 없어서 OverHead 적음
• 콘솔로 관리해야하므로 사용성 낮음(처음 셋업 시 윈도우 설치처럼 진행해야함)
• 예) Xen, x86용 오라클 VM서버, 마이크로소프트 Hyper-V, VMWare의 ESX 서버

Type 2. Hosted

• 호스트 OS 위에 설치되어 호스트 OS-하이퍼바이저-가상머신 HW간 Overhead 발생함
• APP 설치하는 것처럼 VirtualBox 설치 후 가상머신 이미지 생성하는 방식
• 예) VMWare Workstation, VirtualBox, Mac Paralles 

참고

https://www.ibm.com/kr-ko/topics/virtualization

https://www.redhat.com/ko/topics/virtualization/what-is-a-hypervisor

문제 링크 : https://www.acmicpc.net/problem/1339

import java.util.*;
public class BOJ_1339_단어수학 {


    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        String[] strArr = new String[N];
        int[] alphaArr = new int[26];
        Arrays.fill(alphaArr, 0);

        for(int i = 0; i<N; i++){
          String str = sc.next();
          //System.out.println(str);
          int len = str.length();
          for(int j = 0; j<len; j++){
              char c = str.charAt(j);   // c = 'A', 'B' ...
              alphaArr[c - 'A'] += (int)Math.pow(10, len-1-j);  //'A'면 alphaArr[0]
          }
        }

        Arrays.sort(alphaArr);
        int multipleNum = 9;
        int index = 25;
        int sum = 0;
        while(alphaArr[index]>0){
            sum += alphaArr[index] * multipleNum;
            index--;
            multipleNum--;
        }
        System.out.println(sum);
    }
}

참고  : https://mountain96.tistory.com/21

문제 링크 : https://www.acmicpc.net/problem/1722

출력

k번째 수열을 나타내는 N개의 수를 출력하거나, 몇 번째 수열인지를 출력하면 된다.

 

 

---

 

접근 방법

주어진 시간은 2초밖에 되지 않기 때문에 노가다로 하면 시간 초과가 뜰 것이다. 

먼저 소문제 번호 = 1인 경우를 보자.

N = 5 

배열 = {1, 2, 3, 4, 5}

k = 61이라고 해보자. 

61번째 순열을 어떻게 구할 수 있을까?

먼저 61번째의 첫번째 숫자는 무엇일지 생각해보자. 2*4! < 61 < 3*4! 이므로 첫번째 숫자는 3이다.

1 _ _ _ _  => 4! (24) 가지가 있음

2 _ _ _ _ => 4! (24) 가지가 있음

3 _ _ _ _ => 4! (24) 가지가 있음

이런 방식을 활용해보면 처음 61에서 24씩 빼면서 경계를 찾아 나가다가 

61 - 24 = 37

37 - 24 = 13

13 - 24 < 0 가 됨. 24를 세번째 뺀 것이므로 세번째 범위에 답이 있고 처음 숫자는 3이 되는 것이다. 

 

그 다음을 보자. 우선 3은 가장 앞자리로 고정이 되었기 때문에 제외하고 1, 2, 4, 5 가 남았다. 

 

3, 1, _ _ _ => 3! (6) 가지가 있음 (49 ~ 54)

3, 2, _ _ _ => 3! (6) 가지가 있음 (55 ~ 60) 

3, 4, _ _ _ => 3! (6) 가지가 있음 (61 ~ 66)- > 이 중에 61번째 순열이 있음 

3, 5, _ _ _ => 3! (6) 가지가 있음 (67 ~ 73)

 

단순하게 보면 위와 같은데, 처음에 썼던 빼기 규칙을 써보면 

13 - 6 = 7 > 0이고

7 - 6  = 1 > 0이고 

1 - 6 <0 이므로 세번째 범위에 답이 있고 두번째 숫자는 4가 되는 것이다. 

이런 식으로 계속 빼 나가면서 숫자를 지정해나가면 된다. 

 

 

다음 소문제 번호 = 2인 경우를 보자.

위에서 했던 방식을 거꾸로 하면 된다. 

N = 5일 때 61번째 순열인 {3, 4 ,1 ,2, 5} 를 보자. {3, 4, 1, 2, 5}를 보고 어떻게 61번째 순열인지 알 수 있을까?

각 자리의 숫자보다 작은 수로 시작하는 순열의 가지수를 세가면서 더하면 된다. 

1, _ _ _ _ 는 4! (24)가지

2, _ _ _ _ 도 4!(24)가지이다. 

그럼 우선 sum은 24+24 = 48이 된다. 

3은 visit 표시를 해 놓고 다음 차례인 4를 보자. 

 

3, 4, _ _ _ <- 이 순열의 전에는 

3, 1, _ _ _  

3, 2, _ _ _

이 두 순열이 우선이 됐을 것이다. 각각 3! (6) 가지이므로 48 + 6 + 6 = 60이 된다. 

 

3, 4, _ _ _ 정해졌고 남은 수는 1, 2, 5 인데 구하는게 3, 4, 1, 2, 5가 몇번째인지 구하는 것이므로 

sum 인 60에 1을 더하면 된다. 

 

import java.util.*;
public class BOJ_1722_순열의순서 {


    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        long[] fac = new long[21];
        fac[0] = 1;
        for(int i = 1; i<=20 ;i++) fac[i] = i*fac[i-1];

        int N = sc.nextInt();
        int num = sc.nextInt();
        long k = 0;
        int[] arr = new int[N+1];
        boolean[] visited = new boolean[N+1];
        Arrays.fill(arr,0);
        Arrays.fill(visited,false);

        Vector<Integer> ansVec = new Vector<Integer>();
        long ans = 1;

        if (num==1){
            k = sc.nextLong();      //Long으로 입력하지 않으면 런타임 에러뜸
            for(int i = 0; i<N; i++){
                for(int j = 1; j<=N; j++){
                    if(visited[j]) continue;    //이미 사용된 숫자는 패스
                    if(k - fac[N-1-i] > 0) {    //0이랑 같으면 1 3 4 2가 오답으로 출력됨 
                        k -= fac[N-1-i];        
                    }
                    else {                         
                        ansVec.add(j);
                        visited[j] = true;
                        break;
                    }
                }
            }
            for(int i = 0; i<ansVec.size(); i++){
                System.out.print(ansVec.elementAt(i) + " ");
            }

        }
        else if (num==2){
            for(int i = 0; i<N; i++){
                arr[i] = sc.nextInt();  
            }
            for(int i = 0; i<N; i++){
                for(int j = 1; j<arr[i]; j++){      //arr[i] 보다는 작은 수가 앞에 나올 수 있으므로 
                    if(visited[j] == false){
                        ans += fac[N-1-i];
                    }

                }
                visited[arr[i]] = true;
            }
            System.out.println(ans);



        }
    }
}

 

 

MacOS에서 Wireshark로 패킷 분석 실습을 해보자.

먼저 아래 링크에서 WireShark를 다운받는다. 

https://www.wireshark.org/download.html

본인은 Intel CPU라서 그에 맞게 다운했다. 

Wireshark를 Applications로 드래그 앤 드롭해서 설치해준다. 

설치가 완료되었으면 아래 화면을 볼 수 있다. 

Wi-Fi:en1을 클릭하니 아래와 같은 에러가 떴다. 

You do not have permission to capture on device "en1".
((cannot open BPF device) /dev/bpf0: Permission denied)

Please check to make sure you have sufficient permissions.

If you installed Wireshark using the package from wireshark.org, close this dialog and click on the "installing ChmodBPF" link in "You can fix this by installing ChmodBPF." on the main screen, and then complete the installation procedure.

터미널에 아래 명령어를 입력해보자. 

sudo chown gildong /dev/bpf*

정상적으로 실시간 패킷이 잘 확인된다. 

아무튼 이제 다시 돌아오자.

각 패킷이 어디서부터(Source) -> 어디로(Destination) / 어떤 포트를 사용해서 / 패킷을 어느 정도의 길이만큼 주고 받았는지를 확인할 수 있다. 

왼쪽 하단에는 각 패킷의 세부 정보가 나와 있는데 세부 정보에 우클릭을 해서 Apply as Column을 클릭하면

해당 세부 정보를 컬럼으로 추가할 수 있다. 

패킷 필터링

이 많은 패킷들 중 네트워크 지연 분석을 하려면 어떻게 해야할까?

우선 이 많은 패킷들에 필터를 걸어서 원하는 패킷들만 추출해서 볼 수 있어야 한다. 

패킷 필터 방법

패킷 필터 방법은 아래 두 가지가 있다.

1. Capture Filter

• 패킷 수집할 때 부터 필터를 걸어서, 원하는 패킷만 Capture(수집)하는 방법
• 이 방법은 처음 수집할 때부터 조건이 적용되기 때문에 성능에 영향을 줄 수 있다.
• ex. tcp port 443

2. Display Filter

• 먼저 전체 패킷을 수집하고 그 이후에 Display 되는 화면에서 필터를 걸어서 보는 방법
• 다양한 필터 조건을 걸 수 있고, 대게 권장되는 방법이다. 
• ex. tcp.port = 443

패킷 필터 종류

이제 필터의 종류에 대해 알아보자.

우선 필터 예시를 확인해보자.

Analyze > Display Filters 를 클릭하면 

아래와 같이 필터 예시가 나온다. +를 눌러서 자주 쓰는 필터를 추가할 수도 있다. 

유용한 필터들을 자세히 좀 정리해보자.

• 프로토콜 필터 : tcp || udp

패킷 세부 정보를 볼 때 해당 패킷 기준으로 필터를 걸고 싶을 때는 해당 정보에 우클릭 후 Apply as Filter 를 사용하면 된다. 

그럼 위쪽의 필터에 자동으로 ip.src==142.250.256.238 조건이 지정되었고

Source Address가 142.250.256.238 인 패킷들만 display 된 것을 확인할 수 있다. 

Packet Delay 여부를 분석하기 위해서는 어떻게 해야 할까?

우선 가장 기본이 되는 시간 컬럼을 잘 분석해야 한다. 

Req ~ Rep 간에 소요되는 시간이 패킷별로 일정한지, 일정하지 않다면 변화가 생기는 지점을 분석해봐야 한다. 

참고로 시간 포맷은 View > Time Display Format 으로 들어가서 선택할 수 있다. 

Time Column 종류

• Seconds Since First Captured Packet
  • 첫번째 패킷이 캡쳐된 시간을 0으로 지정하고 그 이후의 패킷들은 첫번째 패킷의 시간을 기준으로 비교해서 측정된다. 

• Seconds Since Previous Captured Packet
  • 이전 패킷을 기준으로 다음 패킷이 수집되기까지 (받거나 보내거나) 걸리는 시간을 보여준다. 
  • 아래 예시를 보면 2번 패킷은 1번 패킷이 수집되고 0.003859초만에 왔다.
  • 3번 패킷은 2번 패킷이 수집되고 0.000018초만에 왔다. 
  • 4번 패킷은 3번 패킷이 수집되고 0.000001초만에 왔다. 

• Seconds Since Previous Displayed Packet
  • 화면에 디스플레이 된 패킷들만 대상으로 두고, 이전 패킷을 기준으로 다음 패킷이 수집되기까지(받거나 보내거나) 걸리는 시간을 보여준다.
  • 이 옵션은 필터가 지정되어 있지 않을 때는 위의 Captured Packet 옵션이랑 동일하다.
  • 그러나 필터가 적용되면 아래와 같이 화면에 보여지는 패킷들(조건 지정된 패킷들) 만 대상으로 패킷간에 전달된 시간을 보여준다. 
  • 7번과 9번 패킷을 보면 7번 패킷 이후에 9번 패킷이 오기까지 0.048793초가 걸렸다. 이는 위 사진을 보면 7번~8번 패킷 간 걸린 시간인 0.001079초와 8번~9번 패킷 간 걸린 시간인 0.047714초를 더한 시간임을 알 수 있다. 

네트워크 지연의 원인

1. 흐름 제어 (Flow Control)

수신 측 처리 속도보다 송신 측 전송 속도가 빠를 때 발생한다. 

수신 측의 용량보다 더 빠르게 보내서 패킷이 손실되면(OverFlow), 다시 불필요한 전송과 Ack/Nack 응답을 주고 받아 확인해야하므로 이로 인한 딜레이가 발생할 수 있다. 

해결 방법으로는 Stop and Wait와  Sliding Window 가 있다.

1) Stop and Wait

첫번째 Stop and Wait 방식은 매번 잘 받았다고 응답을 보내야 다음 패킷을 보내는 방식이기 때문에 데이터 유실 없이 안정적인 전송이 가능하겠지만 데이터 전송에 시간이 오래 걸릴 수 있다.

2) Sliding Window

두번째 Sliding Window 방식은 받는 쪽에서 정한 데이터 크기(Window Size) 에 해당하는 패킷들을 전부 보내서 각 패킷의 응답이 오지 않아도 여러 패킷을 보낼 수 있다. 각 패킷별로 잘 받았다는 응답이 와야 다음 패킷을 보낼 수 있는 Stop and Wait 보다 훨씬 효율적인 방법이다. 통신 과정 중에 네트워크가 혼잡하다면 윈도우 크기는 유동적으로 바뀔 수 있다. 

Sliding Window 방식으로 흐름제어를 하지만 이로 인해 데이터 읽기 속도 저하가 발생할 수 있다. 아래를 보자.

* 흐름제어로 인한 데이터 읽기 속도 저하

TCP header 에는 Window Size가 있다. Window Size값이란 수신자가 받을 수 있는 최대 데이터 크기를 의미한다. 

App(수신자)이 네트워크를 통해 전달된 패킷을 받으면 버퍼가 채워지고, App이 데이터를 처리하면(읽으면) 버퍼가 비워진다. 

만약 App의 처리 속도가 1분에 10개의 패킷을 처리한다고 했을 때, Sender 쪽에서 그 보다 더 빠른 속도로 패킷을 전송하면 App의 Window가 점점 차게 된다. 

그럼 Sender 는 데이터의 일부만 보내거나 아예 보낼 수 없는 상황이 발생하고 서버가 전체적으로 지연되는 것이다. 

이런 상황은 어떻게 알 수 있을까?

네트워크에 쓰기 요청을 했는데 그 결과가 0 byte만큼 썼다고 나오면 -> Window Size로 인해 서버 지연이 발생하고 있는 상황을  의심해 볼 수 있다. 

2. 혼잡 제어(Congestion Control)

혼잡제어도 흐름제어와 동일하게 받는 쪽에서 처리하는 데이터 속도보다 보내는 쪽의 속도가 더 빠를 때의 문제를 해결하기 위한 기법이다. 다른점은 혼잡제어는 흐름제어와 달리 보다 넓게 호스트 및 라우터를 포함한다. 

1) AIMD (Additive Increase Multiplicative Decrease)

정상 시 윈도우 크기를 1씩 증가시키면서 보내다가 패킷 전송 실패 혹은 딜레이 발생 시 패킷 전송 속도를 절반으로 줄이는 방식이다. 

처음에 전송 속도가 느리다는 단점과 문제가 발생하고 나서야 개선을 한다는 단점이 있다.

2) Slow Start

AIMD와 비슷하지만 윈도우 크기를 지수적으로 증가시킨다. 즉, 매 RTT마다 2배를 키우다가 (1,2,4,8,16,,) 문제 발생 시 윈도우 크기를 1로 줄인다. 

참고) 

아래 그림은 하드웨어의 네트워크 지연을 나타낸 그림이다.

1. 전송 지연 : 네트워크 장비 자체의 속도로 인함
2. 전파 지연 : 전송 거리로 인함
3. 처리 지연 : 라우터 자체 작업 처리로 인함 (패킷 헤더 처리, 비트 데이터 오류 등)
4. 큐 지연 : 라우터에서 처리하는 중에 추가로 들어오는 데이터들은 큐에 push 후 전송함 

참고) 정상적인 지연 발생 케이스

[정상적인 지연]

앞서 잠깐 언급한 것처럼, 일정 수준의 지연은 많이 발생하기 때문에 이러한 지연은 정상적인 지연으로 분류하고 따로 분석하지 않는다. 정상적인 지연에 해당하는 경우는 아래와 같다.

▶ .ico 파일 요청

- 브라우저 탭에 있는 아이콘을 눌렀을 때 관련 파일을 받아오기 위해 발생하는 지연이다.

▶ SYN 패킷 지연

- 새로운 연결 설정을 위해 첫 SYN 패킷 앞에서 지연이 발생한다.

▶ FIN/RST 패킷

- 연결을 종료하기 위해 사용되는 패킷이다.

- 새로운 탭에서 작업을 수행하거나, 현재 사이트에서 최근 활동이 없을 때, 브라우징 세션이 페이지가 로드된 뒤에 자동으로 닫히도록 구성됐을 때 등의 경우에 지연이 발생한다.

- 사용자가 알 수 없는 지연이다.

▶ GET 요청

- 사용자가 다음 페이지를 요청하거나 백그라운드 프로세스가 페이지 연결을 시도할 경우, 해당 페이지로 연결할 때 지연이 발생한다.

▶ DNS 쿼리

- 여러 개의 하이퍼링크를 가진 페이지가 클라이언트 컴퓨터 상에서 로드될 때 지연이 발생한다.

- 각각의 페이지를 일일이 로드해야 하기 때문에 발생하는 지연이다.

▶ TLS v1 암호화된 경고

- TCP 리셋 바로 전에 발생하는 지연이다.

- 발생 확률은 낮다.

다음 세미나 주제

실제 현장에서 네트워크 딜레이 발생 시 원인 분석을 단계별로 해 나가는 방법 및 실전에서 사용하는 툴

https://blog.ahnlab.com/1288

참고

https://velog.io/@joosing/Wireshark-%ED%8C%A8%ED%82%B7-%ED%95%84%ED%84%B0-A-to-Z

https://as-backup.tistory.com/31

문제 링크 : https://www.acmicpc.net/problem/10164

접근 방법

처음에는 조합으로 풀었다가 32점이 나와서 dp로 문제를 해결했다.

처음 접근 방법은 K가 0이 아니면

K의 좌표를 구한 다음 -> 그 좌표까지 가려면 우측 방향으로 몇번 가야하는지와 아래 방향으로 몇 번 가야하는지를 조합을 사용해서 계산햇다. 

예제를 예시로 들면 아래에서 K까지 가려면 처음 [0][0]에서 우측으로 두 번, 아래 방향으로 한 번 가면 되는 것이다.

총 세번 이동을 해야하는데 그 중에 아래 화살표들을 순서 상관 없이 나열하는 조합의 경우의 수를 구하면 된다. 

➡️➡️⬇️

➡️⬇️➡️

⬇️➡️➡️

import java.util.Scanner;

public class Main {

    static int combi(int n, int r){
        if(n==r || r==0) return 1;
        return combi(n-1, r-1) + combi(n-1,r);
    }
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        int N = sc.nextInt();
        int M = sc.nextInt();
        int K = sc.nextInt();
        int ans = 0;

        if(K!=0){
            int kRow = K/M;
            int kCol = K%M -1;

            int first = combi(kRow+kCol, kCol);
            int second = combi(M-kCol-1 + N-kRow-1, N-kRow-1);
            ans = first*second;
        }
        else{
            ans = combi(N+M-2, N-1);
        }
        System.out.println(ans);

    }
}

그러나 이 방법으로는 32점밖에 안 나와서 N,M이 커지면 서브테스크 3번부터 막히는 것 같아 dp로 다시 풀었다.

dp로 풀때 주의할 점은 K의 위치를 잘 구해야 한다는 것이다.

예제로 주어진 문제로만 푸는 것이 아니라

반레로 K가 M으로 딱 나눠서 떨어지는 경우 즉 입력 값이 (2, 2, 2) 인 케이스도 생각하면 서브 테스크 3,4번도 모두 맞출 수 있다

import java.util.Scanner;

public class BJOJ_10164_격자상의경로 {

    static int combi(int n, int r){
        if(n==r || r==0) return 1;
        return combi(n-1, r-1) + combi(n-1,r);
    }
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        int N = sc.nextInt();
        int M = sc.nextInt();
        int K = sc.nextInt();
        int ans = 0;
        int[][] dp = new int[N][M];
        dp[0][0] = 0;

        if(K!=0){
            int kRow = K/M;
            int kCol = K%M;
            if(K%M == 0) {		//K가 오른쪽 끝에 붙어있는 경우 고려
                kRow -= 1;
                kCol = M-1;
            }else kCol-=1;


            for(int i = 1; i<=kRow; i++) {
                dp[i][0] = 1;
            }
            for(int i = 1; i<=kCol; i++){
                dp[0][i] = 1;
            }
            for(int i = 1; i<=kRow; i++){
                for(int j = 1; j<=kCol; j++){
                    dp[i][j] = dp[i-1][j] + dp[i][j-1];
                }
            }
            for(int i = kRow+1; i<N; i++) dp[i][kCol] = dp[kRow][kCol];
            for(int j = kCol+1; j<M; j++) dp[kRow][j] = dp[kRow][kCol];
            for(int i = kRow+1; i<N; i++){
                for(int j = kCol+1; j<M; j++){
                    dp[i][j] = dp[i-1][j] + dp[i][j-1];
                }
            }

        }
        else{
            for(int i = 1; i<N; i++) {
                dp[i][0] = 1;
            }
            for(int i = 1; i<M; i++){
                dp[0][i] = 1;
            }
            for(int i = 1; i<N; i++){
                for(int j = 1; j<M; j++){
                    dp[i][j] = dp[i-1][j] + dp[i][j-1];
                }
            }
        }
        System.out.println(dp[N-1][M-1]);


    }
}