Abstract

이 논문에서 문제점으로 삼고 있는 것은 dialouge management(이하 DM)을 scalable하고 robust하게 만드는 것이 어렵다는 것임. 그리고 이 논문의 저자가 말하고자 하는 것은 DM을 디자인 관점에서 연구자들에게 향후 연구 방향을 알려주고자 함.

1. Introduction

Conversational System은 크게 두 분류로 나뉨 1. task-oriented system 2. non-task-oriented system 여기서 non-task-oriented는 단순 대화 같이 별도 행위가 필요하지 않은 시스템이고 task-oriented는 예매와 같은 구체적인 태스크를 수행하는 시스템임. 이 논문에선 task-oriented 시스템을 다룸. DM에는 다양한 접근법이 있고, 각각 장단점이 있음.

2. Problem fundamentals and dimensions

A. Dialouge Management

위 그림은 DM의 전체적인 플로우임. DM은 크게 위 아키텍처를 벗어나지 않고 거의 정석으로 사용됨. NLU가 가장 처음으로 유저 발화 정보를 추출함. 크게 3가지로 Intent, entity, dialouge act를 가져옴. 즉 어떤 의도로 말했고, 어떤 것을 말했고, 어떤 행위를 요구하는지를 파악하기 위함임.

1. intent는 goal/task와 거의 동의어로 사용됨
2. entity는 slot과 동의어로 봐도 됨. 위 그림 1을 예로 들자면 departure_city나 destination_city가 entity가 됨.
3. dialouge act는 유저가 단순 서술인지, 질문인지, 요청인지 파악하기 위해 사용됨

그리고 이 모든 정보는 Dialouge State Tracking(이하 DST)에게 전달함. 그리고 DST는 NLU에서 받은 구조적 representation을 저장해둠. 어떻게 대답할지 결정하기 위해. 다른 말로 표현하면 Dialouge State(이하 DS) 유지를 위해 명시적이거나 암시적인 정보까지 전부 저장해둠

그리고 DS에 기반해서 다음 행동은 Dialogue Policy(이하 DP)가 결정함. DP는 일종의 함수로 봐도 됨. DS에 기반해서 행동(Dialouge Act)을 매핑시켜주기 때문에. (일종의 if else와 같이 룰 베이스 형식인듯. NLU에서 처리한 Dialouge Act를 DP에서 받아서 실행시켜주는 방식인듯). 예를 들면 flight-booking이라는 domain에선 action이 크게 4가지로 제한됨. Request, Confirm, Query, Execute. 만약 Request라면 출발 시간과 도착 시간을 물어봐야하고, Confirm이라면 도착 위치가 여기가 맞는지 물어봐야하고, Query라면 항공편 리스트를 가져와야하고, Execute라면 예약 신청해야 함. 이러한 DP 동작의 결과를 NLG가 적절한 응답으로 생성함.

DM 시스템은 이렇게 동작하지만 산학계에서 제안 된 다양한 아키텍처들이 있음. 제시한건 NLU, DST, DP, NLG지만 하나로 합쳐진 것도 있고 그럼.

B. Analysis Dimension

크게 4가지 차원에서 구체적으로 설명함

1. DS: 어떻게 DS가 representation되고, 어떤 정보가 포함되고, 수작업인지 데이터로 학습하는지 설명
2. DST: DS가 결정되는 과정을 설명
3. DP: 다음 action이 어떻게 결정되는지 설명
4. Context support: 유저 의도를 파악하고 적절한 답을 주기 위해, 크게 3가지를 활용함 Converstional history, User profile, External knowledge

3. DM 접근법

DM 방식에는 크게 3가지가 존재함 1. 수작업 2. data-driven 3. 혼합

3.1 Hand-crafted

Rule-based

Rule-based 방식은 가장 초기에 나온 방식으로 한 번에 NLU, DM, NLG 태스크를 수행하는 방식임. AIML(AI Markup Language)라는 개념이 있음. 이건 크게 두 개념으로 구성되는데 1. 카테고리 2. 주제로 구성됨. 명확히 이해는 안되지만 이 논문에선 챗봇으로 예를 들었는데 사용자가 Hi robot이라 입력해야 대화가 시작되고 Hi robot에 대한 답변이 이미 정해져 있어 Hi human이란 답을 하는 방식이라고 함. 아무튼 이 방식의 특징은 당연히 DST와 DP의 역할이 거의? 없다는 것. 바로 NLU 한 다음 NLG를 함. 결론적으로 수 많은 패턴이 있어야 하기 때문에 간단한 태스크 조차 쉽지 않고, 패턴간 중복이나 충돌이 발생해서 이걸 처리하는 비용이 들기 때문에 비효율적이다. (고비용 & 스케일업 어려움)

