개발하는 리프터 꽃게맨입니다.

(참고: 기본적인 구현인 '인접 행렬'을 사용해서 구현했습니다.) 서론 탐색은 우리가 관리하는 자료구조의 전체를 순회하거나 원하는 자료를 찾고자 하는 것을 뜻합니다. 자료구조를 다루는 시점에서 '탐색'은 필수적이죠. 그런데, 그래프 구조는 복잡하기에 단순하게 순회하는 것조차 힘듭니다. 일반적으로 탐색의 방법은 '깊이 우선 탐색 DFS' '너비 우선 탐색 BFS' 2가지가 존재합니다. 깊이 우선 탐색 1. 개요 깊이 우선 탐색은 말 그대로 출발점에서 가장 멀리 있는 노드(가장 깊이 있는 노드)를 도달하고자 하는 탐색방법입니다. A에서 가장 멀리 있는 노드는 F죠 그래서 A -> D -> F를 먼저 탐색하고 나머지 노드를 탐색합니다. 이런 식으로 탐색하는 이유는 '스택'의 특성 때문에 그렇습니다. 알고리즘의..

개요 그래프(Graph)는 '정점(vertex, node)'과 '간선(edge, adjacent, link)'의 집합으로 이루어진 자료구조입니다. 어떻게 보면, 하나의 노드를 가리키는 '연결리스트' 다수의 노드를 한 방향으로 가리키는 '트리'의 확장된 버전으로 이해할 수 있습니다. (문서를 찾다보면 정점 = Node = Vertex 등 용어가 혼용되고, 간선 = edge = adjacent = link 용어가 혼용됩니다. 다 알아두시길 바랍니다.) 이런 식으로 노드와 노드는 간선으로 연결됩니다. 트리, 연결리스트에 비해 현실 상황을 잘 재현하는 자료구조라고 여겨집니다. 어떻게 보면 지하철 노선도와 같은 형태를 띠고 있으며 이렇게 정보를 가지고 있는 '노드'를 간선으로 직관적으로 연결하고 '복잡한 관계'에..

https://www.acmicpc.net/problem/16928 16928번: 뱀과 사다리 게임 첫째 줄에 게임판에 있는 사다리의 수 N(1 ≤ N ≤ 15)과 뱀의 수 M(1 ≤ M ≤ 15)이 주어진다. 둘째 줄부터 N개의 줄에는 사다리의 정보를 의미하는 x, y (x < y)가 주어진다. x번 칸에 도착하면, y번 칸으 www.acmicpc.net 처음으로 문제 풀이를 하는 포스팅을 작성했는데.. 날아가니까 의지가 팍 꺾이네요 ㅎㅎ 해당 문제는 그래프 탐색 알고리즘을 통해 풀 수 있는 문제입니다. 꽤나 좋은 문제에요 백트래킹, 너비 우선 탐색 둘 다 사용할 수 있으니 시간있으면 도전해보는 것을 추천합니다.

const라는 수식어는 Constant에서 따온 것으로 수학적으로 '상수'라고 부르며 '변하지 않는 값'을 뜻합니다. 항상 변할수 있는 값인 '변수'와는 반대 개념이죠. 처음에는 '상수'라는 개념을 어디에 사용하는지 궁금했으나, 대부분 상수의 능력은 프로그램이 어느 정도 커졌을 때 빛을 발합니다. 간단하게 상수가 사용되는 예시를 보여드리겠습니다. 1. 하드 코딩 방지 하드 코딩이란 데이터를 코드 내부에 직접 입력하는 것을 뜻합니다. int main() { int arr[100]; for (int i = 0; i < 100; i++) arr[i] = 0; } 위 코드는 전혀 이상한 코드가 아닙니다. 근데, for문의 '조건 블럭'을 보면 그냥 직접 100이라고 코딩해 두었죠. 만약, 배열의 사이즈가 50으..

기본 접근권한을 제외하고는 전혀 차이가 없습니다. 접근권한을 명시하지 않을 경우 구조체는 public 클래스는 private라는 차이점만 존재하고 클래스에서 할 수 있는 모든 기능은 구조체 또한 할 수 있습니다. 컴퓨터 또한 이 둘을 구분하지 못하죠. 구조체도 class처럼 멤버 함수, 멤버 변수, 생성자, 소멸자, operater 오버로딩, 가상 함수, 상속 등.. 모든 걸 다 할 수 있습니다. 근데, 보통은 가능하다해도 구조체를 class 처럼 쓰는 사람은 별로 없습니다. 대부분의 코딩 규약에서는 둘을 엄밀하게 구분하죠, 헷갈리니까요. 개발자들은 구조체는 전통적인 C 스타일로 쓰는 것을 선호합니다. 다른 데이터 형식을 묶어서 관리하는 용도로만 쓰이죠. 멤버 함수, 가상함수, 상속 등 OOP 개념은 완..

