참여 동기

스위프 앱 2기에 참여하게 된 가장 큰 이유는 다양한 직군의 팀원들과 함께 실제 프로젝트를 진행하며 협업 경험을 쌓을 수 있다는 점이었다. 또한 단순한 개발 경험을 넘어 실제 사용자 트래픽과 수익화를 직접 경험할 수 있다는 점이 매력적으로 다가왔다. 여기에 더해서 , 아래 사진과 같이 다양한 혜택이 제공된다는 점도 큰 동기부여가 되었다.

*스위프 앱 2기 프로그램 세부 내용 : *https://swyp.im/mobile#program

우리 2팀이 개발한 앱

우리 2팀은 운이 나쁘게도 PM을 뽑지 못했다. ( PM 수가 부족했다 ㅠㅠ ) 그래서 나랑 디자이너가 PM 일을 나눠서 했다. 우리 2팀은 디자이너 2명 , 앱개발 2명 , 백엔드 3명 ** 총 7명**으로 구성된 팀이었다.

나는 2팀의 팀장으로서, 동시에 앱 개발 파트를 담당했다. 우리 팀이 만든 앱의 이름은 “Kori”로, 한국에 사는 외국인들이 서로 연결되고 소통할 수 있는 소셜 네트워킹 서비스를 개발했다. 한국에서 외국인들이 느낄 외로움과 문화적 장벽을 조금이나마 줄여주는 것이 목표였다.

🔧 Kori App 기술 스택

🏗️ Kori App 아키텍처

▶️ Kori - Google 플레이 스토어 https://play.google.com/store/apps/details?id=com.SWYP.kori

🍎 Kori - Apple 앱스토어 https://apps.apple.com/kr/app/kori-korea-foreigners-meet/id6752611613

🎬 Kori 소개영상 https://www.youtube.com/watch?v=uRbe3UljSes

가장 인상 깊었던 경험

가장 인상 깊었던 경험은 우리 2팀의 앱이 구글 플레이스토어와 애플 앱스토어에 정식으로 출시된 직후였다. 처음에는 서비스 테스트와 사용자 수를 늘리기 위해 팀원들의 지인들을 초대해 회원 가입을 유도했다. 그런데 어느 날, 실제로 브라질 사용자가 우리 앱에 가입했고, 채팅 기능을 통해 그 사람과 직접 대화를 나누게 되었다. 그때 처음으로 “이게 진짜 서비스구나”라는 실감이 났다. 단순히 개발을 넘어, 실제 사용자가 있는 서비스를 운영한다는 것이 얼마나 특별한 일인지 몸으로 느낄 수 있었다.

그 밖에 인상 깊었던 경험은 팀장+앱 프론트 개발+약간의 PM 일을 병행하면서 거의 두달 가까이 잠을 하루에 4시간 미만으로 잤다. 잠을 거의 못자다보니 무서운 현상이 발생했다. 어느 날 , 샤워를 하는데 머리를 샴푸하고 씻고나서 또 샴푸하는 내 자신을 발견하였다. 조금 그때 무서웠다.. "치매"라는 것이 어떤 것인지 간접적으로나마 경험할 수 있었다. 잠은 역시 잘 자야되는 것 같다...!!

배운 것과 성장한 부분

🧑‍💼 팀장을 경험하면서...

1️⃣ 프로젝트 규모를 기간에 맞게 산정하는 것이 중요하다. 지금 돌이켜보면, 우리 팀은 다른 팀들에 비해 기능을 거의 두 배 정도 더 많이 넣었던 것 같다. 다같이 밤새워 열정적으로 작업을 해서 다행이지 만약 팀원 중 몇 분이라도 대충 하거나 중간에 빠졌다면 절대 완성하지 못했을 것이다. 다행히도 각 파트마다 실력자(에이스)들이 계셔서 끝까지 완주할 수 있었다. ( 특히 곽00 디자이너님, 정말 감사했습니다. 🙏 덕분에 든든하게 마무리할 수 있었어요. )

2️⃣** 팀원을 너무 신뢰하면 안된다.** 나는 일을 맡기면 100% 신뢰하는 성향이 있다. 그래서 팀원이 며칠 어디를 다녀오더라도, 정해진 기간 안에 일을 마무리할 것이라 믿었다. 하지만 그것이 정말 큰 오판이었다. 결국 마감 직전에 일이 몰리면서, 밤을 새지 않아도 될 일을 밤새워 마무리해야 했다.

