ul태그가 있고 얘가 li태그들을 자식들로 갖고 있다고 하자. 이 li태그들에 어떤 이벤트를 등록하려면 지금까지는 다음과 같이 해왔었다. 

<ul id="some-list">
    <li>가계부 정리하기</li>
    <li>자바스크립트 강의듣기</li>
    <li>리액트 공부하기</li>
    <li>코딩테스트 문제 풀기</li>
</ul>
const someList = document.getElementById("some-list");

for (let item of someList.children){
    item.addEventListener("click", function(e){
        e.target.ClassList.toggle("done");
    };
}

즉 자식들로 잡든 처음부터 getElementsByClassName으로 잡던 li태그들 하나하나에 직접 이벤트 리스너들을 때려박는 형태였다. 그러나 하나하나 때려박는다는 것이 성능상 안 좋기도 하고, 나중에 js코드로 some-list에 새로운 li태그를 넣을 경우 새로 넣어진 li태그에도 별도로 다시 저 이벤트를 때려박아야 하는 번거로운 일이 생긴다.

 

이런 상황에서 쓸 수 있는 것이 이벤트 위임.

간단하게 말해서, 자식들의 이벤트 리스너를 부모에서 다루는 것이다. 

이벤트 버블링을 통해서.

 

알다시피 이벤트 버블링은 자식에서 발생한 이벤트가 부모로 퍼져가는 것을 말한다. 즉 위와 같은 클릭 이벤트를 등록하는 상황에서, 자식(li태그)에서 발생한 click이벤트가 부모(ul태그 등)으로 퍼져나가는 것을 활용한다는 것이다. 그리고, e.target을 활용하면 이벤트를 발생시킨 녀석에 대한 특정한 동작 등이 가능하다!! 즉 다음과 같이 할 수 있다.

const someList = document.getElementById("some-list");

someList.addEventListener("click", function(e){
    if (e.target.tagName == "li"){
        e.target.ClassList.toggle("done");
    }
});

if (e.target.tagName == "li")를 넣은 이유는, ul태그의 영역에서 li태그가 없는 공간을 클릭하는 상황에도 저 이벤트 리스너가 수행되는 상황을 막는 것이다. 해석하자면 ul태그의 영역에 대해 클릭 이벤트가 발생했을 때 이벤트 리스너를 실행하는데 그 중에서도 ul 태그 내의 li태그가 클릭돼서 수행되는 경우에만 if문 내의 코드를 실행한다는 것. 

 

기존에 쓰던 반복문을 통해 하나하나 이벤트 리스너를 때려박는 방법이 비효율적이라곤 생각했으나 이렇게 쉬운 방법이 있을 줄 몰랐다. 강의를 듣던 중 관련된 질문에 "아니 이렇게 하면 부모에 등록되는 건데, 이 경우엔 자식에도 등록이 되어지는 거냐?"란 질문이 있던데, 내 생각은 "No. 아닙니다. 자식인 li태그를 클릭하면 캡처링 단계에서 수수숙 내려와 li태그 즉 사건을 불러일으킨 놈을 찍고, 다시 부모 요소들로 올라가는 버블링이 생기게 되는데 그 때 저 이벤트 리스너가 수행되면서 target을 통해 불러일으킨 놈이 내 자식 중에서 li일 때만 수행하는 방식입니다"이다.

 

참고로 이 이벤트 위임이란 방법은 버블링을 이용하는 방법이므로, 당연한 소리지만 자식 태그에 버블링을 막도록 코드를 짜놨으면 무용지물이다. 이 점 알아두고 사용하자.

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

 

11726번: 2×n 타일링

2×n 크기의 직사각형을 1×2, 2×1 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오. 아래 그림은 2×5 크기의 직사각형을 채운 한 가지 방법의 예이다.

www.acmicpc.net


1. 브루트 포스로 접근한다면

첫 번째 열부터 마지막 열까지 채운다고 할 때 

지금 열을 세로블록으로 채울지

지금 열 + 바로다음열을 가로블록 2개로 채울지

를 선택함

러~프하게 생각하면 2^N개정도의 경우가 나오고 N은 최대 1000까지 주어지니 이 방법은 못 쓴다.

 

2. DP로 접근

k번째 열까지 채우는 것은

1) k - 2번째 열까지 채우고 세로블록 두 개 연달아 놓거나 가로블록 찍찍 놓거나