1. 생성자란? 생성자(constructor)란 클래스에서 해당 타입의 객체를 초기화하는 방법을 정의하는 특별한 멤버 함수를 의미합니다. 생성자에서는 객체가 선언되었을 때 멤버 변수를 초기화하거나, 동적 할당을 하는 등 초기에 해줘야 할 행동들을 명시합니다. 기본적인 형태는 다음과 같습니다. /* 학생의 이름, 나이, 키를 저장하는 클래스 */ class Student { //참고: class의 기본적인 접근 제어자는 'private' 입니다. //생성자는 무조건적으로 public으로 지정한 뒤 정의하도록 합니다. public: Student() {} private: string_name; int_age; float_height; }; 위 형태처럼 인자를 아무것도 넣지 않은 상태의 생성자를 '기본 생성자..

malloc과 new 둘 다 동적 메모리 할당, 힙 메모리의 사용을 위해 호출하는 명령어입니다. 언뜻 보기에는 둘 다 똑같은 명령어 같고, 동적 메모리 할당할 때 malloc은 C에서 쓰고 new는 C++에서 쓰는 명령어다! 라고 이해하시는 분들도 많습니다. 간단하게 두 개의 공통점과 차이점, 예시를 알아보도록 하겠습니다. 1. 공통점 - 동적 메모리를 할당한다. - 지정된 크기의 메모리 블록을 할당하고, 시작 주소의 포인터를 반환한다. - 명시적으로 해제를 해줘야 한다. 2. malloc의 특징 /* malloc의 기본 형식 */ #include void *malloc(size_t size); - malloc은 void* 를 반환한다. 그래서 형변환 캐스팅이 필수적입니다. - size를 바이트 단위로 ..

📕 개요그리디 알고리즘은 '욕심쟁이 알고리즘'이라는 별칭을 가지고 있습니다. 이는 '지금 이 순간 최적의 답을 선택하여, 전체 문제를 해결하자!'라는 아이디어로부터 출발합니다. 간단한 예시를 들어보겠습니다. 서울에서 부산으로 가고자 하는데, 무조건 대전, 대구를 경유해서 가야 한다고 가정해 보겠습니다. 어떻게 해야 가장 빠르게 부산에 도착할 수 있을까요? 서울 ~ 대전까지 가장 빠르게 도달하는 시간 + 대전 ~ 대구까지 가장 빠르게 도달하는 시간 + 대구 ~ 부산까지 가장 빠르게 도달하는 시간 = 서울 ~ 부산까지 가장 빠르게 도달하는 시간 일 겁니다. 그때그때 최적의 답을 선택하고, 그것을 모아서 전체 문제에 대한 해답을 찾고자 합니다. 그러나, 그리디 알고리즘이 항상 최적의 결과를 도출하는 것은 아닙..

📕 개요 RAII는 C++ 에서 메모리 누수를 막기위해 탄생한 '디자인 패턴'입니다. Resource Acquisition Is Initialization 줄여서 RAII라고 부릅니다. '자원의 할당은 객체 초기화시, 자원의 반환은 객체 소멸시한다.' 라는 원칙이라고 이해하시면 되겠습니다. 자원의 할당은 생성자에서 보장해주고 자원의 반환은 소멸자에서 보장해주는 것이죠. C++에서 '힙(heap)' 메모리를 사용하고자 할 때, 우리는 직접 자원을 할당하고 직접 해제해야 합니다. //힙 메모리를 할당 int* number = new int; //number 포인터가 가리키는 힙 메모리 할당 해제 delete number; 그런데 조금 큰 프로그램을 개발하는 과정에서 필히 발생하는 것이 '메모리 누수' 문제죠..

참고: https://powerclabman.tistory.com/13 [C++/알고리즘] 퀵 정렬 (Quick Sort) 참고: https://powerclabman.tistory.com/12 [C++/알고리즘] 분할정복 (Divide and Conquer) + 병합정렬 (Merge Sort) 📕 개요 '분할 정복 알고리즘'이란, 엄청나게 크고 방대한 문제를 해결할 수 있는 단위까지 쪼개서 powerclabman.tistory.com 이번 글은 퀵정렬을 모르면 이해하기 힘듭니다. 📕 문제 N 사이즈의 정수배열 arr 이 존재할 때 배열 arr에서 k번 째로 작은 수를 선택해라 예시) N = 7 arr = {5, 9, 3, 7, 11, 2, 0} k = 4 일 때, 결과값은 5 설명) arr을 오름차순 ..