이런 비효율적인 Rule-based를 보완하기 위해서 DS와 DP가 필요했음. 왜냐면 rule-based는 보통 바로 이전 발화만 저장했는데, 정교하게 만들기 위해 이전 발화 모두를 저장해서 활용할 필요가 생겼고 또 사용자 맞춤을 위해 user-profile 정보가 필요했음. 이런 발화 정보와 유저 프로필과 같은 대화에 도움을 주는 것을 context support라 부름.

Finite State-based

Final State Method는 규칙 기반으로 동일함. 하지만 룰베이스에서 조금 더 확장된 것이라 볼 수 있음. 사용자가 원하는 행위가 충분히 polynomial한 질문 수와 절차로 해결하는 방식이기 때문임. 비행기 예약과 위 그림 3 시나리오로를 보자면 프로그래밍을 통해 시퀀셜하게 이미 정해진 절차가 있어서 반드시 이걸 따라야 함. “다음 주 월요일에 리옹에서 시드니로 가는 편도 항공편을 예약하고 싶다**”**고 말 못함 왜냐면 “출발지 → 목적지 → 날짜 → 편도/왕복”의 일련의 절차 대로 말해야 하기에.

Frame-based

domain ontology기반 방식임. 예를 들자면 음악 틀어달라는 태스크라면 사전정의된 frame은 domain으로 Music을 가질 것이고 intent는 Play music일 것임. 그리고 slot이 될 수 있는 장르와 뮤지션을 요구하거나 수집할 수 있음. frame-based는 사전 정의된 frame을 보고 어느 슬롯이 채워졌고 안채워졌는지 확인해서 DS를 파악할 수 있음. rule-based와 activity-based 기반과 비교해 다른 점은 조금 더 유연하단 것이 장점임.

앞서 기술했듯 어떤 slot이 채워졌는지 안채워졌는지 파악해서 추가 요구하기 때문임. 반면 단점으론 복잡한 DP 알고리즘이 필요하고, 모든 조건에서 추가적으로 정보를 요청하는지 안하는지 테스팅이 필요함. 그럼에도 불구하고 frame-based는 현재에도 사용되는 방식임. 애플 시리, 아마존 알렉사, 구글 어시스턴트가 여기에 해당함. 그래도 이런 어시스턴트 들에서 조금 더 추가되는 부분은 NLU에서 머신러닝 방식이 사용되고, 프레임외에 control model을 추가한다고 함. Control model이 정확히 무엇인지 모르겠지만 봇 개발자가 복잡한 DP 지정을 방지할 수 있다고 함.

3.2 Data-driven

Supervised Learning(이하 SL)과 Reinforce Learning(이하 RL)이 사용됨. SL로는 라벨 있는 데이터로 corpus를 학습하고, RL로는 tiral-and-error 과정을 학습함

….. 읽으면서 추가 예정

결론부터 요약해두자면 이 논문에서 말하고자 하는 DM 접근법은 크게 3가지가 있고 장단점은 다음과 같다.

Abstract

• 의도 분류는 Spoken Language Understanding(SLU)의 하위 태스크에 해당하며, 의도 분류는 SLU의 또 다른 서브 태스크인 Semantic Slot Filling 태스크로 곧 바로 연계되기 때문에 그 중요성을 가짐.
• ML 기반으론 유저 발화 이해가 어렵다. 때문에 이 논문에선 DL 기반의 의도 분류 연구가 최근까지 어떻게 이뤄져왔는지 분석, 비교, 요약한하고, 나아가 다중 의도 분류 태스크가 어떻게 딥러닝에 적용되는지 기술함.

내가 추출한 키워드: intent detection, mulit-intent detection, spoken language understanding, semantic slot filling.

Introduction

Dialouge System은 크게 5개 파트로 나뉨: ASR, SLU, DM, DG, TTS.

• 유저가 발화 하면 ASR을 통해 유저의 발화를 생성하고 SLU 과정으로 넘어가 말하고자 하는 1. 주제 파악 2. 의도 파악 3. Semantic slot filling을 과정을 거침. 이후 Dialouge Management를 거치고 답변 생성 후 TTS로 유저에게 전달.
• 과거엔 SLU에서 Domain recognition이 없었다. 왜냐면 dialouge system이 specific domain에 국한됐기 때문임. 하지만 최근엔 넓은 범위의 domain을 다루고자 하는 필요성이 있기 때문에 추가 됨.
• Intent detection을 다른말로 Intent classification이라고도 부름.
• 도메인 별, 의도 별 사전 정의된 카테고리를 이용해 유저 발화 분류함. 만약 사전 정의돼 있지 않다면 의도를 잘못 분류해서 잘못된 대답을 하게 됨.

