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이벤트로 등록해줬다. 실제로 저 글을 클릭하면 다음과 같이 알림창이 뜬다.

jsx문법으로 작성된 코드를 javascript변수에 담아줄 수도 있다. 예를 들면, 

import ReactDOM from 'react-dom';

const element = <h1>hello, my name is JSH</h1>;

ReactDOM.render(
  element, document.getElementById('root')
);

이렇게 할 수 있다는 것. element를 콘솔에 찍어보면(console.log를 활용해서) 자바스크립트 객체라고 나오며, 이때 이 element를 react element라고 한다. 공식 문서의 내용에 따르면 react element는 react의 가장 작은 단위이며, 화면에 표시되는 내용이 되고, 컴포넌트를 구성하는 요소가 된다. 또한 이 react element를 함수 형태로 작성하면 jsx문법을 쓸 때 custom한 태그처럼 쓸 수도 있다. 예를 들면,

import ReactDOM from 'react-dom';

function func(){
  return <h1>hello, my name is JSH</h1>;
}

const element = (
  <>
    <func />
    <func />
  </>
)

ReactDOM.render(
  element, document.getElementById('root')
);

이렇게 쓸 수도 있다는 말. <func />는 func()가 리턴하는 녀석이 된다. 이때, 이 코드에서 func와 같은 함수를 컴포넌트라고 부른다! 리액트를 앞으로 공부하면서 이렇게 react element 또는 이들의 묶음을 컴포넌트로 만들어서 활용하는 일들이 많다.

 

이를 활용한다면, index.js가 아니라 다른 데서 컴포넌트들을 만들고 이를 index.js에서 import하여 사용할 수도 있다. 아니면 A라는 컴포넌트를 작성할 때 B라는 컴포넌트를 import해서 A에 사용하는 등 활용법은 무궁무진하다. 그 샘플을 예로 들어보자.

 

index.js가 있는 위치 즉 src폴더에 jofe.js라는 javascript파일을 만들고 다음과 같이 Jofe라는 컴포넌트를 만들었다.

function Jofe(){
    return (
        <>
            <h1>jofe component</h1>
            <p>hello, i am studying react</p>
        </>
    );
}

export default Jofe;

참고로 컴포넌트 이름은 항상 첫글자는 대문자로 시작해야 한다고 함. 그렇게 정했다네요.

마지막 줄에선 다른 데서 이 컴포넌트를 쓸 수 있도록 export.

그럼 이 Jofe라는 컴포넌트를 index.js에서 다음과 같이 활용 가능하다.

import ReactDOM from 'react-dom';
import Jofe from './jofe'

ReactDOM.render(
  <Jofe/>, document.getElementById('root')
);

터미널에 npm start를 입력해서 나오는 모습을 보면,

이렇게 잘 나온 것을 확인가능하다.

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

 

1167번: 트리의 지름

트리가 입력으로 주어진다. 먼저 첫 번째 줄에서는 트리의 정점의 개수 V가 주어지고 (2 ≤ V ≤ 100,000)둘째 줄부터 V개의 줄에 걸쳐 간선의 정보가 다음과 같이 주어진다. 정점 번호는 1부터 V까지

www.acmicpc.net

문제

트리의 지름이란, 트리에서 임의의 두 점 사이의 거리 중 가장 긴 것을 말한다. 트리의 지름을 구하는 프로그램을 작성하시오.

입력

트리가 입력으로 주어진다. 먼저 첫 번째 줄에서는 트리의 정점의 개수 V가 주어지고 (2 ≤ V ≤ 100,000)둘째 줄부터 V개의 줄에 걸쳐 간선의 정보가 다음과 같이 주어진다. 정점 번호는 1부터 V까지 매겨져 있다.

