영화 <컨텍트, Arrival>를 봤다. 다른 책에서 삶에 대한 관점을 바꾼 인생 영화라고 언급해서 보게 된 영화. 영화는 지구에 도착한 외계인들을 탐색하고 대응하기 위해 한 물리학자와 언어학자를 파견하는 내용이다. 이 영화가 전달하는 메세지는 두 가지 학문 분야의 개념을 바탕으로 한다. 파견된 학자들의 분야에서 유추가능하듯 물리학과 언어학이다. 

 

지구에 온 외계인들을 다리가 7개라는 의미로 헵타포드(Hepta = 일곱, pod = 다리)라고 부르는데, 이 헵타포드들은 표의어를 사용한다. 즉, 마치 중국어 한자처럼 문자가 음이 아닌 의미를 바탕으로 한다. 이들 언어의 또다른 특징은 바로 시제가 없다는 점이다. 이들에게는 '시간은 흐른다'는 개념이 없다. 과거에서 미래로의 방향으로 흐르는 시간의 개념을 가진 인간들의 언어에는 '~했다(did)', '~한다, 하고 있다(do, be doing)', '~할 것이다(will do)' 등의 다양한 시제가 있지만 이들의 언어에는 없다. 이들이 인지하는 시간에는 과거와 현재, 미래의 개념이 분리되어 있지 않다. 그것들은 모두 하나이다. 

 

다중우주의 개념을 직관적으로 보여주려는 그림

 

이러한 개념은 물리학의 아인슈타인의 상대성이론을 바탕으로 한다. 시간은 블록 우주(block universe, "시공간에서의 모든 사건이 하나의 장에 찍힌 점이다") 개념에 따라 절대적인 흐름이 아니라, 관찰자의 위치와 상태에 따라 상대적으로 다르게 경험되며(시간의 고유성), 또 과거, 현재, 미래가 시공간에 고정된 점들처럼 존재하며, 시간의 흐름은 단지 인지적 환영일 수 있다는 이론이다. 이 영화를 보며 예전에 선물 받아 읽다가 머리에 쥐날 것 같아서 포기하고 넣어둔 <시간은 흐르지 않는다>를 꺼내봤다. 세계적인 이론 물리학자 카를로 로벨리가 양자역학과 상대성 이론을 바탕으로 한 시간에 대한 현대의 시각을 굉장히 쉽게 (써도 어렵지만 감은 잡을 수 있다) 쓴 책이다. 놀랍게도 이 과정에서 방정식은 딱 한 번 밖에 등장하지 않으며 놀랍도록 추상적인 개념을 여러 예를 들어 쉽게 설명하려 한 로벨리의 열정을 느낄 수 있다. 내용을 한 마디로 정리하면, 시간은 흐르지 않는다. 동시에 존재한다. 헵타포드들의 시간 인지 방식처럼.

 

또 시제가 없는 언어를 이해하게 된 언어학자 주인공이 그들처럼 과거와 미래를 다른 개념이 아니라 같은 것으로 인지하고 미래를 '예측'이 아닌 '알 수' 있게 된다는 점은 언어가 사고를 규정한다는 언어 결정론(linguistic theory)를 바탕으로 한다. 이거 때문에 마침 저번주 도서관에서 빌려왔다가 처박아뒀던 비트겐슈타인의 <논리 철학 논고> 소개서를 꺼내봤다. "언어의 한계가 곧 세계의 한계다"라고 말한 비트겐슈타인의 초기 철학이 언어 결정론에 영향을 미쳤다는 부분을 책의 서두에서 읽었던 것 같았기 때문이다. 실제로 영화의 배경이 된 언어 결정론 이론 사피어-워프 이론은 이러한 철학에서 많은 영향을 받았다고 한다. 작년에 읽은 <어른의 어휘력> 이라는 에세이에서도 비슷한 이야기를 한 것 같아 또 이게 이렇게 연결되는구나, 하고 신기했다.

 