• 의도 분류에서 어려운 것은 다중 Domain이 들어왔을 때 어떤 Domain에 속하는지 명확히 해야함. 그렇지 않으면 Domain보다 더 세분화되어 있는 Intent category으로 접근하기 어려움. 위의 예시로 들면 맥락상 기차 말고 비행기 탈꺼니까 기차 환불하고 가장 빠른 비행기 시간 확인해 달라는 것임. 근데 환불인지 시간 확인인지 Domain 수준에서 파악이 안되면 그 다음 단계인 Intent detection과 semantic slot filling을 못함.

2. Intent Detection의 어려움

2.1 데이터 부족

부족하다.

2.2 화자 표현 광범위, 모호함.

• 일반적으로 구어체 사용하고, 짧은 문장과 넓은 컨텐츠를 다루기 때문에 의도 파악이 어려움. 가령 예를 들어 “I want to look for a dinner place”라고 말하면 저녁 식사 장소 찾고 싶단건데 domain이 명확하지 않음. (사실 이 정도면 충분하다 생각하는데 불확실한가 봄)
• 다른 예시 들자면 Hanting이라는 호텔이 있지만 Hanting Hotel이라고 구체적으로 이야기하지 않으면 이해하기 어려움. 또는 티켓 예약 하고 싶다고만 말하면 비행기 티켓인지 기차 티켓인지 콘서트 티켓인지 알 수 없는 것처럼 화자의 표현이 광범위하거나 모호한 경우가 발생해서 machine이 적절한 답변을 주기 어려움.

2.3 암시적인 의도 분류

의도는 명시적인 것(Explicit)과 암시적인 것(Implicit)으로 나눌 수 있음. 유저가 암시적으로 말하면 진짜 유저 의도가 뭔지 추론할 필요가 생김. 예를 들어 요새 건강에 관심이 있다고 말하면 아 오래살고 싶구나 하고 이해할 수 있어야 하는데 그게 어려움. (내가 만든 예시)

2.4 multiple intents detection

multi-label classification과 비슷하지만 다름. 그 차이점은 multi-label classification은 긴 문장 multiple intnets detection은 짧은 문장을 다룸. 짧은 문장으로 다중 의도 분류 해야해서 어려움. 짧은 발화안에 다양한 의도 분류를 해야하고 그 의도 수를 결정해야 하는게 쉽지 않음.

3. Main methods of intent detection

3.1 전통적인 Intent detection 방법론

• 최근에는 intent detection을 Semantic Utterance Classification (SUC)로 여긴다.
• 1993년엔 rule-based가 제안된 적 있고, 2002-2014까진 통계적으로 피처를 뽑아서 분류했다. 가령 예를 들면 나이브 베이즈나 SVM이나, Adaboost, 로지스틱 회귀를 썼었다. 근데 룰베이스의 경우 정확도는 높지만 새로운 카테고리가 추가될 때마다 수정해야 하는 번거로움이 있고, 통계적인 방식은 피처의 정확도나 데이터 부족문제가 있다. 근데 지금도 화자의 real intent detection은 여전히 어려운 연구 주제다.

3.2 현재 주류 방법론

워드 임베딩, CNN, RNN, LSTM, GRU, Attention, Capsule Network 등이 있다. 전통적인 방법과 비교하면 성능이 크게 좋아졌다.

3.2.1 워드 임베딩 기반 의도 분류

3.2.2 CNN 기반 의도 분류

• CNN 기반으로 해서 피처 엔지니어링 과정을 많이 줄이고 피처 표현력도 좋아졌다. 근데 여전히 CNN으론representation 한계 있다.

3.2.3 RNN 기반 의도 분류

• CNN과 달리 워드 시퀀스를 표현할 수 있음. 2013년에 context 정보 이용해서 Intent detection의 error rate를 줄인 연구가 있음. RNN은 기울기 소실과 기울기 폭발 문제가 있고 이 때문에 long-term depdendence 문제를 초래함.
• 그래서 이 문제 해결하려고 LSTM이 나옴. LSTM가지고 ATIS 데이터셋 (Air Travel Information System)에서 RNN보다 에러율 1.48%을 줄임.
• GRU는 LSTM 개선한 모델임. ATIS와 Cortana 데이터셋에서 성능이 둘다 같았지만 GRU가 파라미터가 적었음.
• 2018년엔 짧은 텍스트로 인해 발생하는 data sparse 문제를 해결하기 위해 Biterm Topic Model(BTM)과 Bidirectional Gated Recurrent Unit(BGRU) 기반 멀티턴 대화 의도 분류 모델이 제시됨.
• 위 두 모델을 합친 모델은 의료 의도 분류에서 좋은 성능을 냈음.

. . .

3.2.6 캡슐 네트워크 모델 기반 의도 분류

캡슐 개념은 CNN의 표현 한계 문제를 해결하기 위해 2011년에 힌튼에 의해 제시됐었음. 캡슐은 vector representation을 가짐. 이후 2017년에 CNN scalar output feature detector를 vector representation capsule로 대체하고 max pooling을 프로토콜 라우팅으로 대체하는 캡슐 네트워크가 제안됨. CNN과 비교하자면 캡슐 네트워크는 entity의 정확한 위치 정보를 유지함.