3️⃣ 시간이 부족하더라도, 짧은 기간 단위로 팀 단위 테스트 시간이 반드시 필요하다. 기능을 개발한 사람이 직접 테스트를 하더라도, 팀 전체가 함께 검증하는 과정은 필수적이다. 왜냐하면 개발자는 자신이 만든 기능의 일부만 집중적으로 보게 되어, 다른 영역의 문제를 놓치기 쉽기 때문이다. 또한 “작동만 되면 개발이 끝났다”는 착각에 빠지기 쉬워, 세부적인 오류를 간과할 가능성도 높다. 실제로 팀 단위 테스트를 소홀히 했을 때, 마감 직전 예기치 못한 버그가 발생해 모두가 고생하는 경험을 했다.

4️⃣ 팀장은 결국 냉정해야 한다는 걸 이번에 절실히 느꼈다. ‘괜찮겠지’라는 마음으로 팀원들의 편의를 봐주다 보니, 막판에 오히려 모두가 힘들어졌다. 일을 추진할 때는 항상 최악의 경우를 생각하고, 초반부터 적당한 압박과 긴장감을 유지해야 한다. 다음부터는 6주 프로젝트라면 4주 안에 마무리한다는 목표로 진행하려 한다.

🛠️ 앱 개발을 경험하면서...

원래 나는 자바 백엔드 개발자를 준비하던 취준생이었다. 하지만 스위프 팀빌딩 기간에 앱 개발자를 구하기 어려운 상황이 되었고, 프론트엔드와 풀스택에도 관심이 있었기에 직접 앱 개발을 맡게 되었다. 앱 프론트엔드를 처음 맡으면서 많은 걸 깨달았다.

1️⃣** UI와 데이터 설계의 중요성** 화면을 먼저 구성하다 보니, 어떤 데이터가 필요한지 명확하게 정의하지 않으면 개발이 꼬이기 쉽다는 걸 배웠다.

2️⃣ 백엔드와의 데이터 스펙 조율 프로젝트 초기에 데이터 스펙을 최대한 정확하게 맞춰야 한다. 실제로 개발 중에 스펙이 달라지는 경우가 자주 있었고, 변경이 많을수록 프론트엔드 작업 난이도는 기하급수적으로 올라갔다.

3️⃣** 소통이 핵심인 역할** 프론트엔드는 디자이너와 백엔드 사이의 통로 역할을 한다. 그래서 단순히 코드를 짜는 능력보다 소통 능력과 협업 감각이 훨씬 중요하다는 걸 느꼈다.

4️⃣ 플랫폼별 이슈의 고통 안드로이드, iOS, 기기별·버전별로 동작이 달라지는 현실은 정말 고통스러웠다. 플랫폼 , 기종 , 버전에 따라서 UI가 깨지는 현상이 발생했다. 프론트 개발 시 플랫폼 , 기종 , 버전을 고려하여 개발하는 것이 얼마나 중요한지 깨달았다.

5️⃣ 이미지 로딩 시간 최적화의 중요성 이미지 로딩 속도는 사용자 경험에 큰 영향을 준다. 개인적으로, 로딩 시간을 얼마나 줄이느냐에 따라 앱의 사용 만족도가 천차만별로 달라진다고 느꼈다.

그래도 이러한 깨달음을 통해 프론트 개발자의 입장과 마음을 조금이나마 이해할 수 있었고, 풀스택 개발자로 성장하기 위한 좋은 발판이 되었다.

💡어려웠던 점과 극복한 방법

나는 앱 개발을 맡으면서 iOS와 Android 플랫폼을 동시에 출시하고 싶었다. 그래서 크로스 플랫폼인** React Native**를 선택했다. 하지만 문제는 내가 React Native를 한 번도 사용해본 적이 없었다는 것이다. 6주라는 짧은 시간 안에, 처음 접하는 기술로 큰 규모의 프로젝트를 완성할 수 있을까 하는 두려움이 있었다.

😎 그렇다면 어떻게 극복했을까? 먼저 프로젝트를 시작하기 전, 노○드 코더 선생님의 강의를 구매해 최대한 빠르게 모든 강의를 수강했다. 이를 통해 React Native의 전반적인 구조와 동작 방식을 빠르게 익힐 수 있었다. 다만 강의가 오래된 버전이라 코드가 맞지 않는 경우가 종종 있었다. 그럴 때마다** AI 도구, Expo 공식 문서, 기술 블로그 , YouTube 자료**를 활용해 스스로 문제를 해결했다.

