1. 시작 배경

졸업을 앞두고 추억 한번 만들어보자는 계기로 대동제에 노점을 열기로 했다. 단순히 음식을 파는 데서 끝내지 않고, 나름 전공인데 뭐라도 해야하지 않겠냐며 모바일 주문·결제 시스템을 도입하자고 제안했고, 그 제안을 실제로 구현하게 되었다.

2. 기획 단계

주제 선정 발주자와 사용자가 명확했기에 복잡한 기획 없이 바로 주문-결제 시스템을 만들기로 결정.

인원 배정 프론트엔드 팀, 백엔드 팀으로 나눴으며, 백엔드 인원중 한명이 DB 설계를 맡기로 함.

일정 계획 축제일인 6월 4일 전까지 완성. 마감은 5월 28일로 잡고 계획을 세움.

회고 실사용자가 곁에 있어 빠른 피드백이 가능했던 점은 장점. 그러나 일정이 촘촘하게 계획되진 않아 일정관리가 어렵게 느껴졌음. 백엔드를 맡은 2·3학년들에게 개념을 가르치는 데 많은 시간이 들었고, 그만큼 실제 구현 경험을 많이 주지 못한 것이 아쉬움.

3. 설계 단계

프론트엔드 산출물

• 와이어프레임
• 스토리보드
• 프로토타입

백엔드 산출물

• DB 설계
• API 기본 구조 정립

회고 산출물이 중간중간 빠졌고, 공유 위치도 통일되지 않아 팀 간 진행도를 파악하기 어려웠음. 팀 간 소통 공간이 제대로 정해지지 않은 것도 문제였음. 산출물 관리와 마일스톤 정의의 중요성을 절감.

4. 구현 단계

진행 과정 본격적으로 개발을 시작하면서 여러 이슈가 발생.

이슈 요약

스토리보드 불명확성 그림 중심의 추상적인 스토리보드가 이해를 방해하여 스크립트로 보완 → 스토리보드 스크립트

API 문서 부재 프론트와 백 간의 연결을 위해 API 명세를 요청하고 작성 → API 문서 (1차), 최종본

깃허브 충돌 서로 다른 루트 커밋으로 브랜치가 갈라짐. → 루트 커밋 강제 삭제

회고 이슈가 본격적으로 터지기 시작한 시기. API 명세는 정말 필수라는 걸 체감했고, 미완성된 산출물조차 유용했다는 점이 역설적으로 느껴졌다. 그리고 백엔드에서 데이터를 거지같이 만들어서 주면 아무리 구조분해 할당을 해도 코드와 기분이 아주 더러워진다는 점도 알게됨. 원래는 모놀리식 아키텍처를 염두에 뒀으나, 사용자 기준으로 기능이 나뉘다 보니 결과적으로 MSA와 유사한 구조로 확장됨. 하지만 명확한 아키텍처 산출물 없이 진행하다 보니 설계에 일관성이 없어진 점은 아쉬움으로 남음.

5. 배포 단계

환경 AWS EC2 기반 배포.

주요 이슈 및 해결 과정

도커 제약 문제 (학교 실습용 서버) 인바운드/아웃바운드 포트가 한 개라는 제약으로 인해 운영 불가능 → AWS로 변경하여 문제 해결

프론트 통합 실패로 사용자별 개별 서버 구성 형상관리 도중 병합 충돌, 병합한 코드가 제대로 작동하지 않는 문제 → 각 사용자별 개별 서버 운영 및 포트 개방

EC2 메모리 부족 프론트 서버 메모리 점유율이 높아 백 엔드 서버가 구동되지 않음. → 메모리 크기를 늘린 인스턴스 신규 생성 및 이전으로 해결

실시간 장애 대응 테스트에서는 경험하지 못했던 케이스들이 다양하게 나타났음. → 장애 대응 기록 및 실시간 수정으로 어떻게든 해결

회고 버그가 알파/베타 테스트를 통과한 후에도 끊임없이 터졌다. 예상치 못한 상황, 특히 인터넷 연결 불안정 등은 사용자 경험에 큰 영향을 줬다. QA 관점 테스트와 실제 운영 환경 테스트는 큰 차이가 있다는 걸 체감. 도커파일과 도커 컴포즈의 필요성을 뼈저리게 느꼈고, 다중 서버 관리에는 모니터링 도구도 필요하다는 교훈을 얻음. 접속 로그나 트래픽같은 걸 측정하지 못한게 너무 아쉬웠다.

6. 종합 회고

프로젝트는 졸업 전 마지막 팀 활동이자 실사용자를 위한 실전형 프로젝트였고, 동시에 개발과 운영을 총괄해본 경험이었다.

아쉬운 점은 많았지만, 오히려 그런 점에서 배우는 것도 많았다. 특히 기술에 욕심내서 오버 엔지니어링으로 완성하지 못하고 끝내는 것보다 차라리 덕지덕지 기워붙여서 어떻게는 동작하는 게 훨씬 나은 결과물인 것을 체감했다...

아키텍처 설계, 산출물 관리, 명세 문서화, 자동화 및 모니터링, 배포 전략 등 실무에서 필요한 요소들에서 내가 얼마나 부족한지 뼈저리게 깨닫게 되었다.

완전 자동 결제 시스템을 만들고 싶었는데, 사업자 등록되어야 가능한 이슈로 인해 사용자가 직접 송금시키고 캐셔가 수동으로 확인하는 방향으로 바뀌어서 아쉬웠다.

공부해볼 것들 키워드

SSE, 메세징 큐 MSA, 헥사고날 아키텍처, 도커 컴포즈, 오케스트레이션 CI/CD, 테스트 자동화 서버 모니터링

내 멘탈도 구겨졌다