결론을 말하자면 capsule network는 텍스트 분류 태스크 잘 수행하고, multi-label 텍스트 분류에도 잘 동작함.

. . .

4. 의도 분류 평가 방법

현재 Intent Detection은 Semantic Discourse Classification 문제로 여겨짐. 결론은 F1-score 사용함.

5. 성능 비교

아래는 다른 연구 논문에서 가져온 성능 비교 결과임. 데이터셋은 SNIPS와 CVA(Commercial Voice Assistant)를 사용했음. 참고로 SNIPS는 영어 데이터셋이고 CVA는 중국어 데이터셋임.

Intent Capsnet이 가장 성능이 좋더라.

Conclusion

• 머신러닝 기반의 의도 분류 태스크는 깊이 이해 못한다. 그래서 딥러닝 기반 의도 분류 태스크가 성능이 좋다. capsule network model이 의도 분류 태스크에서 좋은 성능을 내고, multi-label classification도 잘한다. self-attention 모델은 의도 분류 과정에서 문장의 다양한 semantic feature들을 추출할 수 있다.
• 의도 분류는 e-commerce, travel consumption, medical treatment, chat에도 적용되고 있으며, 침입 탐지 시스템과 같은 네트워크 보안 분야에서도 적용된다.
• 전통적인 dialouge system은 주로 single intent detection만 가능하다. 하지만 다양한 의도는 셀 수 없이 많으므로 multi intent detection이 가능하도록 연구가 필요하다.

궁금해진 것

1. Semantic slot filling의 과정은 구체적으로 어떻게 이뤄지는가?
2. Dialouge Management란 무엇이고 어떻게 동작하는가?
3. Dialouge Generation 과정은 구체적으로 어떻게 이뤄지는가?
4. task-oriented vertical domain이 무엇인가? vertical이 있으면 horizontal domain도 있을 것인데 각각은 무엇인가?

알게 된 것

1. 도중에 fine-grained라는 말이 나옴. 이건 잘게 쪼갠 것을 의미함. 반면 coarse-grained는 덩어리째를 의미함.

한 줄 평

• 큰 틀에서 연구가 어떻게 이뤄지는지 대략적으론 알 수 있어서 좋았지만 Dialougue System의 구체적으로 어떻게 이뤄지는지 나와있지 않고 데이터셋을 잘 정리해서 소개하지 않아서 아쉬움.

1. 버블 정렬 (Bubble Sort)

버블정렬은 서로 인접해 있는 요소 간의 대소 비교를 통해 정렬한다. 버블 정렬은 정렬 알고리즘 중 가장 단순한 알고리즘이으로, 단순한 만큼 비효율적이다. 시간 복잡도가 최고, 평균, 최악 모두 $O(n^2)$이며 공간복잡도는 하나의 배열만 사용하므로 $O(n)$을 가진다. 동작 방식은 인접한 두 요소간의 대소 비교를 진행한다.

만약 배열에 n개의 요소가 있을 경우 1번째 원소 vs 2번째 원소를 비교하고 2번째 원소 vs 3번째 원소를 비교하고, ... n-1번째 원소 vs n번째 요소를 비교하면 1회전 비교가 끝난다. 1회전이 끝나면 가장 큰 원소는 맨 뒤에 위치하게 되므로 2회전 비교에서는 제외된다. 마찬가지로 두 번째로 큰 원소는 가장 큰 원소 앞에 위치하게 되므로 3회전 비교에서는 제외된다. 즉 버블 정렬을 1회 수행할 때 마다 정렬해야 할 원소가 하나씩 줄어든다. 이를 코드로 구현하면 아래와 같다. 

def bubble_sort(array):
	""" Best: O(n^2) Average: O(n^2) Worst: O(n^2) | O(n) """
    for i in range(len(array)):
        for j in range(len(array)-i-1):
            if array[j] > array[j+1]:
                array[j], array[j+1] = array[j+1], array[j]
    return array

2. 삽입 정렬 (Insert Sort)

삽입 정렬이란 정렬을 진행할 원소의 index보다 낮은 곳에 있는 원소들을 탐색하며 알맞은 위치에 삽입해주는 정렬 알고리즘이다. 동작 방식은 두 번째 index부터 시작한다. 그 이유는 첫 번째 index보다 작은 원소가 없기 때문이다. 알고리즘이 동작하는 동안 계속해서 정렬이 진행되므로 반드시 맨 왼쪽 index까지 탐색하지 않아도 된다는 장점이 있다. 모두 정렬되어 있는 Optimal한 경우 모든 원소가 한 번씩만 비교되므로 $O(n)$의 시간 복잡도를 가진다. 또한 공간복잡도는, 하나의 배열에서 정렬이 이루어지므로 $O(n)$이다.