먼저 정점 번호가 주어지고, 이어서 연결된 간선의 정보를 의미하는 정수가 두 개씩 주어지는데, 하나는 정점번호, 다른 하나는 그 정점까지의 거리이다. 예를 들어 네 번째 줄의 경우 정점 3은 정점 1과 거리가 2인 간선으로 연결되어 있고, 정점 4와는 거리가 3인 간선으로 연결되어 있는 것을 보여준다. 각 줄의 마지막에는 -1이 입력으로 주어진다. 주어지는 거리는 모두 10,000 이하의 자연수이다.

출력

첫째 줄에 트리의 지름을 출력한다.

예제 입력 1 

5

1 3 2 -1

2 4 4 -1

3 1 2 4 3 -1

4 2 4 3 3 5 6 -1

5 4 6 -1

예제 출력 1 

11


 우선 결론적으로, 트리의 지름에 대해 알아야 풀 수 있는 문제다.

 처음에는 1을 루트노드로 잡고 DFS를 돌려서 가장 먼 거리의 노드를 구하면 그 노드까지의 거리가 트리의 지름이겠다 싶었는데, 풀다보니 "도대체 어떤 노드를 루트노드로 해줘야 가장 먼 거리의 노드까지의 거리가 트리의 지름이 될 것인가?"라는 문제에 봉착했다. 그러다가 임의의 노드(x) 하나를 루트노드로 잡고 거기서 가장 먼 거리의 노드를 구한 후, 구한 노드를 루트 노드로 잡고 거기서 다시 먼 노드를 구했을 때 구한 노드가 바로 전에 돌렸던 DFS에서의 루트노드라면 그 거리가 최장거리이지 않을까라는 생각을 하게 됐다. 왜냐하면 어쨌든 최장거리가 될 수 있는 후보들은 끝 노드와 끝 노드간의 거리들이기 때문이다. A가 만약 끝점이고, 여기서 가장 먼 거리의 노드가 B일 때 B에서 가장 먼 끝점도 A면 A와 B사이의 거리가 최장거리가 된다는 것. 근데 만약 B에서 가장 먼 거리의 노드가 A가 아니라면 A가 끝점이 아니거나, A까지의 거리보다 더 먼 거리를 가지는 끝점이 있거나 둘 중 하나가 되는 것이다.

 

 그럼 처음에 내 맘대로 루트노드를 1로 잡고 DFS를 돌려서 가장 먼 거리의 노드를 찾고, 다시 그 노드를 루트노드로 잡고 DFS를 돌려서 찾은 노드가 전에 돌렸던 DFS의 루트노드와 같다면, 그 때 측정한 거리가 루트의 지름이다!는 것을 알 수 있는데, 이렇게 연속된 두 번의 DFS결과를 비교하며 트리의 지름을 찾는 방식은 비효율적일것 같았다. 막말로 DFS를 몇 번 돌리게 될지도 모르는건데..그래서 그냥 루트의 지름에 대해서 공부했다.

 

참고한 링크 : https://blog.myungwoo.kr/112

 

트리의 지름 구하기

트리에서 지름이란, 가장 먼 두 정점 사이의 거리 혹은 가장 먼 두 정점을 연결하는 경로를 의미한다. 선형 시간안에 트리에서 지름을 구하는 방법은 다음과 같다: 1. 트리에서 임의의 정점 $x$를

blog.myungwoo.kr

 

요악하자면, 처음에 임의의 노드 하나를 루트노드로 잡고 가장 먼 거리의 노드를 찾은 다음, 그 녀석을 다시 루트노드로 잡고 가장 먼 거리의 노드를 찾으면 그 노드와의 거리가 트리의 지름이란 말이다.

 

암튼 뭐..그래서 코드는 다음과 같다.

import sys
sys.setrecursionlimit(10**6) # RecursionError 방지

V = int(sys.stdin.readline())
Tree = [[] for i in range(V + 1)]

for i in range(V):
    c = list(map(int, sys.stdin.readline().split()))
    for j in range(1, len(c) - 1, 2):
        Tree[c[0]].append([c[j], c[j + 1]])  # 각 노드에 연결된 노드와 간선의 길이 표현