이 과정을 통해 단순히 기술만 익힌 것이 아니라, 새로운 기술을 짧은 시간 안에 학습하고 문제를 스스로 해결하는 능력을 키울 수 있었다. 이 경험이 나를 크게 성장시켰다.

💡기타 깨달은 점

💻 개발 관련 깨달음

1️⃣ 애플은 까다로운 친구 구글 심사는 무난히 통과되었지만, 애플 심사는 3번이나 리젝됐다. 애플 기준에 맞춰 꼼꼼히 개발해야 한다.

2️⃣ 코딩 스타일의 사전 합의 필요 협업 전 개발자 간 스타일을 맞춰야 유지보수가 원활하다.

3️⃣ 짧은 기간에도 아키텍처 설계 중요 일정이 짧더라도 초기 설계가 프로젝트 완성도를 좌우한다.

4️⃣ 유료 플랜 구독은 확실히 돈 값을 한다

Ex ) Expo 무료: 최대 5~6시간 빌드 Expo 유료: 약 10분 내 완료

➕ 기타 깨달음

1️⃣ 라이프 스타일을 초반에 맞추기 프로젝트 초반부터 생활 패턴과 업무 리듬을 잡는 것이 중요하다.

2️⃣ 사람을 100% 믿지 말 것 신뢰는 좋지만, 검증과 확인은 필수

3️⃣ 철저한 교차 검증 필수 기능이나 데이터 검증 시, 여러 사람이 확인해야 오류 최소화 가능

4️⃣ 사람마다 기대치 차이 존재 서로 다른 기대치로 갈등 발생 가능 → 초반 조율 필요

5️⃣ 간단한 운동이라도 필요 체력이 정말 중요한 것 같다. 10분이라도 밖에 나가서 달리기를 하자!

6️⃣ 소통 능력은 개발 실력만큼 중요 상대방을 존중하고 본질에 벗어나지 않게 이성적으로 소통 해야한다.

7️⃣ 회의록 꼼꼼하게 작성 구두로 협의된 것은 각자 다르게 해석될 수 있어 후에 갈등을 일으킬 수 있다. 그래서 회의록을 꼼꼼하고 명확하게 작성해야 한다.

8️⃣ UX/UI 디자인과 마케팅은 정말 중요!! 적극적인 마케팅 -> 수익화 발생 💸 잘 만든 UX/UI 디자인 -> 사용자 이탈 방지 🧲

프로젝트 결과

여러 매체를 통해서 열심히 홍보한 결과 목표치보다 많은 신규 사용자를 확보할 수 있었습니다. 하지만 아쉽게도 기간 내에 수익화는 하지 못했습니다.

운이 좋게도 완성도면에서 좋은 평가를 받고 다른 팀들의 팀원분들이 좋게 평가를 해주셔서 8팀 중 1등을 해서 대상을 수상하게 됐습니다. 🥇🏆

프로젝트 소감

좋은 기회로 2팀의 팀장을 맡게 되어 2달이라는 시간 동안 좋은 팀원들과 함께 할 수 있어서 감사했다.

프로젝트가 진행되면서 어려움도 많았지만 잘 마무리될 수 있어 감사했다.

이번 스위프 프로그램 덕분에 팀장의 자리에서 다양한 직군의 분들과 소통하면서

기획 ➡︎ 디자인 ➡︎ [앱 개발+백엔드] ➡︎ 배포 ➡︎ 출시 ➡︎ 마케팅(홍보) 으로 이어지는 전체적인 앱 출시 및 수익화 Flow 를 경험하면서 많이 배운 것 같다. 이 경험이 훗날 창업의 기회가 있을 때 많은 도움이 될 것 같다.

( 번외로..감사하게도 지금의 여자친구를 프로젝트 데모데이 행사날에 만났다. 역시 사랑이 싹트는💖 스위프 최고...!! )

🛤️ 더** 깊은 이야기로 초대드립니다**

아이디어가 실제 서비스가 되기까지, Kori 팀의 성장 스토리

https://blog.swyp.im/idea-to-service-growth

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

😭알린이의 실수😭