삽입 정렬을 코드로 구현하면 아래와 같다. 첫 번째 for문은 정렬할 원소를 차례대로 선택하는 것이며, 두 번째 for문은 정렬할 원소보다 아래 인덱스에 있는 요소와 비교하기 위함이다. 

def insert_sort(array):
	""" Best: O(n) Average: O(n^2) Worst: O(n^2) | O(n) """
    for i in range(1, len(array)):
        for j in range(i, 0, -1):
            if array[j-1] > array[j]:
                array[j-1], array[j] = array[j], array[j-1]
    return array

삽입 정렬을 최적화할 경우 아래 코드와 같다.

def insert_sort(array):
    for i in range(1, len(array)):
        j = i
        while j > 0 and array[j-1] > array[j]:
            array[j-1], array[j] = array[j], array[j-1]
            j -= 1
	return array

3. 선택 정렬 (Selection Sort)

선택 정렬이란 배열에서 최소값을 반복적으로 찾아 정렬하는 알고리즘이다. 

시간복잡도 최선, 평균, 최악 모두 $O(n^2)$에 해당하는 비효율적인 알고리즘으로 정렬 여부와 상관없이 모든 경우의 수를 전부 확인한다. 동작방식 3단계로 구성된다. 첫 번째는 주어진 배열에서 최소값을 찾는다. 두 번째는 최소값을 맨 앞의 값과 바꾼다. 세 번째는 바꿔준 맨 앞 값을 제외한 나머지 원소를 동일한 방법으로 바꿔준다. 이를 알고리즘으로 나타내면 다음과 같다.

def selection_sort(array):
	""" Best: O(n^2) Average: O(n^2) Worst: O(n^2) | O(N^2) """
	for i in range(len(array)):
		idx = i
		for j in range(i+1, len(array)):
			if array[idx] > array[j]:
				idx = j
		array[idx], array[i] = array[i], array[idx]
	return array

덧붙여 선택 정렬은 크게 2가지로 최소 선택 정렬과, 최대 선택 정렬이 있다. 최소는 위와 같이 오름차순으로 정렬하는 것이고 최대는 위와 반대로 내림차순으로 정렬하는 것이다. 

4. 퀵 정렬 (Quick Sort)

퀵 정렬은 분할정복법과 재귀를 사용해 정렬하는 알고리즘이다. 파이썬이나 자바에서 언어에서 자체 내장되어 있는 정렬 알고리즘도 퀵 정렬을 기반으로 한다. 

퀵 정렬에는 피봇(Pivot)이라는 개념이 사용된다. 피봇은 한 마디로 정렬 될 기준 원소를 뜻한다. 피봇 선택 방법에 따라 퀵 정렬의 성능이 달라질 수 있다. 최적의 피봇 선택이 어려우므로 임의 선택을 해야 한다. 보통 배열의 중앙 값을 선택한다. !퀵 정렬의 동작방식은 다음과 같다. 가령 예를 들어 배열 [5, 6, 1, 4, 2, 3, 7]이 있고, 피봇을 임의로 4를 선택했다 가정하자. 이후 4를 기준으로 작은 것은 왼쪽으로 큰 것은 오른쪽으로 보내 [1, 2, 3] < 4 < [5, 6, 7]를 생성한다. 다시 왼쪽에서부터 임의의 피봇 2를 설정하여 [1] < 2 < [3]을 생성하고 오른쪽에선 임의의 피봇 6를 설정하여 [5] < 6 < [7]로 나눈다. 만약 배열 길이가 1이 된다면 가장 정렬 완료된 것이므로 분할된 배열을 합쳐 줌으로써 정렬을 마친다. 이를 알고리즘으로 구현하면 다음 코드와 같다.

def quick_sort(array : list) -> list:
    """ Best: O(nlogn) Average: O(nlogn) Worst: O(n^2) | O(nlogn) """
    if len(array) <= 1:
        return array

    pivot = array[len(array) // 2]
    small, equal, big = [], [], []

    for num in array:
        if num < pivot:
            small.append(num)
        elif num > pivot:
            big.append(num)
        else:
            equal.append(num)

    return quick_sort(small) + equal + quick_sort(big)

5. 병합 정렬 (Merge Sort)

6. 힙 정렬 (Heap Sort)

7. 셸 정렬 (Shell Sort)

8. 기수 정렬 (Shell Sort)

9. 카운팅 정렬 (Counting Sort)

Reference

[1] https://jinhyy.tistory.com/9 

[2] https://velog.io/@delmasong/AlgorithmInsertion-Sort-삽입-정렬

[3] https://gfycat.com/ko/snappymasculineamericancicada

4] https://latte-is-horse.tistory.com/197