def DFS(Tree, start_node, distance):
    for node, dis in Tree[start_node]:
        if not distance[node]:               # node까지 가는 거리가 0이라면 (기록되지 않았다면)
            distance[node] = distance[start_node] + dis  # node까지 가는 거리 기록
            DFS(Tree, node, distance)

distance = [0 for i in range(V + 1)]
DFS(Tree, 1, distance)
distance[1] = 0   # distance는 start_node에서 각 노드까지의 거리를 저장하는 리스트이므로, 자기 자신에서 출발해 자기 자신까지의 거리는 0으로 해야 함.

start_node, max_distance = -1, -1
        # 무지성으로 max(distance)를 하면 가장 먼 거리는 알 수 있는데, 어떤 노드까지의 거리
        # 인지는 모르게 돼서, 이렇게 선형탐색같은 방법으로 가장 먼 거리를 가지는 노드를 찾음
                                       
for i in range(1, V + 1):
    if distance[i] > max_distance:
        max_distance = distance[i]
        start_node = i

distance = [0 for i in range(V + 1)]
DFS(Tree, start_node, distance)
distance[start_node] = 0                  # distance는 start_node에서 각 노드까지의 거리를 저장하는 리스트이므로, 자기 자신에서 출발해 자기 자신까지의 거리는 0으로 해야 함.
print(max(distance))

 이걸 풀면서 배운 것은 배열을 통한 트리의 표현방법과, 재귀를 통한 DFS방법.

트리의 지름도 조만간 정리해서 올려야지.

분리집합(Disjoint Set)이란 서로 중복되지 않는 부분집합들로 나뉜 원소들에 대한 정보를 다루는 자료구조이다. Union-Find 알고리즘은 이 자료구조를 활용하는 대표적인 그래프 알고리즘 중 하나로, '합집합을 찾는다'라는 의미를 가진다. 디테일하게 들어가면 원소 x, y를 고른 다음 x가 속한 집합과 y가 속한 집합이 같은지 판별하는 알고리즘안대, 이는 여러 노드가 존재할 때 내가 선택한 임의의 두 노드가 서로 같은 그래프에 속하는지 판별한다는 것과 같은 개념으로 생각할 수 있다.

 

그냥 내가 이해한대로 쉽게(나름대로) 설명하자면, Union-Find알고리즘과 분리집합은 집합을 표현하는 하나의 형태이다. 1부터 5까지의 원소들이 있고 이들이 각각 집합의 형태를 이루고 있다고 하자. 즉,

 

{1}, {2}, {3}, {4}, {5}

 

이렇게 있는 것이다. 근데 이를 표를 통해 다음과 같이 표현할 수 있다.

  1 2 3 4 5
리더 1 2 3 4 5

{1}의 입장에서 자기가 속한 집합의 리더는 자기 자신(1)이고, {2}나 다른 애들 입장에서도 마찬가지다. 즉 표를 통해 자신이 속한 집합의 리더를 나타내준것! 근데 여기서 {1}과 {2}가 만나서 합집합 {1, 2}를 만들어냈다고 하자. 1과 2가 같은 집합의 원소로 구성된 것이다. 현재 존재하는 집합들은

 

{1, 2}, {3}, {4}, {5}

 

인 것이다. 이는 방금과 같은 표를 통해 어떻게 표현할 수 있을까?

  1 2 3 4 5
리더 1 1 3 4 5

다른 건 변함없고 2만 변화가 생겼다. 자신이 속한 그룹의 리더가 1이 된 것! 사실 뭐 2를 리더로 할 수도 있지만..집합을 이루는 원소 중 가장 작은 놈을 리더로 뽑는 것이다. 쉽게 생각해서 2는 1이 이끄는 집합의 멤버가 된 것이라고 생각해도 된다. 만약 다른 애들도 서로 합치고 지지고 볶고 해서 집합들이 다음과 같이 됐다면?

 