위에 있는 사진을 보면 시간초과가 발생하였다. 왜 시간초과가 발생했을까 ?? ( 답은 잘 나옴에도 불구하고 ) 밑에 코드를 봐보자

# 시간 초과가 발생한 코드!!!!!
from collections import deque
import sys
import itertools

# 보물섬 지도 입력 받는 부분
sero,garo=map(int,input().split())

arr=[[]*garo for _ in range(sero)]

L_position=[]
for i in range(sero):
    str1=input()
    for k in range(len(str1)):
        arr[i].append(str1[k])
        if str1[k]=="L": # 육지 위치 저장
            L_position.append([i,k])

# 시작하는 위치와 목적지 위치의 모든 경우의 수를 조합으로 구함
nCr=list(itertools.combinations(L_position,2))

# 상하좌우 탐색 배열
dx=[-1,1,0,0]
dy=[0,0,1,-1]
ans=-1

# 조합으로 구한 모든 경우의 수에 대한 최단거리 구하기 
for i in range(len(nCr)):
    visited=[[0]*garo for _ in range(sero)]
    distance=[[-1]*garo for _ in range(sero)]
    start=nCr[i][0] #시작 위치
    end=nCr[i][1] # 목적지
    queue=deque()
    queue.append(start)
    visited[start[0]][start[1]] = 1
    distance[start[0]][start[1]] = 0

    #BFS 탐색 시작
    while queue:
        lst=queue.popleft()
        for i in range(4): # 상하좌우 탐색
            x=lst[0]+dx[i]
            y=lst[1]+dy[i]
            if 0<=x<sero and 0<=y<garo:
                if visited[x][y]==0 and arr[x][y]=="L":
                    visited[x][y]=1
                    distance[x][y]=distance[lst[0]][lst[1]]+1
                    queue.append([x,y])

    if distance[end[0]][end[1]]!=-1:
   # 최단 거리로 이동하는데 있어 가장 긴 시간이 걸리는 육지 두 곳의 최단거리 
   # 결국 모든 경우의 수의 최단거리 중 가장 큰 값을 찾으면 된다.
        ans=max(ans,distance[end[0]][end[1]]) 


print(ans)

실수한 이유

1. 문제 해석과 풀이방법을 너무 1차원적으로 생각하였다. -> 보물이 묻혀있는 두 곳을 모르네? -> 그 두 곳을 고르기 위해 모든 경우의 수가 필요하네? -> 조합을 써서 모든 경우의 수를 구하자 -> 모든 경우의 수를 BFS 탐색해서 최단거리들을 구하고 그 중에서 가장 큰 값을 구하자! -> 시간초과!!

2. 시간복잡도를 정확하게 계산하지 않고 그대로 구현으로 들어갔다.

이 부분에서

시간 복잡도

( 2500C2 )[조합 구할때 시간복잡도] x (50x50 )[ BFS 탐색시 시간복잡도 ] => 3,123,750 * 2500 => 7,809,375,000 => 약 78억 =>약 78초쯤 걸린다. 78초이면 당연히 시간초과가 발생할 수 밖에 없다!!!

😎풀이 (해결책)😎

그럼 어떻게 풀어야 할까??

어차피 시작점에서는 "L"이 있는 모든 곳에 다 방문을 해야한다. 그리고 BFS 탐색시 "L"에 있는 모든 곳에는 시작점으로부터의 최단거리가 기록이 된다.

즉 , 우리는 조합을 사용하지 않더라도 어차피 시작점이 바뀔때마다"L"이 있는 모든 곳에 시작점으로부터의 최단거리가 기록이 되기 때문에 그때의 최단거리 최댓값을 구하면 된다.
그리고 그 최단거리 최댓값들 중에서 최댓값을 구하면 결국 가장 긴 시간이 걸리는 보물이 묻힌 육지 2곳에서의 최단거리를 알수 있다.

# 정답 코드
from collections import deque

# 상하좌우 탐색을 위한 배열
dx=[-1,1,0,0]
dy=[0,0,1,-1]

