우선적으로 Flutter 앱 내에 Firebase를 추가하고, 등록하는 절차를 수행해야 한다.
아래 링크에서 시키는 대로 하자.

https://firebase.google.com/docs/flutter/setup?hl=ko&platform=ios

 

Flutter 앱에 Firebase 추가

Google은 흑인 공동체를 위한 인종적 평등을 추구하기 위해 노력하고 있습니다. 자세히 알아보기 이 페이지는 Cloud Translation API를 통해 번역되었습니다. Switch to English 의견 보내기 컬렉션을 사용해

firebase.google.com

1,2,3 단계 수행 이후

flutter pub add cloud_firestore
flutter pub add firebase_messaging
flutterfire configure
flutter run

 

위의 명령어를 이용해 Flutter app에 파이어스토어와 클라우드메세지 플러그인을 추가한다.
파이어스토어가 필요한 이유는 기기마다 앱의 고유한 주소가 형성되어 그쪽으로 알림을 보내게 되는데, 서버(Python)에서 그 주소(토큰)를 저장하고 조회하는 수단으로 DB를 사용하기 위함이다.

이 포스트에서는 안드로이드 대상으로만 구현한다. ios는 추가적인 설정이 필요함.

 

/android/build.gradle 

만약 빌드 시 sdk version 관련 에러가 뜨는 경우, compileSdkVersion 을 33으로 minSdkVersion을 32로 수정한다. 
임시 조치지만, 현재로써는 이게 최선.

 

/main.dart

import 'package:flutter/material.dart';
import 'package:firebase_core/firebase_core.dart';
import 'package:firebase_messaging/firebase_messaging.dart';
import 'firebase_options.dart';
import 'package:cloud_firestore/cloud_firestore.dart';

@pragma('vm:entry-point')
Future<void> _firebaseMessagingBackgroundHandler(RemoteMessage message) async {
  print("Handling a background message: ${message.messageId}");
}

main() async {
  WidgetsFlutterBinding.ensureInitialized();
  await Firebase.initializeApp();
  FirebaseMessaging.onBackgroundMessage(_firebaseMessagingBackgroundHandler);
  final fcmToken = await FirebaseMessaging.instance.getToken();
  await FirebaseFirestore.instance.collection("UserTokens").doc("User").set({
    'token': fcmToken,
  });
  runApp(MyApp());
}

class MyApp extends StatelessWidget {
  const MyApp({Key? key}) : super(key: key);

  // This widget is the root of your application.
  @override
  Widget build(BuildContext context) {
    return MaterialApp(
      title: 'Flutter Demo',
      theme: ThemeData(
        primarySwatch: Colors.blue,
      ),
      home: const MyHomePage(title: 'Flutter Demo Home Page'),
    );
  }
}

class MyHomePage extends StatefulWidget {
  const MyHomePage({Key? key, required this.title}) : super(key: key);

  final String title;

  @override
  State<MyHomePage> createState() => _MyHomePageState();
}

class _MyHomePageState extends State<MyHomePage> {
  @override
  void initState() {
    FirebaseMessaging.onMessage.listen((RemoteMessage message) {
      final snackBar = SnackBar(content: Text(message.data.toString()));
      ScaffoldMessenger.of(context).showSnackBar(snackBar);
    });
    super.initState();
  }

  @override
  Widget build(BuildContext context) {
    return Scaffold(
      appBar: AppBar(
        // Here we take the value from the MyHomePage object that was created by
        // the App.build method, and use it to set our appbar title.
        title: Text(widget.title),
      ),
      body: Center(),
      floatingActionButton: FloatingActionButton(
        onPressed: (() => 0),
        tooltip: 'Increment',
        child: const Icon(Icons.add),
      ), // This trailing comma makes auto-formatting nicer for build methods.
    );
  }
}