{1, 2}, {3, 4, 5}

 

표는 다음과 같아질 것이다.

  1 2 3 4 5
리더 1 1 3 3 3

그럼 생각해보자. 내가 임의로 두 원소를 뽑았는데 그 놈이 2랑 4다. 이들이 각각 속한 집합은 같은가?

표를 통해서 다르다는 것을 알 수 있다. 왜 Why? 2는 1이 이끄는 집합에 속해있고, 4는 3이 이끄는 집합에 속해있기 때문이다. 서로가 속한 집합의 리더가 다르기 때문에 이들이 속한 집합은 서로 다른 집합이다라고 말할 수 있는 것이다. 이것이 Union-Find알고리즘이다. 

 

근데 Union Find알고리즘은 여러 노드가 존재할 때 두 노드를 선택해서 이 두 녀석이 같은 그래프에 속하는지 판별하는 것으로도 이해할 수 있다고 했다. 간단하다. 단지 집합으로 표현하던 걸 그래프로 나타낼 때 Union Find가 저렇게 표현될 뿐이다. 1~5까지의 각 원소들이 집합의 형태를 이루고 있는 상태를, 1~5까지의 노드들이 서로 연결되지 않고 존재하는 상태라고 이해하면 된다. 그리고 집합들이 합쳐지는 것은 노드들 간에 연결선이 생겨서 연결되는 것으로 생각하면 된다. 따라서 내가 고른 임의의 두 노드가 서로 같은 그래프에 존재하는지 확인하는 것은 각각의 root노드들을 확인해서 같으면 같은 그래프 상에 존재하는 것이다! ...사실 이 부분은 글로만 써서 이해가 잘 안 될 수도 있으니 공부할 때 참고한 나동빈 님의 영상을 링크로 걸어두겠다.

 

https://www.youtube.com/watch?v=AMByrd53PHM 


그럼 Union Find를 파이썬으로 구현해보자.

parant = [i for i in range(n + 1)]

def getParant(x):         # x의 부모를 리턴하는 함수
    if parant[x] == x:    # x의 부모가 자기자신이라면 x를 그대로 리턴
        return x        
    parant[x] = getParant(parant[x])  # x의 부모가 자기자신이 아님 -> 재귀호출로 x의 부모 재설정
    return parant[x]                  # 최종적으론 x의 부모 리턴
    
def union(x, y):        # x가 속한 집합과 y가 속한 집합 합치기 - 가장 부모을 비교해 더 작은 쪽으로 합침
    x, y = getParant(x), getParant(y)
    if x < y:           # x가 더 작으니까 y의 부모를 x로
        parant[y] = x
    elif x > y:         # y가 더 작으니까 x의 부모를 y로
        parant[x] = y

def hasSameParant(x, y):         # x, y가 같은 부모를 같는지 즉 같은 집합에 속해있는지
    x, y = getParant(x), getParant(y)
    if x == y:
        return "YES"
    else:
        return "NO"

리더로 표현하던 것을 부모로 표현하는 것에만 차이가 있다. getParant함수가 이 알고리즘의 핵심으로 자신의 부모가 자기자신이 아니라면 재귀호출을 통해 자신의 부모를 최상단 노드, 즉 집단 내에서 가장 작은 놈으로 설정해준다.  이를 통해 백준 사이트에서 대표적으로 다음과 같은 문제를 풀 수 있다.

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

 

1717번: 집합의 표현

첫째 줄에 n(1 ≤ n ≤ 1,000,000), m(1 ≤ m ≤ 100,000)이 주어진다. m은 입력으로 주어지는 연산의 개수이다. 다음 m개의 줄에는 각각의 연산이 주어진다. 합집합은 0 a b의 형태로 입력이 주어진다. 이는

www.acmicpc.net

 

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

 

1806번: 부분합

