유진's 공부로그

런너(Runner) 기법 연결 리스트 순회 시 2개의 포인터를 동시에 사용하는 기법. 한 포인터가 다른 포인터보다 앞서게 하여 병합 지점이나 중간 위치, 길이 등을 판별할 때 유용하게 사용할 수 있다. 연결리스트의 경우 중간 위치나 길이를 파악하는 데에 배열에 비해 상대적으로 복잡하다. (전체를 다 탐색해야 하므로 O(n)의 시간이 소요됨) 따라서 fast runner와 slow runner 간의 step을 2배 차이를 두는 식으로 (ex. fast, slow = 2,1) 지정한 후 fast runner가 리스트의 끝지점에 도착하면 slow는 정확히 리스트의 중간 지점에 도달하게 된다. 중간위치를 찾아냄으로써 값 비교 (palindrome linked list 문제), 뒤집기를 시도하는 등의 연결 리스트..

1. (정적)배열 : 연속된, 정해진 크기의 메모리 공간을 할당. 같은 타입의 원소만을 담을 수 있음. (정해진 크기의 메모리 공간을 할당하고, 이를 원소 타입, 원소 개수에 맞춰서 분할하기 때문) 또한 한 번 생성한 배열은 크기 변경이 불가능하다. 배열의 장점은 어느 위치에나 O(1)에 조회가 가능하다는 점이다. (배열 시작 주소 + 원소 타입에 따른 바이트 크기 * 원소 인덱스)로 해당 배열 원소 값의 주소 계산 및 메모리 접근이 가능하기 때문. (배열 원소 개수에 독립적) 그러나, 원소의 삭제나 삽입 등의 작업은 최악의 경우 O(n)의 시간복잡도를 갖는다. 예를 들어 원소의 가장 첫번째 원소를 삭제한다고 가정하면 나머지 모든 원소를 하나씩 override해야 하기 때문에 (당겨와야 하기 때문에) n..