알고리즘
-
[백준] 3079번 입국 심사알고리즘/백준 2021. 8. 27. 18:44
문제 링크 프로그래머스 풀이 심사대의 범위가 1 ~ 100,000이고 친구들의 숫자가 최대 10억명이므로 이분 탐색을 사용하지 않으면 시간이 너무 오래 걸리게 될 겁니다. 이 문제에서는 어디에 이분 탐색을 사용해야 할까요. 우리가 구하고자 하는 답은 주어진 인원이 입국 심사 하는 데 걸리는 최소 값입니다. 입국 시간과 인원과의 상관 관계를 먼저 생각해볼게요. 예제에서 두 개의 심사대가 주어지고 각각 심사 시간이 7분, 10분입니다. 만약 입국자에게 5분이 주어진다면 어느 누구도 심사대를 통과할 수 없을 겁니다. 7분이면 1명만 통과할 수 있고요 10분은 돼야 2명이 받을 수 있습니다. 직관적으로 계산할 수 있지만 수식으로 해보면, 주어진 시간이 X일 때 각 심사대의 심사 시간을 나눈 값을 더한 총합입니다..
-
[백준] 1920번 수 찾기알고리즘/백준 2021. 8. 27. 12:27
문제 링크 풀이 이분 탐색 혹은 이진 탐색은 매 탐색 마다 탐색 범위를 절반으로 줄여 나가는 방식입니다. O(logN)의 시간 복잡도를 가지는데요. 약 40억 개의 데이터라도 32번 이하의 횟수에서 원하는 데이터를 찾을 수 있습니다. 찾을 수 없더라도 32번만에 알 수 있는 것이지요. 코드에서 find가 A[mid]가 되거나 혹은 mid == low == high 상황일 때(이 경우는 최대로 다 순회한 상태) 값을 찾았다고 판정하게 됩니다. 그리고 이분 탐색은 반드시 데이터가 정렬되어 있어야 합니다. 중간 값을 기준으로 요소의 크고 작음을 이용하는 것이기 때문입니다. 기본 흐름은 찾고자 하는 주어진 정수 데이터의 중간 값을 구해서 중간 값이 찾고자 하는 데이터보다 작으면 low 인덱스를 mid + 1로 ..
-
[백준] 2193번 이친수알고리즘/백준 2021. 8. 23. 17:12
문제 링크 풀이 다섯 번째 항까지 직접 경우의 수를 세어 보면 피보나치 수열과 동일한 규칙을 찾을 수 있습니다. 90번째 항까지 구해야 하는데, int형은 표현 범위를 초과하기 때문에 점화식은 long long으로 만들어줍니다. 규칙을 이렇게도 생각해볼 수 있습니다. 다섯 자리라고 할 때 10xxx0인 경우와 10xx01인 경우입니다. 0으로 끝날 때 d[n-1]과 01으로 끝나는 경우인 d[n-2]를 더해서 d[n]을 구하는 것입니다. d[n] = d[n-1] + d[n-2]이고 초기값만 잘 세팅해주면 됩니다. 코드 #include int main() { int N; scanf("%d", &N); long long d[90] = {}; d[0] = 1; d[1] = 1; for (int i = 2; i..
-
[백준] 2156번 포도주 시식알고리즘/백준 2021. 8. 23. 16:25
문제 링크 풀이 계단 오르기 문제와 비슷한데 다릅니다. 계단 오르기 문제는 반드시 마지막 계단을 밟아야 한다는 조건이 있었지만 이 문제는 아닙니다. 점화식을 구할 때 d[i]가 i번째 와인인 w[i]을 반드시 선택할 필요는 없다는 의미입니다. 예를 들어 8 5 4 2에서 3개를 선택하는 연속합의 최대값을 구할 때 마지막 숫자인 2를 반드시 포함해야 한다면 5+4+2=11이지만 마지막을 선택하지 않아도 된다면 8+5+4=17입니다. d[i]를 구할 때 w[i]를 포함하는 경우에서의 최대값을 구하고 나서 d[i-1]과도 비교를 해야 하는 이유입니다. 코드 #include int max(int a, int b) { return a > b ? a : b; } int main() { const int MAX = ..
-
[백준] 11053번 가장 긴 증가하는 부분 수열알고리즘/백준 2021. 8. 19. 20:12
문제 링크 풀이 자세한 설명보다는 개념적으로 설명하겠습니다. { 1, 2, 1, 2, 3, 5, 4 }라는 수열로 예를 들겠습니다. d[i]는 i번째 요소를 마지막 수로 하는, 증가하는 수열의 길이로 하겠습니다. 인덱스는 1부터 하겠습니다. d[1]은 1이고 d[2]는 2입니다. d[3]은 1이고요 d[4]는 2, d[5]는 3, d[6]은 4, d[7]은 4입니다. d[i]는 i번째 요소보다 작은 요소 중에서 가장 큰 요소를 마지막 값으로 하는 수열의 길이에서 1을 더한 값이 됩니다. 예를 들어, 다섯 번째 요소가 3인데요, 이는 3보다 작은 수 중에 가장 큰 수인 2를 마지막 요소로 하는 수열의 길이에서 1을 더한 값이라는 거죠. 그니까 3보다 작은 d[i]의 최대값을 찾아 1을 더하면 됩니다. 코드..
-
[백준] 1932번 정수 삼각형알고리즘/백준 2021. 8. 18. 19:17
문제 링크 풀이 이차원 배열도 일차원 배열처럼 연속된 메모리에 지나지 않지만 개발자가 작업할 때는 직관적으로 접근할 수 있어서 편합니다. 이 문제를 이차원 배열로 풀면 조금 편합니다. 예제로 주어진 입력값을 이차원 배열을 이용해 다음처럼 할 수 있습니다. 이 배열은 점화식을 위한 이차원 배열이며 dp[3][2]는 [3][2] 위치까지 합산된 최대값을 표현합니다. 즉 dp[2][1]과 dp[2][2]를 비교해서 더 큰 값을 [3][2]의 좌표의 값과 더해서 dp[3][2]를 갱신하면 됩니다. 점화식은 다음과 같습니다. d[i][j] = max(d[i-1][j-1], d[i-1][j]) + triangle[i][j] 반복문 사용을 최소화하기 위해 triangle 이차원 배열을 선언하지 않고 일차원 배열을 하..
-
[백준] 2579번 계단 오르기알고리즘/백준 2021. 8. 18. 17:23
문제 링크 풀이 계단을 연속해서 세 계단을 오를 수 없고 연속해서 두 번 혹은 한 계단을 건너뛸 수 있습니다. n번째 계단은 반드시 밟아야 합니다. 즉 n-3, n-2, n 순서대로 밟거나 n-3, n-1, n의 두 가지 경우를 점화식으로 도출할 수 있습니다. 이 중에서 큰 값을 구하면 되는 것이죠. 앞의 순서는 d[n-2] + s[n]이며 뒤는 d[n-3] + s[n-1] + s[n]입니다. 코드 #include #include int main() { int N; scanf("%d", &N); int s[301] = { 0 }; int d[301] = { 0 }; for (int i = 1; i
-
[프로그래머스] 추석 트래픽알고리즘/프로그래머스 2021. 8. 15. 19:58
문제 링크 풀이 문자열로 되어 있는 시간 로그를 실제 숫자로 변경해 주어진 로그에서 시작 시간을 구해, 시작 시간과 완료 시간을 pair로 가지는 벡터에 넣습니다. 1초 동안 최대로 걸려 있는 처리량을 구하는 것이 답입니다. 문제를 보면 lines 배열은 응답완료시간을 오름차순 정렬이 되어 있습니다. 이 말은 n번째 로그의 완료시간은 무조건 n-1보다 늦다는 이야기가 됩니다. 즉 시작 시간을 기준하면 됩니다. 예제 2를 보면 첫 번째 로그가 끝나는 시점과 두 번째 로그의 시작 지점이 1초에 같이 속하기 때문에, 최대 2개가 카운트 된다는 것이 힌트입니다. 1초라는 간격을 적용했을 때 카운트할 수 있는 최대값을 찾는 것이 목표입니다. 즉 n번째의 시작 시간이 n-1번째의 완료시간 + 999ms보다 같거나 ..