[C++] 객체 생성 방법 두 가지 (+ Stack과 Heap)

인트로 C++에서 객체를 생성하는 두 가지 방법에 대해서 알아보려 한다. 결론부터 말하면 각각은 서로 다른 결과를 가져오는데 하나는 객체가 힙에 다른 하나는 스택에 할당된다. 객체 생성 코드 #include using namespace std; class Orange { private: int price; public : Orange(int price) { this->price = price; cout

• format_list_bulleted C++
• · 2021. 9. 26.
• textsms

[Algorithm] 이진 탐색 (이분 탐색, Binary Search) 코드와 시간 복잡도

인트로 이진 탐색이란 정렬된 배열에서 특정 값을 찾는 탐색 알고리즘이다. 이진 탐색은 배열의 중간을 기준으로 데이터를 탐색하기 때문에 반드시 데이터가 정렬된 상태로 존재해야 한다. 이진 탐색의 시간 복잡도는 O(logN)으로 배열을 전수 조사하는 O(N)에 비하면 상대적으로 빠른 탐색 알고리즘에 속한다. O(logN)만에 값을 찾을 수 있는 이유는 중간을 기준으로 탐색 대상을 절반씩 줄여나가기 때문이다. 본 포스팅 말미에 코드와 시간 복잡도 계산법을 상세히 적어놨으니 참고하시길 바랍니다. 이진 탐색 : 개념 이진 탐색은 내가 찾고자 하는 값이 정렬된 배열의 중간 값보다 크면 중간값을 포함한 하위 값들은 탐색 대상에서 제외된다. 반대로 찾고자 하는 값이 배열의 중간 값보다 작으면 중간 값을 포함한 상위 값..

• format_list_bulleted Algorithm/탐색
• · 2021. 9. 16.
• textsms

[C, C++] Call by value, Call by reference 쉽게 이해하기

인트로 (본 포스팅은 포인터와 관련이 깊습니다.) 함수의 호출 방법은 대표적으로 Call by value(값에 의한 호출)와 Call by reference(참조에 의한 호출)가 있다. 함수 호출이란 말 그대로 정의된 함수를 호출하는 것으로 함수에 정의한 매개변수의 형태에 따라 Call by value 혹은 Call by reference인지 결정된다. 참고로 이 둘의 차이를 쉽게 이해하려면 포인터와 Stack을 어느 정도 알고 있어야 한다. Call by value Call by value란 함수 호출 시 넘기는 인자의 값이 매개변수에 복사(Copy)돼서 함수 내에서 매개변수에 직접적인 데이터 조작을 가해도 인자에 전혀 영향을 주지 않는 것이다. 여기서 값이란 주소 값이 아닌 그 자체로 유의미한 데이터..

• format_list_bulleted C++
• · 2021. 9. 11.
• textsms

[Algorithm] A* 알고리즘 : 최단 경로 탐색

✍️ 인트로 A* 알고리즘은 그래프의 탐색 알고리즘으로 주로 게임에서 플레이어를 목표지점으로 이동시킬 때 사용하는 알고리즘이다. 대표적인 그래프 탐색 알고리즘들과 A*의 차이점은 BFS는 가중치가 없는 그래프에서 최단 경로를 찾는 완전 탐색 알고리즘이며 다익스트라는 가중치 그래프에서 시작 노드를 기준으로 모든 노드까지의 최단거리를 구하는 그리디 알고리즘이다. 반면 A* 알고리즘은 가중치 그래프에서 시작 노드에서 목표 노드까지의 최단 경로만 구하려 하는 그리디 알고리즘이다. [※ 정리 ※] BFS : 가중치 없는 그래프, 시작 노드 기준으로 모든 노드의 최단 경로 구함, 완전 탐색 다익스트라 : 가중치 그래프, 시작 노드 기준으로 모든 노드의 최단 경로 구함, 그리디 알고리즘 A* : 가중치 그래프, 시작..

• format_list_bulleted Algorithm/탐색
• · 2021. 9. 3.
• textsms

[Data Structure] 우선순위 큐와 힙(Priority Queue and Heap) 이해하기

인트로 본 포스팅을 이해하기 위해선 힙 자료구조 배경지식이 필요합니다. 본 포스팅은 1)우선순위 큐 설명 2)우선순위 큐와 힙의 관계 3)구현 코드로 구성되어 있습니다. 우선순위 큐란? 큐(Queue)란 먼저 들어간 데이터가 먼저 나오는 선입 선출(First In First Out, FIFO) 구조의 자료구조를 말한다. 우선순위 큐(Priority Queue)는 일반 큐와 이름은 비슷하지만 동작하는 방식이 다르다. 우선순위 큐의 각 원소(데이터)는 저마다의 우선순위를 가지고 있으며 들어간 순서에 상관없이 높은 우선순위를 가진 원소가 순서대로 나온다는 특징이 있다. 우선순위 큐와 힙 (우선순위 큐 ≠ 힙) 당신에게 음료수 자판기를 만들라는 과제가 주어졌다. 당신은 자판기를 만들기 위한 고민을 하기 시작할 ..

• format_list_bulleted Data structure
• · 2021. 9. 2.
• textsms

[Algorithm] 다익스트라 알고리즘 : 최단 경로 탐색(1) - 배열

인트로 다익스트라 알고리즘은 그래프의 탐색 알고리즘으로 BFS가 가중치 없는 그래프의 최단경로를 찾는 알고리즘이라면 다익스트라 알고리즘은 가중치가 있는 그래프의 최단경로를 구할 때 사용된다. 참고로 다익스트라 길 찾기 알고리즘은 DFS, BFS와 마찬가지로 완전 탐색 알고리즘에 속한다. 다익스트라(Dijkstra) 이해하기 1) 아래와 같은 가중치 그래프가 있다. 0번 정점에서 시작해 5번 정점까지의 최단거리를 구해보자. 최단거리를 저장할 배열(DIST)이 다음과 같은 형태로 있다. DIST[ ∞, ∞, ∞, ∞, ∞, ∞ ] (+ 아직 최단거리를 모르니 모두 ∞로 초기화한다.) 2) 시작 정점인 "0"번 정점을 방문한다. 시작 정점인 "0"번 정점은 최단거리가 "0"이므로 DIST[ 0, ∞, ∞, ∞..

• format_list_bulleted Algorithm/탐색
• · 2021. 8. 31.
• textsms