시갑복잡도, 공간복잡도
시간 복잡도는 알고리즘이 문제를 해결하는 데 필요한 시간을 나타냅니다. 이는 주로 알고리즘에 사용되는 연산의 횟수로 측정되며, 입력 크기에 따라 얼마나 많은 시간이 걸리는지를 나타내는 함수로 표현됩니다
공간 복잡도는 알고리즘이 문제를 해결하는 데 필요한 메모리 공간을 나타냅니다. 이는 알고리즘 실행에 필요한 저장 공간의 양으로 측정되며, 입력 크기에 따라 얼마나 많은 공간이 필요한지를 나타내는 함수로 표현됩니다
시간복잡도가 높은 경우 취할 수 있는 일반 전략을 3가지 정도 설명해주실 수 있을까요
시간 복잡도가 높은 경우, 즉 알고리즘이 실행되는 데 시간이 많이 걸리는 경우에는 다음과 같은 전략을 취해 볼 수 있습니다
알고리즘 최적화: 알고리즘 자체를 개선하여 실행 시간을 줄일 수 있습니다. 예를 들어, 불필요한 연산을 제거하거나, 더 효율적인 자료구조를 사용하거나, 동적 프로그래밍 같은 기법을 사용하여 중복 계산을 줄이는 등의 방법이 있습니다''
병렬 처리: 가능한 경우, 여러 개의 프로세스나 스레드를 사용하여 작업을 동시에 처리하도록 알고리즘을 수정할 수 있습니다. 이렇게 하면 CPU 자원을 더 효율적으로 활용하여 전체 실행 시간을 줄일 수 있습니다.
근사 알고리즘 사용: 정확한 해답을 찾는 데 시간이 너무 많이 걸리는 경우, 근사 알고리즘을 사용하여 빠르게 근사값으로 처리할수도 있습니다.
공간 복잡도가 높은 경우, 즉 알고리즘이 실행되는 데 많은 메모리를 사용하는 경우에는 다음과 같은 전략을 취해 볼 수 있습니다
데이터 구조 최적화: 사용하는 데이터 구조를 최적화하여 메모리 사용량을 줄일 수 있습니다. 예를 들어, 배열 대신 연결 리스트를 사용하거나, 트리 구조를 사용하여 데이터를 효율적으로 저장하는 등의 방법이 있습니다.
메모리 관리 기법 사용 가비지 사용: 메모리 관리 기법을 사용하여 불필요한 메모리 사용을 줄일 수 있습니다. 예를 들어, 가비지 컬렉션을 사용하여 더 이상 필요하지 않은 메모리를 자동으로 해제하거나, 메모리 풀링 기법을 사용하여 메모리를 효율적으로 재사용하는 등의 방법이 있습니다
메모리 절약 알고리즘 사용: 메모리 사용량이 적은 알고리즘을 사용하여 메모리 사용량을 줄일 수 있습니다123. 예를 들어, 동적 프로그래밍 알고리즘은 문제를 작은 부분 문제로 나누어 해결하는 방법으로, 이를 통해 메모리 사용량을 크게 줄일 수 있습니다
이분탐색이 무엇이고 시간복잡도는 어떻게 되며 그 이유는 무엇인가요?
이분 탐색은 사전에서 '바나나’라는 단어를 찾을 때, 사전을 중간에서 펼쳐서 만약 '바나나’가 중간에 위치한 단어보다 앞에 있다면, 사전의 앞부분에서 다시 중간을 찾아 '바나나’를 찿는식으로 범위를 절반씩 줄여나가며 원하는 단어를 찾는게 이분탐색 입니다.
이분탐색의 시간복잡도는 오 로그엔(0 log n)라고 불리는데, 데이터의 양에 따라 시간이 달라지지만 모든 데이터를 전부 조사하는 오 엔 이랑은 다르게 반씩 나눈다는 특성 덕분에 더 빠른 것이 오 로그 엔입니다.
스택, 큐에 대해 설명해주실 수 있을까요?
스택(Stack)은 수직으로 쌓아올린 책더미 같은 구조로, 가장 최근에 들어온 데이터가 가장 먼저 나간다는 후입선출 구조로 되있습니다. 스택은 컴퓨터에서 아주 많이 사용되는 자료구조로, “뒤로 가기” 키를 눌렀을 때 현재 수행되는 작업이 종료되고 바로 직전에 수행되던 작업이 다시 나타나는데, 이때 사용되는 것이 스택입니다1.
큐(Queue)는 원통 형태와 같은 자료구조로, 먼저 들어온 데이터가 먼저 나간다는 선입선출 구조로 되어있습니다. 큐는 은행 ATM기에서 예금을 인출하는 경우처럼 먼저 줄을 선 사람이 먼저 인출하는 상황에 이용됩니다4.
배열, 링크드리스트를 비교하여 설명해주실 수 있을까요?
배열(Array)은 마치 영화관의 좌석과 같습니다. 영화관의 좌석은 일렬로 늘어서 있고, 각 좌석은 고유한 번호를 가지고 있습니다. 이 번호를 통해 좌석을 빠르게 찾을 수 있습니다. 하지만 좌석 사이에 새로운 좌석을 추가하거나 기존 좌석을 제거하려면 다른 좌석들을 옮겨야 하므로, 이런 작업은 시간이 좀 걸립니다.
링크드 리스트(Linked List)는 열차와 비슷합니다. 열차는 여러 개의 칸으로 이루어져 있고, 각 칸은 붙어있는 다음 칸과 이전 칸을 알고 있습니다. 열차의 중간에 새로운 칸을 추가하거나 기존 칸을 제거하는 것도 쉽습니다. 하지만 칸에는 이름이 없어서 특정 칸을 찾으려면 열차의 처음부터 차례대로 찾아야 하므로, 이런 작업은 시간이 좀 걸립니다.
해시테이블의 원리, 충돌 해소 전략에 대해 설명해주실 수 있을까요?
해시테이블은 열쇠와 그에 해당하는 '상자’입니다. 각각의 열쇠는 고유한 번호인 '해시 코드’를 가지고 있습니다. 이 해시 코드는 '상자의 위치’를 알려줍니다. 이런 방법으로 해시테이블은 정보를 빠르게 찾을수 있습니다.
그런데 문제는 서로 다른 열쇠가 같은 해시 코드, 즉 '상자의 위치’를 가질 때 발생합니다. 이를 '충돌’이라고 합니다. 이 충돌을 해결하기 위한 방법이 두 가지 있습니다.
개방 주소법은 충돌이 발생하면 다른 '상자’에 값을 저장합니다.
폐쇄 주소법은 책상에 여러 서랍이 잇듯이 각 '상자’에 여러 공간을 만들어서 충돌이 발생하면 그 ‘상자’ 안의 다른 공간에 값을 넣는겁니다.
우선순위 큐의 시간복잡도는 어떻게 되며 그 이유는 무엇인지 설명해주실 수 있을까요?
우선순위 큐는
'이진 힙’이라는 구조를 사용하는데 이진 힙은 트리 형태로, 위에서부터 아래로 내려가면서 부모 노드는 자식 노드보다 항상 작거나 같은 값을 가집니다.
이런 구조 때문에, 새로운 값을 넣거나 기존 값을 빼는 데는 조금의 시간이 걸립니다. 왜냐하면 이진 힙의 구조를 유지하기 위해 값을 넣거나 뺄 때마다 트리를 재정렬해야 하기 때문입니다. 그래서 새걸 추가하거나 제거하는 시간복잡도는 크고
가장 작은 값을 찾는 시간복집도는 적습니다. 왜냐하면 가장 작은 값은 항상 트리의 맨 위, 즉 '루트’에 위치하기 때문입니다. 그래서 이 작업은 '상수 시간’이라고 합니다.
인덱스
인덱스(Index)는 데이터베이스의 테이블에 대한 검색 속도를 향상시켜주는 자료구조 입니다.
테이블의 특정 컬럼(Column)에 인덱스를 생성하면, 해당 컬럼의 값과 물리적 주소를 (key, value)의 한 쌍으로 저장합니다. 그리고 인덱스는 빠른 검색이 가능하니만 양방향 관계에선 인덱스가 적용되지 않으니 주의해야 합니다.
인덱스를 어떤 상황에 사용해야 좋은지도 설명해주세요.
데이터가 많고, 조회를 많이하며 수정을 적게할 상황에 사용하는게 좋습니다.