Step-by-Step

특정 구간에 있는 N개의 수들의 합을 구하는 경우 O(N)의 시간 복잡도가 생긴다. 얼핏 보면 여기서 더 좋은 방법이 있을까? 싶지만, 있다. (이번에 알게 되었음..) 시간을 절약하기 위해서는 특정 구간을 미리 알고 있으면 좋은데, 이때 세그먼트 트리를 사용한다. ※예를들어 0~4번째 수의 합과 5~9번째 수의 합을 알고 있다고 가정하자. 4~9의 합을 구하려면 원래는 6개의 숫자를 모두 꺼내서 더하는 6번의 작업을 거쳐야 하는데, 해당 방법을 사용하면 4번째 숫자와 5~8번째 합을 꺼내서 더하는 작업 2번만 수행하면 된다. 세그먼트 트리 (Segment Tree) 일정 간격에 대한 정보를 저장하는데 사용하는 트리 데이터 구조 특정 구간의 합을 구하는 작업시 유용하게 사용됨 세그먼트 트리 형태 1. F..

큐(Queue) FIFO(First In First Out) 특성을 가진 자료구조 데이터가 들어오는 위치는 가장 뒤로 후단(Rear or Back)이라 하고, 데이터가 나가는 위치는 가장 앞인 전단(Front)이다 스택에서는 삽입, 삭제 모두 top을 통해서 이루어지는데, 큐에서는 front에서 삭제, rear에서 삽입을 담당한다 큐의 추상자료형(Abstract Data Type; ADT) - 입력 : 엔큐(Enqueue) - 출력 : 디큐(Dequeue) ※ 간혹 스택과 동일하게 Push,Pop을 쓰기도 하고, Push,Pull을 사용하기도 한다 큐의 종류 1. 선형 큐 - 1차원 배열을 정의한다 - 삽입, 삭제를 위한 변수인 front와 rear을 만든다 - front와 rear의 초기값은 -1이다 ..

순환(Recursion) 어떤 알고리즘이나 함수가 자기 자신을 호출하여 문제를 해결하는 프로그래밍 기법 가장 대표적인 예시로 정수의 팩토리얼을 구현한 함수가 있다 int factorial(int n) { if(n

스택(Stack) LIFO(Last In First Out) 특성을 가진 자료구조 메모리에 들어오는 데이터 위치가 메모리 말단(Top Pointer)이고 쓰기 위해 내보내는 데이터 역시 메모리 말단을 거친다 스택의 추상자료형(Abstract Data Type; ADT) - 입력연산 : 푸시(Push) - 출력연산 : 팝(Pop) - 조회연산 : 피크(Peek) ※ 조회연산은 탑 포인터가 가리키는 데이터를 조회만 할 뿐 탑의 순번(인덱스)은 변화시키지 않는다 스택의 Push, Pop 과정 1. Push - 먼저 Top Pointer의 값을 증가 시킨 후, 증가시킨 Top의 위치에 데이터를 넣는다 2. Pop - 먼저 데이터를 꺼낼 Top의 위치를 다른 변수(인덱스)에 별도로 저장한 후, Top의 위치를 감..

데이터(data) 프로그램에서 데이터(data)는 처리의 대상이 되는 모든 것 데이터 타입(data type) 데이터의 집합과 데이터에 적용할 수 있는 연산의 집합 즉 데이터 타입 = 객체(Object) + 객체 간의 연산(Operation) 이 된다 ※ 예로 C언어에는 int라는 데이터 타입을 제공하는데, int 데이터 타입에서 데이터는 "정수의 집합"이고, 연산은 "정수 간 연산"을 의미한다 추상 데이터 타입(abstract data type; ADT) 새로운 데이터 타입을 추상적,수학적으로 정의한 것 자료 자체의 형태와 그 자료에 관계된 연산들을 "수학적으로만" 정의한 것 데이터 타입의 정의가 그 데이터 타입의 구현으로부터 분리된 데이터 타입 ※ 즉 추상 데이터 타입에서 데이터나 연산이 무엇(wha..

그동안 까먹었던 내용을 복습도 하고, 기본을 다질 겸책을 펼치게 되었다 공부한 내용들을 잊지 않게 블로그에 차근차근 정리하기로 했다! 자료구조(Data Structure) 프로그램에서 자료들을 정리하는 여러가지 구조들 프로그래밍에서 데이터를 구조적으로 표현하는 방식과 이를 구현하는 데 필요한 알고리즘에 대해 논하는 기초 이론 ※ 컴퓨터의 대부분 프로그램에서 자료(data)를 처리하고 있고, 자료들은 자료 구조(data structure)를 사용하여 표현되고 저장된다 알고리즘(Algorithm) 컴퓨터로 문제를 해결하기 위한 단계적인 절차나 방법 문제와 컴퓨터가 주어진 상태에서 문제를 해결하는 방법을 정밀하게 장치가 이해할 수 있는 언어로 기술한 것 좁은 의미로 자료구조 내에서 기본적인 연산을 하기 위한 ..

그래프(Graph) 정점(Vertex)와 간선(Edge)로 구성된 자료구조 그래프 G는 꼭짓점의 집합 V와 변의 집합 E의 순서쌍으로 정의된다 G = ( V , E ) 그래프 용어 정점(vetex) : 노드(node)라고 불리며 데이터가 저장되는 장소 간선(edge) : 링크, arcs 라고 불리며 노드간의 관계를 나타냄 인접 정점(adjacent vertex) : 간선에 의해 직접 연결된 정점 정점의 차수(degree) : 무방향 그래프에서 하나의 정점에 인접한 정점의 수 진입 차수(in-degree) : 방향 그래프에서 외부에서 오는 간선의 수 진출 차수(out-degree) : 방향 그래프에서 외부로 향하는 간선의 수 단순 경로(simple path) : 경로 중 반복되는 정점이 없는 경우 사이클(..