Ray`s Tech Lab

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

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을 쓸려면 단일 태그로 컴포넌트를 작성하는 게 아니라 여는 태그 + 닫는 태그로 컴포넌트를 작성하게 되므로!

props : 컴포넌트가 어떤 값을 전달받아 사용해야 할 때 이용된다. 컴포넌트에 속성들을 지정하는 형태로 전달하며,  객체 형태로 전달된다! 무슨 말인지는 예시 코드를 보자.

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

function App(){
    return (
        <>
            <Jofe />
        </>
    );
}

export default App;

이런 코드가 있다고 하자. App에서 Jofe라는 컴포넌트를 사용하는 모습이다. 이 때 Jofe컴포넌트에 "jsh"를 name이란 이름으로 전달하고 싶다면?

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

function App(){
    return (
        <>
            <Jofe name="jsh"/>
        </>
    );
}

export default App;

이렇게 태그의 속성을 지정하는 형태로 컴포넌트에 전달할 수 있다는 얘기다. 객체 형태로 전달된다는 것은, {name : "jsh"}이런 형태로 전달된다는 말이고.

Jofe 컴포넌트에선 이를 props라는 파라미터 이름으로 전달받아 사용가능하다. prrops말고 다른 이름도 쓸 수 있지만 다들 의미를 알기 쉽게 할려고 props라는 이름으로 쓴다고 한다.

import React from 'react';

function Jofe(props){
    return (
        <>
            <p>my name is {props.name}</p>
        </>
    );
}

export default Jofe;

- Props를 여러 개 전달하기

다음과 같이 여러 개의 props를 전달하는 것도 물론 가능하다.

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

function App(){
    return (
        <>
            <Jofe name="jsh" age={24}/>
        </>
    );
}

export default App;

props를 전달할 때 자바스크립트 숫자를 전달하기 위해선 {}로 감싸서 해야 한다고 한다. 문자열같은 건 ""로 하면 되고. 또한 Jofe 컴포넌트에선 props라는 이름으로 파라미터를 받는 게 아니라 다음과 같은 형태로 받을 수도 있다.

import React from 'react';

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

export default Jofe;

이렇게 하면 매번 props.name이나 props.age 등 번거롭게 props라는 이름을 달아줄 필요가 없다. 또한 props를 전달받지 않는 상황에 대비해 디폴트 props를 지정가능하다.

import React from 'react';

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

export default Jofe;

다음과 같은 방법으로도 디폴트 props를 지정 가능.

import React from 'react';

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

Jofe.defaultProps = {
    name: 'jsh',
    age: 24
}

export default Jofe;

- 함수도 전달할 수 있다

함수도 props로 전달가능하다. 

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;

alert를 이용해 hi라는 알림창을 띄우는 함수 func를 Jofe컴포넌트에 전달하는 모습. Jofe컴포넌트에선 다음과 같이 활용가능하다.

import React from 'react';

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

export default Jofe;

p태그의 onclick이벤트로 등록해줬다. 실제로 저 글을 클릭하면 다음과 같이 알림창이 뜬다.