영화를 이해하기 위해 알아두면 좋은 배경지식을 찾다가 이렇게 여러 책들을 읽게 되고, 지식들이 연결되며 이를 통해 시야가 확장되는 경험이었다. 특히 시간은 흐르지 않는다는 개념, 그리고 언어가 사고를 규정한다는 이 영화의 배경이 된 주요 두 이론은 나의 현재 고민을 새로운 시각으로 볼 수 있게 해주었는데, 우선 진로 고민이 많은 이 시점에서 미래를 보는 관점을 다르게 할 수 있었다. 어차피 여러 평행 우주 중 하나의 정해진 미래가 있다면. 진로 고민은 미래의 불확실성에서 기인한다. 그러나 정해진 미래는 있다면? 영화 <에브리띵 에브리웨얼 올엣원스> 처럼 다중우주의 여러가지 버전의 미래 지점은 이미 존재하고, 그저 현재의 선택이 그곳을 찾아간다면? 미래를 '예측'하는 것이 아닌 '안다'고 인지한다면? 터무니 없어도 좋다. 그러나 이 관점은 내게 신선할 뿐 아니라 유용하다. 그렇게 눈에 보이지 않는 것을 상상할 수 있게된 것 만으로도 현재의 불안이 많이 줄어들었니. 이미 네가 그리는 미래는 여러 버전으로 존재하고, 어느 미래가 될지는 결국 지금 현재의 선택에 달려있다. 그냥 너는 현재와 미래가 다르지 않다는 것을 '알고' 걸어나가면 된다. 

 

 

“If you could see your whole life from start to finish, would you change things?”

 

 

또 이 영화는 사랑에 대한 관점을 다른 층위, 즉 물리학의 관점으로도 생각해 볼 수 있는 기회를 주었다. 영화 초반부에는 언어학자가 딸을 잃는 장면이 등장한다. 관중들은 이 장면으로 언어학자가 딸을 잃었다는 것을 '알게' 된다. 그러나 영화의 마지막에서 그것은 사실 '과거'의 일이 아닌, 헵타포드의 언어를 해석하며 알게된 언어학자의 '미래' 시점의 일이라는 것을 깨닫는다. 영화 진행 시점 기준, 언어학자에게 딸은 아직 존재하지 않는다. 미래에 그녀는 함께한 물리학자와 사랑에 빠지고 딸을 하나 얻지만, 그는 그녀를 떠나고 딸마저 어린 나이에 암으로 그녀보다 앞서 세상을 떠난다. 당신은 이를 안다고 해도 그 삶을 살아나가겠는가? 길을 안다고 해도 그것을 걷지 않으면 결국 의미가 없기 때문에 그것은 선택이다. 이 장면은 언어학자에게 뿐 아니라 관객에게도 같은 묵직한 질문을 던진다. 그 엄청난 상실의 아픔을 현재에도 실감함에도 그녀가 그 길을 걷겠다고 생각한 것은, 딸을 사랑하는 마음이 미래 뿐 아니라 현재에도 과거에도 존재하기 때문이었다. 그는 그의 아직 만나지 않은 딸을 사랑했다. 고통 뿐 아니라 미래에 그녀를 사랑한 마음 역시 현재에 실존했다. 그래서 그녀를 만나기를 선택했다.

 