맨 위에 선언된 Handler는 백그라운드를 담당하고, 포그라운드에서 메세지를 수신한 경우에는 MyHomePageState에서
실행된 FirebaseMessaging.onMessage.listen 리스너가 메세지를 수신하여 message로 콜백한다. 위의 예제는 스낵바를 이용해서 포그라운드 메세지를 출력할 뿐이다. 백그라운드 알림을 수정하기 위해서는 다른 설정을 해줘야 한다. 주의할 점은 main 에서 Firebase.InitializeApp()를 호출하는 부분에서 await 키워드를 사용했다는 점, 그리고 아래와 같이 fcmToken을 얻어서 파이어스토어에 송신한다는 점.

이제 콘솔에서 새 캠페인을 시작해서 테스트 메세지를 보내보면 백그라운드 상태와 포그라운드 상태일 때 Debug Console에서 수신했다는 메세지가 뜬다. 백그라운드 알림은 Title/body에 따라서 오는데, 포그라운드 알림은 데이터가 텅 비어 있는 것처럼 보인다. 내용물을 전달하려면 Title/body가 아니라,  추가 옵션에서 key:value를 추가해서 보내면 된다.

 

이제 fcm으로 메세지를 보내는 서버를 구현해야한다.

먼저 firebase 내 프로젝트 설정 페이지에서 키를 만든다.
그리고 아래의 python 파일을 새롭게 만들고, 키 파일의 경로를 입력한다.

 

fcm_messaging.py

import firebase_admin
from firebase_admin import credentials
from firebase_admin import messaging
from firebase_admin import firestore
cred = credentials.Certificate("키 파일 경로")
default_app = firebase_admin.initialize_app(cred)
db = firestore.client()
doc_ref = db.collection("UserTokens").document("User")
registration_token = doc_ref.get().to_dict()['token']
message = messaging.Message(
    notification=messaging.Notification(
    title="테스트 제목",
    body="테스트 내용",
),
    data={
        'score': '8501',
        'time': '2:45',
    },
    token=registration_token,
)
response = messaging.send(message)
print('Successfully sent message:', response)

간단히 설명하면 DB에 저장된 fcmToken을 불러온 뒤, 그쪽으로 메세지를 송신한다. 
쓰임새에 따라 함수로 만들어서 원하는 알고리즘에 집어넣으면 된다.

 

동일한 연산임에도 답이 다르게 나올 때가 있다.

나누기 연산의 결과는 float로 바뀌므로 아랫 자리 수가 소실됨.
int를 이용해서 캐스팅해도 막을 수 없음.

동적 프로그래밍은 n번째의 정답을 추론하기 위해 n-1 번째 정답을 이용하는 것을 의미한다.

수열에서의 가장 큰 합을 가지는 Subarray를 찾는 문제를 해설.

풀이는 다음과 같다.

class Solution:
    def maxSubArray(self, nums: List[int]) -> int:
        max_num = -99999
        now_num = 0
        for i in nums:
            if(now_num < 0):
                now_num = 0
            now_num = now_num+i
            max_num = max(max_num, now_num)
        return max_num

수열 nums에 대해서 maximum subarray의 합을 구하는 것은

nums[:-2] 즉, 마지막 바로 직전까지의 수열을 이용하면 가능하다.

nums보다 하나 적은 수열에서 얻은 maximum subarray의 합이

다음 정답에 어떻게 영향을 미치는 가를 고민해보자.

 

x_n이 수열의 마지막 숫자라고 생각했을 때,
생각할 수 있는 정답은 3가지 경우 중 하나가 된다.

① 바로 이전 항을 포함하며 계속 이어지는 수열
② x_n 단 하나 (바로 이전 항까지의 합이 음수인 경우)
③ x_(n-1) 을 포함하지 않는 이전의 수열

 

여기서 헷갈릴 수 있는 부분이 x_n이라는 수를 만나기 전까지

그 직전까지의 Subarray를 생각하는 것이다. 

최대의 Subarray를 찾기 위해서는 수열의 첫번째 항부터

그 다음 수가 양수이든 음수이든 상관없이 계속 더해보면서

