목록2024/02 (17)
체뚱로그
풀이 시간: 2h24m16s06 시간 복잡도: O(N) 공간 복잡도: O(1) 참고 자료: https://astrid-dm.tistory.com/429 문제 N개의 스위치와 N개의 전구가 있다. 각각의 전구는 켜져 있는 상태와 꺼져 있는 상태 중 하나의 상태를 가진다. i(1 < i < N)번 스위치를 누르면 i-1, i, i+1의 세 개의 전구의 상태가 바뀐다. 즉, 꺼져 있는 전구는 켜지고, 켜져 있는 전구는 꺼지게 된다. 1번 스위치를 눌렀을 경우에는 1, 2번 전구의 상태가 바뀌고, N번 스위치를 눌렀을 경우에는 N-1, N번 전구의 상태가 바뀐다. N개의 전구들의 현재 상태와 우리가 만들고자 하는 상태가 주어졌을 때, 그 상태를 만들기 위해 스위치를 최소 몇 번 누르면 되는지 알아내는 프로그램을..
풀이 시간: 1h14m34s34 시간 복잡도: O(100001 * log (100001)) // 큐 연산(log), 최대 100001개 큐 연산 반복 공간 복잡도: O(100001) // visited 참고 자료: https://kimyunseok.tistory.com/136 문제 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 걷는다면 1초 후에 X-1 또는 X+1로 이동하게 된다. 순간이동을 하는 경우에는 0초 후에 2*X의 위치로 이동하게 된다. 수빈이와 동생의 위치가 주어졌을 때, 수빈이가 동생을 찾을 수 있는 가장 빠른..
풀이 시간: 1h06m22s97 + 2h 시간 복잡도: O(M log M) + O(M log N) = O(M log MN) // Sort 연산 + Union-Find 연산(트리높이 탐색(log N) * 길의 개수(M)) 공간 복잡도: O(N + M) // parent와 v 벡터 크기 참고 자료 https://gmlwjd9405.github.io/2018/08/29/algorithm-kruskal-mst.html https://swblossom.tistory.com/51 문제 동물원에서 막 탈출한 원숭이 한 마리가 세상구경을 하고 있다. 그러다가 평화로운 마을에 가게 되었는데, 그곳에서는 알 수 없는 일이 벌어지고 있었다. 마을은 N개의 집과 그 집들을 연결하는 M개의 길로 이루어져 있다. 길은 어느 방향..
풀이 시간: 2h16m46s58 시간 복잡도: O(Tn) 공간 복잡도: O(n) 참고 자료: https://ongveloper.tistory.com/167 문제 이번 가을학기에 '문제 해결' 강의를 신청한 학생들은 텀 프로젝트를 수행해야 한다. 프로젝트 팀원 수에는 제한이 없다. 심지어 모든 학생들이 동일한 팀의 팀원인 경우와 같이 한 팀만 있을 수도 있다. 프로젝트 팀을 구성하기 위해, 모든 학생들은 프로젝트를 함께하고 싶은 학생을 선택해야 한다. (단, 단 한 명만 선택할 수 있다.) 혼자 하고 싶어하는 학생은 자기 자신을 선택하는 것도 가능하다. 학생들이(s1, s2, ..., sr)이라 할 때, r=1이고 s1이 s1을 선택하는 경우나, s1이 s2를 선택하고, s2가 s3를 선택하고,..., s..
풀이 시간: 4h07m40s52 시간 복잡도: O(N) + O(M) + O(V+E) = O(V+E) = O(V+6V) = O(7V) = O(V) // 여기서 V는 정점, E는 간선, V의 최댓값은 100 // 간선 E는 각 100개의 정점에서 갈 수 있는 경우의 수가 최대 6번이므로 6V = 600 공간 복잡도: O(101) + O(101) + O(V) = O(V) // 순서대로 arr, visited, queue 참고 자료: https://chanmuzi.tistory.com/4 문제 뱀과 사다리 게임을 즐겨 하는 큐브러버는 어느 날 궁금한 점이 생겼다. 주사위를 조작해 내가 원하는 수가 나오게 만들 수 있다면, 최소 몇 번만에 도착점에 도착할 수 있을까? 게임은 정육면체 주사위를 사용하며, 주사위의 ..
풀이 시간: 1h37m26s53 + 22m53s69 + 36m22s01 시간 복잡도: O(D2*D2) 공간 복잡도: O(2001*2001) 참고 자료: https://david0506.tistory.com/74 문제 KOI 공연장의 관중석에는 가운데에 있는 무대를 중심으로 반지름이 자연수인 동심원(중심이 같은 여러 원들) 위에 다음과 같이 좌석들이 배치되어 있다. 반지름이 1인 원 위에는 좌석이 1개, 반지름이 2인 원 위에는 좌석이 2개, 이런 식으로 반지름이 D 인 원 위에는 좌석이 D 개가 있다. 또한, 무대에서 정확히 북쪽 방향에는 모든 원들에 좌석이 있으며, 하나의 원 위에 있는 좌석들은 동일한 간격을 두고 배치되어 있다. 이번 공연에 반지름이 D1보다 같거나 크고, D2(D1 ≤ D2)보다 같..