1. 다익스트라 알고리즘이란? 알고리즘을 공부하다보면 그래프를 공부하는 것이 굉장히 중요하다는 것을 자주 느낄 것이다. 그 중에서도 DFS, BFS와 더불어 가장 기초적이면서도 중요하게 생각되는 것이 최단경로 알고리즘일 것이고, 그 중에서도 다익스트라 알고리즘은 한 노드에서 다른 노드로의 최단 거리를 계산하는 중요한 알고리즘이다. 2. 간단하게 구현하기 소제목이 '간단하게 구현하기'인 만큼 문제가 있는 코드라고 생각할 지도 모르겠다. 실제로 아래와 같은 구현은 시간복잡도에서 조금은 '복잡한 구현' 보다 불리한 면이 있다. 하지만 다익스트라를 처음 공부할 때, 이해를 위해서 이와 같은 방법을 꼭 알고 있는 것이 좋다고 생각한다. 이것이 '간단하게 구현하기'인 이유는 3번에서 서술하겠다. 다른 알고리즘들이 ..

1. DFS / BFS 란? DFS와 BFS는 그래프에서 사용하는 대표적인 탐색 알고리즘이다. 방법의 차이는 있지만, 두 알고리즘 모두 한 노드에서부터 시작해 그 노드에 연결된 모든 노드를 탐색한다. DFS와 BFS가 무엇인지, 사용되는 기술은 무엇인지 알아보자. (1) DFS DFS는 'Depth First Search' 의 줄임말이다. 해석하자면 '깊이 우선 탐색' 이라고 할 수 있겠다. 즉, 한 노드를 집중적으로 파고들어, 그 노드에 연결된 노드를 깊숙이 들어가보는 것이다. 그렇기 때문에 DFS를 위해서는 스택이 사용된다. DFS를 C++과 STL로 구현한 코드는 다음과 같다. #include #include using namespace std; void DFS(vector v, int start)..

1. 우선순위 큐란 무엇인가? '선입선출(FIFO, First In First Out)'으로 대변되는 큐 자료형의 기본적인 기능에, 우선순위가 높은 자료형을 가장 먼저 삽입 및 삭제할 수 있게 한 자료형이다. 이러한 우선순위 큐는 운영체제 스케줄링 등 다양한 곳에서 사용된다. 2. C++ 에서의 사용방법 큐가 그렇듯이, C++에서는 STL을 통해서 사용자가 간편하게 정의하고 사용할 수 있다. 기본적인 사용 방법은 다음과 같다. #include priority_queue pq; pq.push(5); pq.push(8); pq.pop(); pq.pop(); priority_queue 이는 우선순위 큐의 선언이다. T는 원하는 자료형 및 클래스, Container는 vector와 같은 컨테이너, Compare..

1. 일반적인 입력받기 C++을 처음 접하면 다음과 같은 방식으로 사용자로부터 입력을 받는다. char buf[100]; std::cin >> buf; 이렇게 입력받으면 사용자가 입력한 내용이 buf로 들어가게 된다. 하지만 공백이 포함되어 있는 경우, 예를 들어 "Hi, my name is Steve."라고 입력한다면 중간에 삽입된 공백으로 인해 Hi, 까지의 내용만 입력된다. 이러한 현상을 해결하기 위해 입력 라인 전체를 변수에 입력할 수 있는 방법이 있다. 2. 사용법 간단하다. 예를 들어서 100자리를 입력받고 싶다면 다음과 같이 사용하면 된다. char buf[100]; std::cin.getline(buf, 100); 이렇게 사용하면 공백이 포함되어 있어도 전체 내용을 입력받을 수 있다.

C++로 작성한 다양한 스크립트를 구경하다가 'auto' 라는 키워드가 있는 것을 발견하였다. 지금은 C++을 공부하고 있는 단계이기 때문에 이러한 키워드를 정리하는 것이 도움이 될 것이라고 생각한다. 1. auto 키워드란? 우리가 C++에서 변수를 선언할 때 주로 다음과 같은 자료형을 사용한다. bool : 1바이트, 1(true) / 0(false)를 가짐 char : 1바이트, 한 글자를 저장할 수 있음 int : 4바이트, 정수형 float : 4바이트, 실수형 이렇게 자료형을 미리 선언해서 사용하면 계산, 출력 등의 정확한 사용이 가능하다. 하지만 이마저도 귀찮을 때가 있는데, 이럴 때에는 auto 키워드를 사용해보는 것이 좋다. 즉, auto 키워드는 사용자가 자료형을 직접 지정하지 않아도 ..

1. C/C++ 입출력 속도 차이? C에서 사용하는 입출력 함수는 다음과 같은 것들이 있다. 이러한 함수는 속도는 빠르지만 사용하기에 불편하거나 귀찮은 것이 단점이다. printf scanf gets putchar 반면 C++에서 제공하는 cin, cout과 같은 함수는 사용이 쉽지만 입출력 속도가 C의 기본 함수만 못하다. 그렇기 때문에 C++에서 빠르고 편리한 입출력을 위해서는 입출력 속도를 향상시켜줘야 할 필요가 있다. 특히, 알고리즘 문제 풀이와 같은 경우에서는 많은 입출력으로 인해서 시간지연이 발생할 수 있기 때문에, 이러한 테크닉은 사용하는 것이 좋다. 2. 함수의 설명 cin.tie(NULL) 이 함수는 cin과 cout의 연결(tie)을 끊어주는 함수이다. 다시 말해서, cin과 cout ..