Algorithm
Coding Test(Union-Find, Disjoint-set)
유니온 파인드(Union-Find) Disjoint-set(서로소 집합, 분리 집합) 이라고도 하며 순수히 노드 간의 연결 관계를 파악할 때 유용하게 사용 무방향 그래프 내에서의 사이클을 판별할 때 사용(서로의 Root Node가 같다면 사이클 발생) 방향 그래프에서 사이클을 판별할 땐 DFS(DFS타다가 자기자신으로 돌아오면 사이클 발생) 0) Make - 간선이 아직 연결되어있지 않은 그래프에서 모든 값이 자기 자신을 가르키게한다 = > 자기 자신이 부모노드가된다 for(int i=1;i
백준 13900 순서쌍의 곱의 합(구현)
https://www.acmicpc.net/problem/13900 13900번: 순서쌍의 곱의 합 첫 번째 줄에는 입력 받을 정수의 개수 N(2 ≤ N ≤ 100,000) 두 번째 줄에는 N 개의 정수가 주어진다. 이때 입력 받는 정수들의 범위는 0이상 10,000 이하이다. www.acmicpc.net n의 범위가 100000이기 때문에 combination으로 풀면 안된다는것을 바로 알았다. 근데 어떻게 풀지를 몰라 한참을 고민하다가 리스트에 있는 값을 변수화 시켜서 구하는 과정을 해봤더니 list = [a,b,c,d] a(b+c+d) + b(c+d) + cd 이런식으로 규칙이 보이기 시작했다. 구현문제는 항상 어떠한 규칙을 찾아내야 하는데 쉬워보여도 생각이 잘 나지않아 어려운 것 같다. n = i..
백준 11571 분수를 소수로(구현)
https://www.acmicpc.net/problem/11571 11571번: 분수를 소수로 입력의 첫 번째 줄에는 테스트 케이스의 수 T (1 ≤ T ≤ 15,000)가 주어진다. 이후 각 테스트 케이스에 대해 한 줄에 분자와 분모 (0 ≤ 분자 < 1024, 0 < 분모 < 1024)가 공백으로 구분되어 정수로 주어진 www.acmicpc.net 개인적으로 엄청 어려운 문제였다. 처음에 접근한 방법은 소수점 아래의 숫자들을 문자열이라고 치고 반복적으로 나타나는 패턴을 찾기 위해 브루트포스를 이용하거나 한번 나온 숫자가 뒤에 다시 나올 떄 조건을 두는 방식으로 했는데 잘못된 생각이였고 잘 풀리지 않았다. 분수를 소수로 바꾸는 과정은 위의 사진처럼 나눗셈을 하면서 나머지에 대해 처리를 해주면서 진행이..
백준 7662 이중 우선순위 큐(Heapq)
https://www.acmicpc.net/problem/7662 7662번: 이중 우선순위 큐 입력 데이터는 표준입력을 사용한다. 입력은 T개의 테스트 데이터로 구성된다. 입력의 첫 번째 줄에는 입력 데이터의 수를 나타내는 정수 T가 주어진다. 각 테스트 데이터의 첫째 줄에는 Q에 적 www.acmicpc.net 문제는 간단하게 데이터를 삽입하고 최대값, 최소값을 삭제 해주면서 데이터를 관리하는 작업이였다. list를 선언하고 list.index, list.remove 등 list 연산을 쓰면 무조껀 시간초과가 나기때문에 최소힙, 최대힙을 사용하여 최소, 최댓값에 대한 처리를 해야겠다고 생각했다. 여기서 유의할점은 단순히 우선순위큐 모듈인 PriorityQueue()을 사용하려고 했지만 최소, 최대를 ..
백준 16928 뱀과 사다리 게임(BFS)
https://www.acmicpc.net/problem/16928 16928번: 뱀과 사다리 게임 첫째 줄에 게임판에 있는 사다리의 수 N(1 ≤ N ≤ 15)과 뱀의 수 M(1 ≤ M ≤ 15)이 주어진다. 둘째 줄부터 N개의 줄에는 사다리의 정보를 의미하는 x, y (x < y)가 주어진다. x번 칸에 도착하면, y번 칸으 www.acmicpc.net 뱀과 사다리의 좌표가 주어진 것을 활용하기 위해 list의 in 개념을 이용하려고 했지만 비효율적인 것 같아 Dict의 key, value를 이용해서 접근 하기로 했다. 주사위를 굴려서 1~6을 이동하면서 좌표의 cnt를 기억해두는 dp배열을 하나 만들고 저장하기로 했다. 유의할점은 뱀과 사다리로 이동하는 것은 주사위를 굴리는 것이 아닌 행동이기 때문..