[2019 카카오 개발자 겨울 인턴십] 징검다리 건너기(Java, 간단한 코드, Union-Find)
programmers.co.kr/learn/courses/30/lessons/64062# 코딩테스트 연습 - 징검다리 건너기 [2, 4, 5, 3, 2, 1, 4, 2, 5, 1] 3 3 programmers.co.kr ## 접근 시뮬레이션 형태로 접근하면 절대 안된다. 시간복잡도가 대략적으로 계산해봐도 너무 크다. 따라서, 삭제해야할 돌을 우선순위큐에 넣어놓고, 순차적으로 접근한다. 돌이 가지고 있는 값이 지나갈 수 있는 사람의 수라고 볼 수 있다. 값이 3인 돌을 지우다가, 간격이 k보다 같거나 크면 문제가 발생하고 종료해야 한다. 순차적으로 돌들을 지우면서, 간격을 확인하는 방법을 생각해봐야 한다. 특정한 돌을 지울 때, 앞 뒤로 비어있는 돌들을 확인해서 값을 확인하면 된다. 앞 뒤로 비어있는 돌을..
[BOJ 9938] 방 청소(Java, Union-Find, 문제 이해하기)
https://www.acmicpc.net/problem/9938 9938번: 방 청소 처음 6개의 술은 규칙 1에 의해서 1, 3, 5, 7, 9, 2번 서랍에 보관할 수 있다. 7번째 술은 규칙 3을 적용할 수 있다. 1번 서랍에 들어있는 술을 2로, 2번 서랍에 들어있는 술을 3으로, 3번 서랍에 들어있�� www.acmicpc.net ## 접근 서랍에 대한 boolean 배열을 통해서, 서랍의 비어있는 유무를 파악하도록 한다. 서랍이 가득찼을 때, 규칙3과 규칙4에 말하는 다른 서랍의 의미를 파악하는 것이 중요하다. 다른 서랍의 핵심은 기존의 들어있는 술을 옮길 수 있는 서랍이여야 한다. 다른 서랍들에 대한 저장할 수 있는 자료구조가 필요하다. 서랍에 기존의 술이 있을 때, 기존의 술을 옮기기 위..
[BOJ 1717] 여행 가자(Union-Find, Java, 자세한 설명)
## 접근 여행 경로가 가능한지 알아보기 위해서는, 두 점 사이에 경로가 존재하는지 확인해야 한다. 점들을 경유해서 두 점 사이의 경로가 만들어질 수도 있으므로, 가능한 모든 경로를 찾아봐야 한다. 위의 생각은, 점의 갯수가 작을 때는 시간복잡도가 작지만, 점의 개수가 많아지면 시간복잡도로 시간초과가 발생할 수 있다. 따라서, 점들을 경유해서 두 점 사이의 경로가 만들어지면, 두 점의 경로 유무를 저장해줄 수 있는 자료구조가 필요하다. 그렇다면, 두 점 사이의 경로가 있는지 확인하는 방법을 정해야 한다. 만약에, N이 200일 때, 모든 점 사이의 경로를 본다면, 최대 200 ^ 200의 시간 복잡도가 발생한다. 무조건 시간초과이다. 연결이 되는 점들을 모두 같은 집합에 넣는 Union-Find 방식을 ..