#BFS 탐색
def bfs(i,j):
    queue=deque()
    visited=[[0]*garo for _ in range(sero)]
    distance=[[0]*garo for _ in range(sero)]
    queue.append([i,j])
    visited[i][j]=1
    cnt=0 # 시작점으로부터 가장 먼 목적지의 최단거리를 구하기 위한 변수
    while queue:
        lst=queue.popleft()
        for k in range(4): # 상하좌우 탐색
            x=lst[0]+dx[k]
            y=lst[1]+dy[k]
            if 0<=x<sero and 0<=y<garo and visited[x][y]==0 and arr[x][y]=="L":
                visited[x][y]=1
                #"L"이 있는 곳마다 시작점으로부터의 최단거리를 기록한다.
                distance[x][y]=distance[lst[0]][lst[1]]+1
                queue.append([x,y])
                # 시작점으로부터 가장 먼 목적지의 최단거리 구하기
                cnt=max(cnt,distance[x][y])
    return cnt

# 보물섬 지도 입력
sero,garo=map(int,input().split())
arr=[[]*garo for _ in range(sero)]
for i in range(sero):
    str1=input()
    for k in range(len(str1)):
        arr[i].append(str1[k])

ans=0 # 최댓값 최단거리들 중에서의 최댓값 -> 가장 먼 두 곳 사이의 최단거리

# 전체 순환으로 시작점 업데이트 하면서 최댓값 최단거리들 중 최댓값 구하기
for i in range(sero):
    for j in range(garo):
        if arr[i][j]=="L":
            ans=max(ans,bfs(i,j)) # 최댓값 최단거리들 중 최댓값 업데이트

print(ans)

👩‍🎓 총평 👩‍🎓

* 아직 🟨골드 티어 문제 앞에서 나는 문제에 함정이 있는 것이 아닐까? 골드 문제라서 어렵지 않을까? 라는 두려움을 갖고 나아간다. *

이번 문제는 단순하게 최댓값 최단거리들 중 최댓값을 찾는 문제인데 위의 이유로 너무 복잡하게 생각한 것이 컸다.

이번 문제를 통해 배운점

1. 항상 문제를 꼼꼼하게 읽고 문제의 본질을 파악하자 2. 시간복잡도를 꼼꼼하게 계산하여 알고리즘을 설계하자 3. 단계별로 잘 알고리즘을 차근차근 설계하자 -> 🟨골드 문제에 겁먹지 말자

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

😭알린이의 실수😭

나눠진 구역들의 시작점과 끝점의 좌표를 함수의 파라미터로 설정하여 나눠진 구역에 대해서 1 또는 0으로만 되어있는지 검사를 하려고 했다. Ex) divide_paper(n,a,b,c,d) -> 파라미터가 너무 많아져서 함수 자체가 복잡해보임 -> 로직을 짜는데 복잡해짐 -> 결국 , 끝점의 좌표값을 처리하기 어려웠고 값도 정확하게 나오지 않음.

😎 풀이 ( 해결책 )

끝점을 없애고 시작점만을 기준으로 로직을 세웠다.

Ex ) divide_paper(n,a,b,c,d) -> divide_paper(n,a,b) 여기서 n은 나눠진 구역의 변의 길이 , (a,b)는 시작점의 좌표

자세한 풀이는 주석 참고!

N=int(input())

def divide_paper(n,a,b): 
    global blue_paper
    global white_paper
    if n==1:
        if arr[a][b]==1: # 1일때 파란색 색종이 갯수 +1
            blue_paper+=1
        else:
            white_paper+=1 # 0일때 하얀색 색종이 갯수 +1
        return

    # 나눠진 구역이 1 또는 0 으로만 이루어져있는지 검사하는 부분
     """
    여기서 (a,b) , ( a+(n-1) , b+(n-1) ) 좌표가
    나눠진 구역의 시작점과 끝점이다.
    """
    flag=False
    t=arr[a][b]
    for i in range(a,a+n):
        if flag==True:
            break
        for j in range(b,b+n):
            if arr[i][j]!=t:
                flag=True

    # 나눠진 구역이 1또는 0으로만 이루어져있을때
    if flag==False:
        if t==1:
            blue_paper+=1
            return
        elif t==0:
            white_paper+=1
            return

    # 나눠진 구역이 1 과 0이 섞여있을때
    k=n//2
    # 4개의 구역으로 나누고 함수 호출
    divide_paper(k,a,b) 
    divide_paper(k,a,b+k) 
    divide_paper(k,a+k,b)
    divide_paper(k,a+k,b+k)

arr=[[0]*N for _ in range(N)]

for i in range(N):
    arr[i]=list(map(int,input().split()))