최근, 향후 창업을 준비하고자 몇몇 세미나를 듣고 있다. 이번이 세 번째다. 어제는 (2022.07.26(화) 16:00~18:00) 스타트업 해외진출 관련하여 마곡, 서울창업허브 (M+)에서 "Awake, It's time to innovation Asia"라는 주제로 세미나를 들었다. 연사는 엑센트리벤처스의 윤우근 이사회 의장이다. 엑센트리는 런던베이스 엑셀러레이터로, 스타트업이 런던쪽에 랜딩할 수 있도록 자본 지원과 프로그램을 제공한다고 한다. 오늘 세미나의 핵심 내용은 간단했다. 스타트업의 해외 진출을 위해선 6~7가지로 요약할 수 있었다.

첫 번째로는 스타트업의 핵심기술이 글로벌 IP(Intellectual Property)로 보호받고 있어야 하는 것이다. 그 이유는 대기업의 기술 탈취가 심하기 때문이라 한다. 법정 공방에서도 중소기업 vs 대기업 구도에서 중소기업의 패소율이 84%에 달하며 대기업은 0.2%이란 수치를 볼 수 있었다. 보통 선진국에서는 약자 보호 시스템이 마련되어 있지만 우리나라는 그렇지 않다는 것이다. 그렇기에 핵심 기술이 글로벌 IP로 보호받고 있어야 해외진출이 가능하다 말한다. 두 번째는 전 세계에 핵심 기술을 알릴 홍보맨이 반드시 필요하다는 것이다. 홍보맨은 CEO만큼 제품이나 서비스를 잘 알고 있는 사람이여야 하며, 투자유치를 위해 계속해서 IR도 함께 해야 한다고 한다. 쓰는 시점에서 헷갈리는 데, IR은 대표의 역할인지 홍보맨의 역할인지 아니면 아무나 해도 상관 없는지 헷갈린다. IR에 대해 들으며 들었던 생각으론 가급적이면 외부 자본을 차입하지 않고 외부 자본에 독립적인 기업을 만들 수 있다면 가장 좋지 않을까 하는 생각이 들었다. 세 번째는 영어라고 말한다. 더 말하지 않아도 필요성을 절감한다. 창업 직전에는 어느 정도 네이티브와 비즈니스 영어를 문제 없이 구사하는 것을 목표로 하고 있다.

네 번째는 현지 모임에서 동양인, 한국인을 찾아 일원이 되어야 한다고 말한다. 런던 스타트업은 주로 60%~70%가 서양인이라 우리도 그렇듯 어느정도 차별이 있을 수 있기 때문이라 말한다.  다섯 번째는 정부지원 등 각종 프로그램을 타고 해외로 진출하는 것이 그나~마 성공 확률이 높다고 말한다. 여섯 번째는 현지 밴처캐피털이나 CEO와 밋업을 하는 것이라 말하고, 일곱 번째는 잠재적 고객과의 만남이라고 한다. 또 중요한 것은 Global standard 수립이라는 것이다. 삼성과 SK케미칼과 같이 1,2차 벤더사가 되기 위해서는 회계나 법률적인 부분을 6개월간 수정을 거쳐 일종의 표준화를 시키는 과정이 있다는 것이다. 여기까지가 들었던 핵심 내용이다.

이외의 내용으론 몇몇이 있었는데 그 중 첫 번째는 유니콘 기업 관련 산업이었다. 전세계 유니콘 기업이 약 1,170(?)개가 있고 미국 629개, 중국 173개, 인도 68개, 영국 44, 독일 29, 프랑스 24, 이스라엘 22 등등이 있다고 한다. 이러한 유니콘 기업은 대부분 헬스케어, 전기차, 빅데이터, 바이오이지만 한국에는 이러한 기업이 없고, 따라서 기회가 있다고 한다. 두 번째는 창업은 돌파구라고 말하며 창업은 돈이 아니라 소명의식이 필요하다 말한다. 절감한다. 소명의식의 예로는 사회공헌이나 고용창출이 있다고 말했다. 고용창출은 생각해본 적 없었지만 유니콘 기업 하나가 많은 고용창출을 하여 사회에 도움이 된다고 한다.

세 번째는 지금은 산업간의 경계가 모호한 빅테크의 시대라고 말한다. 단계를 밟아가면 느릴 수 있다고 말한다. 뛰어넘어야 관심받고 투자 받는다고 한다. 중국이 현금 사용하다가 곧 바로 QR로 넘어간 것을 예를 들어 줬다. 네 번째부턴 맥락이 잘 기억이 나질 않는데 초기엔 VC 심사역을 만나는 것은 도움이 되지 않는다는 것이다. 엔젤이나 LLC(?)를 만나야 한다고 한다. 또 한국 법인과 해외 법인을 함께 만들라 한다. 해외법인만 설립하면 지원받기 힘들다는 이야길 하셨다.

