CS/PS

CS/PS
[BOJ] 2933번 : 미네랄
https://www.acmicpc.net/problem/2933 2933번: 미네랄 창영과 상근은 한 동굴을 놓고 소유권을 주장하고 있다. 두 사람은 막대기를 서로에게 던지는 방법을 이용해 누구의 소유인지를 결정하기로 했다. 싸움은 동굴에서 벌어진다. 동굴에는 미네랄 www.acmicpc.net 복잡한 구현 문제다. 문제 서술이 조금 빈약한 점이 있는데, 클러스터가 떨어질 때에는 무조건 아랫 면이 다른 클러스터와 닿아야 멈출 수 있다. 예를 들어 예제 3번을 보면 ㄱ자 클러스터가 떨어지는 와중에 오른쪽 면이 다른 클러스터와 닿는 경우가 생기는데, 이때는 멈추지 않는다. 이런 느낌이다. 따라서 다음의 생각을 가지고 해결하면 된다. 1. 모든 클러스터는 바닥과 연결되어 있어야 한다. BFS로 체크한다. 단..
→2022.09.08
CS/PS
[BOJ] 3197번 : 백조의 호수
https://www.acmicpc.net/problem/3197 3197번: 백조의 호수 입력의 첫째 줄에는 R과 C가 주어진다. 단, 1 ≤ R, C ≤ 1500. 다음 R개의 줄에는 각각 길이 C의 문자열이 하나씩 주어진다. '.'은 물 공간, 'X'는 빙판 공간, 'L'은 백조가 있는 공간으로 나타낸다. www.acmicpc.net 꽤 복잡한 BFS 문제다. BFS로 해결해야 한다는 건 알겠는데, 하루가 지날 때마다 BFS를 쓰면 $O(E) \sim 10^7$ 를 최대 ${150 \over 2} = 75$번 수행하고, 백조도 다시 BFS를 써야 하므로, 여기에 2를 곱해주면 된다. 그럼 대충 $10^8 \times \alpha$가 나오는데.. 이대로 하면 TLE가 뜰 것이다.. 따라서 조금 최적화..
→2022.09.02
CS/PS
[BOJ] 1655번 : 가운데를 말해요
https://www.acmicpc.net/problem/1655 1655번: 가운데를 말해요 첫째 줄에는 백준이가 외치는 정수의 개수 N이 주어진다. N은 1보다 크거나 같고, 100,000보다 작거나 같은 자연수이다. 그 다음 N줄에 걸쳐서 백준이가 외치는 정수가 차례대로 주어진다. 정수는 -1 www.acmicpc.net 수 하나를 집어넣고 median값을 물어보는 query가 있을 때, 100000번의 query를 어떻게 0.1s(1e7번 내외의 iteration) 안에 처리할 것인가 하는 문제이다. query의 개수를 $N$이라고 하고$(N \leq 100000)$, 정수의 범위를 $M$이라고 하자. $(M \leq 20000)$ 처음에 떠올릴 수 있는 방법은 linked list로 수를 집어넣..
→2022.07.04
CS/PS
[BOJ] 4386번 : 별자리 만들기
https://www.acmicpc.net/problem/4386 4386번: 별자리 만들기 도현이는 우주의 신이다. 이제 도현이는 아무렇게나 널브러져 있는 n개의 별들을 이어서 별자리를 하나 만들 것이다. 별자리의 조건은 다음과 같다. 별자리를 이루는 선은 서로 다른 두 별을 일 www.acmicpc.net 아주 기초적인 MST 문제다. 별자리들의 좌표를 받아서 별들 사이의 거리를 저장해서 prim's algorithm으로 풀든지 kruskal's algorithm으로 풀던지 하면 된다. 나는 kruskal's algorithm으로 풀었다. N이 매우 작기 때문에 시간은 크게 고려하지 않아도 된다. time complexity를 따지자면, $O(N^2 \log{N} * \alpha)$ 정도일듯. 두 n..
→2022.07.01
CS/PS
[BOJ] 9466, 1202, 14003, 2166
BOJ 9466 : 텀 프로젝트 https://www.acmicpc.net/problem/9466 9466번: 텀 프로젝트 이번 가을학기에 '문제 해결' 강의를 신청한 학생들은 텀 프로젝트를 수행해야 한다. 프로젝트 팀원 수에는 제한이 없다. 심지어 모든 학생들이 동일한 팀의 팀원인 경우와 같이 한 팀만 있을 www.acmicpc.net DFS 문제이다. 크게 어렵지는 않은데, 주의할 만한 점은 vertex의 개수가 100000이므로 (edge의 개수도 당연히 100000이다) 모든 정점에 대해 BFS를 수행하면 O(VE)니까 TLE가 뜬다. 따라서 한 번 방문한 vertex에 대해서는 다시 방문하면 안 되고, cycle이 발생하는 경우에도 잘 체크를 해 줘야 한다. 어떤 방식으로든 한 번 방문한 ver..
→2021.09.01
CS/PS
[BOJ] 2749번 : 피보나치 수 3
https://www.acmicpc.net/problem/2749 2749번: 피보나치 수 3 첫째 줄에 n이 주어진다. n은 1,000,000,000,000,000,000보다 작거나 같은 자연수이다. www.acmicpc.net • 접근 보통 피보나치 문제를 접근할 때에는 divide and conquer 또는 DP로 접근한다. n이 매우 작은 경우(BOJ 2747 참조)에는 재귀로 풀어도 풀 수 있다. 시간복잡도가 O(2^N)이기 때문이다. 그보다 n이 조금 더 커진다면 DP로 풀 수 있다. 이 경우 time complexity가 O(N)이므로 N이 대략 2억 언저리인 경우까지도 해결이 가능하다. 이 문제는 다르다. n의 upper bound가 1e18이다. 이런 경우에는 O(N)으로 풀 수 없다. ..
→2021.08.25

• 이전
• 1
• 2
• 3
• 4
• 다음