알루 코딩

오늘은 자료구조 설계에 대한 흥미로운 문제를 가져왔습니다. 겉으로 봤을 때는 해당 문제가 쉽게 풀릴 것입니다. 즉, O(1)이 아니고서는 문제 구현이 쉬울 것 입니다. 하지만, 이 문제에서는 O(1)의 시간 복잡도로 요소를 삽입, 삭제 및 무작위로 가져오는 자료 구조를 구현하는 것이 핵심입니다. 저는 이 문제를 처음 시도했을 때, 파이썬의 'set'자료구조를 사용했습니다. 'set'을 사용하면 삽입과 삭제는 평균적으로 O(1)의 시간 복잡도를 가지기 때문이죠.(자세한 이유는 이 링크를 참조하세요) 하지만, 문제는 getRandom() 메소드에 있었습니다. rand()와 같은 함수는 해시 집합에서 사용할 수 없기 때문에, 'set'을 'list'로 변환하는 과정이 필요합니다. 이 때, O(n) 시간이 걸리..

한 번 문제를 이해해봅시다. 입력값으로 주어진 asteroids 배열은 소행성 배열입니다. 이 소행성은 양수값을 가질 수도 있고, 음수값을 가질 수도 있습니다. 양수값을 가진 소행성은 오른쪽으로 움직이고, 음수값을 가진 소행성은 왼쪽으로 움직입니다. 모든 소행성은 크기에 관계없이 같은 속도로 움직이기 때문에, 추월, 정지 등의 사건이 발생하지 않습니다. 두 소행성이 충돌했을 때는, 소행성의 크기의 절댓값에 따라서 소행성이 사라집니다. 예를 들어, '2'의 소행성과 '-5'의 소행성이 충돌했다면, '-5'의 소행성이 더 절댓값이 크기 때문에 '2'의 소행성이 없어지고, '-5'의 소행성은 계속해서 움직였던 방향대로 지나갑니다. 이 때, 두 소행성의 크기의 절댓값이 같다면, 두 소행성이 충돌했을 때는 두 소..

리트코드에서의 1번문제입니다. 문제를 설명해보자면, 입력값으로 nums 라는 숫자배열이 주어집니다. 그리고 target값도 입력값으로 주어지는데요, nums배열에서 두 숫자를 더해 target을 만들 수 있다면, 해당 두 숫자의 인덱스 값을 배열 형태로 출력하는 문제입니다. 문제 자체는 비교적 간단한 문제입니다만, 이 문제를 어떻게 효율적으로 풀어야 할지는 고민해봐야 할 부분입니다. 해당 문제를 직관적으로 풀자면 for문을 두 번 돌면 됩니다. 대략적인 코드는 아래와 같겠죠. for i in range(len(nums)): for j in range(i+1,len(nums)): if (nums[i] + nums[j]) == target: return [i,j] 하지만, 위와 같이 푼다면, 이미 시간복잡도..

코딩 테스트 문제를 풀 때, 시간과 메모리를 측정하는 방법을 알아보자! 파이썬에서는 프로그램 수행 시간과 메모리 사용량을 측정할 수 있다. 문제를 풀면서, 자신이 제대로 알고리즘을 작성하고 있는지 알아야 하기 때문이다. 몇몇 기업은 코딩 테스트를 볼 때, 제출 횟수를 제한 하기 때문에 시간과 메모리를 중간에 체크하는 법을 알면 문제를 옳은 알고리즘으로 풀었는지 미리 알 수 있을 것이다. 아래는 특정한 프로그램의 수행 시간을 측정하는 소스코이다. import time start_time = time.time() # 측정 시작 # 프로그램 소스코드 ~~~~ end_time = time.time() # 측정 종료 print("time : ", end_time - start_time) # 수행시간 출력 예를 들..

복잡도(Complexity) 시간 복잡도(Time Complexity) : 특정한 크기의 입력에 대하여 알고리즘이 얼마나 오래 걸리는지를 의미 (알고리즘을 위해 필요한 연산의 횟수) 공간 복잡도(Space Complexity) : 특정한 크기의 입력에 대하여 알고리즘이 얼마나 많은 메모리를 차지하는지를 의미 (알고리즘을 위해 필요한 메모리의 양) 효율적인 알고리즘을 사용한다고 했을 때, 보통 시간 복잡도와 공간 복잡도는 일종의 Trade off 관계가 성립한다. 메모리를 조금 더 많이 사용하는 대신에 반복되는 연산을 생략하거나 더 많은 정보를 관리하면서 계산의 복잡도를 줄일 수 있다. 이 때, 메모리를 더 소모하는 대신에 얻을 수 있는 시간적 이점이 매우 큰 경우가 종종 있다. 실제로 메모리를 더 많이 ..