blue_paper=0 # 파란색 색종이 갯수
white_paper=0 # 하얀색 색종이 갯수
divide_paper(N,0,0) # 색종이 만들기 함수
print(white_paper) 
print(blue_paper)

👨‍🎓 더 성장..

다른 사람의 풀이를 한번 봐보자.

이 분의 풀이를 보고 내 코드에서 피드백할 부분을 찾아보자. ( 위 사진이 [출처] )

import sys

N = int(sys.stdin.readline())
color_matrix = [ [] for _ in range(N)]
for i in range(N):
    color_matrix[i] = list(map(int,sys.stdin.readline().strip().split()))

white=0
black=0

def dfs(n,x,y): # 다음 쪼갠부분에도 시작포지션 그래서 x,y 매개변수
    global black
    global white
    half = n//2
    if n==1:
        if color_matrix[x][y] ==0:
            white += 1
        else:
            black += 1
        return

    # 구역이 1 또는 0으로만 되어 있는지 검사하는 부분
    for i in range(x,x+n):
        for j in range(y,y+n):
            if color_matrix[i][j] != color_matrix[x][y]:
                dfs(half, x, y) # 1사분면
                dfs(half, x+half, y) # 2사분면
                dfs(half, x, y+half) # 3사분면
                dfs(half, x+half, y+half) # 4사분면
                return 

      # 구역이 1 또는 0으로만 되어 있다면
    if color_matrix[x][y] ==0:
        white += 1
    else:
        black += 1

dfs(N,0,0)

print(white)
print(black)

나는 flag라는 변수를 쓰면서 코드가 길어진 느낌이 있었다.

하지만 , 내가 참고한 분의 코드를 보면 이런식으로 flag 같은 쓸데없는 변수를 쓰지 않고 표현한 것을 볼수 있다.

👨‍🏫 총평

실버 문제에 아직 허덕이는 나, 많이 부족하다는 것을 느꼈다.

분할정복 문제를 풀때

1. 구역 시작점의 올바른 좌표 설정
2. 구역의 올바른 범위를 정확하게 파악하고 로직을 짜는 것 이 2가지가 중요하다는 것을 이 문제를 통해서 깨달았다.

예시로 그림을 보면서 이해해보자

지금 현재 나는 15kg 용량까지 넣을 수 있는 배낭을 가지고 있다. 그리고 주변에는 여러가지 물건들이 있는데 그 물건들은 각각 무게와 가치를 가지고 있다.

배낭의 최대 용량을 넘지 않는 선에서 어떤 물건들을 넣어야 최대 가치를 얻을 수 있을까? 예를 들어 , 이 그림에서는 A,E,D 물건을 넣어야 배낭의 최대 용량 15kg을 넘지 않으면서 최대 가치인 $7를 얻을 수 있다.

즉, 물건들을 잘 조합해서 배낭의 최대 용량을 초과하지 않으면서 담은 가치를 최대로 하는 문제가 배낭 문제이다.

배낭 문제를 어떻게 풀어야 할까??🤔

배낭 문제는 물건을 쪼갤수 있냐 없냐에 따라 풀이법이 달라진다.

물건을 쪼갤수 있다! ⮕ 부분 배낭 문제 ( fractional knapsack problem )

물건을 쪼갤수 없다! ⮕ 0/1 배낭 문제 ( 0/1 knapsack problem )

부분 배낭 문제 ( fractional knapsack problem )

해결 방법 : 무게당 가치가 높은 짐을 최대한 많이 넣는 그리디 알고리즘을 사용한다.

예시 )

𝐀 ⮕ 무게당 가치 : $4 ÷ 12kg = 1/3 𝐁 ⮕ 무게당 가치 : $2 ÷ 1kg = 2 𝐂 ⮕ 무게당 가치 : $10 ÷ 4kg = 2.5 𝐃 ⮕ 무게당 가치 : $1 ÷ 1kg = 1 𝐄 ⮕ 무게당 가치 : $2 ÷ 2kg = 1

무게당 가치 C > B > D=E > A

부분 배낭 문제 풀이

1. 무게당 가치가 제일 높은 C를 다 넣는다. ⮕ 배낭 용량 15kg-> ( 15kg - 4kg )=11kg ⮕ 이 때의 최대 가치 : $10

2. 무게당 가치가 그 다음으로 높은 B를 넣는다. ⮕ 배낭 용량 11kg -> ( 11kg - 1kg ) = 10kg ⮕ 이 때의 최대 가치 : $10+ $2 = $12