사랑이란 무엇일까? 무엇이 그토록 고통스러울 것을 알아도 그것을 선택하게 하는가? 사랑이 무엇이냐는 질문은 답이 없고 현학적인 질문이라 생각해 마음 속 구석에 처박아 놨었다. 이 질문을 다시 꺼내보며 어떤 질문들은 답이 없고 실용적이지 못할 지언정, 그것에 대해 생각하는 것만으로도 개인을 더 나은 사람으로 성숙시킨다는 걸 깨닫는다. 그래서 사랑이란 무엇일까? 영화 <대도시의 사랑법>에서는 설익은 철학을 바탕으로 온몸으로 20대를 경험해 나가는 구재희씨가 말한다. "사랑은 너무 추상적이고 어려운데, '보고 싶다'는 참 명확해." 이 두 영화를 보고 난 뒤 지금 내게 사랑을 묻는다면 다음과 같다: 시간과 공간을 초월해 당신이 보고 싶은 것. 시공간과 관계없이 여전히 당신을 향한 마음이 내 안에 존재하는 것. 그래서 다른 시공간 속에 살아가면서도 여전히 옆에 있다고 느껴지고, 느낌과 현실의 간극을 좁히고자 기꺼이 만나러 가게 되는 것. 나의 가장 절친한 친구는 시애틀에 산다. 그와 나 사이에는 약 8,700km 정도의 공간차와 1000분의 몇 초쯤의 시간차가  존재한다. 그러나 그를 떠올리면 여전히 내 옆에 있는 것처럼 느껴진다. 2년 전 보낸 나의 첫 강아지 역시 여전히 옆에 있는 것 같다. 그리고 나의 미래라 여겨지는 시공간의 인연들을 감히 말하건대 사랑한다. 현재와 미래와 과거가 다르지 않고, 이곳이 저곳과 다르지 않으며, 나와 남이 결국 하나라고 느껴지게 만드는 이 마음이 지금은 딱 꼬집어 설명할 수 없지만 삶을 살아가는 데 중요한 것 같다.

 

 

 

 

 

https://www.youtube.com/watch?v=aduVMrS-v4o&t=6s

 

최근 공개된 Figma Config 2024에서 새로 공개한 Figma의 기능을 보면 점점 디자이너와 프론트엔드의 경계가 모호해지는 것 같다. IT업계 선두 그룹에서 인턴을 경험한 지인도, Figma, Framer 등을 활용해 디자이너의 디자인을 코드로 변환시킨 것을 프론트엔드 개발자가 조금 다듬고 서버와 연결 지어 업데이트 한다고 했다. AI가 디자인까지 해버리고 그걸 코드로까지 내놓는 세상이 왔다. 디자이너도, 프론트엔드 개발자의 역할도 달라지고 있다. 디자이너분들의 의견도 궁금하긴 하지만, 난 개발자니 개발자의 역할은 어떻게 달라질지를 생각해본다. 

 

직업은 사라지고 생겨난다. 그 역할이 조금씩 변하기도 한다. AI의 등장으로 결국 가까운 다음 대세는 AI를 잘 활용하는 인재와 AI가 할 수 없는 부분을 할 줄 인재가 대우 받겠지. 비기술적으로는 고유성과 창의성을 지닌 경영, 영업, 기획, 디자인 부분이나, 기술쪽으로는 AI가 (아직까지는) 파악하기 어려운, 데이터를 위한 데이터 구조를 짜는 백엔드 직군이 더 강력해질 거란 생각이 든다. 즉, 결국 감각적이고 창의적인 기획으로 인간의 고유 기술을 갈고 닦거나, 아니면 결국은 "데이터"를 다루는 것이 중요해질 거란 생각이 들었다.

 

프론트엔드직군의 경우, PC의 대중화로 혜성처럼 등장했고, 모바일앱의 유행으로 CSR이 유행하는가 하더니 Next.js의 등장으로 SSR으로 다시 돌아와 서버쪽도 결국은 다뤄야 하는 방향으로 가고 있다. AI의 등장으로 디자인을 반영하고 프론트측 데이터를 다루던 역할에서 디자인의 영역은 점점 그 중요성이 사라지고 있는 것 같다. 이번 Figma Config를 보면 이제 정말 CSS쪽 지식의 입지는 점점 작아지는 게 보인다. 유지보수 관리가 쉽도록 회사 관리 방식에 맞게 수정해주는 정도는 필요하겠지만, 이제 웬만한 베이스는 AI가 다 깔아주니 말이다. 점점 프론트엔드 개발자의 역할은 프론트 측에서의 "데이터"의 관리쪽에 더 집중되는 것 같다. 아직까지도 AI에게 코드를 부탁하면 '던져주는' 정도이다. 어떻게 하면 더 효율적으로 돌아가며 유지보수가 쉬워지는 코드를 짜는 지는 프론트엔드 개발자 역량에 달린 것 같다. 서비스가 커질 수록 그 역량은 빛이 날 것이고. 

 

