조합 계산은 일상적인 프로그래밍 문제에서 자주 등장한다. 예를 들어. 여러 개의 아이템 중에서 일부를 고를 수 있는 경우나, 팀 구성, 경기 조합 등의 문제에서 자주 활용된다.이때 조합을 계산하는 가장 일반적인 방법은 팩토리얼을 이용하는 방법이다. 조합 계산의 기본 공식은 다음과 같다.하지만 팩토리얼을 이용해서 조합을 계산한 결과 특정 테스트 케이스에서는 작동이 되지 않는 문제가 발생하였다.이에 대한 원인은 큰 수를 다룰 때 부동소수점 오차와 오버플로우 문제로 인해 발생하는 것이었다. 🔥 문제 1 : 부동 소수점 오차 (Floating-point Precision Error)컴퓨터에서는 실수를 부동소수점 방식으로 저장한다. 부동 소수점 방식이란 실수를 일정한 자릿수로 근사하여 저장하는 방식이다.이는 ..
코딩테스트의 핵심은 주어진 문제에 시간복잡도를 얼마나 잘 고려하여 알고리즘을 선택하는지가 중요하다. 이번 포스팅에서는 시간복잡도에 대한 개념과 이를 문제에 어떻게 활용할 수 있는지에 대해 작성하고자 한다. 시간복잡도 시간복잡도는 주어진 문제를 해결하기 위한 연산 횟수를 말한다. 실제 시간복잡도는 크게 3가지 표기법으로 나타내어 지고는 한다. 빅-오메가(Ω(n)) : 최선일 때 연산 횟수 빅-세타(Θ(n)) : 보통일 때 연산 횟수 빅-오(O(n)) : 최악일 때 연산 횟수 만약 n^2기준이라면 각각의 시간 복잡도는 아래와 같은 의미를 가지거나 최소 만족해야 한다. 빅-오메가 : 최소 n^2은 되어야 한다. 빅-세타 : n^2일 때 빅-오 : 모든 차수가 n^2보다 작아야 한다. 더보기 💡코딩테스트에서는 ..
Algorithm/개념정리 2025. 3. 10. 18:49
조합 계산은 일상적인 프로그래밍 문제에서 자주 등장한다. 예를 들어. 여러 개의 아이템 중에서 일부를 고를 수 있는 경우나, 팀 구성, 경기 조합 등의 문제에서 자주 활용된다.이때 조합을 계산하는 가장 일반적인 방법은 팩토리얼을 이용하는 방법이다. 조합 계산의 기본 공식은 다음과 같다.하지만 팩토리얼을 이용해서 조합을 계산한 결과 특정 테스트 케이스에서는 작동이 되지 않는 문제가 발생하였다.이에 대한 원인은 큰 수를 다룰 때 부동소수점 오차와 오버플로우 문제로 인해 발생하는 것이었다. 🔥 문제 1 : 부동 소수점 오차 (Floating-point Precision Error)컴퓨터에서는 실수를 부동소수점 방식으로 저장한다. 부동 소수점 방식이란 실수를 일정한 자릿수로 근사하여 저장하는 방식이다.이는 ..
Algorithm/개념정리 2024. 2. 15. 15:51
코딩테스트의 핵심은 주어진 문제에 시간복잡도를 얼마나 잘 고려하여 알고리즘을 선택하는지가 중요하다. 이번 포스팅에서는 시간복잡도에 대한 개념과 이를 문제에 어떻게 활용할 수 있는지에 대해 작성하고자 한다. 시간복잡도 시간복잡도는 주어진 문제를 해결하기 위한 연산 횟수를 말한다. 실제 시간복잡도는 크게 3가지 표기법으로 나타내어 지고는 한다. 빅-오메가(Ω(n)) : 최선일 때 연산 횟수 빅-세타(Θ(n)) : 보통일 때 연산 횟수 빅-오(O(n)) : 최악일 때 연산 횟수 만약 n^2기준이라면 각각의 시간 복잡도는 아래와 같은 의미를 가지거나 최소 만족해야 한다. 빅-오메가 : 최소 n^2은 되어야 한다. 빅-세타 : n^2일 때 빅-오 : 모든 차수가 n^2보다 작아야 한다. 더보기 💡코딩테스트에서는 ..