hello world!
"HELLO WORLD"
블로그 시작
๑•̀ㅂ•́)و✧
ASCII 코드 테이블
출처 위키백과
이 블로그의 인기 게시물
[백준] 1316번: 그룹 단어 체커
문제 https://www.acmicpc.net/problem/1316 풀이 현재 문자(i)와 다음 문자(i+1)을 비교하여 둘이 같을때는 신경쓰지 않고 달라질때 현재 문자(i)가 이미 방문했던 문자인지 알파벳 개수 만큼 있는 check배열을 확인하여 이미 방문했던 문자였으면(true이면) 현재 문자(i)는 떨어져 있는 문자이므로 그룹 문자가 아니다. 결과 코드 https://github.com/ziwonii24/Algorithm/blob/master/Baekjoon/1316.cpp
[백준] 1717번: 집합의 표현
문제 https://www.acmicpc.net/problem/1717 풀이 이 문제는 disjoint-set문제로서 union-find로 풀었다. disjoint-set(서로소 집합) : 교집합이 공집합인 집합 Union(a, b) : a가 속한 집합과 b가 속한 집합을 합집합 Find(a) : a가 속한 집합의 번호를 반환 i 1 2 3 4 5 6 7 arr[i] 1 2 3 4 5 6 7 입력 n = 7일때, 서로소 집합의 초기값은 위의 표와 같이 되어있다. Find(1)을 하면 arr[1]==1이므로 1을 return한다. 만약에 같지 않을 경우, 재귀적으로 원소의 부모를 쫓아 올라간다. Union(1, 3)을 하면 먼저 Find를 각각한다. 그러면 pa=1, pb=3이 된다. 둘은 다른 그룹에 있기 때문에 arr[1]=3으로 그룹 번호를 업데이트 해준다. i 1 2 3 4 5 6 7 arr[i] 3 2 3 4 5 6 7 이런 식으로 쭉 진행한다. union-find를 이용하여 kruskal algorithm으로 mst찾는데 쓰인다. 결과 Union연산에서 if(pa != pb) 면 그룹번호를 갱신하도록 조건이 있는데 시간을 단축시키기 위함이다. 이 문제에서는 없어도 맞았다고 한다! 코드 https://github.com/ziwonii24/Algorithm/blob/master/Baekjoon/1...
댓글
댓글 쓰기