또 결국 서비스를 만드는 건 회사에서 사람들이 하는 일 아닌가. AI가 돌아다니면서 협업하고, 부서 돌아다니면서 언제까지 되냐고 쪼고(?), 의견을 조율하고 하지는 않는다. AI는 컴퓨터 속에 있고 제품 생산을 돕지만, 이 각 분야의 생산물을 합쳐 시장에 내놓는 것은 인간들이다. 그리고 그 과정에서 협업이 정말 중요하겠고. 움직이는 하드웨어를 가진 인간으로서 이런 컴퓨터속 AI가 못하는 사람과의 상호작용이라는 걸 잘하는 것도 (지금도 중요하지만 앞으로는 더욱더 빛날 역량이 아닌가 하는 생각이 든다. 

 

프론트엔드의 역할이 달라져가는 이 시대, 결국은 단기적인,  "데이터"를 다루는 "상태관리"를 얼마나 잘 하는지, 깊게 다뤄봤는지가 좁혀져가는 입지에서 그나마 중요한 포인트인 듯하다. 능동적인 부분을 찾자면 그렇다. 

https://brunch.co.kr/@sukyoung59/32

 

전세계 130만 누적 다운로드 앱을 만든 여성 CTO

밀레니얼 여성 창업가 인터뷰 - 루티너리 박현주 CTO | 코로나 이후 MZ세대 사이에서는 ‘미라클 모닝’, ‘기상 스터디’와 같이 자기개발과 루틴 만들기에 집중하는 ‘갓생 살기’가 유행입니

brunch.co.kr

 

https://velog.io/@kennys/%EB%A6%AC%EC%95%A1%ED%8A%B8%EC%97%90%EC%84%9C-%EC%A2%8B%EC%9D%80-%EA%B5%AC%EC%A1%B0%EB%9E%80

https://www.linkedin.com/feed/update/urn:li:activity:7193850888266866688/

 

LinkedIn 김민설 페이지: 프론트엔드 개발자 김민설 특

[ 취준생 개발자 특강 발표자료 공유 ] 제 취준생 시절의 경험을 기반으로 작성했던 [ 내가 개발자가 될 수 있었던 노하우 ]의 특강 발표 자료로 공유하며 조금이나마 도움이 되고자 합니다. 당시

kr.linkedin.com

 

'다신 안할 것' 에서 많은 것을 하고 있었다.

https://velog.io/@yukina1418/%EC%B7%A8%EC%A4%80%EC%83%9D%EC%97%90%EA%B2%8C-%EB%8F%84%EB%A9%94%EC%9D%B8%EC%9D%B4-%EC%A4%91%EC%9A%94%ED%95%9C%EA%B0%80%EC%9A%94

https://ykss.netlify.app/translation/navigating_the_future_of_frontend/?utm_source=substack&utm_medium=email

https://brunch.co.kr/@susubaa/72

문제

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

 

수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오.

예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이고, 길이는 4이다. 

 

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

둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ Ai ≤ 1,000)

풀이

해설

sequence = [ 10, 20, 10, 30, 20, 50 ]

dp[i] i=0 i=1 i=2 i=3 i=4 i=5
  1 2 2 3 3 4

 

문제

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

 

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

 

예를 들어, ACAYKPCAPCAK의 LCS는 ACAK가 된다.

풀이

const fs = require("fs");

