Ray`s Tech Lab

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

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

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

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

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

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

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

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

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

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

그럼 생각해보자. 내가 임의로 두 원소를 뽑았는데 그 놈이 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

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

문제

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)

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

공부해봐야겠다..

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

문제

민식이는 다음과 같은 폴리오미노 2개를 무한개만큼 가지고 있다. AAAA와 BB

이제 '.'와 'X'로 이루어진 보드판이 주어졌을 때, 민식이는 겹침없이 'X'를 모두 폴리오미노로 덮으려고 한다. 이때, '.'는 폴리오미노로 덮으면 안 된다.

폴리오미노로 모두 덮은 보드판을 출력하는 프로그램을 작성하시오.

입력

첫째 줄에 보드판이 주어진다. 보드판의 크기는 최대 500이다.

출력

첫째 줄에 사전순으로 가장 앞서는 답을 출력한다. 만약 덮을 수 없으면 -1을 출력한다.

예제 입력 1 복사

XXXXXX

예제 출력 1 복사

AAAABB

예제 입력 2 복사

XX.XX

예제 출력 2 복사

BB.BB

[내가 한 풀이]

boards = input().split('.')
answer = ''

for board in boards:
    if len(board) % 2 == 1:
        print(-1)
        break
    else:
        if len(board) >= 4:
            answer += 'AAAA' * (len(board) // 4)
        answer += 'BB' * ((len(board) % 4) // 2) + '.'
else:
    print(answer[:-1])

입력으로 받은 전체 보드판(?)을 split()메소드를 활용해 온점(.)을 기준으로 나눠서 리스트로 만든다.

이후 리스트에 대해 순회하는데, 나는 AAAA와 BB라는 폴리오미노만 갖고 있으므로 홀수칸짜리 보드판에 대해서는 폴리오미노를 덮을 수 없다. 이 경우는 2로 나눈 나머지가 1인 경우에 해당하며, 이땐 -1을 출력하고 break.

보드판이 짝수칸이라면 몇 칸인지에 관계없이 폴리오미노로 덮을 수 있는데, 2칸일 경우에만 처음부터 바로 BB를 채우고 2칸이 아니라면 그냥 무지성으로 AAAA만 신나게 깔아주다가 마지막에 2칸만큼 남으면 BB를 덮으면 된다. 어차피 if-else 이하의 코드는 순회한 보드가 짝수칸일테만 실행되므로, 4칸 이상일 때는 보드칸을 4로 나눈 몫만큼 AAAA를 덮어주고, 이후 나머지 칸에 대해 BB를 덮어준다. AAAA를 다 덮고 남은 칸은 len(board) % 4이다. 

마지막엔 출력할 차례. 순회하는 모든 보드판이 죄다 짝수칸이었다면 break문에 의해 비정상적으로 for문이 종료되지 않았으므로 마지막의 for-else문의 print가 실행된다. 이때 answer의 마지막은 온점(.)이므로 슬라이싱하여 그 전까지만 출력하면 정답이다. 

[더 쉬운 풀이]

board = input()
board = board.replace("XXXX", "AAAA")
board = board.replace("XX", "BB")
if 'X' in board:
    board = -1
print(board)

replace메소드를 활용해 처음엔 문자열 내에 등장하는 모든 XXXX를 AAAA로 바꾸고, 이후 다시 문자열 내에 등장하는 모든 XX를 BB로 바꿔주고, 마지막에 X가 남아있다면 -1을 출력하도록 한다.

replace메소드는 replace(old, new, count) 총 3개의 파라미터를 받으며 old는 현재 문자열에서 바꾸고 싶은 놈, new는 새로 바꿀 문자, count는 정수를 받으며 변경할 횟수를 의미한다. count는 optional로 입력하지 않으면 문자열 전체의 old를 new로 바꾼다.

사실 JSX는 실제로 실행될 때 javascript코드로 바뀌어서 실행된다. 그러면 당연히 JSX에 javascript코드를 넣을 수도 있다.

다음과 같은 코드가 있다고 하자.

import ReactDOM from 'react-dom';

ReactDOM.render(
  <>
    <h1>안녕 리액트!</h1>
  </>,
  document.getElementById('root')
);

여기서 리액트란 단어를 name이라는 javascript 변수로 바꾸려고 한다. 그러면

import ReactDOM from 'react-dom';

const name = "리액트";

ReactDOM.render(
  <>
    <h1>안녕 {name}!</h1>
  </>,
  document.getElementById('root')
);

이렇게 중괄호를 이용해 name이란 javascript변수를 JSX 문법에 사용가능하다. Django에서 템플릿 변수를 사용하는 것과 비슷.

사실 이 중괄호엔 변수 뿐만 아니라 javascript로 쓰인 표현식은 모두 사용가능하다. 예를 들어, 문자열의 문자들을 모두 대문자로 만드는 toUpperCase()메소드도 중괄호 안에서 사용가능하다.

import ReactDOM from 'react-dom';

const name = "reactplease";

ReactDOM.render(
  <>
    <h1>안녕 {name.toUpperCase()}!</h1>
  </>,
  document.getElementById('root')
);

React에선 JSX문법을 사용하므로, 이벤트 핸들러를 등록할 때 addEventListener보단 요소의 속성값으로 이벤트 핸들러를 등록할 때가 많다. 이렇게 특정 태그의 속성값으로도 중괄호를 활용해 javascript를 사용가능하다.

import ReactDOM from 'react-dom';

const name = "reactplease";
function func(){
  alert("s");
}

ReactDOM.render(
  <>
    <h1>안녕 {name.toUpperCase()}!</h1>
    <button onClick={func}>버튼</button>
  </>,
  document.getElementById('root')
);

참고로 중괄호안에서는 javascript 표현식만 사용가능하므로, if문, for문, 함수선언등과 같은 것은 할 수 없다.

JSX란, React.js에서 javascipt를 통해 HTML을 작성할 수 있는 javascript의 확장된 문법이다.

일반적인 HTML태그들과 똑같이 쓸 수 있고, id속성도 똑같이 줄 수 있는데 몇 가지 주의사항이 있다.

HTML태그의 class속성, for속성(label태그등에서) 을 줄 때는 각각 className, htmlFor로 써야 한다는 것이다. 이는 javascript내에서 이미 class, for라는 키워드가 존재하기 때문이다. 그리고

onclick과 같은 event handler를 줄 때도 onClick처럼 camel case로 적어줘야 한다! 두 번째 단어부터는 시작알파벳을 대문자로 적으면 된다는 것임.

두 번째 주의사항은, JXS문법으로 HTML을 작성할 때는 반드시 하나로 감싸진 태그를 작성해야 한다는 것이다. 예를 들어,

import ReactDOM from 'react-dom';

ReactDOM.render(
  <h1>안녕 리액트!</h1>
  <h2>안녕안녕 리액트</h2>,
  document.getElementById('root')
);

이런 식으로 쓰면 안 된다. vscode에서는 저렇게 쓰면 빨간 줄이 생기면서 오류라고 알려준다. JSX요소들은 반드시 하나로 감싸줘야 하기 때문! 이렇게 하면 해결할 수 있게 된다.

import ReactDOM from 'react-dom';

ReactDOM.render(
  <div>
    <h1>안녕 리액트!</h1>
    <h2>안녕안녕 리액트</h2>
  </div>,
  document.getElementById('root')
);

npm start를 하고 페이지 검사를 해주면, root div에게 div가 하나 더 생기고 그 밑에 h1, h2태그가 있는 구조를 확인할 수 있다. 근데 이렇게 div태그로 감싸주는 게 싫다면, React에서 제공하는 Fragment를 이용할 수 있다. 아래처럼 하면 된다.

import { Fragment } from 'react';
import ReactDOM from 'react-dom';

ReactDOM.render(
  <Fragment>
    <h1>안녕 리액트!</h1>
    <h2>안녕안녕 리액트</h2>
  </Fragment>,
  document.getElementById('root')
);

이렇게 하면 root div 밑에 div가 하나 생기고 그 밑에 h1, h2태그가 있는 게 아니라 root div 바로 밑에 h1, h2태그가 생긴다. 참고로 import 문을 굳이 쓴 다음에 Fragment를 할 필요 없고, 그냥 JSX입력할 때 Fragment자동완성되게 하면 알아서 import해준다. 참 편하다. 암튼 이렇게 Fragment를 잘 사용하면 불필요하게 div태그같은 게 생기는걸 방지할 수 있다. 

근데 솔직히 이렇게 맨날 Fragment써주는 것도 귀찮으니 다음과 같이 축약형으로 쓸 수 있다.

import ReactDOM from 'react-dom';

ReactDOM.render(
  <>
    <h1>안녕 리액트!</h1>
    <h2>안녕안녕 리액트</h2>
  </>,
  document.getElementById('root')
);