이분3 [프로그래머스] 징검다리 문제 링크: https://programmers.co.kr/learn/courses/30/lessons/43236 코딩테스트 연습 - 징검다리 출발지점부터 distance만큼 떨어진 곳에 도착지점이 있습니다. 그리고 그사이에는 바위들이 놓여있습니다. 바위 중 몇 개를 제거하려고 합니다. 예를 들어, 도착지점이 25만큼 떨어져 있고, 바위가 programmers.co.kr 프로그래머스 기준 Level 4인, 약간 어려운 문제입니다. 문제 내에서 총 거리가 주어지고 (distance), 각 바위의 위치가 주어집니다. 이후 제거해야 하는 바위의 수 (n)이 주어집니다. n개의 바위를 제거한 후 시작점 - 각 바위 사이 - 도착점 사이의 거리를 구했을 때, 어떤 바위를 제거했느냐에 따라 각 바위 사이 거리가 달.. 2021. 10. 8. [프로그래머스] 입국 심사 문제 링크: https://programmers.co.kr/learn/courses/30/lessons/43238 코딩테스트 연습 - 입국심사 n명이 입국심사를 위해 줄을 서서 기다리고 있습니다. 각 입국심사대에 있는 심사관마다 심사하는데 걸리는 시간은 다릅니다. 처음에 모든 심사대는 비어있습니다. 한 심사대에서는 동시에 한 programmers.co.kr 이분 탐색을 연습하기 위해 고른 문제인데... 처음에는 '이 문제를 어떻게 이분 탐색으로 해결할 수 있지?' 하고 고민했던 문제입니다. 그래서 약간의 힌트를 참고했는데... 맨 처음에 최소시간 0을 left, 최대 소요 시간을 right로 둡니다. 이때 최대 소요 시간은 (사람 수 n * 가장 오래 걸리는 심사관의 시간)이 됩니다. mid = (lef.. 2021. 10. 6. [백준 1300번] K번째 수 난이도: 골드 III 문제 링크: https://www.acmicpc.net/problem/1300 1300번: K번째 수 세준이는 크기가 N×N인 배열 A를 만들었다. 배열에 들어있는 수 A[i][j] = i×j 이다. 이 수를 일차원 배열 B에 넣으면 B의 크기는 N×N이 된다. B를 오름차순 정렬했을 때, B[k]를 구해보자. 배열 A와 B www.acmicpc.net N의 최대 크기가 10만이므로, 배열에 들어갈 모든 수를 계산하기에도 벅찹니다 (10만 x 10만 번의 연산). 따라서 이 문제는 모든 숫자를 계산하지 않고 풀 수 있어야 합니다. K번째 수를 구한다는 것은, 이보다 작은 수가 K-1개 존재한다는 뜻입니다. 이러한 상황에서 비교 연산을 훨씬 덜 하면서 원하는 수를 탐색하는 방법 중 하.. 2021. 9. 17. 이전 1 다음