// 문제 링크 : https://www.acmicpc.net/problem/9251
// 제출 시 path : /dev/stdin

const input = fs.readFileSync("/dev/stdin").toString().trim().split("\n");

const LCS = (str1, str2) => {
  const m = str1.length;
  const n = str2.length;

  const dp = new Array(m + 1).fill(null).map(() => new Array(n + 1).fill(0));

  for (let i = 1; i <= m; i++) {
    for (let j = 1; j <= n; j++) {
      if (str1[i - 1] === str2[j - 1]) {
        dp[i][j] = dp[i - 1][j - 1] + 1;
      } else {
        dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
      }
    }
  }

  let result = "";
  let i = m,
    j = n;

  while (i > 0 && j > 0) {
    if (str1[i - 1] === str2[j - 1]) {
      result = str1[i - 1] + result;
      i--;
      j--;
    } else if (dp[i - 1][j] > dp[i][j - 1]) {
      i--;
    } else {
      j--;
    }
  }

  return result;
}

const solution = (input) => {
  const [firstArr, secondArr] = input;
  const answer = LCS(firstArr, secondArr);
  return answer.length;
};

console.log(solution(input));

해설

for (let i = 1; i <= m; i++) {
    for (let j = 1; j <= n; j++) {
      if (str1[i - 1] === str2[j - 1]) {
        dp[i][j] = dp[i - 1][j - 1] + 1;
      } else {
        dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
      }
    }
  }

str1 = ACAYKP

str2 = CAPCAK

dp[i][j] j=0 j=1 j=2 j=3 j=4 j=5 j=6
i=0 0 0 0 0 0 0 0
i=1 0 0 1 1 1 1 1
i=2 0 1 1 1 2 2 2
i=3 0 1 2 2 2 3 3
i=4 0 1 2 2 2 3 3
i=5 0 1 2 2 2 3 4
i=6 0 1 2 3 3 3 4

i=0 -> j=0,1,2,3,4,5,6 다 비교. 

 

dp[1][1]:

ACAYKP 과 CAPCAK 비교

A !== C 이므로 

dp[1][1]은dp[0][1]과 dp[1][0] 중 최댓값 

dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]) 

 

dp[1][2]:

ACAYKP 과 CAPCAK 비교

A === A 이므로 

dp[1][2]은 dp[0][1]+1 

dp[i][j] = dp[i - 1][j - 1] + 1; 

 

문제

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

 

준서가 여행에 필요하다고 생각하는 N개의 물건이 있다. 각 물건은 무게 W 가치 V를 가지는데, 해당 물건을 배낭에 넣어서 가면 준서가 V만큼 즐길 수 있다. 아직 행군을 해본 적이 없는 준서는 최대 K만큼의 무게만을 넣을 수 있는 배낭만 들고 다닐 수 있다. 준서가 최대한 즐거운 여행을 하기 위해 배낭에 넣을 수 있는 물건들의 가치의 최댓값을 알려주자.

 

첫 줄에 물품의 수 N(1 ≤ N ≤ 100)과 준서가 버틸 수 있는 무게 K(1 ≤ K ≤ 100,000)가 주어진다. 두 번째 줄부터 N개의 줄에 거쳐 각 물건의 무게 W(1 ≤ W ≤ 100,000)와 해당 물건의 가치 V(0 ≤ V ≤ 1,000)가 주어진다. 입력으로 주어지는 모든 수는 정수이다.

4 7 // N K
6 13 // W V
4 8 // W V
3 6 // W V
5 12 // W V

접근

배낭 문제는 짐을 쪼갤 수 있는 경우(무게가 소수일 수 있는 경우)와 짐을 쪼갤 수 없는 경우(이 경우 짐의 무게는 0 이상의 정수만 가능) 두 가지로 나눌 수 있는데, 짐을 쪼갤 수 있는 경우의 배낭 문제를 분할 가능 배낭 문제(Fractional) -Greedy 문제 , 짐을 쪼갤 수 없는 경우의 배낭 문제를 0-1 배낭 문제(0-1 Knapsack) - DP문제 라 부른다. - 위키백과

 

