codeground practice - 극단적인 수 문제 링크 로그인을 해야만 볼 수 있다. 문제 해결 1. K번 째 극단적인 수를 구하는 문제. K의 범위가 10억이므로 자료구조에 담아서 해결하기에 부적합. 2. 극단적인 수를 길이로 나눠보면 길이가 1 늘어날 때, 2배씩 늘어남을 알 수 있다. 이를 이용해서 K번 째 극단적인 수의 길이를 먼저 구한다. 3. K번 째 극단적인 수의 길이가 L이라고 하자. 44...44 부터 77....77 까지는 부터 번 째라고 할 수 있다. 4. 같은 길이의 극단적인 수를 오름차순으로 정렬하면, 맨 앞자리 부터 절반씩 4 또는 7로 나뉘게된다. 그러므로 이분탐색을 이용해서 mid 보다 작으면 4를 출력하고 아니면 7을 출력한다. 주의할 점 || 생각해볼 점 1. 이분탐색을 할 때 끝점을 으로 설정하고, (시작점+1) .. 더보기 BOJ 14621 - 나만 안되는 연애 문제 링크https://www.acmicpc.net/problem/14621 문제 해결 1. "모든 정점이 연결되어야한다", "도로의 합이 최소가 되어야한다" → 최소신장트리(MST) 문제를 크루스칼 알고리즘(Kruskal Algorithm)으로 해결 주의할 점 || 생각해볼 점 1. 최소 경로를 해결하는 Dijkstra 알고리즘을 사용할 수 없다. 실제 정점끼리의 최소 거리랑 신장된 트리에서의 거리는 다를 수 있다. 2. 이분 그래프로 해결하려면 까다롭다. 그래서 정점마다 W or M 을 저장해서 서로 같다면 연결에서 제외했다. 3. 만약 모든 정점이 연결되지 않으면 -1을 출력하는 것을 잊으면 안된다. 참고 - ※ 정확하고 부드러운 태클은 언제나 환영입니다. 더보기 BOJ 1495 - 기타리스트 문제 링크(Link)https://www.acmicpc.net/problem/1495 문제 해결(Solution) 1. dp[i][j] : i번 곡에서 j만큼의 볼륨을 가질 수 있는 지에 대한 여부. 주의할 점 || 생각해볼 점(Caution || Consideration) 1. 재귀함수 안에서 볼륨 j가 0보다 작은 지 또는 M보다 큰지 제일 먼저 확인해줘야 한다. 2. 만약 볼륨 값이 범위를 넘어가게 되면 의미없는 수를 반환해야한다. 그렇지 않으면 그 값이 계속해서 다른 재귀함수에 사용된다. 참고 - ※ 정확하고 부드러운 태클은 언제나 환영입니다. 더보기 이전 1 ··· 15 16 17 18 19 20 21 ··· 32 다음