대학 쿼터제로 운이 좋게 ACPC 본선에 다녀왔다. 예선과 달리 커트라인이 상향 평준화되다 보니 문제 난이도도 그만큼 높아졌는데, A번에서 약 2시간 정도를 쏟고 B번에서 디버깅하다가 아쉽게 마무리하게 되었다. 오프라인 대회는 처음이다 보니 현장은 생각보다 압박감이 심했는데, 옆에서 키보드를 망설임없이 빠르게 치는 소리가 너무 힘들었다... 그냥 실력이 낮아서 그런 걸지도 :(

요즘 PS를 하면서 시간 써가면서 들이박는 경우가 잦았는데, CP나 코딩 테스트에서 경쟁력이 있으려면 문제 풀이 속도도 빨라야 하는 걸 다시금 깨닫게 되는 시간이었다.

그동안 PS에 소홀히 한 면도 있어서 후회되기도 하고... 여러모로 아쉬웠다. 바로 옆에서 쉽게 푸는 모습을 보니 동기 부여는 확실히 받을 수 있었다.

센트럴 시티에서 길 잃어서 버스도 놓쳤다. 인생

언뜻 보면 쉬운 문제여서 시도해 보았다.

A부터 Z를 10부터 35로 변환하여 리스트에 담아준 뒤, summaiton이라는 함수를 통해 진수 계산으로 자릿수를 높여주는 함수를 먼저 만들었다.

def summation(num1, num2):
    result = []
    l1, l2 = len(num1), len(num2)
    if l1 < l2:
        num1, num2 = num2, num1
        l1, l2 = l2, l1

    up = 0 # 자리올림
    idx = 0
    while idx < l2:
        current = up + num1[idx] + num2[idx]
        up = current // 36
        result.append(current % 36)
        idx += 1

    while idx < l1:
        current = up + num1[idx]
        up = current // 36
        result.append(current % 36)
        idx += 1

    if up: result.append(up)
    # print(result, num1, num2)
    return result

def parse(s):
    num = []
    for c in s[::-1]:
        num.append(d[c])
    return num

def reverse(l):
    result = ''
    for e in l:
        result = r_d[e] + result
    return result

그 후, Z로 바꾸는 연산을 해주어야 하는데, 이에 대한 우선순위로 가장 높은 자릿수에 있는 것들을 골랐다. 비효율적이지만 enumerate해서 인덱스와 진수(0~35)를 추출해서 정렬한 뒤, 가장 높은 자릿수를 가져오는 방식을 택했다. 그러나 이 경우는 다음과 같은 경우에서 반례가 생긴다.

4 W0 Z0 Z0 ZX 1

https://www.acmicpc.net/board/view/69763 이곳을 참고했다!

다음과 같은 경우, 0을 Z로 대체하면 W를 Z로 대체한 것 보다 더 큰 기댓값을 얻을 수 있기 때문에 우선순위에 대한 계산식이 관건이었다. 이는 현재 선택한 숫자를 Z로 바꿀시에 대한 기댓값을 계산하고, 이를 기준으로 정렬하여 해결할 수 있는데, 여기까지 왔을 때 구현은 어렵지 않았다. 우선순위에 대해 생각해보는 것이 중요한 문제였다.

끄으윽

# 무지성 재귀

def make(s, N, K):
    # global BLANK
    if s == 1:
        pad = '0' * N
        center = ('0'*BLANK) + ('1'*K) + ('0'*BLANK)
        return [pad]*BLANK + [center] * K + [pad]*BLANK

    mini = make(s-1, N, K)

    pad = []
    for r in mini:
        pad.append(r*N)
    center = []

    for r in mini:
        # print(r)
        center.append(r*BLANK + '1'*K*(N**(s-1)) + r*BLANK)
    # print(center[0])

    return pad*BLANK + center * K + pad*BLANK


s, N, K, R1, R2, C1, C2 = map(int, input().split())
BLANK = ((N-K)//2)
# make(s, N, K)
arr = make(s, N, K)

for i in range(R1, R2+1):
    print(arr[i][C1:C2+1])

무지성으로 재귀돌렸더니 메모리 초과가 나왔다.

패턴을 이해하면 풀 수 있을 것으로 보인다.

mongoDB를 연동하려던 중 대충 이런 메시지를 확인했다. djongo 패키지도 제대로 설치되어 있었기에 호환성 문제인가 싶어서 파이썬을 3.12에서 3.9로 다운그레이드 했다. 깃허브에서 이슈를 찾아보고 pytz도 설치해봤는데 전혀 바뀌지 않았다.

답답해서 오류메시지를 찾던 중 django.utils에 six가 없다는 오류메시지를 발견했다. 구글링해봤더니 아예 PyPI에 패키지가 존재한다.

알고보니 장고 3.x 버전에서는 six 때문에 호환성 문제가 다수 발생하는 것 같다.

패키지를 설치한 후 마이그레이션한 결과 제대로 동작했다.

일줄 알았으나... SQL Decode 문제로 인해 망해버렸다. 버전 호환성이 많이 꼬여서 파이썬 3.6까지 다운그레이드해야 할 것 같아서 다른 방법을 찾기로 했다.

django5 이상을 지원하는 djongo5 패키지가 존재해서 설치해봤는데, 이마저도 authentication 에러가 발생해서 문제를 찾고 있다.

03_19 settings.py가 문제였다. DB user와 DB name이 동일해서 문제가 생겼었다. 만세!!! 이제 authentication 문제는 해결했다... 아 그리고 mongo.conf도 비밀번호 인증 설정이 안되있어서 이것도 바꿔줘야 했다. 하는 김에 호스트 ip도 0.0.0.0으로 바꿔줬다.

    raise SQLDecodeError
djongo.exceptions.SQLDecodeError:

        Keyword: None
        Sub SQL: None
        FAILED SQL: ('INSERT INTO "django_migrations" ("app", "name", "applied") VALUES (%(0)s, %(1)s, %(2)s)',)
        Params: (['accounts', '0001_initial', datetime.datetime(2025, 3, 19, 15, 44, 49, 937159)],)
        Version: 1.3.9

The above exception was the direct cause of the following exception:

.
.
.

django.db.utils.DatabaseError

로그인은 성공했으나... 다시 sql decode 문제가 돌아왔다. 에러메시지를 제대로 알려주지 않아서 문제인데 GPT로 해석시켜보니 NULL, NOT NULL을 안정적으로 변환시키지 못하는 Djongo의 에러라고 한다(???)

계속해서 문제를 찾아보았고, 아직도 전혀 모르겠다.

This version of djongo does not support "NULL, NOT NULL column validation check" fully. Visit https://nesdis.github.io/djongo/support/
  Applying accounts.0001_initial...This version of djongo does not support "schema validation using CONSTRAINT" fully. Visit https://nesdis.github.io/djongo/support/

이런 메시지가 있었다. 그리고 페이지는 닫아버려서 들어가지도 못한다... 뭐냐 이게?

문제를 정확히 알기 위해 계속해서 찾아보고있었는데... ORM이 그냥 decode를 못하고 있었다.

from accounts.models import UserProfile
from django.utils import timezone

# 새로운 유저 데이터 생성
user = UserProfile.objects.create(
    username="testuser",
    email="test@example.com",
    password="securepassword123",
    created_at=timezone.now()  # auto_now_add=True 대신 직접 설정
)

print("✅ 새로운 사용자 생성 완료:", user)

해당 코드를 만드는 과정에서 그냥 파싱을 못하는 것이었다...

Model에 Unique 제약조건이 걸려있어서 이게 문제인가 싶어서 없애봤으나!!! 놀랍게도!!! 그냥 못 만 드 는 것 이 었 다 ! ! !

https://www.mongodb.com/ko-kr/docs/languages/python/django-mongodb/current/model-data/models/ https://docs.djangoproject.com/en/5.1/topics/db/models/ https://docs.djangoproject.com/en/5.1/ref/models/fields/

이것과.. djongo docs도 살펴보았으나 전혀 문제를 해결하지 못했다. 하나도 모르겠다!

핵심 문제

SQL Decode 에러는 결국 sql 파싱과 관련되있기 때문에 혹시...? 하면서 sqlparse 패키지를 다운그레이드 해보았다. (깃헙 이슈가 굉장히 많았다.) 그리고 정상적으로 마이그레이션이 완료되었다. 장고가 5.1.7 버전이기 때문에 sqlparse 패키지와 의존성 문제로 인해 나중에 문제가 생길수도 있다. 굉장히 생각이 많아진다...

어쨌든 마이그레이션은 성공했다.

문제

기숙사에서 살고 있는 준규는 한 개의 멀티탭을 이용하고 있다. 준규는 키보드, 헤어드라이기, 핸드폰 충전기, 디지털 카메라 충전기 등 여러 개의 전기용품을 사용하면서 어쩔 수 없이 각종 전기용품의 플러그를 뺐다 꽂았다 하는 불편함을 겪고 있다. 그래서 준규는 자신의 생활 패턴을 분석하여, 자기가 사용하고 있는 전기용품의 사용순서를 알아내었고, 이를 기반으로 플러그를 빼는 횟수를 최소화하는 방법을 고안하여 보다 쾌적한 생활환경을 만들려고 한다.

예를 들어 3 구(구멍이 세 개 달린) 멀티탭을 쓸 때, 전기용품의 사용 순서가 아래와 같이 주어진다면,

키보드 헤어드라이기 핸드폰 충전기 디지털 카메라 충전기 키보드 헤어드라이기 키보드, 헤어드라이기, 핸드폰 충전기의 플러그를 순서대로 멀티탭에 꽂은 다음 디지털 카메라 충전기 플러그를 꽂기 전에 핸드폰충전기 플러그를 빼는 것이 최적일 것이므로 플러그는 한 번만 빼면 된다.

입력

첫 줄에는 멀티탭 구멍의 개수 N (1 ≤ N ≤ 100)과 전기 용품의 총 사용횟수 K (1 ≤ K ≤ 100)가 정수로 주어진다. 두 번째 줄에는 전기용품의 이름이 K 이하의 자연수로 사용 순서대로 주어진다. 각 줄의 모든 정수 사이는 공백문자로 구분되어 있다.

출력

하나씩 플러그를 빼는 최소의 횟수를 출력하시오.

풀이

문제를 보자마자 페이지 교체 알고리즘이 떠올랐다. 어떤 전기용품을 이용할 것인지 전부 입력으로 주어지므로, Optimal 페이지 교체 알고리즘을 사용해야 하는 것으로 보인다. optimal 교체 알고리즘의 경우 찾아보니 LFD, 벨라디 min 알고리즘 이라고도 하는 것 같다.

먼저 전기용품들이 언제 이용하는 지 시간을 저장하고, 현재 꽂힌 전기용품을 리스트에 넣은 후 가장 나중에 오는 전기용품을 교체하도록 하면 어떤가 라는 방안을 생각해보았다.

예제를 통해 확인해 보았다.

2 5
1 2 3 1 2

다음과 같은 입력이 주어졌을 때, 전기용품 3에 대해 플러그에 꽂힌 전기용품 1을 교체하면 바로 다음에 전기용품 1로 다시 교체해야 하므로 전기용품 2를 교체해야 한다.

2 8
1 2 3 4 5 6 7 1

다음과 같은 입력이 들어올 시, 추후 사용할 여지가 가장 높은 것을 남기는 것이 가장 적절할 것이라 생각했다.

논리가 많이 빈약한데, 정보처리기사에서도 나온 개념이기도 하니 나보단 책을 믿는다는 느낌으로 구현해보았다... 처음 제출했을 때는 키 에러가 나왔었는데, 플러그에 더 꽂을 수 있을 때 전자제품을 중복으로 꽂아 에러가 발생했었다.

input = open(0).readline
# page fault optimal algorithm...?
N, K = map(int, input().split())
plug = [*map(int, input().split())]

future = dict() # 미래시

for i in range(K-1, -1, -1):
    if plug[i] in future: future[plug[i]].append(i)
    else: future[plug[i]] = [-1, i]

memory = []
m_set = set() # 중복 무시 빠른 찾기
length = 0 # 메모리 현재 길이
cnt = 0
for i in range(K):
    current = plug[i]
    if length < N:
        # 안쓰고 있고 자리 남아있으면 집어넣음
        if current not in m_set:
            memory.append(current)
            m_set.add(current)
            length += 1
        future[current].pop()
    else:
        # print(m_set, memory)
        # 있으면 생략
        if current in m_set:
            future[current].pop()
            continue
        change = 0
        latest_position = i
        for j in range(N):
            if future[memory[j]][-1] == -1: # 더이상 나오지 않을 때
                latest_position = future[memory[j]][-1]
                change = j
                break
            elif future[memory[j]][-1] > latest_position: # 현재 가장 늦는 것
                latest_position = future[memory[j]][-1]
                change = j
            # print(change, future[memory[j]], i)
        # 메모리 집합 갱신
        m_set.remove(memory[change])
        m_set.add(plug[i])
        # page fault 교체
        memory[change] = plug[i]
        future[memory[change]].pop()
        cnt += 1
    # print(memory)

print(cnt)

코드가 길어서 클래스로 만들까도 생각했었는데, 다른 풀이의 경우 굳이 그렇게 하지 않고 빠르게 풀었다. 교체할 전자용품을 찾을 때 우선순위 큐를 이용하는 법도 생각해 볼 수 있을 것 같다.

생각할 수 있는 시나리오가 많아서 고민했었는데, 채팅 시 카카오톡의 오픈 채팅처럼 무작위 채팅에 들어갈 수 있는 형태의 서비스를 생각해보았다. 채팅방의 경우, 생성한 시간순으로 정렬되는 느낌으로...

config/settings.py

LOGIN_REDIRECT_URL = "chat-lobby"

로그인 시 redirect 위치를 로비로 수정해주었다.

templates/ws_chat/chatLobby.html

{% for room in rooms %}
    <a href="{% url 'chat_room' room.id %}">{{ room.title }}</a><br>
{% endfor %}

채팅 로비의 경우, 임시로 채팅방 이름만 출력하도록 해두었다. 지금보니 url-name이 잘못되어있다...

consumer는 아래와 같이 수정해줬다.

import json
from channels.generic.websocket import AsyncWebsocketConsumer

class ChatConsumer(AsyncWebsocketConsumer):
    async def connect(self):
        self.room_name = self.scope['url_route']['kwargs']['room_name']
        self.room_group_name = f'chat_{self.room_name}'

        await self.channel_layer.group_add(
            self.room_group_name,
            self.channel_name
        )
        await self.accept()

    async def disconnect(self, close_code):
        await self.channel.name.group_discard(
            self.room_group_name,
            self.channel_name
        )

    async def receive(self, text_data):
        data = json.loads(text_data)
        message = data["message"]
        username = data["username"]

        await self.channel_layer.group_send(
            self.room_group_name,
            {
                "type" : "sendMessage",
                "message" : message,
                "username" : username,
            } )

    async def sendMessage(self, event):
        message = event["message"]
        username = event["username"]

        await self.send(text_data = json.dumps(
            {"message" : message, "username" : username}))

형태는 크게 바뀌지 않았다. 채팅방 이름을 채널 레이어에 저장할 수 있게 만들었다!

models.py

from django.db import models
from django.contrib.auth.models import User
# Create your models here.

class ChatRoom(models.Model):
    title = models.CharField(max_length = 255)
    description = models.TextField(blank=True, null=True)
    created_at = models.DateTimeField(auto_now_add=True)
    created_by = models.ForeignKey(User, on_delete=models.CASCADE)

    def __str__(self) -> str:
        return self.title

class Message(models.Model):
    chatroom = models.ForeignKey(ChatRoom, on_delete=models.CASCADE, related_name="messages")
    user = models.ForeignKey(User, on_delete=models.CASCADE)
    content = models.TextField()
    timestamp = models.DateTimeField(auto_now_add=True)

    def __str__(self):
        return f"{self.user.username}: {self.content[:20]}"

DB에 저장해야 하기 때문에 모델을 추가해주었다. 채팅방과 메시지를 기록해준다.

채팅 로비또한 수정했기 때문에 url도 수정해야 한다. 먼저 routing.py의 path를 수정해주었다.

 websocket_urlpatterns = [
    path("chat/<str:room_name>/" , ChatConsumer.as_asgi()) , 
] 

다음으로 urls.py이다. 여기도 비슷하게 추가 및 수정해주었다.

    path("", chat_views.chatLobby, name='chat-lobby'),
    path("chat/<str:room_name>/", chat_views.chatPage, name="chat-page"),

채팅방을 보여줄 채팅 로비 또한 만들어주어야 한다. views.py를 통해 만들어 주었다.

def chatLobby(request, *args, **kwargs):
    if not request.user.is_authenticated:
        return redirect("login-user")

    # order by recently
    rooms = ChatRoom.objects.order_by("-created_at")
    return render(request, "ws_chat/chatLobby.html", {"rooms": rooms})

채팅 로비의 경우 아직 보여주는 것만 존재하고 생성이 안되기 때문에 현재 서버를 키게 되면 아무것도 없는 빈 화면이 출력된다. 다음에는 채팅방의 CRUD 기능을 추가해야 할 것 같다.

https://devspoon.tistory.com/278

daphne 적용 시 settings의 INSTALLED_APPS 상위에 위치해야 한다.

INSTALLED_APPS = [
    'daphne', # 다프네가 제일 앞으로 와야한다. 서순 신경 쓸 것.
    'channels', 

    "django.contrib.admin",
    "django.contrib.auth",
    "django.contrib.contenttypes",
    "django.contrib.sessions",
    "django.contrib.messages",
    "django.contrib.staticfiles",
]

https://stackoverflow.com/questions/77928535/django-can-login-but-cant-logout-405-method-not-allowed

logout 시, csrf 토큰을 이용한 post 요청만 받기 때문에 form과 버튼이 결합된 형식으로 변경해주어야 한다.

chatPage.html을 수정해주었다.

서비스를 위한 채널의 계층을 다음과 같이 명시해준다. 데이터 공유를 위한 계층이라고 하는데, 보안 취약 문제로 인해 배포시에는 Redis를 이용하는 걸 권장한다. config/settings.py

CHANNEL_LAYERS = {
    "default": {
        "BACKEND": "channels.layers.InMemoryChannelLayer"
    }
}

LOGIN_REDIRECT_URL = "chat-page"

LOGOUT_REDIRECT_URL = "login-user"

CHANNEL_LAYERS = {
    "default": {
        "BACKEND": "channels_redis.core.RedisChannelLayer",
        "CONFIG": {
            "hosts": [("127.0.0.1", 6379)],
        },
    },
}

redis 이용 시 channels_redis 패키지를 설치해야 한다.

config/asgi.py

import os
from django.core.asgi import get_asgi_application

from channels.auth import AuthMiddlewareStack
from channels.routing import ProtocolTypeRouter, URLRouter
from ws_chat import routing

os.environ.setdefault("DJANGO_SETTINGS_MODULE", "config.settings")

application = ProtocolTypeRouter({
    "http": get_asgi_application(),
    "websocket" : AuthMiddlewareStack(
        URLRouter(
            routing.websocket_urlpatterns
        )
    )
})

# ASGI_APPLICATION = 'config.asgi.application'

asgi에 websocket 프로토콜을 추가해주었다. AuthMiddlewareStack는 보안 및 인스턴스 인증, URLRouter는 ws에 대한 라우팅을 담당한다는데... 추가적으로 더 찾아봐야 할 것 같다. ASGI_APPLICATION 이것도 무슨 역할을 하는지 모르겠다.

채팅 기능을 담당하는 클래스를 만들어주었다. AsyncConsumer와 AsyncWebsocketConsumer을 혼동해서 뭐가 문제인지 찾느라 혼났다... ws_chat/consumers.py

import json
from channels.generic.websocket import AsyncWebsocketConsumer

class ChatConsumer(AsyncWebsocketConsumer):
    async def connect(self):
        self.roomGroupName = "group_chat_gfg"
        await self.channel_layer.group_add(
            self.roomGroupName,
            self.channel_name
        )
        await self.accept()

    async def disconnect(self, close_code):
        await self.channel.name.group_discard(
            self.roomGroupName,
            self.channel_name
        )

    async def receive(self, text_data):
        text_data_json = json.loads(text_data)
        message = text_data_json["message"]
        username = text_data_json["username"]
        await self.channel_layer.group_send(
            self.roomGroupName,
            {
                "type" : "sendMessage",
                "message" : message,
                "username" : username,
            } )

    async def sendMessage(self, event):
        message = event["message"]
        username = event["username"]
        await self.send(text_data = json.dumps({"message" : message, "username" : username}))

다음과 같은 기능을 한다고 한다...

• connect() 채팅방의 이름을 채널 레이어에 추가한다.
• disconnect() 그룹에서 인스턴스를 제거한다.
• receive() send()에 의해 트리거된다. JSON 포맷 데이터를 받아와 채팅방의 전원에게 수신한다.
• sendMessage() receive()의 group_send()로 보내진 데이터를 가져온다. json으로 덤프시킨다. (???)

connection의 open이랑 created라는 상태가 나오던데 django docs를 찾아봐야 할 듯...

ws_chat/routing.py

from django.urls import path, include
from ws_chat.consumers import ChatConsumer

websocket_urlpatterns = [
    path("" , ChatConsumer.as_asgi()) , 
] 

채팅 기능을 연결해줄 스크립트이다. as_asgi()를 통해 비동기 통신이 구현되는 것 같다.

config/urls.py에 다음과 같이 앱의 url을 추가해주었다.

from django.contrib import admin
from django.urls import path, include

urlpatterns = [
    path("admin/", admin.site.urls),
    path("", include("ws_chat.urls")),
]

app 이름의 경우 ws_chat이므로 여기와는 앱의 이름이 다르다.

다음으로는 앱에서의 url을 설정해준다.

from django.urls import path, include
from ws_chat import views as chat_views
from django.contrib.auth.views import LoginView, LogoutView


urlpatterns = [
    path("", chat_views.chatPage, name="chat-page"),

    # login-section
    path("auth/login/", LoginView.as_view
         (template_name="ws_chat/loginPage.html"), name="login-user"),
    path("auth/logout/", LogoutView.as_view(), name="logout-user"),
]

루트 url의 경우 채팅을 하는 페이지이다. (사실 잘 모른다. 이름 때문에 그러려니 하고 있다.) 로그인/로그아웃의 경우, 장고에 이미 존재하는 뷰들을 가져와주었다. name 패러미터의 경우 장고 문법에서 redirect 등과 같은 함수 사용 시 name 패러미터를 url과매핑해주는 역할을 한다고 한다. 아래와 같이 쓰인다.

from django.shortcuts import render, redirect

# Create your views here.
def chatPage(request, *args, **kwargs):
    if not request.user.is_authenticated:
        return redirect("login-user")
    context = {}
    return render(request, "ws_chat/chatPage.html", context)

이제 필요한 html이 두가지 있다. 채팅 기능을 구현할 chatPage.html, loginPage.html 이렇게 두개를 만들어주어야 한다. templates/ws_chat/chatPage.html templates/ws_chat/loginPage.html

먼저 chatPage.html이다.

<!DOCTYPE html>
<html>
  <body>
    <center><h1>Hello , Welcome to my chat site ! {{request.user}}</h1></center>
    <br>
    {% if request.user.is_authenticated  %}
    <center> Logout the chat Page <a href = "{% url 'logout-user' %}">Logout</a></center>
    {% endif %}
    <div
      class="chat__item__container"
      id="id_chat_item_container"
      style="font-size: 20px"
    >
      <br />
      <input type="text" id="id_message_send_input" />
      <button type="submit" id="id_message_send_button">Send Message</button>
      <br />
      <br />
    </div>
    <script>
      const chatSocket = new WebSocket("ws://" + window.location.host + "/");
      chatSocket.onopen = function (e) {
        console.log("The connection was setup successfully !");
      };
      chatSocket.onclose = function (e) {
        console.log("Something unexpected happened !");
      };
      document.querySelector("#id_message_send_input").focus();
      document.querySelector("#id_message_send_input").onkeyup = function (e) {
        if (e.keyCode == 13) {
          document.querySelector("#id_message_send_button").click();
        }
      };
      document.querySelector("#id_message_send_button").onclick = function (e) {
        var messageInput = document.querySelector(
          "#id_message_send_input"
        ).value;
        chatSocket.send(JSON.stringify({ message: messageInput, username : "{{request.user.username}}"}));
      };
      chatSocket.onmessage = function (e) {
        const data = JSON.parse(e.data);
        var div = document.createElement("div");
        div.innerHTML = data.username + " : " + data.message;
        document.querySelector("#id_message_send_input").value = "";
        document.querySelector("#id_chat_item_container").appendChild(div);
      };
    </script>
  </body>
</html>

js가 나올줄은 몰랐는데 구아아악 웹소켓을 이용해 채팅을 구현한 것 같다.

다음으로 loginPage.html이다.

<!DOCTYPE html>
<html>
<body>
    <form method ="post">
        {% csrf_token %}
        {{form.as_p}}
        <br>
        <button type = "submit">Login</button>
    </form>
</body>
</html>

이제 로그인 기능을 테스트해보자.

마이그레이션 후 super user 만들어주기까지 추가로 해주었다. super user도 마이그레이션을 완료해야 만들 수 있다. 지식이 늘었다...

python manage.py makemigrations
python manage.py migrate
python manage.py createsuperuser

이때, templates 디렉토리의 구조가 다음과 같을 경우 html 파일을 못 찾을 수 있다. 각 앱마다 templates 디렉토리가 존재할 수 있기 때문에 해당 앱 내부의 templates에 html을 추가하여야 한다... 라는 자료가 있었는데, 관리가 번거롭기 때문에 config/settings.py에 들어가 기본 디렉토리를 설정해주었다.

TEMPLATES = [
    {
        'BACKEND': 'django.template.backends.django.DjangoTemplates',
        'DIRS': [BASE_DIR / 'templates'], # base_dir 추가해주기
        'APP_DIRS': True,
        'OPTIONS': {
            'context_processors': [
                'django.template.context_processors.debug',
                'django.template.context_processors.request',
                'django.contrib.auth.context_processors.auth',
                'django.contrib.messages.context_processors.messages',
            ],
        },
    },
]

이제 멀쩡하게 출력이 된다.

이번에는 asgi 세팅을 해볼 것이다. ASGI가 무엇인지에 대해서는 아래 링크를 참고하였다. CGI, WSGI, ASGI 정리 Python ASGI vs WSGI

ASGI (Asynchronous Server Gateway Interface)

ASGI는 비동기 및 동기 처리를 모두 지원하는 확장된 표준 인터페이스입니다. ASGI는 WSGI의 한계를 극복하기 위해 설계되었으며, 특히 비동기 작업이 필요한 환경에서 효율적입니다.

위 내용 정도로 요약되는 것 같다. 자세한 내용은 링크를 들어가서 확인하자.

bash

위에서 나온 ASGI를 사용하기 위해선 django-channels 라이브러리가 필요하다고 한다. 이를 위해 pip을 이용하여 설치할 수 있다. 또한 channels 4.0부터는 개발모드에서 asgi runserver가 작동하지 않아 daphne를 설치해야 한다고 한다. daphne는 django-channels를 위해 개발된 http, http2, 웹소켓 서버라고 한다.

python -m pip install -U channels
python -m pip install -U daphne

config 수정

config의 settings.py에 설치한 라이브러리를 추가해주었다.

INSTALLED_APPS = [
    "django.contrib.admin",
    "django.contrib.auth",
    "django.contrib.contenttypes",
    "django.contrib.sessions",
    "django.contrib.messages",
    "django.contrib.staticfiles",

    # 'daphne', # daphne 넣으니까 오히려 작동안함....??
    'channels' , 
]
ASGI_APPLICATION = 'config.asgi.application'

이상한게 있었지만 일단 넘어갔다.

그 다음으로는 config의 asgi.py의 스크립트를 수정해주었다.

import os

from channels.routing import ProtocolTypeRouter
from django.core.asgi import get_asgi_application

django_asgi_app = get_asgi_application()

os.environ.setdefault("DJANGO_SETTINGS_MODULE", "config.settings")

application = ProtocolTypeRouter({
    "http:": django_asgi_app,
    # just HTTP for now. (We can add other protocols later!)
})

ASGI_APPLICATION = get_asgi_application()

앱의 라우터를 channels의 라우터로 바꿔주었다.

+)알아볼 것

• 장고 코어의 asgi와 channels의 차이점
• daphne 쓰는 법

추가로 읽어볼 것

How to use Django with Daphne django daphne 사용 정리

참고1 참고2

문제

세준이는 N개의 물건을 가지고 있고, 최대 C만큼의 무게를 넣을 수 있는 가방을 하나 가지고 있다.

N개의 물건을 가방에 넣는 방법의 수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 N과 C가 주어진다. N은 30보다 작거나 같은 자연수, C는 $10^9$보다 작거나 같은 음이 아닌 정수이다. 둘째 줄에 물건의 무게가 주어진다. 무게도 $10^9$보다 작거나 같은 자연수이다.

출력

첫째 줄에 가방에 넣는 방법의 수를 출력한다.

풀이

기존 냅색 문제처럼 풀고 경우의 수를 전부 추적하는 방식을 생각했으나, 문제의 취지에 맞을 것 같지도 않고 오래 걸릴 것 같았다. C도 $10^9$여서 다른 방법을 이용해야 된다...

결국 못참고 찾아봤는데, MITM(Meet in the Middle)이라는 전략을 이용하여 풀이하는 문제였다.

리스트를 반으로 나눈 뒤, 각각의 리스트들의 수열을 만들고, 이분 탐색을 활용하는 것이다. 재귀적으로 가르지도 않고 한 번만 가르길래 띠용했었는데 문제 풀이를 통해 로직을 이해했다.

리스트1의 임의의 요소를 골라 C에서 뺀 값을 리스트2에서 찾는다. 이때 인덱스 번호는 리스트2에서 C 이하가 되는 경계점과 같다. 이런식으로 모든 요소에 접근하여 더하면 모든 경우의 수를 탐색할 수 있다.

def dfs(lst, sum, target, end_p):
    if target != end_p:
        lst.append(sum + weights[target])
        dfs(lst, sum + weights[target], target + 1, end_p)
        dfs(lst, sum, target + 1, end_p)

수열을 만드는 함수이다. itertools의 combinations를 쓸 수도 있지만 dfs를 이용하였다. lst의 주소를 참조하기 때문에 바로 추가해준다... 개발 에서 좋은 함수인지는 몰?루

from bisect import bisect_right
def solve():
    cnt = 0
    for i in weights1:
        cnt += bisect_right(weights2, C-i)
    return cnt

bisect 모듈의 bisect_right 함수를 이용해 이분탐색한다. 중복 값이 존재 시 left를 이용하면 다른 값이 나올 수 있다.

토이프로젝트로 웹소켓, 비동기 처리 실습 + 웹스택 공부를 하기 위해 헤딩한다는 마음으로 시작했다.

장고 5.1을 이용하였다.

가상환경은 venv 모듈을 이용해 생성해주었다.

py -3.12 -m venv venv 

python 버전이 여러 개 설치되어 있을 경우 다음과 같이 버전을 명시할 수 있다고 한다. 아래처럼 작성도 가능하다.

python3.12 -m venv venv

취향대로 이용하면 될 것으로 보인다.

django-admin startproject config .
django-admin startapp ws_chat

websocket을 이용할 것이기 때문에 ws_chat이라고 설정해두었다.

Todo

• 로그인/로그아웃 구현
• 1:1 채팅 구현
• 채팅 세션 구현
• 그룹 채팅 구현

지금 당장 생각나는 건 이정도인 듯...

# CCW
def ccw(a, b, c):
    ans = a[0]*b[1] + b[0]*c[1] + c[0]*a[1]
    ans -= a[1]*b[0] + b[1]*c[0] + c[1]*a[0]
    if ans: return 1
    else: return 0 # 평행

# 무조건 기울기가 1이상인 벡터가 아닐 수 있다.
def p_comp(a, b):
    if a[0] > b[0] or (a[0] == b[0] and a[1] > b[1]): a, b = b, a
    return a, b

# 선분 교차 판정 : 평행 케이스
def isIntersect(l1, l2):
    a, b = l1
    c, d = l2
    ab = ccw(a, b, c) == ccw(a, b, d) == 0
    cd = ccw(c, d, a) == ccw(c, d, b) == 0
    # '이어지는' 선 평행체크
    if ab and cd:
        a, b = p_comp(a, b)
        c, d = p_comp(c, d)
        # 거지 발싸개 같은 문제
        # 벡터 정렬
        return p_comp(c, b) == (c, b) and p_comp(a, d) == (a, d)
        # return c[0] <= b[0] and c[1] <= b[1] and a[0] <= d[0] and a[1] <= d[1]
    # 겹치는 경우 : b가 c보다 커서 c랑 b가 겹친다. d가 항상 a보다 커야 한다.
    # 안 그러면 그냥 평행함
    return 0

def find(n):
    if parent[n] != n: parent[n] = find(parent[n])
    return parent[n]

def union(a, b):
    a = find(a)
    b = find(b)
    if a > b: a, b = b, a
    parent[b] = a

input = open(0).readline
N = int(input())
parent = list(range(N))
lines = []
for _ in range(N):
    # fucking floating point
    x1, y1, x2, y2 = map(lambda x: int(round(float(x)*100)), input().split()) 
    lines.append([(x1, y1), (x2, y2)])

for i in range(N-1):
    for j in range(i+1, N):
        if isIntersect(lines[i], lines[j]):
            # union
            union(i, j)

for i in range(N): parent[i] = find(i)

print(len(set(parent)))

개미는(뚠뚠) 오늘도(뚠뚠) 열심히(뚠뚠) 일을 하네.

개미는 아무말도 하지 않지만 땀을 뻘뻘 흘리면서 매일 매일을 살길 위해서 열심히 일을 하네.

한 치 앞도(뚠뚠) 모르는(뚠뚠) 험한 이 세상(뚠뚠) 그렇지만(뚠뚠) 오늘도 행복한 개미들!

우리의 천재 공학자 윤수는 이 개미들이 왜 행복한지 궁금해졌다.

행복의 비결이 개미가 사는 개미굴에 있다고 생각한 윤수는 개미굴의 구조를 알아보기 위해 로봇 개미를 만들었다.

로봇 개미는 센서가 있어 개미굴의 각 층에 먹이가 있는 방을 따라 내려가다 더 이상 내려갈 수 없으면 그 자리에서 움직이지 않고 신호를 보낸다.

이 신호로 로봇 개미는 개미굴 각 층을 따라 내려오면서 알게 된 각 방에 저장된 먹이 정보를 윤수한테 알려줄 수 있다.

로봇 개미 개발을 완료한 윤수는 개미굴 탐사를 앞두고 로봇 개미를 테스트 해보기 위해 위 그림의 개미굴에 로봇 개미를 투입했다. 로봇 개미의 수는 각 개미굴의 저장소를 모두 확인할 수 있을 만큼 넣는다.

다음은 로봇 개미들이 윤수에게 보내준 정보다.

KIWI BANANA KIWI APPLE APPLE APPLE APPLE BANANA KIWI 공백을 기준으로 왼쪽부터 순서대로 로봇 개미가 각 층마다 지나온 방에 있는 먹이 이름을 뜻한다.

윤수는 로봇 개미들이 보내준 정보를 바탕으로 다음과 같이 개미굴의 구조를 손으로 그려봤다.

APPLE --APPLE --BANANA ----KIWI KIWI --APPLE --BANANA

개미굴의 각 층은 "--" 로 구분을 하였다. 또 같은 층에 여러 개의 방이 있을 때에는 사전 순서가 앞서는 먹이 정보가 먼저 나온다.

우리의 천재 공학자 윤수는 복잡한 개미굴들을 일일이 손으로 그리기 힘들어 우리에게 그려달라고 부탁했다.

한치 앞도 모르는 험한 이세상 그렇지만 오늘도 행복한 개미들!

행복의 비결을 알기 위해 윤수를 도와 개미굴이 어떤 구조인지 확인해보자.

입력

첫 번째 줄은 로봇 개미가 각 층을 따라 내려오면서 알게 된 먹이의 정보 개수 N (1 ≤ N ≤ 1000)개가 주어진다.

두 번째 줄부터 N+1 번째 줄까지, 각 줄의 시작은 로봇 개미 한마리가 보내준 먹이 정보 개수 K (1 ≤ K ≤ 15)가 주어진다.

다음 K개의 입력은 로봇 개미가 왼쪽부터 순서대로 각 층마다 지나온 방에 있는 먹이 정보이며 먹이 이름 길이 t는 1 ≤ t ≤ 15를 만족한다. 먹이 정보는 알파벳 대문자로만 이루어져 있다.

출력

개미굴의 시각화된 구조를 출력하여라.

개미굴의 각 층을 "--" 로 구분하며, 같은 층에 여러개의 방이 있을 때에는 사전 순서가 앞서는 먹이 정보가 먼저 나온다.

최상위 굴을 포함하여 하나의 굴에서 개미굴이 여러개로 나뉠 때 먹이 종류별로 최대 한 번만 나올 수 있다.

문제 풀이

트라이 구현 문제 클래스로 트라이를 구현해주고 이를 출력하도록 하였다.

이때 트라이가 하나의 문자가 아니라 문자열 단위로 저장하도록 해주었다.

class TrieNode:
    def __init__(self):
        self.children = {}

class Trie:
    def __init__(self):
        self.root = TrieNode()

    def insert(self, words):
        cur_node = self.root
        for word in words:
            if word not in cur_node.children:
                cur_node.children[word] = TrieNode()
            cur_node = cur_node.children[word]

각 노드가 문자열을 저장하지 않고, children이 문자열을 저장한다. 각 키를 통해 문자열을 조회 가능하다. word=True,False 속성의 경우 노드마다 문자열이 들어가기 때문에 생략하였다. 따라서 에지에 데이터를 저장한 형태의 트라이가 완성되었다.

출력하는 함수는 다음과 같다

# (생략)
    def __str__(self):
        result = ''

        def dfs(node, depth):
            nonlocal result
            for key in sorted(node.children):
                result += '--'*depth + key + '\n'
                dfs(node.children[key], depth+1)
        dfs(self.root, 0)
        return result

Pythonic한 방법으로는 이런 방법도 있다.

# (생략)
    def __str__(self):
        result = []

        def dfs(node, depth):
            for key in sorted(node.children):
                result.append('--' * depth + key + '\n')
                dfs(node.children[key], depth + 1)

        dfs(self.root, 0)
        return ''.join(result)

클래스는 너무 쓰지 않는 것 같아 ADT를 구현해서 해결해보았다. 자식 노드를 계속 정렬해줬는데 입력의 크기가 작아서 충분히 해결 가능한 문제였다.

선형 탐색을 이용하여 찾을 수도 있다. 이때, 둘 다 높이를 올려가며 찾기 때문에 깊이가 다를 경우 속도가 달라 공통조상을 찾지 못할 수 있다. 따라서 깊이를 동일하게 맞춰준다.

희소배열을 활용해 개선한 경우, $2^i$번째 조상을 비교하여 찾는다.

$2^i$랑 $2^i+1$ 사이에 공통조상이 있을 경우? 동일한 깊이로 조정한 다음 조상을 탐색하기 때문에 희소배열을 이용할 시 자동으로 고려된다고 한다. -> 인덱스를 말하는 것인지도...

조상 비교시, 역순으로 비교한다. 가장 긴 노드간의 거리 조사하는 거랑 비슷한건가 알고리즘 리뷰도 보고있는데 머리 깨질것같다 으아아아아악

희소배열? 배열 원소의 개수가 무조건 length값 보다 작은 배열. 메모리를 더 적게 사용한다.

참고자료 최소공통조상 희소배열

시도한 문제 A, B

A번부터 J번까지 문제를 읽어본 결과 수열과 조합론이 주된 풀이 방식인 것 같았다. 역량이 부족한 건지 B번에서 막혔다. (다른 문제들은 풀이가 감도 안왔음.) 풀어본 것들 정리나 해야겠다...

A : K 정렬

(i+K) mod N 이므로, 처음에는 N%K가 0일 경우에만 생각을 했다. N%K가 0일 경우 K가 N의 약수이므로 교체할 수 있는 위치가 제한된다. 따라서 i%K와 A[i]%K가 다르다면 교체할 수 없는 위치에 존재하므로 NO를 출력할 것이다.

그런데 이 경우 N이 20, K가 6일 경우 i가 0일때, 교체할 수 인덱스는 0, 2, 4, 6... 인데 K가 6이기 때문에 교체할 수 있는 위치가 달라지게 된다. 따라서 해당 반례에 의해 WA를 받았다.

반례에 맞추기 위해 입력을 확인하던 중 N = 20, K = 8 일때 교체 가능한 위치가 i=0일 때 기준 0 4 8 12 16 이었다.

왜 그런지 확인한 결과 N과 N-K의 gcd 값이 교체 가능한 간격이었다. (아마 N과 K의 gcd를 이용해도 가능할 듯.) gcd 값이 1일 경우 모두 교체 가능하고, 이외의 경우 gcd 값을 교체 가능한 간격으로 이용하여 나머지 연산을 하고 i에도 동일하게 gcd 값을 나머지 연산할 시 다르다면 NO를 출력한다.

B : 또또 수열 문제야 수열을 예상하는 문제 임의의 수열에 대해, 수열A의 원소 개수 N개와 A[i]와 A[j]를 곱한 집합을 제시해준다. 이때 i, j는 1~N 사이의 임의 수이다.

이때 수열을 구성하는 문제인데, 골드 문제정도는 될 것 같은데 이걸 어떻게 구성해야할 지 감이 안온다.

미리 제곱수들을 N의 범위인 1001까지 구하긴 했는데 입력으로 오는 제곱수가 사실 i==j가 아닌 경우 어떻게 처리할 지 생각만 한 것 같다.

원소 개수 N개에 대해 [i*2-1]에 위치한 원소가 제곱수일 것이다... 라고 예측했었는데 a b c d 와 같이 수열이 구성되있을 경우 ac <= b 인 경우도 있었다. 대회 풀이가 나올 때까지 기다리거나... 다른 사람이랑 같이 풀거나 질문을 해야 할 듯...

• 소프트웨어 개발을 위한 설계, 운용, 유지보수 등의 과정을 각 단계별로 나눈 것.
• 소프트웨어 생명 주기는 소프트웨어 개발 단계와 각 단계별 주요 활동, 활동 결과에 대한 산출물로 표현됨

대표적 생명 주기 모형

• 폭포수 모형
• 프로토타입 모형
• 나선형 모형
• 애자일 모형

폭포수 모형(Waterfall Model)

순차적인 개발 프로세스로, 개발 흐름이 마치 폭포수처럼 지속적으로 아래로 흐르는 것처럼 보이는 데서 이름이 붙여졌다. 폭포수 모델은 다음과 같은 단계가 순차적으로 기술되어 있다. 요구사항 기술 - 설계 - 구현 - 시험과 디버깅 - 설치(통합) - 유지보수 단계로 이루어져있다. 책에서는 순차적으로 이루어지기 때문에, 이전 단계로 돌아갈 수 없다는 것이 전제되어 각 단계를 철저하게 매듭짓고 다음 단계로 진행하는 방법론이라고 기술한다.

• 가장 오래되고 폭넓게 사용된 전통적 소프트웨어 생명주기 모델이다.
• 모델을 적용한 경험과 성공 사례가 많다.
• 각 단계가 끝난 후, 다음 단계를 수행하기 위한 결과물이 명확하게 산출되어야 한다.

프로토타입 모형(Prototype Model, 원형 모형)

실제 개발될 소프트웨어에 대한 견본품(Prototype)을 만들어 최종 결과물을 예측하는 모델

• 견본품은 사용자와 시스템 사이의 인터페이스에 중점을 두어 개발한다. image from https://www.geeksforgeeks.org/software-engineering-prototyping-model/ 출제는 잘 되지 않는다?

나선형 모형(Sprial Model, 점진적 모형)

• 나선을 따라 돌듯이 여러 번의 소프트웨어 개발 과정을 거쳐 점진적으로 완벽한 최종 소프트웨어를 개발하는 모델
• 보헴이 제안함
• 폭포수 모형, 프로토타입 모형의 장점에 위험 분석 기능을 추가한 모델
• 누락되거나 추가된 요구사항 첨가 가능
• 유지보수 과정이 필요 없다

4가지 주요 활동

• 계획 수립
• 위험 분석
• 개발 및 검증
• 고객 평가

애자일 모형(Agile Model)

고객의 요구사항 변화에 유연하게 대응할 수 있도록 일정한 주기를 반복하며 개발하는 모형 특정 개발 방법론이 아닌, 고객과의 소통에 초점을 맞춰 빠르고 낭비없게 만들기 위한 방법론을 통칭함.

• 폭포수 모형과 대조적
• 기업 활동 전반에 걸쳐 사용됨

대표적 개발 모형

• 스크럼(Scrum)
• XP(eXtreme Programming)
• 칸반(Kanban)
• Lean
• 기능 중심 개발(FDD : Feature Driven Development)

애자일 핵심 가치

• 프로세스와 도구보다 개인과 상호작용에 더 가치를 둔다
• 방대한 문서보다 실행되는 SW에 가치를 둔다
• 계약 협상보다 고객 협업에 가치를 둔다
• 계획을 따르기 보다 변화에 반응하는 것에 가치를 둔다

주헌이는 매운맛을 좋아한다. 정확히는, 매운맛을 먹음으로써 느낄 수 있는 고통에서 희열을 느끼는 진정한 '즐기는 자'다.

'스코빌 지수'란 고추류가 가진 매운맛의 원인인 캡사이신의 농도를 수치화 한 단위이다. 주헌이가 느끼는 매운 정도는 굉장히 독특한데, 먹고 있는 메뉴의 절대 수치가 아닌 음식과의 상대수치에 기반한다. 예를 들어 [5, 2, 8]의 스코빌 지수를 가진 음식을 먹을 때 주헌이가 느끼는 매운 정도는 가장 높은 수치인 8과 가장 낮은 수치인 2의 차이인 6만큼의 매운맛을 느낀다. 이처럼 메뉴들의 스코빌 지수가 있을 때 그 최댓값과 최솟값의 차이를 "주헌고통지수"라고 정의한다.

최근 주헌이에게 좋아하는 매운맛 전문점이 생겼다. 메뉴가 아주 다양한 이 음식점은 모든 메뉴의 스코빌 지수를 명시한 메뉴판을 제공한다. 주헌이의 목표는 이 음식점의 모든 음식 조합을 먹어보는 것이다. 하지만 주헌이는 까다로워서 한 번 먹어본 조합은 다시 먹지 않는다.

이 음식점의 모든 조합을 먹어 볼 때 주헌이가 즐길 수 있는 주헌고통지수의 합을 구해보자.

입력

첫 줄에 메뉴의 총 개수 N이 주어진다. 두 번째 줄에는 N개의 메뉴의 스코빌 지수가 주어진다. 모든 스코빌 지수는 0보다 크거나 같고 231-1보다 작거나 같은 정수이다.

출력

한 줄에 모든 조합의 주헌고통지수 합을 1,000,000,007로 나눈 나머지를 출력한다.

풀이

브루트 푸스 풀이와 좀 더 똑똑하게 푸는 방식이 존재한다.

먼저 브루트포스 풀이이다. 최소값을 지정하는 변수 i, 최대값을 지정하는 변수 j를 이용해 2중 for문을 만들어 선택해준다. 이때 존재할 수 있는 조합의 개수는 i-j-1이다. 따라서 조합의 개수와 최댓값과 최소의 차이를 곱해서 계속해서 더해주면 된다.

input = open(0).readline

def faster(n):
    if n in pow_m: return pow_m[n]
    pow_m[n] = pow(2, n, MOD)
    return pow_m[n]

pow_m = dict()
N = int(input())
arr = sorted(map(int, input().split()))
MOD = 10**9 + 7
ans = 0
for i in range(N):
    for j in range(i, N):
        tmp = arr[j]-arr[i]
        tmp *= faster(j-i-1)
        ans += tmp
    ans%=MOD
print(ans)

하지만 이런 나이브한 풀이는 입력값이 많으면 시간초과된다. 더 개선된 풀이방식이 필요한데, 조합식을 구성하다 머리가 터져버려서 풀이를 확인하였다.

i번째 원소에 대해, i번째 원소를 최소값으로 가지는 조합의 개수와 최대값으로 가지는 조합의 개수를 비교해주면 시간을 개선할 수 잇다.

위 브루트 포스 계산식에서는 j와 i의 차를 이용하는데, 이때 i는 최소값이다. 만약 i번째 원소를 지정했을 시, 최소값일 때는 빼주고 최댓값일 때는 더하므로(양의 정수) 최댓값으로 가지는 조합의 개수 M과 최소값으로 가지는 조합의 개수 m을 뺀 만큼 곱해주면 된다.

input = open(0).readline

N = int(input())
arr = sorted(map(int, input().split()))
MOD = 10**9 + 7

pows = {i: pow(2, i, MOD) for i in range(N)}
ans = 0
for i in range(N):
    tmp = pows[i] - pows[N-i-1]
    tmp*=arr[i]
    ans = (ans+tmp)%MOD
print(ans)

조합어렵당

LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다.

예를 들어, [1, 2, 3]과 [1, 3, 2]의 LCS는 [1, 2] 또는 [1, 3] 이다.

1부터 N까지 정수가 모두 한 번씩 등장하는 두 수열 A와 B가 주어졌을 때, 두 수열의 LCS 크기를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 두 수열의 크기 N (1 ≤ N ≤ 100,000)이 주어진다.

둘째 줄에는 수열 A에 들어있는 수가, 셋째 줄에는 수열 B에 들어있는 수가 주어진다.

출력

두 수열의 LCS의 크기를 출력한다.

풀이

처음 보고 에잉 쉽네 했는데 머리가 깨져버렸다. https://chanhuiseok.github.io/posts/algo-34/ 해당 글을 통해 lcs 구성방법을 읽어보았다. 원래는 LCS? substring인가? 그럼 보이어-무어 써도 되는 거 아닌가 생각했었는데 SubString이 아니라는 점때문에 보이어-무어 알고리즘이 아니라 LIS를 이용해야 했다. 글에서는 dp를 이용하지만 이분탐색을 이용해 해결하고 싶었다.

A와 B의 lis를 구성하고 순차 탐색으로 세는 방법도 고려해봤는데 A와 B의 lis가 다를 수도 있어서 실패했다.

결국 힌트를 보게되었는데, A를 참고하여 B를 통해 수열을 구성하는 것이었다. 정확히는 B의 i번째 인덱스가 A에서 어디에 위치하는지에 대해 알아내고, 이를 토대로 수열을 구성하는 것이다. 2250, 1365 와 유사한 문제였다. A와 B간의 관계를 찾아내고, 최대한 많은 관계를 이어주면 되기 때문에 인덱스의 위치를 이용한 LIS 문제였던 것이다.

풀이는 쉬운데 생각하기 어려운 문제 유형이었다...

from bisect import bisect_left

input = open(0).readline

def lis(arr, N):
    k = []
    l_k = []
    for i in range(N):
        idx = bisect_left(k, arr[i])
        if idx == len(k): k.append(arr[i])
        else: k[idx] = arr[i]
        l_k.append(idx+1)
    return max(l_k)

N = int(input())

arr = []
A=dict()
for v, i in zip(map(int, input().split()), range(N)):
    A[v] = i
B = [*map(int, input().split())]
for i in range(N): arr.append(A[B[i]])

A_lis = lis(arr, N)
print(A_lis)

구에엑

에린은 엔지니어이자, 기차를 운전하는 기관사입니다. 또한 그녀는 각 열차를 구성하는 차량을 배열하는 일도 합니다. 그녀는 차량들을 정렬할 때, 열차의 전면에 가장 무거운 차량을 놓고, 후미로 갈수록 중량이 감소하는 순서로 차량을 넣는 것을 좋아합니다.

불행하게도, 차량을 배열하는 일은 쉽지 않습니다. 기존에 구성된 열차에 다른 차량을 끼워넣는 일은 비실용적이어서 하지 않기에, 한 차량은 오로지 열차의 전면 혹은 후미에만 추가하는 것이 가능합니다.

차량들은 미리 준비된 순서에 따라 역에 도착합니다. 에린은 각 차량이 기차역에 도착할 때, 전면 혹은 후미에 차량을 추가하거나, 차량을 열차에 추가하는 것을 거부할 수 있습니다. 에린이 최종적으로 만든 열차는 가능한 길어야(많은 차량으로 구성되어야)하지만, 그 과정에서 열차는 에린이 배열하고자하는 정렬 순서에 맞아야 합니다.

각 차량이 역에 도착하는 순서대로 차량들의 중량이 주어질 때, 에린이 만들 수 있는 가장 긴 열차배열의 길이(=차량의 수)는 얼마입니까?

입력

첫째 줄에 차량의 수를 나타내는 N (0 <= N <= 2000)이 주어집니다. 이후 N개의 각 줄에는 음이 아닌 차량의 무게가 주어집니다. (단, 서로 다른 두 차량의 무게가 같은 일은 발생하지 않습니다.)

출력

에린이 만들 수 있는 가장 긴 열차의 길이를 출력하세요.

풀이

LIS 설명 생략

lis와 lds를 모두 구하고 적절히 활용해야 했던 문제. LIS 처음 봤을 때보다 어려웠다.

차량을 끼워넣을 때, 전면과 후미에 끼워넣을 수 있는 형태이다. 차량은 내림차순 형태로 만들 수 있다. 전면에 붙이는 걸 고려한다면 LIS가 될 것이고, 후미에 붙인다면 LDS 형태로 붙일 수 있을 것이다.

처음에는 조건을 잘못 읽어서 전면 혹은 후미에만 붙이는 줄 알았다... 하지만 전면과 후미 모두에 붙일 수 있다. 따라서 LIS와 LDS 모두를 구해야 하는데, 이때 숨겨진(?) 조건이 하나 더있다. LIS(반대도 가능)를 구성할 때, i번째 차량 번호로 시작한다면 LDS 또한 i번째 차량 번호로 시작해야 한다는 것이다.

아래 예제를 통해 확인해보자.

1 4 3 2 5

해당 입력에서 LIS는 1 3 5, LDS는 4 3 2이다. 그러나 문제의 조건에 따르면 최적해를 이루는 LIS는 4 5, LDS는 4 3 2이다. 만약 i번째 열차를 시작 열차로 선택했다면 반드시 해당 열차의 전면 혹은 후미에만 부착할 수 있기 때문에, 시작하는 원소의 값이 다를 시 최적해를 구성할 수 없다!

최적해의 경우, i 번째 원소를 포함하는 최장 증가 부분 수열에 대해, lis(i)라고 하자. 이때 lis(i)의 길이가 L1이라고 하고, 반대로 최장 감소 부분 수열의 경우 lds(i)라 하고 이때의 길이는 L2라고 해보자. lis와 lds 모두 공통 원소로 i 번째 원소를 포함하므로 L1+L2-1로 계산해주면 해결할 수 있을 것이다.

코드 구현의 경우 lis 함수 내부에서 수열 구성을 위해 쓰이는 리스트 k에서 인덱스 0번(i번 열차)가 갱신되지 않도록 구성해보았다.

LDS의 경우, 입력을 음수로 바꾼 배열을 추가로 만들어 구현하였다. 우선순위큐에 값을 음수로 넣어주는 거랑 비슷하다.

from bisect import bisect_left

input = open(0).readline

def lis(arr, N, start):
    k = [arr[start]]
    l_k = []
    for i in range(start+1, N):
        idx = bisect_left(k, arr[i])
        if not idx: continue # idx == 0
        if idx == len(k): k.append(arr[i])
        else: k[idx] = arr[i]
        l_k.append(idx+1)
    return max(l_k) if l_k else 1

N = int(input())
arr = [int(input()) for _ in range(N)]
# arr = [*map(int, input().split())] # for test

lis_l = [lis(arr, N, i) for i in range(N)]
drr = [-arr[i] for i in range(N)] # for lds
lds_l = [lis(drr, N, i) for i in range(N)]

ans = 0
for i, j in zip(lis_l, lds_l):
    ans=max(ans, i+j-1)
print(ans)

놀랍게도, dp를 이용한 풀이가 더 빨랐다. 아마 lis와 lds를 한번의 루프안에서 끝낼 수 있어서인 것 같다. 입력값이 2000 이내라서 dp를 이용한 풀이도 가능한 것 같기도...