2) k - 1번째 열까지 채우고 세로블록 하나 놓거나

이 방법이다. 

나는 여기서 k - 2번째 열까지 채우고 세로블록 두 개를 연달아 놓는 것과 k - 1번째 열까지 채우고 세로블록을 하나 놓는 것은 중복되는 것이 있으므로 그 부분을 처리하기 위해 공을 들였는데, 다 풀고 보니 예외처리할 필요가 없었다. 

 

k - 2번째 열까지 채우고 세로블록을 두 개 연달아 놓는 행위가 k - 1번째 열까지 채우고 세로블록 하나 놓는 행위에 포함되기 때문. 

k - 2번째 열까지 채우고 세로블록을 두 개 놓는 것을 동시에 놓는 게 아니라 하나하나 놓는다고 해보면, k - 2번째 열까지 채우고 세로블록을 하나 낳고 그 다음에 하나를 마저 놓는 것이지만 처음에 하나를 놓는 과정에서 이미 k - 1번째 열까지 채운 것이 된다는 것이다.

 

즉 k - 2번재 열까지 채우고 k번째 열까지 채우는 과정은 가로블록을 찍찍 놓는것만 생각하면 되는 것이었다.

 

일단 아쉬운 대로 내 풀이 공유..

N = int(input())

MOD = 10007
# dp[x][0] : x번째 열까지 채우는데 마지막이 세로로 끝나는 경우
# dp[x][1] : x번째 열까지 채우는데 마지막이 가로로 끝나는 경우
dp = [[0, 0], [1, 0], [1, 1], [2, 1]]

for i in range(4, 1001):
    dp.append(
        [(sum(dp[i - 2]) + dp[i - 1][1]) % MOD, sum(dp[i - 2]) % MOD]
    )

print(sum(dp[N]) % MOD)

 

더 나은 풀이

N = int(input())

MOD = 10007

dp = [0, 1, 2, 3]

for i in range(4, N + 1):
    dp.append((dp[i - 2] + dp[i - 1]) % MOD)

print(dp[N])

느낀점

일단 이런 DP문제를 점화식을 세우는 과정에서 앗? 중복되니까 예외처리할 부분이 있는데? 라고 생각되는 부분들이 있다. k - 2번째와 k - 1번째에 어떤 연산?을 해주어 k번째를 구하는 경우, k - 2번째에서 구하는 것과 k - 1번째에서 구하는 것들이 새로 중복되는 게 있는 거 같은데? 하는. 그러나 k - 2번째에서 특정 연산을 하는 것을 유심히 보며 중간에 k - 1번째가 '되는' 부분이 있는지 봐야할 것이다. 그렇다면 그 부분을 빼고 생각하면 중복처리 땜에 머리 굴릴 필요가 없어지니까. 애시당초 k - 2번째와 k - 1번째에 서로 다른 종류의 연산을 가미해 중복될 일이 없도록 처음부터 생각하는 것도 방법일 듯하다.

 

그리고 굳이 처음부터 어떤 관계가 있을까 하며 뇌피셜로 점화식 세울라 하지 말고, 일단 2번째일땐 이 만큼의 가짓수, 3번째일땐 이만큼의 가짓수, 4번째일땐 이만큼의 가짓수..하면서 쭉 쓰다가 점화식 관계를 발견하는 것도 하나의 방법일 듯하다. 하나의 틀에 박히지 말자.