첫째 줄에 N (10 ≤ N < 100,000)과 S (0 < S ≤ 100,000,000)가 주어진다. 둘째 줄에는 수열이 주어진다. 수열의 각 원소는 공백으로 구분되어져 있으며, 10,000이하의 자연수이다.

www.acmicpc.net

문제

10,000 이하의 자연수로 이루어진 길이 N짜리 수열이 주어진다. 이 수열에서 연속된 수들의 부분합 중에 그 합이 S 이상이 되는 것 중, 가장 짧은 것의 길이를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 N (10 ≤ N < 100,000)과 S (0 < S ≤ 100,000,000)가 주어진다. 둘째 줄에는 수열이 주어진다. 수열의 각 원소는 공백으로 구분되어져 있으며, 10,000이하의 자연수이다.

출력

첫째 줄에 구하고자 하는 최소의 길이를 출력한다. 만일 그러한 합을 만드는 것이 불가능하다면 0을 출력하면 된다.

예제 입력 1 복사

10

15 5 1 3 5 10 7 4 9 2 8

예제 출력 1 복사

2

 


[접근방식]

 

1. 배열의 첫 번째 원소부터 시작해 합이 S 이상이 되는 가장 짧은 구간의 길이를 구한다.

2. 배열의 두 번째 원소부터 시작해 합이 S 이상이 되는 가장 짧은 구간의 길이를 구한다.

3. 배열의 세 번째 원소부터 시작해 합이 S 이상이 되는 가장 짧은 구간의 길이를 구한다.

...이렇게 해서 각 단계에서 구한 길이 중 가장 짧은 놈을 고른다.

 

import sys

N, S = map(int, sys.stdin.readline().split())
length = []

arr = list(map(int, sys.stdin.readline().split()))

for i in range(len(arr)):
    j, sum = i + 1, arr[i]

    while(sum < S and j < len(arr)):
            sum += arr[j]
            j += 1
    if sum >= S:
        length.append(j - i)

if length:
    print(min(length))
else:
    print(0)

근데 위 코드는 시간초과가 발생한다. 왜일까?

우선 코드를 보면 난 for문에서 i를 시작점으로 설정하며 각 구간들을 구하는데, j라는 변수가 구간의 끝점역할을 한다. 따라서 구하는 구간의 합이 S이상이 되는 순간 구간의 길이인 j - i를 length리스트에 더하고 마지막에 min메소드로 가장 짧은 길이를 출력하면 그것이 정답이다. 근데 시간초과가 뜨는 이유는 다름아닌 j, sum와 관련되어 있다.

바로 매 순간 새로 측정을 시작할 때마다(즉 시작점 i가 바뀔 때마다) j를 i + 1로 세팅한 뒤, j를 늘려가면서 측정하기 때문! 이것이 시간을 잡아먹는다. 마찬가지로 sum을 매 측정마다 새로 설정해주는 것도 시간을 잡아먹는다. 왜 Why?

어떤 단계에서 합이 S이상이 되는 구간을 구했다고 할 때, 이 구간의 끝점이 있다.

다음 단계에서 합이 S이상이 되는 구간을 또 구할텐데, 이 때 새로 구하게 되는 구간의 끝점은 이전 단계에서 구한 구간의 끝점보다 같거나 클 수밖에 없기 때문! 따라서 매 측정의 단계에서 사용한 j와 sum을 그대로 재활용?하는 느낌으로 써주는 식으로 코드를 수정했다.

import sys

N, S = map(int, sys.stdin.readline().split())
length = []

arr = list(map(int, sys.stdin.readline().split()))
sum_arr, j = arr[0], 1

for i in range(len(arr)):           
    while(sum_arr < S and j < len(arr)):   
        sum_arr += arr[j]             
        j += 1
    if sum_arr >= S:                       
        length.append(j - i)
    sum_arr -= arr[i]                     

if length:                                
    print(min(length))
else:                                      
    print(0)

이런 방식?을 투포인터 알고리즘 이라 부르는 것 같다.

공부해봐야겠다..

+ Recent posts