해당 문제는 0-1 배낭 문제(0-1 Knapsack)로 DP로 접근한다.

DP문제는 문제의 답을 구하는 규칙성(점화식)을 빨리 찾는게 관건이다.(개인생각, 2023.02.022)

결론부터 말하면 문제의 점화식은 아래와 같다: 

DP[i][j] = max(DP[i - 1][j], DP[i - 1][j - W[i]] + V[i]);

 

풀이

const fs = require("fs");

// 문제 링크 : https://www.acmicpc.net/problem/12865
// 제출 시 path : /dev/stdin

const input = fs
  .readFileSync("./input.txt")
  .toString()
  .trim()
  .split("\n")
  .map((v) => v.split(" ").map((v) => parseInt(v)));

const solution = (input) => {
  const [N, K] = input.shift();
  const weight = input.flat().filter((val, idx) => idx % 2 === 0);
  const value = input.flat().filter((val, idx) => idx % 2 !== 0);
  const dp = Array.from(Array(N + 1), () => Array(K + 1).fill(0));

  // 점화식: dp[i][j] = Math.max(dp[i-1][j], dp[i-1][j-weight[i]]+value[i])

  for (let i = 1; i <= N; i++) {
    for (let j = 1; j <= K; i++) {
      if (j - weight[i] >= 0)
        dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i]);
      dp[i][j] = dp[i - 1][j];
    }
  }

  return dp[N][K];
};
console.log(solution(input));

 

해설

DP[i][j] = max(DP[i - 1][j], DP[i - 1][j - W[i]] + V[i]); 인가?

인덱스 문제 때문에 arr[0] 부분을 형식상 채워준다.

 

row: 아이템1, 2, 3, 4

col: 현재 배낭의 무게

 

 

 

 

 

문제풀이는 이해가 가는데 계속 런타임 에러가 나는 이유를 모르겠다. 내일은 아래 보면서 이부분 디버깅 해봐야겠음.

let fs = require("fs");
let knapsack = fs.readFileSync("예제.txt").toString().split("\n");
const N = Number(knapsack[0].split(" ")[0]);
const K = Number(knapsack[0].split(" ")[1]);
knapsack = knapsack.map((element) =>
  element
    .trim()
    .split(" ")
    .map((value) => Number(value))
);
const weight = [];
const value = [];
for (let n = 0; n <= N; n++) {
  weight.push(knapsack[n][0]);
  value.push(knapsack[n][1]);
}

const dp = Array.from(new Array(N + 1), () => new Array(K + 1));

for (let i = 0; i <= N; i++) {
  dp[i][0] = 0;
}
for (let j = 0; j <= K; j++) {
  dp[0][j] = 0;
}
for (let j = 1; j <= K; j++) {
  if (knapsack[1][0] <= j) {
    dp[1][j] = knapsack[1][1];
  } else {
    dp[1][j] = 0;
  }
}

for (let i = 2; i <= N; i++) {
  for (let j = 1; j <= K; j++) {
    if (j < weight[i]) {
      dp[i][j] = dp[i - 1][j];
    } else {
      // 현재 물건을 포함하지 않는 경우 : dp[i - 1][j]
      // 현재 물건을 포함하는 경우: dp[i-1][j - weight[i]] + value[i]
      dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i]);
    }
  }
}
console.log(dp[N][K]);

문제

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

접근

1을 빼거나 2나 3을 나누어 1로 만드는데 걸리는 연산 횟수의 최솟값을 구하는 문제입니다.

첫째줄는 1이상 10^6이하의 정수 N이 주어집니다. 수의 범위가 크기 때문에 계산가능한 모든 수를 구하는 완전탐색 등은 이 문제에 어울리지 않은 접근법입니다. 한 번 연산한 값을 기억해 두고 문제를 풀 수 있는 DP가 적절해 보입니다.

 

