study blog

유니온 파인드란? 대표적 그래프 알고리즘으로 서로소 집합 ( Disjoint - set ) 를 찾는 알고리즘 Disjoint - set : 서로 중복되지 않는 부분 집합들로 나눠진 원소들에 대한 정보를 저장하는 자료구조 여러 노드가 존재할 때, 두 개의 노드를 선택해서, 현재 서로 같은 그래프에 속하는지 판별하는 알고리즘 3가지의 연산으로 이루어져 있다. make : 가장 작은 단위의 단위 집합을 만드는 연산 (초기화 연산) Find : 해당 노드가 속한 집합을 찾는 연산 ( 해당 노드가 속한 집합의 대표자를 찾는 연산 ) Union : x가 속한 집합과 y가 속한 집합을 합치는 연산 보통 연결리스트 혹은 트리로 구현하는데 연결리스트로 구현하기보다 자신의 집합에 속해있는 부모의 관계를 이용해 배열로 구현..

★★★☆ 문제 https://www.acmicpc.net/problem/1726 1726번: 로봇 많은 공장에서 로봇이 이용되고 있다. 우리 월드 공장의 로봇은 바라보는 방향으로 궤도를 따라 움직이며, 움직이는 방향은 동, 서, 남, 북 가운데 하나이다. 로봇의 이동을 제어하는 명령어는 www.acmicpc.net 풀이시간 : 50분 풀이 도착 지점까지의 최소값을 구해야 하므로 BFS 탐색으로 구현하였다. 1. 앞으로 한칸 ~ 세칸 까지 전진 2. 왼쪽 혹은 오른쪽으로 90도 회전 이 두가지의 경우 중 방문하지 않은 지점만 큐에 추가하면서 탐색한다. 로봇이 바라보고 있는 방향도 고려해야 하기 때문에 visited 배열을 3차원 배열로 선언하였다. 어렵지 않은 문제임에도 계속 통과하지 못했는데 전진 명령을..

★★★☆ 문제 https://www.acmicpc.net/problem/2212 2212번: 센서 첫째 줄에 센서의 개수 N(1 ≤ N ≤ 10,000), 둘째 줄에 집중국의 개수 K(1 ≤ K ≤ 1000)가 주어진다. 셋째 줄에는 N개의 센서의 좌표가 한 개의 정수로 N개 주어진다. 각 좌표 사이에는 빈 칸이 하나 있 www.acmicpc.net 풀이시간 : 30분 풀이 문제 설명이 이해가 가지 않아서 조금 헤멘 문제이다. N개의 센서가 어떤 거리에 위치해 있고, 우리는 그 거리에 집중국을 세워야 한다. K개의 집중국으로 N개의 센서를 모두 커버해야 하는데, 각각의 집중국들은 정해진 최대 거리가 없다! ( 집중국마다 최대 거리를 다르게 설정 할 수 있다) 집중국을 세울 때 각각의 집중국들의 설정 거리..

★★☆ 문제 https://www.acmicpc.net/problem/9019 9019번: DSLR 네 개의 명령어 D, S, L, R 을 이용하는 간단한 계산기가 있다. 이 계산기에는 레지스터가 하나 있는데, 이 레지스터에는 0 이상 10,000 미만의 십진수를 저장할 수 있다. 각 명령어는 이 레지스터에 www.acmicpc.net 풀이시간 : 45분 풀이 1. 명령어 String과 레지스터 값이 포함된 Node 클래스를 생성한다. 2. A에서 B가 되는 최소한의 명령어를 출력해야 하기 때문에 BFS 너비 우선 탐색으로 완전 탐색을 돌면서 가장 빨리 B가 되는 Node의 명령어를 출력하면 된다. 첫 제출에서는 메모리 초과가 났다. visited 여부를 체크를 하지 않아서 메모리 초과가 났다! 우리는 ..

★★☆ 문제 https://www.acmicpc.net/problem/11000 11000번: 강의실 배정 첫 번째 줄에 N이 주어진다. (1 ≤ N ≤ 200,000) 이후 N개의 줄에 Si, Ti가 주어진다. (0 ≤ Si < Ti ≤ 109) www.acmicpc.net 풀이 시간 : 30분 풀이 초기 풀이 방향은 이랬다. 1. 먼저 강의를 시작시간을 기준으로 오름차순 정렬해야 한다. 최소한의 강의실을 써야 하기 때문이다. 2. 정렬한 강의를 순서대로 강의실 큐에 넣는다. 각각의 강의실 큐에서 마지막 강의의 끝나는 시간과 비교해서 강의가 가능한 강의실에 추가한다. 이렇게 진행하려 했는데 생각해보니 굳이 강의를 다 가지고 있을 필요 없이 강의실의 마지막 강의의 끝나는 시간만 알고 있어도 괜찮다는 것을..