PC방 알바하던 중이었다. 잠깐 시간이 비어서 카운터 컴퓨터로 유튜브를 켰는데 알고리즘으로 침착맨의 "가장 쉽게 질리는 음식 16강"이란 제목의 영상이 떴다. 영상을 보다가 "나도 한 번 16강 웹사이트를 만들어볼까?"라는 생각으로 시작하게 됐다.


어떤 식으로 할 건지 구상해봤다.

우선 처음 시작하면 16개의 아이템들이 랜덤하게 섞이고, 2개씩 사용자 화면에 출력된다. 사용자가 선택한 음식들은 별도의 배열에 담기고, 16개의 아이템에 대해 모두 셀렉이 끝나면 8강을 진행. 이후 4강 진행, 결승.

 

난이도가 있는 프로젝트는 아니라고 생각되지만, 강의 실습이 아니라 처음으로 스스로 하는 프로젝트가 될 것 같다. 작년 멋사에서 Django로 플젝할 때와는 다른 설렘이 생기는 듯. 역시 강의들으며 실습보단 스스로 뭔가 만드는 게 더 재밌는 건가 싶다 ㅋㅋ

 

일단 이 플젝은 내가 리액트로 처음 하는 개인 플젝이므로, 이 플젝으로 얻고 싶은 소소한 목표는 다음과 같다.

 

1. 기본적인 컴포넌트 다루는 법 익히기 

: 강의 실습이 아니라 내가 스스로 만들면서 하는 거니까 컴포넌트의 개념이 좀 더 와닿지 않을까 생각한다.

2. json파일 다루기

: 대부분의 웹사이트는 json배열 등을 가공하고 출력하고 뭐 그런다고 한다. 강의에서는 API로 데이터를 받아오기 전에 mock데이터(샘플로 쓸 데이터를 mock데이터라고 부른다고 하더라)를 만들어서 쓰던데, 나도 이 플젝을 통해 json파일 등을 다루는 데 좀 익숙해지면 좋겠다. 작년에 Django로 해커톤할때도 json을 다루는 일이 종종 있었기 때문..

3. API로 데이터를 받아오는 것 이해하기

: 사실 js를 공부하고 리액트를 시작한게 아니라 리액트와 js를 병행하면서 그 때 그 때 모르는 걸 찾아보는 식으로 하기 때문에 fetch, async, await, premise? 이런 거 잘 모른다. 이 플젝을 하면서 이런 게 뭔지 이해하자. 일단 처음엔 나도 mock.json만들고 다루다가 좀 가닥이 잡히면 API로 데이터 받아와보는 식으로 해야겠다.

 


# 일단 mock.json만들자!

일단 샘플 데이터들이 있는 mock.json을 만들기로 했다. 근데 시작부터 나름 큰 난관에 봉착.

 

"도대체 어떤 16강 월드컵을 만들지?"

 

킹받는 롤 챔피언 16강 만들까? 이런 거 고민하다가 카페에서 하던 중이라 그런지 갑자기 가장 먹고 싶은 디저트 16강으로 정했다.ㅋㅋㅋㅋㅋ

 

나름 샘플 만드는 과정도 재밌었다. 디저트를 뭘로 하지?부터 이미지는 다운받아서 로컬에 넣을까 하다가 그냥 구글에 검색해서 이미지 주소 복사해서 쓰기로 했다. 근데 이거 저작권에 문제 생기나..? 문제 생기면 프로젝트 폐기 이런건가..

 

mock.json은 다음과 같이 만들어졌다.

배열 형태고 각 원소?들은 id, name, imgUrl속성?을 갖도록. 이제 이 놈을 App.js에서 다음과 같이 임포트했다

import mock from "../mock.json";

리액트는 import를 활용해 모듈이나 파일을 추가하듯이 이미지를 추가할 수 있다.  리액트에서 로컬에 있는 이미지 등을 다룰 땐 저렇게 임포트해서 경로를 쓰는게 더 낫다 카더라. 아니면 오류가 난다꼬..json도 저렇게 import하면 mock이란 이름으로 쓸 수 있다.

 

