알고리즘
-
디스크 컨트롤러 - 왜 그렇게 풀리는가? 개념 알아보기 [프로그래머스]개발/알고리즘 문제풀이 2023. 11. 11. 16:30
문제를 풀고 나서 인터넷에 풀이들을 찾아 봤습니다. '이 방식을 쓰면 된다'는 풀이들은 많았으나, 왜 그렇게 풀면 풀리는지에 대해 이유를 설명한 글을 찾아보기가 어려워서 이렇게 글을 포스팅하게 되었습니다. 본문에는 풀이법과 정답 코드가 포함되어 있으니, 열람을 원치 않는 분들께서는 주의하여 주시기 바랍니다. 문제 보러 가기 > 개념 풀이 문제의 조건에 따르면, 작업의 요청부터 종료까지 걸린 시간의 평균을 가장 줄이는 방법을 찾아야 합니다. 한 번에 한 작업씩만 들어온다면 우선 순위가 필요 없겠지만, 현재 작업을 진행하는 도중에 여러 작업 요청이 있을 수 있습니다. 따라서 우선 순위에 따라 처리해야 하는데요. 우선 순위를 처리하는 정답부터 말씀드리자면, 현재 작업이 진행되는 동안 요청된 작업들 중에 가장 ..
-
[WEEK01/DAY01] 백준 문제 : 소수 찾기SW Jungle/TIL (Today I Learned) 2022. 9. 24. 02:24
https://www.acmicpc.net/problem/1978 1978번: 소수 찾기 첫 줄에 수의 개수 N이 주어진다. N은 100이하이다. 다음으로 N개의 수가 주어지는데 수는 1,000 이하의 자연수이다. www.acmicpc.net 오늘 풀었던 알고리즘 중에 제일 어려웠던 문제다. 소수는 약수가 1과 자기 자신밖에 없는 1보다 큰 자연수를 말한다. 그래서 1보다 큰 자연수 n이 주어졌을 때 n이 소수인지를 판별하는 가장 간단한 방법은 2에서 n-1 까지의 모든 자연수로 나누어 보는 것이다. 만약 한 경우에라도 나누어 떨어진다면, n은 소수가 아닌 것이다. 위 방법으로 풀이하면 시간 복잡도가 O(N)이 된다. 좀 더 빠른 방법이 있는데, 굳이 2에서 n-1까지 반복하지 않고 √n 까지만 반복해도..