유진's 공부로그

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

브루트 포스 (brute force) 가능한 모든 조합을 다 탐색 (답이 나올 때까지) 답을 무조건 찾을 수는 있으나, 답을 찾는 데에 비용이 너무 크다는 단점이 있음. (시간 복잡도가 크다. 탐색해야 할 것이 많다면 코테에서 타임아웃이 뜰 것) 대체적으로 완전 탐색의 시간 복잡도는 O(n!) or O(2^n) Ex) 리트코드 15번 3Sum 합이 0이 되는 3개의 수의 조합을 찾는다. 이때 brute force는 가장 간단한 방법. but, 3개이므로 배열에서 3번의 loop을 돌아야 하기 때문에 (double nested loop) 시간 복잡도가 O(n^3)임. 따라서 매우 비효율적인 방법이라고 할 수 있다. 또한 코드 가독성 또한 떨어짐. (아래 참고) for i in range(len(nums)-..

그래프 : 연결되어 있는 객체 간의 관계를 표현하는 비선형 자료구조 가장 일반적인 자료구조의 형태로, tree도 그래프의 특수한 경우이다. 예를 들면, 전기회로의 소자 간 연결 상태나 혹은 운영체제의 프로세스와 자원 관계 또한 그래프로 표현이 가능하다. 그래프의 정의 그래프 G는 (V,E)로 표시하며, 이때 V는 정점 vertex의 집합을 E는 간선 edge의 집합을 의미함. - vertex (정점) : 여러 가지 특성을 가질 수 있는 객체를 의미함. 노드(node)라고도 함. - edge (간선) : 정점들 간의 관계를 의미. link라고도 함. 그래프의 종류 1) 무향 그래프 (undirected graph) : 무향 에지는 양방향의 의미임. 예컨대 조합(combination)처럼 (A,B) = (B..