Ray`s Tech Lab

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

이 문제를 무식하게 모든 경우의 수를 따져서 풀려고 하면 어떻게 할 수 있을까? 각 열에서 하나의 스티커만 뽑을 수 있으므로 최대 n개의 스티커를 뽑을 수 있다. 즉 각 열에 대해 위의 스티커를 뽑던가, 아래의 스티커를 뽑던가, 안 뽑던가의 3가지 갈래가 있고 n열까지 있으니 3^n개의 조합들이 나오고, 여기서 변을 공유하는 스티커를 뽑은 케이스를 쳐내야한다. 즉 이 방법의 시간복잡도는 O(3^n)정도가 될 것이고 n은 문제에서 최대 100,000으로 주어진다 했으니 연산횟수는 천문학적인(?) 숫자가 된다. 주어진 시간제한 1초 내에 이 방법으로 문제를 푸는 것은 매우 힘들다..고 봐야 한다.

그럼 어떻게 접근할 수 있는가. 그리디하게 접근한다면 일단 각 열에서 무조건 스티커를 떼는데, 가장 높은 값의 스티커들만 떼가야 한다. 그러나 당연히 이는 불가능하다. 변을 공유하는 스티커를 뗄 수 없으니 1번째 열의 스티커를 떼면 그 다음 열에서 뗄 수 있는 스티커, 또 그 다음 열에서 뗄 수 있는 스티커가 정해진다. 이 방법은 최적의 답을 도출할 수 없다.

이번엔 dp를 의심해보자. 일단 이 문제는 부분 문제로 쪼갤 수 있다. 1번째 열부터 차례차례 스티커를 떼고 n번째 열의 스티커를 뗀다고 해보자. 물론 각 열의 스티커는 안 뗄 수도 있다. 이 때 정답은 가장 큰 점수를 얻는 스티커 조합이므로, 위쪽 스티커든 아래쪽 스티커든 간에 n번째 열의 스티커는 떼야 한다. 그렇다면 답은

마지막 스티커(n번째 열)을 위쪽을 뽑은 경우

마지막 스티커(n번째 열)을 아래쪽을 뽑은 경우

이 둘 중 하나다. 여기서 단순히 n번째 열 스티커를 위쪽을 뽑았다면, 이 점수를 n - 1번째 스티커를 아래쪽을 뽑은 경우에 나오는 값에 더해야 합니다. 라고 하면 안된다.  다음 예시를 보자

1 ~ 3열까지 스티커를 뽑았을 때 나오는 최대 점수는 몇인가? 라는 문제라면 1, 2열에서 뭘 뽑던 3열에서 스티커 하나를 뽑은 케이스가 정답이 된다. 3열에서 아래쪽을 뽑은 케이스를 알기 위해 2열에서 위쪽을 뽑은 케이스를 더한다면 이 때 구해지는 점수는 2 + 2 + 25 = 29가 된다. 그러나 3열에서 아래쪽을 뽑은 케이스의 최대값은 35다! 1열에서 10을, 2열에서 아무것도 안 뽑고 3열에서 25를 뽑은 케이스. 즉, n번째 열의 위쪽을 뽑은 경우 얻는 점수의 최대는

n - 1번째 스티커를 아래쪽을 뽑은 경우의 최대누적합

n - 2번째 스티커를 뽑은 경우(위, 아래 상관없음)의 최대누적합

이 둘 중 더 큰 값에 n번째 열의 위쪽스티커의 점수를 합한 것이다. dp[1][i]이 i번째 열에서 위쪽 스티커를 뽑은 경우의 최대누적합, dp[2][i]가 i번째 열에서 아래쪽 스티커를 뽑은 경우의 최대누적합이라 하면 점화식은 다음과 같이 얻어진다.

dp[1][n] = max(dp[2][n-1], max(dp[1][n-2], dp[2][n-2]))

dp[2][n] = max(dp[1][n-1], max(dp[1][n-2], dp[2][n-2]))

이걸 고대로 코드로 옮기면 된다.

import sys

T = int(sys.stdin.readline())

for _ in range(T):
    n = int(sys.stdin.readline())
    sticker = [[0]]
    sticker.append([0] + list(map(int, sys.stdin.readline().split())))
    sticker.append([0] + list(map(int, sys.stdin.readline().split())))

    dp = [[0 for i in range(n + 1)] for j in range(3)]
    dp[1][1] = sticker[1][1]
    dp[2][1] = sticker[2][1]

    for i in range(2, n + 1):
        dp[1][i] = max(dp[2][i - 1], max(dp[1][i - 2], dp[2][i - 2])) + sticker[1][i]
        dp[2][i] = max(dp[1][i - 1], max(dp[1][i - 2], dp[2][i - 2])) + sticker[2][i]

    print(max(dp[1][n], dp[2][n]))

브루트포스 알고리즘은 사실 설명하기 민망할 수 있을 정도로 직관적이다. 가능한 모든 경우를 따져가며 답을 찾는 방식. 따라서 시간만 충분하다면 이 방식으로 찾은 답은 정답임이 보장된다. 모든 경우를 다 따져본 거니까..

ex - 1) 1부터 N까지의 합은?

: 무식하게 풀자면, 1부터 N까지 숫자들을 하나하나 다 더해보면 됨. 시간은 좀 걸리지만 100% 확실한 정답을 보장.

sum = 0
for i in range(1, N + 1):
	sum += N

ex - 2) 주어진 배열에 x라는 수가 있는가?

: 무식하게 풀자면, 주어진 배열의 원소를 순서대로 순회해보면 된다. 모든 원소를 순회해보면 있는지 없는지 100% 따질 수 있다.

N = 100

def solution(N, arr):
	for i in arr:
    	if i == N:
        	return True
    return False

이 방법의 최고 장점은 100% 확실한 답을 보장한다는 것. 그러나 단점은 시간이 오래 걸릴 확률이 매우 높다는 것! 

최근 알고리즘 스터디를 시작했는데, 문제를 푸는 방법에 대해 설명을 들었다. 다음과 같다.

1. 우선 무식하게 접근해보기. 즉 브루트하게 풀려면 어떻게 할 수 있나 설계해보기

2. 설계한 브루트 방식의 시간복잡도를 계산해보고, 주어진 문제의 시간제한 내에 풀 수 있을 것 같으면 코드로 옮기기

3. 시간 내에 풀 수 없을 것 같으면 다른 방식으로 해보기. 설계했던 브루트한 방식을 어떻게 최적화할 수 있을지도 고민하기.

참고로 c++언어는 대략 1억번의 연산을 1초 내로 할 수 있고, 파이썬 언어는 대략 5천만번의 연산을 1초 내에 할 수 있다고 한다. 따라서 설계한 브루트한 방식의 시간복잡도가 O(n^2) 뭐 이런 식으로 나왔다면, 여기에 문제에서 n의 최댓값으로 주어지는 값을 넣어봐서 시간 내에 충분히 될 것 같으면 코드를 짜보라는 것. 참고로 애매하게 음 한 1억번 정도 연산할 것 같은데? 로 되지는 않고 100억번 정도  연산하네? 또는 100만번만 연산하네? 정도로 확실하게 주어진다고 한다.

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

무식하게 풀어보자.

2차원 배열 형태로 필드가 주어졌을 때, 비의 양을 0부터 100까지 해주면서 생기는 영역의 개수를 하나하나 세보면 된다. 영역의 개수를 세는 것은 N * N짜리 필드의 칸들을 하나하나 순회하면서 센다고 할 때, N으로 가능한 최댓값은 100이므로 이론상 최악의 경우 100 * 100 * 100 = 100만번 정도의 계산을 하게 된다. 문제의 제한시간은 1초인데 파이썬은 1초 내에 충분히 100만번의 연산이 가능하므로 통과할 수 있으리라 어림짐작이 가능하다.

조금만 더 최적화시켜서, 비의 양을 굳이 0부터 100까지 순회할 필요는 없다. 비의 양이 0이면 안전영역의 개수는 무조건 1이고(각 영역의 높이는 무조건 1이상이므로), 비의 양이 주어진 필드의 최고높이가 되는 순간 모든 지역이 물에 잠겨 안전영역의 개수는 0이 된다. 따라서 비의 양을 0 ~ 100까지가 아니라 1 ~ 필드에서 주어진 최고높이까지만 순회하면 됨

import sys
sys.setrecursionlimit(10000)

N = int(sys.stdin.readline())
height, checked = [], []

for _ in range(N):
    height.append(list(map(int, sys.stdin.readline().split())))
    checked.append([True] * N)

# 인접한 영역들 싹 다 표시하기
def checkArea(N, r, c):
    checked[r][c] = False
    directions = [(r - 1, c), (r, c + 1), (r + 1, c), (r, c - 1)]
    for nr, nc in directions:
        if (0 <= nr < N) and (0 <= nc < N) and checked[nr][nc]:
            checkArea(N, nr, nc)  


# 빗물의 높이가 rain으로 주어졌을 때 안전영역 개수 계산
def calculate(N, rain):
    areas = 0
    # 잠기는 영역들 구하기 - False로 표현
    for r in range(N):
        for c in range(N):
            if rain >= height[r][c]:
                checked[r][c] = False
            else:
                checked[r][c] = True
    # 안전 영역 개수 구하기
    for r in range(N):
        for c in range(N):
            if checked[r][c]:
                checkArea(N, r, c)
                areas += 1
    return areas


# 안전영역의 최대 개수 리턴
def solution(N):
    # 답이 될 수 있는 값의 최소 = 1 (각 지점 높이 최소 = 1, 빗물 최소높이 = 0이므로)
    answer = 1
    for rain in range(1, 101):
        areas = calculate(N, rain)
        # 만약 특정 빗물 높이에 대해 안전영역이 0이면 break -> 빗물이 height의 최댓값과 같아진 거니까
        if areas == 0:
            break
        if answer < areas:
            answer = areas
    return answer

print(solution(N))

인접한 영역을 어떻게 셀 것인가에 대해 고민해본 문제다. 이는 재귀를 통해 방문한 지역들을 모두 방문처리(본 코드에선 cheked배열을 이용)하는 것으로 구현했다. 어떤 지점으로부터 상하좌우방향으로 1칸씩 이동하며 순회해야 할 때, checkArea함수에서 쓴 것처럼 방향배열을 설정해두고 사용하면 매우 편리하다. 아니면 다음처럼 해도 편리한 것 같다. 스터디에서 다른 스터디원이 쓰는 걸 참고했음ㅋㅋ

# global하게 방향배열 만들기
direction = [(0, -1), (0, 1), (-1, 0), (1, 0)]

# 어딘가에서 만든 함수에서 이용
def some_func(r, c):
	...
    for dr, dy in direction:
        nr = r + dr                               # 다음 row좌표구하기
        nc = c + dc                               # 다음 col좌표구하기
        ...

왜 이문제가 DFS, BFS분류에도 들어가는지 궁금했는데, 현재 위치에서 상하좌우에 있는 칸 중 잠기지 않은 칸들을 그래프처럼 표기할 수 있겠다는 생각이 든다. 그러면서 방문여부를 따지면서 "전에 방문한 적 있네? 그럼 넌 안 봐"하면서 따지니까 굳이 따지자면 내가 한 방식은 DFS인 듯.

state?

: 리액트에서 데이터를 다룰 때 사용하는 것으로, props가 부모 컴포넌트에서 자식 컴포넌트로 값을 전달할 때 사용하는 것이었다면 state는 컴포넌트 자기 자신이 갖는 값을 의미한다. props의 주인은 부모이지만 state의 주인은 나! 인 느낌.

이 state의 값이 바뀔 때마다 얘를 갖고 있는 컴포넌트들이 새로 렌더링되며, state는 다음과 같이 만들 수 있다.

import { useState } from 'React';

function Component(){
	const [num, setNum] = useState(1);
    
	return(
    	<>
        </>
	)
}

export default Component

Component란 컴포넌트에서 num이란 이름의 state를 만든 모습이다. 보통 이렇게 Destrucrturing 문법으로 작성한다. 초기엔 useState를 통해 초깃값을 할당하는데 파라미터로 준 값이 초깃값이 된다. setNum은 setter함수라고 부르며 보통 state이름 앞에 set을 붙이고 camel case로 명명한다. state를 변경하는 것은 기존에 하던 것처럼 num = 5 이런 식으로 하면 안되고, 이 setter함수를 이용해야 한다. 예를 들어 setNum(5)를 해야 num이란 state가 5로 바뀐다. 

참조형 state?

js를 공부하다보면 참조형 변수라는 걸 만나게 된다. 기본형 변수는 변수에 값을 그대로 할당하는 반면 참조형 변수는 값의 주소를 할당한다는 점(즉 참조한다)에 차이가 있다. 참조형의 예로는 객체, 배열 등이 있다.

예를 들어 let a = 1; 을 하면 a라는 변수를 위한 공간이 메모리의 100번지에 마련되고, 100번지에 해당하는 공간에 1이란 값이 들어간다. 즉 값이 그대로 할당되는 것. 그러나 let b = [1, 2, 3]을 하면 b라는 변수를 위한 공간이 메모리의 101번지에 마련되지만 이 101번지에 해당하는 공간에 [1, 2, 3]이 아니라 메모리 어딘가에 만들어둔 [1, 2, 3]의 주소가 할당되는 것이다.

즉 js에선

let b = [1, 2, 3];
let c = b;
c[2] = 5;

console.log(b);
console.log(c);

출력되는 두 결과가 [1, 2, 5]로 같다. 

암튼, 리액트도 js를 기반으로 만들어진 놈이니 state를 다룰 때 state를 배열같은 걸로 해준다면, 참조형을 다루는 것이므로 예기지 못한 상황에 직면할 수 있다.  

다음과 같은 state를 만들었는데, 배열을 사용하는 놈이라고 하자.

const [list, setList] = useState([]);

이 때 다음 코드를 실행한 결과는 무엇이 될까?

list.push(5)
setList(list)

당연히 이 코드를 작성한 사람이 원한 것은 list에 5를 추가하는 것인데, setter함수로만 list를 조작할 수 있으니 push를 해주고 setList를 통해 list를 다시 설정해주는 것. 그러나 이렇게 하면 list state에는 아무런 변화가 없다..!

list는 배열이니까 주소를 갖고 있는데, push하던 뭘하던 주소엔 변화가 없으니까 리액트는 상태가 바뀌었다고 판단하지 않는 것.

그래서 참조형 변수를 state로 활용할 때 state를 변경하고 싶다면 새로운 참조형 변수를 만들어야 한다. 위와 같은 상황에서 가장 쉬운 방법은 Spread문법을 활용하는 것.

setList([...list, 5]);

※ spread문법

펼치다 라는 뜻을 갖는 문법.

let a = [1, 2, 3, 4];가 있다고 하자. a는 배열이다. 그럼 a를 펼치면 뭐가 되는가? 1, 2, 3, 4가 된다.

...은 그런 '펼치는' 역할을 해준다.

list라는 배열이 있고 [1, 2, 3, 4]일 때, 여기에 5를 push한 새 배열을 만들고 싶다. 그러면 [...list, 5]를 해주면 된다. list를 펼친 1, 2, 3, 4가 그대로 ...list에 들어간다고 생각하면 됨.

객체에서도 spread문법을 활용가능하다. 다음처럼. 얘도 똑같~~이 펼치다 라는 뜻에 주목해서 보면 됨.

const obj1 = {
    name : "JSH",
    age : 24
}

const obj2 = {
   ...obj1
   gender : "man"
}

// obj2는 name, age, gender프로퍼티를 가지며 value는 각각 "JSH", 24, "man"

props에 대해 정리해보자.

JSX문법에서 컴포넌트 작성 시 컴포넌트에 지정한 속성들을 props라 부른다. properties의 약자이며, 컴포넌트에 속성을 지정해주면 얘네들이 하나의 객체로 모여서 컴포넌트를 지정한 함수의 첫 번째 파라미터로 전달된다! 이 때 파라미터 이름은 통상 props로 해주는 게 깔끔. 이 때 props로 전달하는 것은 함수도 가능하다.

ex)

import React from 'react';
import Jofe from './jofe';

function App(){
    const func = function(){
        alert("Hi!");
    }
    return (
        <>
            <Jofe name="lje" age={23} func={func}/>
        </>
    );
}

export default App;

이렇게 App.js에서 Jofe라는 컴포넌트를 사용하는데 이런 식으로 props들을 Jofe컴포넌트로 전달가능하며, 이 녀석들은 다음과 같은 형태 즉 객체의 형태로 묶여서 전달됨.

{
    name : "lge",
    age : 23,
    func : func
}

그럼 여기서 children이란 걸 알아본다. props에서 특별취급하는 prop으로, JSX 문법에서 컴포넌트 작성 시 컴포넌트를 단일 태그가 아닌 여는태그 + 닫는태그의 형태로 작성하면, 이 태그 사이에 작성된 코드가 자동으로 아무것도 해주지 않아도 children이란 값에 담겨 컴포넌트로 전달된다.

import React from 'react';
import Jofe from './jofe';

function App(){
    return (
        <>
            <Jofe name="lje" age={23}>안녕안녕children</Jofe>
        </>
    );
}

export default App;

즉 여기선  안녕안녕children이란 문자열이 chidren에 담겨 Jofe컴포넌트에 전달된다. children이란 값에 담겨 전달되니 Jofe컴포넌트를 지정한 함수에선 children이란 이름으로 접근해 사용가능.

import React from 'react';

function Jofe({name, age, children}){
    return (
        <>
            <p>my name is {name} and age = {age}, children = {children}</p>
        </>
    );
}

export default Jofe;

그럼 children을 쓰면 뭐가 좋은가?

1. 화면에 보여질 모습을 좀 더 직관적인 코드로 쓰고자 할 때 활용 가능

2. 컴포넌트 안에 컴포넌트 작성 또는 컴포넌트 안에 복잡한 태그들 작성 가능. children을 쓸려면 단일 태그로 컴포넌트를 작성하는 게 아니라 여는 태그 + 닫는 태그로 컴포넌트를 작성하게 되므로!