DP의 인덱스는 숫자를 뜻합니다.

D[N-1]: N에서 1을 빼서 1을 만드는 연산 횟수

D[N/2]: N에서 2를 나눠 1을 만드는 연산 횟수

D[N/3]: N에서 3을 나눠 1을 만드는 연산 횟수

 

D[N] 숫자 N이 1이 되는데 걸리는 최소한의 연산 횟수를 저장합니다.

N이 2로 나눠진다면 D[N] = D[N-1] + 1 과 D[N/2] + 1 중 더 작은 값, N이 3으로 나눠진다면 D[N] = D[N-1] + 1 과 D[N/3] + 1 중 더 작은 값이 됩니다.

각 경우의 수 뒤에 +1 이 되는 이유는 D[N-1],D[N/2],D[N/3] 이 각 N을 구하기 이전의 연산횟수를 나타내기 때문입니다.

 

예를 한 번 들어볼까요?

D[N-1] + 1 :

4를 1을 빼서 1로 만드는 연산 횟수는 3입니다. 4-1-1-1=1

3을 1을 빼서 1로 만드는 연산 횟수는 2입니다. 3-1-1=1

2를 1을 빼서 1로 만드는 연산 횟수는 1입니다. 2-1=1

이를 뒤집어보면 숫자 N을 1을 만들 때까지 1을 빼는 연산의 횟수는 N-1을 1을 만들 때까지 1을 빼는 연산의 횟수 +1 임을 알 수 있습니다. 

D[N/2] + 1

2를 2로 나눠서 1로 만드는 연산 횟수는 1입니다. 2/2 = 1

4를 2로 나눠서 1로 만드는 연산 횟수는 2입니다. 4/2 = 2, 2/2 =1 

8을 2로 나눠서 1로 만드는 연산 횟수는 3입니다. 8/2 = 4, 4/2 = 2, 2/2 = 1

이를 뒤집어보면 숫자 N을 1을 만들 때까지 2를 나누는 연산의 횟수는 N-1을 1을 만들 때까지 N을 나누는 연산의 횟수 +1 임을 알 수 있습니다.

D[N/3] + 1도 위와 D[N/2] + 1의 경우와 마찬가지입니다.

 

문제를 한 번 풀어볼까요? N=4 로 예를 들어봅시다.

우선 D[0]은 문제 범위 밖이므로 0으로 처리해 줍니다. 

D[1] = 0 입니다. 1을 1로 만들 수 있는 연산의 횟수는 0회이기 때문입니다.

D[4] = Math.min( D[3] + 1 , D[4/2] +1) = Math.min( 1 + 1, 2 + 1 ) = Math.min(2, 3) = 2 가 됩니다.

 

이를 코드로 풀어보면 아래와 같습니다.

풀이

const input = fs
  .readFileSync("/dev/stdin")
  .toString()
  .trim()
  .split("\n")
  .map((v) => v.split(" ").map((v) => parseInt(v)));
const solution = (input) => {
  const N = +input;
  const DP = Array.from({ length: N + 1 }, () => 0);

  for (let i = 2; i < N + 1; i++) {
    DP[i] = DP[i - 1] + 1; // 1을 빼서 1로 만드는 연산의 횟수로 우선 설정

    if (i % 2 === 0) {
      // 2로 나눠진다면,
      DP[i] = Math.min(DP[i], DP[i / 2] + 1); // 1을 빼서 1로 만드는 연산의 횟수와  2로 나눠 1로 만드는 횟수 중 더 작은 경우로 선택.
    }

    if (i % 3 === 0) {
      DP[i] = Math.min(DP[i], DP[i / 3] + 1);
    }
  }

  return DP[N];
};

console.log(solution(input)); // 3

 

+ Recent posts