그래프 용도 용어 정리 기본 심화 구현 인접 행렬 인접 리스트 비교 연산 분류 방향성에 따른 분류 연결에 따른 분류 사이클에 따른 분류 특수한 그래프 탐색 도출된 문제들 관련 알고리즘 참고 그래프 그래프란 '노드'와 노드를 연결하는 '간선'으로 이루어진 자료구조이다. 지금까지의 살펴본 자료구조들(리스트, 스택, 큐 등)과는 달리 그래프는 비선형 자료구조 이다. 용도 그래프는 일상생활에서 연결되어있는 객체 간의 관계를 표현할 때 사용된다. 예로 지도나 지하철 노선도, 전기회로, 도로 등을 들 수 있다. 또한 컴퓨터 세부전공에서는 통신 네트워크 분야에서도 쓰이며, 논리회로를 설계하고 분석하는 데에도 사용된다. 최근에는 웹사이트의 링크 연결(Page Rank)이나 SNS 상의 친구관계를 표현하는 데에도 사용되..

서론 자료구조 자료구조는 컴퓨터에서 자료를 정리하고 조직화하는 다양한 구조를 말한다. 프로그램은 자료구조와 알고리즘으로 이루어져있기 때문에, 자료구조는 반드시 공부해야하는 분야이다. 자료구조는 먼저 단순 자료구조와 복합 자료구조로 구분되고, 복합 자료구조에는 선형 구조와 비선형 구조가 있다. 순차적으로 살펴보자. 배열, 문자열 연결 리스트 스택, 큐, 덱 그래프 트리 힙 구조체

스택 특징 용도 연산 삽입 삭제 접근 구현 큐 용도 종류 연산 삽입 삭제 접근 구현 우선순위 큐 덱 용도 구현 스택 스택은 LIFO(Last-In First-Out), 즉 후입선출의 자료구조이다. 구조는 다음과 같은 형태이며, 접시처럼 쌓여서 이후에 삽입된 데이터가 먼저 빠져나가도록 되어있다. top 변수는 가장 최근에 들어온 요소를 가리키며 스택이 비어있으면 -1이다. 특징 LIFO 내부 요소를 확인할 방법이 pop 말고는 없다. 용도 입력의 역순이 필요할 때 스택을 주로 사용하며, 함수의 호출에서 복귀 주소를 기억하기 위해서 시스템 스택이 사용되기도 한다. 또한 괄호 검사, 계산기, 미로 탐색 등의 경우에 스택이 유용하게 사용된다. 계산기에서 중위 표기식(infix)을 후위 표기식(postfix)으로..

연결 리스트 리스트란? 정의 배열과의 비교 연산 삽입 삭제 접근 종류 / 구현 리스트란? 리스트는 순서를 가진 항목들의 모임이다. 이를 나타내는 대표적인 방법은 2가지가 있는데, 하나는 배열을 이용하는 방법이고 나머지 하나는 연결리스트를 이용하는 방법이다. 배열을 이용한 리스트를 선형리스트라고 하는데 구현 자체는 간단하고 임의접근이 가능하지만, 삽입 / 삭제 연산 시 다른 요소들의 이동이 불가피하므로 오버헤드가 크다. 연결리스트는 구현이 복잡하고 순차접근이 필요하지만 삽입, 삭제가 효율적이다. 정의 연결리스트란 아래의 그림과 같이 데이터와 링크로 이루어진 노드로 구성되어있다. 링크는 다음 요소를 가리키는 포인터이다. 연결리스트의 처음에는 헤드 포인터가 헤드 노드를 가리키고 있으며, 마지막 노드의 링크는 ..

목차 배열 선언 초기화 접근 다차원 배열 희소 행렬 표현 주소와 포인터 포인터 특징 제약 동적 메모리 할당 동적 배열(vector) 문자열 선언 초기화 함수 배열 / 문자열 배열 배열이란 단일 식별자로 _같은 자료형_의 여러 변수를 접근할 수 있게 해주는 자료구조이다. 선언 c++에서는 int arr[3];와 같이 자료형 배열이름[배열 길이];로 변수를 선언한다. 이 때, 대괄호 내의 요소의 갯수는 '컴파일 타임 상수'여야한다. 소스코드를 컴파일할 때, 고정 배열의 길이를 알아야하기 때문이다. 따라서 매크로 기호 상수 (ex_ #define ARRAY_LEN 5)나 열거자(ex_enum A{ARRAY_LEN = 5})는 배열의 길이로 사용할 수 있다. const 또한 컴파일 시 고정되는 상수이므로 사용가..

Mutex와의 비교 코드 #include #include #include #include #include #include using namespace std; class Node { public: int value; Node* next; Node() : value(0) { next = NULL; } Node(int k_value) { next = NULL; value = k_value; } }; int node_n; //random 구현 random_device rd; mt19937 gen(rd()); uniform_int_distribution dis(0, 10); //출력을 위한 mutex mutex mut; class LFStack { private: Node * head; public: void ..

컨테이너에 기본값 채우기 배열 1차원 배열 기존 코드 #include using namespace std; int main() { int arr[3]; for (int i = 0; i < 3; i++) { cout

소수 찾기 프로그램 방법 n-1까지 구하기 O(n) n-1 까지 소수를 모두 구하는 다이나믹 프로그래밍으로 알고리즘 짜기 소수 배열을 만들어서 소수 배열만 돌면서 나누어지는지 판단 O(n) 소수 배열을 만드는 데에 O(n) => 메리트 없음 루트 n까지 돌리면서 짝수 제외하기 O(sqrt(n)) 조건 추가 몇 개의 소수( 3, 5 )를 가지고 해당 수의 배수이면 뛰어넘기 3, 5 계산 시 나누어떨어지지 않았으면 해당 수의 배수에도 나누어떨어지지 않음 구현 시 주의 해당 수가 3으로 나누어떨어지는지, 5로 나누어떨어지는지를 계산하려면 모듈러 연산을 사용해야하는데 시간이 오래 걸림 변수 하나씩 지정하고 1씩 더하는 방법으로 구성 3과 5의 공배수가 나오면 먼저 거치는 3의 if문에서 continue 됨으로 ..