• 이후로 생각나는 대로 적자면 정부에선 예산 사용에 관심 있지 스타트업이 잘 되는 것 관심이 없다.
• 현지서 피봇 기다려주는 엑셀러레이터 별로 없다. 하지만 최근 피봇까지 도와주는 몇몇이 생겨났다. 찾아서 그 프로그램 타고 글로벌 진출해라.
• 한 나라에 특화된 산업 거의 없다. 장벽 거의 허물었다.
• 희석된 지분에 대해 VC가 바라보는 관점은 Co-founder에게 많으면 +고 단순 엔지니어에게 많으면 -다. 한 질문자가 표면적으로라도 지분 조정을 해야할까요 하는 질문으로 미루어 서류상으로 무언가가 되나보다. 연사께서 CEO가 67.4%를 가져야 한다고 말한다. 어떤 배경에서 이런 수치가 나온 것인지 검색해보니 주총에서 보통 결의사항과 특별 결의사항이 있는데 이 중 특별 결의사항을 통과시키기 위해 2/3의 지분이 있어야 한다는 것이다. 결론적으론 안정적인 경영을 위한 것이다.
• 홍보 담당자는 스타트업 초기에 채용은 부담스러울 수 있기에 스케일 업이 필요 할 때 채용하는 것이 적합하다.
• 국내 글로벌 진출 프로그램관련해서 무역협회~, 중소기업~ 두 가지 추천해주셨는데 잘 듣지 못했다.
• 엑센트리 벤처스에서 하는 것은 기업 특징에 따라 다르지만, 크게 두 가지로 첫 번째론 잠재 고객이 누굴까 깊이 고민해서 BM을 재구성해주는 것과 두 번째는 해외 투자자의 관점으로 어떤 것을 수정하면 조금이라도 더 투자를 받을 수 있을지를 도와준다고 한다

import sys
input = sys.stdin.readline

N, M = map(int, input().split())
dp = [[0] * (N+1)]

for _ in range(N):
    nums = [0] + list(map(int, input().split()))
    dp.append(nums)

for i in range(1, N+1):
    for j in range(1, N):
        dp[i][j+1] += dp[i][j]
    
for j in range(1, N+1):
    for i in range (1, N):
        dp[i+1][j] += dp[i][j]

for _ in range(M):
    x1, y1, x2, y2 = map(int, input().split())
    result = dp[x2][y2] - dp[x1-1][y2] - dp[x2][y1-1] + dp[x1-1][y1-1]
    print (result)

이 문제를 관통하는 핵심아이디어는 아래와 같이, 입력 받은 표의 수를 행축으로 합을 구해준 다음 열 축으로 합을 구해주는 것이다. 

행 슬라이딩 합 이후 열 슬라이딩 합까지 해준 테이블을 우리는 DP 테이블이라 하자. 이후 구간합을 구하기 위한 예시로 (1, 1)과 (4, 4)를 입력 받았다면 구간합은 입력 받은 표의 빨간 영역의 합이 될 것이다. (45 = 3+4+5+4+5+6+5+6+7)

빨간 영역의 합을 구하기 위해선 전체 입력 받은 표에서 파란 부분을 각각 빼주고 초록 부분이 두 번 차감되었으니 한 번 더해주는 것이다. 

전체 입력 받은 표를 대표하는 값은 (1, 1) ~ (4, 4)의 합이 모두 저장된 DP[$x_2$][$y_2$]에 있다. 또한

첫 번째 파란색 영역을 대표하는 값은 DP[$x_1-1$][$y_2$]에 저장돼 있으며

두 번째 파란색 영역을 대표하는 값은 DP[$x_2$][$y_1-1$]에 저장돼 있으며

세 번째인 초록 영역을 대표하는 값은 DP[$x_1-1$][$y_1-1$]에 저장돼 있다.

따라서 최종 점화식은 dp[$x2$][$y2$] $-$ dp[$x_1-1$][$y_2$] $-$ dp[$x_2$][$y_1-1$] $+$ dp[$x_1-1$][$y_1-1$]이 된다.

문제 링크

https://www.acmicpc.net/problem/1068

풀이 코드

import sys
input = sys.stdin.readline

def dfs(K: int) -> None:
    tree[K] = -2
    for i in range(N):
        if K == tree[i]:
            dfs(i)

if __name__ == "__main__":
    # input 
    N = int(input())
    tree = list(map(int, input().split()))
    K = int(input())

    # main algorithm
    dfs(K)

    # output
    count = 0 
    for i in range(len(tree)):
        if tree[i] != -2 and i not in tree: # 제거 표시인 -2도 아니고, 자신을 부모 노드로 갖는 노드도 존재하지 않을 경우
            count +=1
    print(count)

풀이 과정