이제 이 놈들을 시험 삼아서 화면에 띄워보기로 했다. 배열의 map메소드를 활용하면 배열의 각 아이템들에 대한 가공?이 가능하고, 이 map메소드 안에서 JSX요소를 리턴하면 마치 여러 개의 JSX요소를 추가한 것처럼 동작한다. App에서 다음과 같이 map메소드를 쓰면서 DessertItem 컴포넌트를 만들도록? 했다.

function App(){
    return(
        <div>
            {mock.map((dessert) => {
                return(
                    <li key={dessert.id}>
                        <DessertItem item={dessert}/>
                    </li>
                )
            })}
        </div>
    )
}

아! 그리고 리액트에서 배열을 다룰 때는 저렇게 원소들에 key속성을 넣어줘야 하고, 속성값으로는 각 요소를 구분지을 수 있는 값을 넣어야 한다.  공식 문서에 따르면 key는 리액트가 어떤 항목을 추가, 변경, 또는 삭제할지 식별하는 것을 돕는다고 함. 따라서 배열의 인덱스를 key로 쓰는 멍청한 짓은 하면 안 됨. 배열 요소들의 순서가 바뀔 수도 있으니까 인덱스는 고유한 값이 아니기 때문!

 

암튼 DessertItem는 다음과 같이 작성해 디저트 사진과 이름을 볼 수 있도록 했다.

function DessertItem({item}){
    return(
        <div>
            <h3>{item.name}</h3>
            <img src={item.imgUrl} alt="디저트 사진" />
        </div>
    )
}

이제 출력된 모습!

 

별 거 안했지만 그래도 혼자 해봤다는 게 조금 뿌듯..뿌듯할 레벨은 아니지만 ㅎㅎ..

암튼 이제 시작이다! 잘 만들어보자

 

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

 

13305번: 주유소

표준 입력으로 다음 정보가 주어진다. 첫 번째 줄에는 도시의 개수를 나타내는 정수 N(2 ≤ N ≤ 100,000)이 주어진다. 다음 줄에는 인접한 두 도시를 연결하는 도로의 길이가 제일 왼쪽 도로부터 N-1

www.acmicpc.net


1. 무식한 방법으로 접근한다면?

어떤 도시들에서 기름을 넣을 건지만 정하면 전체 비용이 정해진다. 첫 번째 도시에선 무조건 기름을 넣어야 하므로, 첫 번째 도시 빼고는 기름을 아예 안 넣을 수도 있다(즉 첫 번째 도시에서 마지막 도시로 갈 수 있을 만큼의 기름을 빵빵하게 넣고 가는 경우에 해당)

이는 첫 도시에서 시작해서 그 다음 도시를 선택할지 안 할건지, 그 다음 도시 역시 선택할지 안 할건지,...각 도시에 대해 두 개의 선택지가 있는 것으로, 이 경우 전체 2^(n-2)개의 방법이 나온다. 이 방법 중 최소비용이 나오는 걸 고르면 됨. 그러나 n은 문제에서 10만까지 주어지므로 이 방법으론 시간 내에 풀 수 없다는 결론

 

2. 부분문제로 쪼개기 가능?

가능. 마지막 도시로 가는 것은

N - 1번째 도시까지 오고, N-1번째에서 기름 넣고 N번째 도시로 한 번에 가는 경우

N - 2번째 도시까지 오고, N-2번째에서 기름 넣고 N번째 도시로 한 번에 가는 경우

N - 3번째 도시까지 오고, N-3번째에서 기름 넣고 N번째 도시로 한 번에 가는 경우

...

중에서 min값을 찾으면 됨. N - 1번째 도시까지 오는 부분문제, N - 2번째 도시까지 오는 부분문제들이 생기는 것이다.

 

3. 중복되는 구조 있음? 있으면 DP로 일단 가능할텐데

