알고리즘49 서로소 집합 만들기 서로소 집합 서로소 집합이란, 중복포함된 원소가 없는 집합이다. 서로소 집합은 교집합이 없고, 집합에 속한 하나의 특정 멤버를 통해 각 집합들을 구분한다. 위그림에서 첫번째 A B는 서로소 관계가 아니고, 두번째 A B는 서로소 관계이다. 서로소 집합을 표현하는 방법에는 연결리스트로 표현하는 방법, 트리로 표현하는 방법 두가지가 있다. 서로소 집합 연산 서로소 집합 연산은 아래의 세 함수를 이용해서 진행된다. Make-Set(x) : 집합생성(x원소로 갖는) Find-Set(x) : x가 속한 집합 찾기(대표자 return하기) Union(x,y) : x,y원소를 하나의 집합으로 만들기 서로소집합 x,y 만 union 해줘야됨(Findset 사용해서 보면됨) 대표자끼리 합친다. Make-Set 루트가 대.. 2022. 9. 20. [백준 Java] 주사위 굴리기 2 문제 https://www.acmicpc.net/problem/23288 23288번: 주사위 굴리기 2 크기가 N×M인 지도가 존재한다. 지도의 오른쪽은 동쪽, 위쪽은 북쪽이다. 지도의 좌표는 (r, c)로 나타내며, r는 북쪽으로부터 떨어진 칸의 개수, c는 서쪽으로부터 떨어진 칸의 개수이다. 가장 왼 www.acmicpc.net 풀이방법 알고리즘을 생각해 내기가 빡세다기보단 구현을 하는게 쉽지 않은 문제였다. bfs는 그냥 같은 숫자를 세어주면 되었기 때문에 구현이 복잡하진 않았다. 문제는 주사위의 방향을 만들어주고, 이에 따라 주사위의 전개도를 바꿔주는 것이 좀 복잡했던 문제였다. 주사위 방향을 정하는 코드는 다음과 같다. 시계방향으로 돌릴때는 인덱스에 +1을 더해주었고, 반시계 방향일 때에는 -.. 2022. 9. 19. [백준 JAVA] N과 M(1~6) 재귀함수의 개념을 잡기 위해서 백준의 N과 M 문제를 1~6까지 풀어보았다. 재귀 개념이 부족하다면 아래 문제들을 풀어보는 것을 추천한다. 문제 https://www.acmicpc.net/problem/15649 15649번: N과 M (1) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net https://www.acmicpc.net/problem/15650 15650번: N과 M (2) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사.. 2022. 9. 18. [백준 JAVA] 10826 피보나치 수4 문제 https://www.acmicpc.net/problem/10826 10826번: 피보나치 수 4 피보나치 수는 0과 1로 시작한다. 0번째 피보나치 수는 0이고, 1번째 피보나치 수는 1이다. 그 다음 2번째 부터는 바로 앞 두 피보나치 수의 합이 된다. 이를 식으로 써보면 Fn = Fn-1 + Fn-2 (n ≥ 2)가 www.acmicpc.net 풀이방법 간단한 피보나치 수 문제 같지만, 일반적인 피보나치 수처럼 문제를 풀면, ArrayIndexOutOfBounds 런타임 에러가 나는 문제였다. 입력값을 보면 n은 10,000까지 가기 때문이다. 이 문제를 해결하기 위해서는 BigInteger를 사용해야 했다. Int는 메모리 크기는 4byte로 표현할 수 있는 범위는 -2,147,483,648.. 2022. 9. 18. 이전 1 2 3 4 5 6 ··· 13 다음