3. 무게당 가치가 그 다음으로 높은 D,E를 넣는다. ⮕ 배낭 용량 10kg -> ( 10kg - (1+2)kg ) = 7kg ⮕ 이 때의 최대 가치 : $12+ $1 +$2 = $15

4. A를 쪼개서 7kg를 마저 채운다. ⮕ 배낭 용량 7kg -> ( 7kg-7kg ) = 0kg ⮕ 이 때의 최대 가치 : $10 + $2 + $1 +$2 + $( 1/3 * 7 ) = 약 $17.3 # 위 과정이 끝나면

최대 가치는 $10 + $2 + $1 +$2 + $( 1/3 * 7 ) = $17.3 이 된다.

**즉 , 요약하자면

1. 물건별로 무게당 가치를 구한다.
2. 무게당 가치가 높은 물건부터 넣을 수 있는 만큼 배낭에 넣는다. ( 만약에 배낭 용량이 물건 무게보다 작으면 물건을 쪼개서 넣는다. )
3. 배낭이 허용하는 용량이 0이 될때까지 과정2를 수행한다.**

이렇게 그리디 알고리즘으로 부분 배낭 문제를 풀수 있다.

그렇다면 물건을 쪼갤수 없는
0/1 배낭 문제는 어떻게 풀어야 할까?

대표적인 0/1 배낭 문제

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

이 문제는 물건을 쪼갤수 없는 대표적인 0/1 배낭 문제이다. 어떻게 풀어야 할까?🤔

문제 요약

준서는 K 용량의 배낭을 가지고 있다. 그리고 준서는 N개의 물건을 가지고 있는데 각각의 물건은 무게 W , 가치 V를 가지고 있다. 배낭에 넣을 수 있는 물건들의 가치합의 최댓값을 구해야 한다.

문제 풀이

평범한 배낭 예제 입력 1을 바탕으로 풀어보겠다. 예제 입력 1에서는 배낭의 총 용량을 7kg , 물건의 수를 4로 입력하였다. 또한 각각의 물건들에 대한 무게와 가치를 입력하였다. 편의상 물건들에 대한 이름을 붙였다.

예를 들어 A 물건은 6kg 용량과 가치 $13을 가지고 있다. B 물건은 4kg 용량과 가치 $8을 가지고 있다. C 물건은 3kg 용량과 가치 $6을 가지고 있다. D 물건은 5kg 용량과 가치 $12을 가지고 있다.

준서는 이제 배낭을 싸려고 한다. 준서는 물건을 쪼개서 넣을수 없으므로 준서는 배낭에 각각의 물건에 대해 물건을 넣지 않는다 or 물건을 넣는다. 이 두가지 행동만을 할수 있다. 즉 , 0/1 배낭 문제이다.

2차원 배열을 세워서 풀어보자!!

초기 배낭

파란색 줄은 배낭의 최대용량을 뜻하고 초록색 줄은 물건들을 뜻한다.

배열의 각 칸은 배낭의 최대 용량에 따른 최대가치이다.

배낭에 아무것도 넣지 않으면 최대 가치는 0이므로 0으로 채워준다. 더해서 배낭의 최대 용량이 0이라면 아무것도 넣을수 없으므로 최대 가치는 0이다 >> 0으로 채워준다.

A를 배낭에 넣어보자

A는 무게가 6kg이므로 배낭의 최대 용량이 배낭의 최대 용량이 0~5kg 일때는 넣지 못한다. 배낭의 최대 용량이 6,7kg 일때 A를 넣을 수 있으므로 배낭의 최대 용량이 6,7kg 일때의 최대 가치는 A가 들어있는 경우인 $13이다.

B를 배낭에 넣어보자

B는 무게가 4kg이므로 배낭의 최대 용량이 0~3kg 일때는 넣지 못한다. 배낭의 최대 용량이 4,5,6,7kg 일때 B를 넣을수 있다. 하지만 여기서 생각해볼 것이 A가 현재 배낭에 들어있는 경우와 들어있지 않은 경우를 생각해봐야한다. A가 들어있는 경우 남은 배낭 용량은 1kg이므로 B를 넣지 못한다. 따라서 A만 들어있는 경우 vs A를 빼고 B를 넣는 경우로 최대 가치가 정해진다.

C를 배낭에 넣어보자