있음. N - 1번째 도시로 오는 부분문제도 쪼개면 N - 2번째 도시로 오는 경우 등을 구해야 하는데 이것들이 중복되는 것을 관찰가능.

 

그러나 DP로 풀기엔 애매한게, 이러면 시간복잡도가 O(n^2)정도가 걸리는데 n이 10만까지주어지니까 시간복잡도가 너무 크다. 다른 방법을 모색해야 함.

 

3. 그리디 의심

문제를 그대로 이해하면 k번째 도시에서 기름을 채우고 채운만큼 갈 수 있다. 그대~로 생각한다면 "나는 지금 이 도시에서 기름을 얼마나 채우고 가야 하는가?"로 생각하게 돼서 조금 시간이 걸렸다. 그러나 이 틀에서 벗어나서, 후불로 요금을 지불한다 생각해보자. 각 도시를 거치면서 그 도시에서 파는 기름을 살 때만 내가 이전에 쓰던 기름값을 낸다고 생각하자는 것이다. 즉 첫 도시에서 시작해(즉 첫 도시에서 기름을 사서) 두 번째 도시에 가면 두 번째 도시에서 파는 기름과 내가 지금 들고 있는 기름(첫 도시에서 산 기름) 중 어떤 기름을 쓸 건지를 선택할 수 있게 된다. 여기서 두 번째 도시에서 파는 기름을 쓰기로 했다면 그 도시까지 오는데 사용된 기름값을 그 때 낸다! 이렇게 되면 내가 지금 들고 있는 기름과 새로 방문한 도시에서 파는 기름 중 더 싼 기름만 선택해서 나가면 된다.

 

4. 코드

import sys

input = sys.stdin.readline

N = int(input())

length = list(map(int, input().split()))

cost = list(map(int, input().split()))

ans = cost[0] * length[0]
now_cost = cost[0]

for i in range(1, N - 1):
    new_cost = cost[i]
    now_cost = min(now_cost, cost[i])
    ans += now_cost * length[i]

print(ans)

5. 정당성 검증(그리디니까)

상식적으로 당연히 그 때 그 때 더 싼 기름을 사는게 제일 좋다. 굳이 엄밀한 증명이 필요없다고 생각됨.그래도 공부차원에서 귀류법을 사용해 정당성을 검증하자면

 

가정 : 매 번 가장 싼 기름을 선택해나가는게 답이다.

??? : 아니던데? ㅎㅎ

반박 : 

1) 생각할 필요도 없다. 가장 싼 거 선택해나가면 그게 제일 싸잖아.

2) 그래 너 말이 맞다고 해보자.

그럼 최적해 집합 O = {o1, o2, o3, ..., ok, ..., o(n-1)}이 있고

가장 싼 기름을 선택한 집합 G = {g1, g2, g3, ..., gk, ..., g(n-1)}이 있어.

이 집합들이 합이 전체비용이겠지? 그럼 이 두 집합이 다른 집합이니까 1항부터 k항까지의 부분합이 달라지는 k가 어디엔가 존재하겠지. 그러나 생각할 수 있는 건 gk ~ g(n-1)의 합이 ok ~ o(n-1)보다 작다는 거야. 왜냐 G는 매번 가장 싼 기름을 선택한거니까!

이제 새 집합 N = {o1, o2, o3, ..., gk, ..., g(n-1)}을 만들었다고 해보자. O에서 k번째 항부터를 G의 항으로 바꾼거야. 근데 gk ~ g(n-1)까지의 합 < ok ~ o(n-1)까지의 합이니까 N의 전체합은 O보다 작겠지? 근데 O는 최적해니까 지보다 작은 전체합을 가지는 집합이 있으면 안되잖아? 이거 모순이네?

그래서 내 말이 맞아. 즉 매번 가장 싼 기름을 선택해나가야 한다는 거지.


느낀점

