본문 바로가기
반응형

프로그래밍/Algorithm110

O(N) vs O(2N)은 동일한 시간 복잡도를 갖는다. O(N) vs O(2N)은 동일한 시간 복잡도를 갖는다. 결론부터 이야기하자면 O(N)과 O(2N)는 동일하다. O(N)과 O(2N)이 서로 혼동되어 다르다고 생각한다면 '입력 크기에 따라 런타임이 얼마나 빠르게 증가하는가'가 아니라 '작업 횟수'에 초점을 맞추고 있기 때문이다. 시간 복잡도는 수행시간이 아니다. 아래의 그래프를 보면서 확인해 보자 두 경우 모두 'No Of Operations'가 입력 크기에 따라 그래프가 선형적으로 증가하는 것을 볼 수 있다. 실질적으로 O(N)은 O(2N) 보다 실행 시간이 짧지만 이는 중요하지 않다. N 값이 증가하면 O(N)이 성장을 지배하게 되고 계수 2는 중요하지 않게 된다. 따라서 N의 값이 매우 커지면 둘의 실행 시간이 동일해질 것이다. 예를 들어보자 T(.. 2023. 12. 5.
[프로그래머스 Programmers] 길이에 따른 연산 문제 설명 정수가 담긴 리스트 num_list가 주어질 때, 리스트의 길이가 11 이상이면 리스트에 있는 모든 원소의 합을 10 이하이면 모든 원소의 곱을 return하도록 solution 함수를 완성해주세요. 제한 사항 2 ≤ num_list의 길이 ≤ 20 1 ≤ num_list의 원소 ≤ 9 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 풀이 코드 using System; using System.Linq; public class Solution { public int solution(int[] num_list) { int answer = 0; if .. 2023. 12. 4.
O(log n) 시간 복잡도란 무엇인가? 시간 복잡도란 무엇인가? 시간 복잡도는 입력(n)을 기반으로 알고리즘이 실행(O)되는 데 걸리는 시간을 설명한다. 시간 복잡도는 꽤나 직관적이다. 예를 들어서 O(1)의 시간 복잡도를 가지는 알고리즘이 있다면 이는 입력에 상관없이 실행하는데 항상 동일한 양의 시간이 걸린다. O(n)의 시간 복잡도를 가지는 알고리즘이라면 입력값이 커지면 커질수록 시간도 그에 맞춰서 일정한 속도(선형 진행)로 커진다는 것을 의미한다. O(n^2)의 시간 복잡도를 가지는 알고리즘이라면 입력값이 커지면 커질수록 걸리는 시간이 기하급수적으로 증가할 것이다. 빅-오(Big-O) 표기법 알고리즘에서 중요한 속성 정확성 : 주어진 입력을 모두 처리하며 올바르게 출력해야 한다. 효율성 : 문제를 효율적으로 해결해야 한다. - 시간 복잡.. 2023. 12. 1.
[백준 BAEKJOON] 1978번 소수 찾기 문제 주어진 수 N개 중에서 소수가 몇 개인지 찾아서 출력하는 프로그램을 작성하시오. 입력 첫 줄에 수의 개수 N이 주어진다. N은 100이하이다. 다음으로 N개의 수가 주어지는데 수는 1,000 이하의 자연수이다. 출력 주어진 수들 중 소수의 개수를 출력한다. 풀이 코드 using System; namespace backjun { public class Program { static void Main(string[] args) { var totalCount = Console.ReadLine(); var list = Console.ReadLine().Split(" ").ToList(); int count = 0; foreach(var s in list) { if (IsPrime(Int32.Parse(s).. 2023. 11. 29.
[프로그래머스 Programmers] 정수 제곱근 판별 문제 설명 임의의 양의 정수 n에 대해, n이 어떤 양의 정수 x의 제곱인지 아닌지 판단하려 합니다. n이 양의 정수 x의 제곱이라면 x+1의 제곱을 리턴하고, n이 양의 정수 x의 제곱이 아니라면 -1을 리턴하는 함수를 완성하세요. 제한 사항 n은 1이상, 50000000000000 이하인 양의 정수입니다. 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 풀이 코드 using System; public class Solution { public long solution(long n) { var r = Math.Sqrt(n); return (n % r ==.. 2023. 11. 28.
[프로그래머스 Programmers] 비밀지도 문제 설명 네오는 평소 프로도가 비상금을 숨겨놓는 장소를 알려줄 비밀지도를 손에 넣었다. 그런데 이 비밀지도는 숫자로 암호화되어 있어 위치를 확인하기 위해서는 암호를 해독해야 한다. 다행히 지도 암호를 해독할 방법을 적어놓은 메모도 함께 발견했다. 지도는 한 변의 길이가 n인 정사각형 배열 형태로, 각 칸은 "공백"(" ") 또는 "벽"("#") 두 종류로 이루어져 있다. 전체 지도는 두 장의 지도를 겹쳐서 얻을 수 있다. 각각 "지도 1"과 "지도 2"라고 하자. 지도 1 또는 지도 2 중 어느 하나라도 벽인 부분은 전체 지도에서도 벽이다. 지도 1과 지도 2에서 모두 공백인 부분은 전체 지도에서도 공백이다. "지도 1"과 "지도 2"는 각각 정수 배열로 암호화되어 있다. 암호화된 배열은 지도의 각 가.. 2023. 11. 27.

티스토리툴바