알고리즘/백준 알고리즘

[백준 1717] 집합의 표현

글에 개요 백준 알고리즘 1717번 "집합의 표현" 문제입니다.앞서 다루었던, 아래 참고할 글 1번에 정리한 내용을 보시면 쉽게 푸실 수 있는 문제입니다.유니온 파인드 (Union-Find)를 정리한 글 내용을 꼭 보시길 추천드립니다!!!!이 후 이 문제를 통해 확장할 수 있는 알고리즘이 많기 때문에 더더욱 익히셨으면 좋겠습니다. [백준 1717] 줄 세우기: https://www.acmicpc.net/problem/1717 참고할 글http://brenden.tistory.com/33 ([알고리즘] 유니온 파인드(Union-Find) 정리글)핵심 내용초기에 {0}, {1}, {2}, ... {n} 이 각각 n+1개의 집합을 이루고 있다.여기에 합집합 연산과, 두 원소가 같은 집합에 포함되어 있는지를 확..

2018. 4. 24. 18:23

알고리즘/알고리즘 개념

[알고리즘] 유니온 파인드 (Union-Find)

유니온 파인드(Union-Find) ① 유니온 파인드란? ▷ 대표적 그래프 알고리즘으로 '합집합 찾기'라는 의미를 가지고 있습니다.▷ 상호 배타적 집합(Disjoint-set)이라고도 합니다.▷ 여러 노드가 존재할 때, 두 개의 노드를 선택해서, 현재 두 노드가 서로 같은 그래프에 속하는지 판별하는 알고리즘이다.▷ 2가지 연산으로 이루어져 있습니다. ▶ Find : x가 어떤 집합에 포함되어 있는지 찾는 연산 ▶ Union : x와 y가 포함되어 있는 집합을 합치는 연산 ② 그림으로 보는 Union-Find 위와 같이, 모두 연결되지 않고 각자 자기 자신만을 집합의 원소로 가지고 있을 때, 모든 값이 자기 자신을 가리키도록 만듭니다.i : 노드번호, P[i] : 부모 노드 번호 를 의미하며, 즉 자기 자..

2018. 4. 23. 18:10

알고리즘/백준 알고리즘

[백준 11729] 하노이 탑 이동 순서

글에 개요 백준 알고리즘 11729번 "하노이 탑 이동 순서" 문제입니다.재귀함수를 사용하는 대표적인 예로도 사용됩니다!!! 크게 두 가지 제약조건에 대해 고민하고 더 세분화하여 정의하는 부분이 중요합니다.두 번 세 번 반복하면 분명 도움이 될 것 같아요.저 또한 알고리즘 테스트에서 최근에 보게 되어 다시 상기하고자 풀어보았습니다.벌써 2번의 알고리즘 시험에서 보았기 때문에 여러분도 꼭 한 번 풀어보시고, 다른 방법이 없으실지도 고민하시면 좋을 것 같습니다. [백준 11729] 하노이 탑 이동 순서: https://www.acmicpc.net/problem/11729 참고할 글..핵심 내용제약조건 2가지원반은 한 번에 하나씩만 옮길 수 있다.옮기는 과정에서 작은 원반의 위에 큰 원반이 올려져서는 안된다...

2018. 4. 21. 17:36

알고리즘/백준 알고리즘

[백준 11052] 붕어빵 판매하기

글에 개요 백준 알고리즘 11052번 "붕어빵 판매하기" 문제입니다.이 문제는 DP(동적 계획법)을 활용하는 문제로 '1,2,3의 조합으로 나타내는 방법의 수' 뒤로 연습해보면 좋은 문제입니다.역시 손으로 어느 정도의 규칙이 발견된 후에 점화식을 세우는 것이 좋은 방법인 것 같습니다. 아마 동적 계획법에 사용되는 점화식의 활용에 익숙해지고, 이후 재귀함수로 구현할 때 Top-down, Bottom-up 방식해 질 때까지 최대한 꾸준히 풀어볼 생각입니다. [백준 11052] 붕어빵 판매하기: https://www.acmicpc.net/problem/11052 참고할 글[백준 9095] 1, 2, 3 더하기 : http://brenden.tistory.com/29[백준 10942] 팰린드롬? : http:/..

2018. 4. 20. 11:39

알고리즘/백준 알고리즘

[백준 9095] 1, 2, 3 더하기

글에 개요 백준 알고리즘 9095번 "1, 2, 3 더하기" 문제입니다.이 문제는 DP(동적 계획법)을 활용하는 문제로 팰린드롬에 이어 2번째 등장이네요.아마 동적 계획법에 사용되는 점화식의 활용에 익숙해지고, 이후 재귀함수로 구현할 때 Top-down, Bottom-up 방식해 질 때까지 최대한 꾸준히 풀어볼 생각입니다. [백준 9095] 1, 2, 3 더하기: https://www.acmicpc.net/problem/9095 참고할 글[백준 10942] 팰린드롬? : http://brenden.tistory.com/27핵심 내용정수 n을 1,2,3의 조합으로 나타내는 방법의 수를 구하는 문제입니다.D[i] = i를 1,2,3의 조합으로 나타내는 방법의 수D[i] = D[i-1] + D[i-2] + D..

2018. 4. 20. 11:12

알고리즘/백준 알고리즘

[백준 1509] 팰린드롬 분할

글에 개요 백준 알고리즘 1509번 "팰린드롬 분할" 문제입니다.이 문제는 앞 선 팰린드롬 문제 해결을 바탕으로 한 가지 IDEA만 추가해서 해결하는 것이 중요합니다. 팰린드롬 또한 대기업의 알고리즘 SW TEST에도 기본적으로 활용되기 때문에 꼭 풀어보는 것을 추천드립니다.혹시 어느 곳에서 나왔는지 궁금하신 분은 댓글로 남겨주시면 따로 알려드리겠습니다!! [백준 1509] 팰린드롬 분할: https://www.acmicpc.net/problem/1509 참고할 글[백준 10942] 팰린드롬?] : http://brenden.tistory.com/27핵심 내용 ▷ D[i] = i 번째 문자열까지를 팬린드롬 분할 했을 때, 분할의 최소 개수▷ D[i] = min(D[j-1]) + 1 (i~j는 팰린드롬) ..

2018. 4. 19. 20:18

알고리즘/백준 알고리즘

[백준 10942] 팰린드롬?

글에 개요 백준 알고리즘 10942번 "팰린드롬?" 문제입니다.이 문제는 팰린드롬이 무엇인지에 대해 알아 볼 수 있는 문제이며, DP를 활용해 시간 초과의 이슈를 해결하는 것이 중요합니다. 팰린드롬 또한 대기업의 알고리즘 SW TEST에도 기본적으로 활용되기 때문에 꼭 풀어보는 것을 추천드립니다.혹시 어느 곳에서 나왔는지 궁금하신 분은 댓글로 남겨주시면 따로 알려드리겠습니다!! [백준 10942] 팰린드롬?: https://www.acmicpc.net/problem/10942 참고 내용 팰린드롬 : 뒤집어서 읽어도 똑같이 읽히는 형태를 말합니다.1231 2 2 11 3 3 11 2 3 2 1csl~3 line에 있는 모든 숫자들은 팰린드롬이라고 말할 수 있는 것이죠!! [팰린드롬 구현 코드]1234567..

2018. 4. 19. 11:19