결국 그리디는 선택하는 과정이 있고, 그 과정에서 가장 작은/가장 큰 .. 뭐 이런 선택을 한다. 그러나 이 '선택'은 잘 보이지 않을 때가 있다. 이 문제도 단순하게 "계속 대체 지금 도시에서 얼마나 기름을 채워야 하지? 가장 많이 채워야 하나(?)"식으로 생각했다면 계속 헤멨을 것이다. 그러나 그리디가 의심될 때는 가장 작은 값 또는 가장 큰 값 이런 식으로 선택할 수 있게끔 생각을 전환할 필요가 있다. 브루트 포스로 풀 수 없다는 생각이 들고 DP로 풀기도 애매해서 그리디가 의심된다면 가장 ~~한 선택을 쉽게 할 수 있게끔 생각을 전환할 필요가 있다는 점을 알고 가자.

 

js에서 sort()메소드를 사용하면 배열을 정렬할 수 있다. sort는 정렬한 배열을 리턴해주는데 주의할 점은 정렬한 배열은 새 배열이 아니라 원본 배열과 같은 녀석이다(즉 같은 참조이다).

 

sort()메소드에 아무런 인자도 전달해주지 않으면 기본적으로 유니코드에 정의된 문자열 순서에 따라 정렬해준다.

즉,

const letters = ['A', 'C', 'E', 'B'];
const nums = [111, 13, 20, 10000];

letters.sort();
nums.sort();

console.log(letters); // ['A', 'B', 'C', 'E'];
console.log(nums);    // [10000, 111, 13, 20]

숫자들조차도 문자들 정렬할 때처럼 사전순으로 정렬된 모습이다ㅋㅋ 즉 문자열을 정렬할 경우엔 그냥 sort()를 써도 되지만, 숫자들을 정렬할 때는 sort()만 한다고 되지 않는 모습. 파이썬은 그냥 해주던데..에휴

 

암튼 이렇게 숫자를 정렬하고 싶은 상황 등에선 sort()에 콜백함수를 전달해야 한다. 

const nums = [111, 13, 20, 10000];

nums.sort((a, b) => a - b); // 오름차순 정렬
console.log(nums);          // [13, 20, 111, 10000]

nums.sort((a, b) => b - a); // 내림차순 정렬
console.log(nums);          // [10000, 111, 20, 13]

급하면 여기까지만 보고 나가도 됨.

근데 이제 이 이유가 궁금한 사람들이 있잖아? 나처럼. 

다른 데 가지 말고 여기서 저렇게 해야 하는 이유를 같이 보자구요 :) ㅋㅋㅋㅋㅋㅋ

 

우선, sort()는 파라미터로 compareFunction을 옵셔널로 받음. 옵셔널이란 말은 이 놈을 받을 수도 있고 안 받을 수도 있다는 얘긴데 받는다면 이 compareFunction을 기준으로 정렬이 되고, 안 받는다면 유니코드에 의한 문자열 순서대로 정렬한다는 것.

 

암튼 이 compareFunction은 파라미터를 두 개 받도록 만들어야 함. (a, b)로 받는다고 해봅시다. 그러면 이 함수의 리턴값에 의해 어떻게 정렬할지가 결정되는데, 그건 다음과 같음.

 

1. 리턴값이 음수 : a가 앞으로 오도록 정렬

2. 리턴값이 0 : a, b를 바꾸지 않음

3. 리턴값이 양수 :  b가 앞으로 오도록 정렬

 

따라서 리턴값을 a - b로 하면 오름차순으로, b - a로 하면 내림차순으로 정렬할 수 있는 것임!

 

※ 참고링크

https://developer.mozilla.org/ko/docs/Web/JavaScript/Reference/Global_Objects/Array/sort

 

Array.prototype.sort() - JavaScript | MDN

sort() 메서드는 배열의 요소를 적절한 위치에 정렬한 후 그 배열을 반환합니다. 정렬은 stable sort가 아닐 수 있습니다. 기본 정렬 순서는 문자열의 유니코드 코드 포인트를 따릅니다.

developer.mozilla.org

 

+ Recent posts