C는 무게가 3kg이므로 배낭의 최대 용량이 0~2kg 일때는 넣지 못한다. 배낭이 수용할수 있는 용량이 3,4,5,6,7kg 일때 C를 넣을 수 있다. 여기서 형광펜으로 칠해진 곳을 보자 어떻게 14가 나왔을까?? 준서는 두가지 행동을 할수 있다고 하였다. 물건을 넣는다 or 물건을 넣지 않는다 두가지 행동 중 선택할수 있다.

만약에 준서가 C를 넣지 않는다면 배낭의 최대용량이 7일때의 최대 가치인 13이 그대로 내려온다.

만약에 준서가 C를 넣는다면 배낭의 최대 용량이 7일때에 최대가치는 C의 가치 + [ 배낭의 최대 용량이 ( 7-C의 무게 ) ]일때의 최대가치를 더해준 값이다. 즉
C의 가치 -> $6 , [ 배낭의 최대 용량이 ( 7-C의 무게 ) ] -> $8를 더한 값인 14가 된다. 당연히 14가 13보다 크므로 배낭의 최대 용량이 7일때의 최대가치는 14가 된다.

여기서 점화식을 얻을 수 있는데

배낭의 최대용량이 넣으려는 물건보다 작을때 ⮕ 물건을 넣으면 안된다. 즉 , 물건을 넣기전 배낭 상태의 최대가치가 그대로 최대가치가 된다. ⮕ dp[i][j]=dp[i-1][j] 이란 점화식이 나온다.

배낭의 최대용량이 넣으려는 물건보다 클때 ⮕ 물건을 넣지 않는다 or 물건을 넣는다. 물건을 넣지 않는다 ⮕ dp[i][j]=dp[i-1][j] 물건을 넣는다 ⮕ dp[i][j]=dp[i-1][j-weight]+value 여기서 value를 더해주는 것이 물건을 넣어주는 행위이다. 이 두개를 비교해서 더 큰 값을 집어넣는다.

마지막으로 D를 넣어보자

위에 나온 점화식을 바탕으로 2차원 배열의 칸들을 채워보면 모든 경우의 수를 따졌을때의 최대 가치는 14가 나온다는 것을 알수 있다.

이것을 코드로 짜면..(Feat.자바)

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.StringTokenizer;

class Main{

    static int N,K; // N -> 물건의 갯수 , K -> 배낭의 최대 용량
    static int [][]dp; // 다이내믹 프로그래밍 2차원 배열
    static ArrayList<int[]>bag_list; // 물건 리스트

    public static void main(String []args)throws IOException {

        BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st=new StringTokenizer(br.readLine());

        N=Integer.parseInt(st.nextToken()); // 물건의 갯수 입력 받기
        K=Integer.parseInt(st.nextToken()); // 배낭의 최대용량 입력 받기
        dp=new int[N+1][K+1]; // 2차원 배열 생성
        bag_list=new ArrayList<>(); // 물건 리스트
        bag_list.add(new int[]{0,0}); // 나중에 더 for문 편하게 돌리기 위해서 넣음.

        for(int i=0;i<N;i++) // 물건들 입력받기
        {
            st=new StringTokenizer(br.readLine());
            int weight=Integer.parseInt(st.nextToken()); // 무게 입력받기
            int value=Integer.parseInt(st.nextToken()); // 가치 입력받기
            bag_list.add(new int[]{weight,value}); // 물건 리스트에 넣어주기
        }

        for(int i=1;i<bag_list.size();i++) // 물건들 갯수만큼
        {
            int weight=bag_list.get(i)[0]; // 무게
            int value=bag_list.get(i)[1]; // 가치
            for(int j=1;j<=K;j++) 
            {
                if(weight>j) // 물건의 무게가 배낭의 최대용량보다 크면
                {
                    dp[i][j]=dp[i-1][j]; // 물건을 집어 넣지 않는다.
                }
                else // 물건의 무게가 배낭의 최대용량보다 작으면
                {    
                    // 물건을 넣지 않는다 vs 물건을 넣는다
                    // 이 중 더 큰 값을 집어넣는다.
                    dp[i][j]=Math.max(dp[i-1][j],dp[i-1][j-weight]+value); 
                }
            }

        }
        // 모든 경우의 수를 따졌을때의 나온 최대가치 출력
        System.out.println(dp[N][K]);

    }
}