부분 합을 체크해야 한다. 왜냐하면 subarray를 추가하는 과정에서

중간에 음수가 나온다고 해도 그것을 포함한 수열의 합이 양수라면,

다음에 나타날 숫자들이 역대 최대의 부분합을 만들어 낼 가능성이 있기 때문이다.

( +1이라도 최대에 보탬이 될 수 있음)

다시 말해 새로운 수가 음수여서 직전의 부분합보다 감소한다고 해도

이후 또 새로운 숫자를 추가하면 그 부분합이 역대 최대가 될 수 있다는 뜻이다.

 

다만 만들던 subarray를 끊고, 새롭게 시작해야 하는 순간이 있는데

그것은 여태까지의 subarray의 합이 음수가 되는 시점이다.

이어오던 subarray를 새로운 수에 붙이면 오히려 손해이기 때문에

Subarray를 이어나갈 필요가 없이, 새로운 수를 기점으로 다시 subarray를 따진다.

 

 

 

다시 본론으로 돌아오면 n개의 수열 nums의 최대 부분합은

n-1개의 수열 nums[:-2]의 최대 부분합과,

혹시 몰라서 끌고 온 subarray를 이용해서 구할 수 있다.

 

1. 혹시 몰라서 직전의 수를 포함하면서 끌고 온 subarray + 새로운 수(x_n)

2. 새로운 수(x_n)

3. 1번과 같은 수인지 아닌지는 모르지만 지금까지 중 역대 최대였던 합

 

위의 코드에 의하면 '혹시 몰라서 직전의 수를 포함하면서 끌고 온 subarray'의 부분합은

now_num 이라는 변수에 저장되어 있다. now_num이 역대 최대의 부분합인지는 모르지만

새로운 수 x_n을 더했을 때 최대의 부분합이 될 지,

아니면 그 뒤로도 계속 이어나갈 때 어느 순간 최대의 부분합이 될지 모른다.

그렇기 때문에 now_num에 저장하면서 부분합을 저장해나가는 것이다. 

이것은 지금까지 제일 컸던 부분합을 기억하는 것과는 별개의 것이 된다.

 

물론 끌고 온 subarray가 음수라면 그것은 전혀 의미가 없다. 무조건 방해가 된다.

이때는 0으로 바꾼다. 이것은 새로운 수로부터 다시 subarray를 만들겠다는 

단순한 테크닉에 불과하다. now_num = max( now_num + i, i) 의 꼴로 생각해도 무방하다.

 

 

이전까지의 부분합에 x_n을 더하거나, 혹은 x_n으로 새로운 subarray를 시작한다.

 

최종적으로 지금까지 역대 최대의 합(nums[:-2]의 최대 부분합) max_num과

새롭게 만들어진 subarray를 비교한다. 여기서 이긴 수가 최대의 부분합이 된다.

 

 

카데인 알고리즘은 이 문제만을 풀기 위해 생각한 알고리즘이기 때문에,

단순히 이 문제를 이렇게 풀었다라는 이해를 넘어서는

동적 프로그래밍 관점에서의 포괄적인 이해가 필요하다.

우리는 n번째 항의 정답을 얻기 위해서 n-1번째 정답을 기억해놨다.

그렇지만 n-1번째 정답과 무관한 n번째 정답이 만들어질 가능성이 있었기 때문에

정답이 될 수 있는 경우를 모두 고려해봐야만 했다.

(이를 Greedy 하다고 생각할 수도 있는 것 같다.)

알고리즘의 핵심은 "이전까지의 사례"를 이용했다는 점이다.

subarray를 이어가는 것도, max_num을 기억하고 비교하는 것도 그러하다.

 

결국 직전까지의 항과 지금의 항의 '관계'와 정답의 가능성을 얼마나 잘 이해하고,

가장 효율적인 형태의 식을 정의할 수 있느냐가 동적 프로그래밍의 열쇠인듯 하다.

 

+ Recent posts