CS

참고 링크i 번째 값을 탐색한 뒤의 i+1이 정해지지 않은 구조를 의미그래프점들, 그리고 점들을 연결하는 선들만 이루어진 형태이때 점을 정점(vertex), 선을 간선(edge)이라고 부름인접 행렬 :  O(v*e)인접 리스트 : O(v+e)관련 용어정점(Vertex)연결점, 여러 가지 특성을 가질 수 있는 객체어떤 객체도 정점이 될 수 있음고립 정점간선이 하나도 연결되지 않은 외톨이 정점간선(Edge)두 정점을 연결하는 연결선, 두 정점간의 관계단방향 간선단방향으로만 이동 가능한 간선. 이동이 가능한 방향으로 화살표를 그림양방향 간선양방향으로 모두 이동이 가능한 간선이다. 양쪽 화살표를 사용해도 되지만, 양방향 그래프에서는 모든 간선이 양방향 간선이므로 화살표 대신 선분으로 표현자가 간선자기 자신을 연..

참고 링크선형구조로 된 자료를 탐색하는 방법. 보통 어떤 값이 어디에 있는지 알아내는 것이 목적순차 탐색시작점 부터 순차적으로 탐색하는 것. 전부 탐색한다고 생각할 시에, 연산량은 O(n)이다.이분탐색특수한 상황에서 순차 탐색보다 좀 더 빠른 속도를 기대할 수 있는 알고리즘연산량은 O(log N)가운데에서 시작해서 매번 일정한 조건에 따라 어떤 방향의 가운데 값으로 탐색할 지 결정하는 알고리즘이때 가운데 값이랑 평균이 아니고 중간 값 이를 위해서는 정렬이 되어있어야한다

참고 링크한 종류의 데이터가 선처럼 길게 나열된 자료 구조랜덤 접근 가능모든 자료에 O(1)으로 접근이 보장되는 자료 구조들배열해시해시 함수에 키값을 넣어 주소값을 얻고, 그 주소에 위치한 버킷에 저장된 데이터를 가져오는 방식을 사용한다언제나 O(1)가 보장되는 것은 아님(파이선의 해시는 딕셔너리(dictionary)라고 부른다)랜덤 접근 불가능모든 자료에 O(1)으로 접근이 보장되지 않는 자료구조들이다.스택(Stack)먼저 들어간 자료가 나중에 나오는 자료구조 (LIFO)자료를 넣는 push자료를 빼는 pop큐(Queue)먼저 들어간 자료가 먼저 나오는 구조 (FIFO)자료를 넣는 Enqueue함수와 자료를 빼내는 Dequeue 함수를 가짐연결 리스트로 구현한다 LinkedList데크(Deque)스택과..

참고 링크참고 책시간복잡도알고리즘의 성능을 나타내는 지표입력 크기에 대한 연산 횟수의 상한을 의미시간복잡도는 낮으면 낮을 수록 좋음모든 알고리즘은 입력되는 데이터의 크기 또는 갯수에 따라 이의 계산 횟수 수행 시간이 크게 달라지게 된다입력받은 데이터의 크기에 따른 알고리즘의 수행시간의 변화가 시간복잡도시간복잡도가 더 큰 알고리즘들은 더 큰, 혹은 많은 데이터를 처리할 때 훨씬 더 오랜 시간이 걸리게 되지만계산횟수의 정확한 측정이 어렵기 때문에, 보통 Big O 표기법이라는 것을 이용해 표시Big O 표기법2n+7번 계산하는 알고리즘일 때 n이 커지면 2n과 사실상 차이가 없다그러므로O(2n+7) = O(2n)대략 O표기법은 상수만큼의 시간 차이는 무시하는 것이다계산 횟수에 붙은 상수는 별로 중요하지 않다..