2024. 6. 10. 04:43ㆍIT/CS 지식
알고리즘
시간복잡도와 공간복잡도가 무엇인지 설명해주실 수 있을까요?
시간복잡도 시간 복잡도는 문제를 처리하는데 걸리는 시간을 의미합니다.
즉, 문제를 푸는데 걸리는 연산의 속도와 연결되는 것으로
입력 값에 따라서 수행하는 연산의 수를 나타냅니다.
이는 주로 BigO 표기법을 사용하여 표기되며, 대표적인 시간 복잡도는 아래와 같습니다.
O(1), O(n), O(log n), O(n log n), O(n^2)
공간 복잡도는 문제를 처리하는데 필요한 공간의 크기를 의미합니다.
즉, 문제를 푸는데 필요한 데이터를 저장하는 공간과 연결되는 것으로,
입력 값에 따라서 필요한 메모리를 나타냅니다.
이를 BigO 표기법으로 표현하면 O(1), O(n), O(n^2) 등으로 표현할 수 있습니다.
시간복잡도가 높은 경우 취할 수 있는 일반 전략을 3가지 정도 설명해주실 수 있을까요?
시간 복잡도를 낮추기 위해 취할 수 있는 전략은 아래와 같습니다.
1. 메모이제이션
중복되는 연산을 줄이기 위해 이전에 계산된 결과를 저장하고 재사용하는 방법입니다.
재귀적 알고리즘과 DP(동적 프로그래밍)의 아이디어라고 할 수 있습니다.
2. StringBuilder
문자열을 처리하는 경우에는 StringBuilder를 사용하여 효율적으로 처리할 수 있습니다.
C#에서는 string이 변경되는 경우, 새로운 string을 생성하고 기존의 것을 폐기하므로
이 과정에서 GC가 발생하는 등의 시간 소비가 발생합니다.
StringBuilder는 이러한 불필요한 과정을 방지해주는 역할을 합니다.
3. 적절한 자료 구조 사용
문제에 맞는 적절한 자료 구조를 선택하여 연산을 더 효율적으로 수행할 수 있습니다.
예를 들어서 Dictionary, HashSet 등의 자료구조를 이용하면
특정 조건에서 좀 더 효율적인 연산을 할 수 있으므로 시간 복잡도를 줄일 수 있습니다.
단, 적절하지 못한 자료 구조를 사용하면 원하지 않는 결과를 얻거나
오히려 시간 복잡도가 높아질 수 있으므로, 이를 잘 이해하고 사용하는 것이 중요하다고 할 수 있습니다.
이들 자료 구조를 간략히 소개하면
Dictionary
Key, Value를 저장하는 자료 구조로 해당 Key가 얼마나 존재하는지 저장하기 쉬운 자료 구조입니다.
HashSet
Key를 저장하는 자료 구조로 해당 Key가 주어진 자료에 있는지 확인하기 쉬운 자료 구조입니다.
공간복잡도가 높은 경우 취할 수 있는 일반 전략을 3가지 정도 설명해주실 수 있을까요?
공간 복잡도를 낮추기 위해 취할 수 있는 전략은 아래와 같습니다.
1. 불필요한 변수 줄이기
코드에서 사용하지 않는 변수나 중복된 변수를 줄여 메모리 사용을 최적화합니다.
예를 들어서 반복문을 사용하는 경우에는 반복문에 들어가기 전에 해당 변수를 선언하고 그 값을 바꾸는 방식으로 구현하는 방법이 있습니다.
2. 동일한 기능을 하는 연산은 별도의 메서드로 추출
코드가 길어짐에 따라서 같은 기능을 하는 연산이 반복될 수 있습니다.
이런 경우에 해당 연산을 별도의 메서드로 추출하여 코드의 중복을 줄여 메모리를 절약할 수 있습니다.
3. 효율적인 데이터 구조 사용
문제에 맞는 효율적인 데이터를 사용하면 메모리를 절약할 수 있습니다.
예를 들어서 배열과 리스트를 선택하는 과정에서 주어지는
입력 값의 길이가 일정할 경우 배열을 선택하는 것이 더 효율적이며,
입력 값이 길이가 불분명한 경우에는 리스트를 선택하는 것이 더 효율적입니다.
재미있게 공부한 알고리즘이 있다면 설명해주실 수 있을까요?
제가 재미있게 공부한 알고리즘은 다이나믹 프로그래밍(DP)입니다.
DP의 기능 중에서 가장 매력적이라고 느끼는 부분은
연산한 결과값을 저장하는 메모이제이션 부분으로 특정 정보가 주어졌을 때,
이를 자신의 언어로 바꾸어 저장하는 저의 학습법과 비슷하여 매력을 느꼈습니다.
또, DP를 사용하면 불필요한 연산을 줄일 수 있는 부분도 매우 매력적인 요소라고 생각합니다.
주어진 문제에 대해서 필요한 정보들을 하나씩 연산하여 저장하고
한 단계씩 연산을 거듭하여 결국은 정답을 찾는 과정이 인상적이었습니다.
이분탐색이 무엇이고 시간복잡도는 어떻게 되며 그 이유는 무엇인가요?
이분 탐색이란 원하는 결과값을 찾기 위해서 중간 값에서 시작하여
좌 우로 나눈 후에 해당 값에 가까운 쪽을 선택하는 과정을 반복하는 탐색법입니다.
이분 탐색의 가장 큰 특징은 정렬된 상태에서 사용할 수 있다는 점으로
현재의 값과 목표의 값을 비교하여 가까운 쪽으로 이동하기 위해 정렬이 우선되어야 합니다.
이분 탐색의 시간 복잡도는 BigO(log n)입니다.
이분 탐색은 매 반복마다 탐색 범위가 반으로 줄어들기 때문에
탐색에 따라 남은 범위는 기하급수적으로 작아집니다.
이는 로그 함수의 특징으로 n개의 요소에 대해서 최악의 경우 탐색 횟수는 log n 입니다.