핵심 아이디어는 DFS 알고리즘을 통해 부모 노드를 제거 한 뒤, 부모 노드에 종속된 자식 노드를 탐색하며 제거해주는 것이다.

가령 예제 입력 4번으로 예시를 들면 다음과 같다.

[-1, 0, 0, 2, 2, 4, 4, 6, 6]은 0~8까지의 노드 번호 위치에 부모 노드를 나타낸 것이다. 이 중 4번 노드를 없애고자 한다면 5번째 인덱스 값인 2를 제거해주어야 한다. 하지만 실제로 리스트에서 제거할 경우 인덱스의 변화가 생겨 일관된 알고리즘 적용에 번거로워지므로 제거했단 표기로 대신한다. -1은 루트 노드로 사용되니 -2란 값이 적당할 것이고 이를 적용하면 다음과 같아진다. [-1, 0, 0, 2, -2, 4, 4, 6, 6]

위 그림에서 노드 4를 -2로 제거 표기 해준 것이다. 이후 4에 종속된 5, 6 그리고 6에 또 종속된 7, 8을 DFS 알고리즘으로 반복 탐색하며 -2로 변경한다면 4에 종속되지 않았던 노드들만 남아 있게 될 것이다.

문제에서 요구하는 핵심은 어떤 한 마을에 우체국이 세워진다 가정할 때, 다른 마을 사람들이 우체국이 세워진 마을에 가기 위해 필요한 거리의 합이 최소가 되는 마을 번호를 찾는 것이다. 크게 두 가지 아이디어가 있다. 첫 번째는 단순하게 모든 마을 사람의 총합을 구하고 [(마을 번호, 사람 수), (마을 번호, 사람 수), ...]의 리스트를 순회할 때 절반이 넘어가는 그 마을 번호를 찾는 것이다. 이 접근이 정답의 핵심 아이디어다. 처음에 이 방법이 희번뜩하며 떠올랐지만 단순하단 이유로 올바른 접근이 아닐 것이란 생각을 하고 다른 방법을 찾게 됐다. 

[정답 코드]

import sys
input = sys.stdin.readline

villiage = []
all_people = 0

N = int(input())

for i in range(N):
    n_viliage, people = map(int, input().split())
    villiage.append([n_viliage, people])
    all_people += people

villiage.sort(key= lambda x: x[0])

count = 0
for i in range(N):
    count += villiage[i] [1]
    if count >= all_people/2:
        print (villiage[i][0])
        break

두 번째 아이디어는, 반복문을 통해 [(마을 번호, 사람 수), (마을 번호, 사람 수), ...]을 차례대로 돌면서 최소 값을 구하는 것이다. 구체적으로 첫 번째 마을에 우체국이 세워졌다 가정하면 두 번째 세 번째 마을에서 사람들이 오기 위해 얼마나 비용이 드는지를 구하는 것이다. 예제 입력을 예시로 삼는다면

첫 번째 루프 즉, 첫 번째 마을에 우체국이 세워진다면 아래와 같이 총 11의 비용이 든다.

(1번째 마을 - 1) * 3 = (1-1) * 3 = 0

(2번째 마을 - 1) * 5 = (2-1) * 5 = 5

(3번째 마을 - 1) * 3 = (3-1) * 3 = 6

두 번째 루프 즉, 두 번째 마을에 우체국이 세워진다면 아래와 같이 총 6의 비용이 든다.

(1번째 마을 - 2) * 3 = (1-2) * 3 = 3 

(2번째 마을 - 2) * 5 = (2-2) * 5 = 0

(3번째 마을 - 2) * 3 = (3-2) * 3 = 3

세 번째 루프 즉, 세 번째 마을에 우체국이 세워진다면 아래와 같이 총 11의 비용이 든다.

(1번째 마을 - 3) * 3 = (1-3) * 3 = 6

(2번째 마을 - 3) * 5 = (2-3) * 5 = 5

(3번째 마을 - 3) * 3 = (3-3) * 3 = 0

* 음수가 되는 부분은 절대값을 취해줘야 함

따라서 총 6의 비용이 드는 두 번째 마을이 가장 우체국을 세우기 적합한 것이다. 이를 구현한 코드는 아래와 같으며, O(N^2)의 시간 복잡도로 인해 시간 초과가 발생한다.

[초기 시도한 코드]

import sys
input = sys.stdin.readline

N = int(input())

village = [0] * (N + 1)
people = [0] * (N + 1)

min_values = [0] * (N +1)

for i in range(1, N+1):
    x, a = map(int, input().split())
    village[i] = x
    people[i] = a

for i in range(1, N+1):
    value = 0
    for j in range(1, N+1):
        value += abs(village[j] - i) * people[j]
    
    min_values[i] = value

del min_values[0]
index = min_values.index(min(min_values))
print (village[index+1])