geminanolja 님의 블로그

**이분탐색(Binary Search)**은 정렬된 배열에서 탐색 범위를 절반씩 줄여나가는 방식으로 특정 값을 찾는 알고리즘시간 복잡도는 O(log N)**이며, 이진탐색이라고도 부름문제에서 주어진 배열의 크기가 너무 크거나 어떤 값을 찾아야 하는 로직이 있을 때, 해당 배열을 정렬하고 이분탐색을 사용하면 **O(log N)**의 시간복잡도로 효율적으로 값을 찾을 수 있다이분탐색의 동작 원리초기 설정:배열의 가장 왼쪽 인덱스 left와 가장 오른쪽 인덱스 right를 설정중간값 계산:현재 배열의 중간 인덱스 mid를 계산합니다.중간 인덱스는 mid = (left + right) / 2로 계산됩니다.비교:목표값과 중간값이 같을 때:중간 인덱스 mid에 위치한 값이 목표값(target)과 일치하면 탐색을 종..

자료구조&알고리즘/C++ 2025. 1. 22. 11:09

문제를 해결할 때 각 단계에서 그 순간에 최선이라고 생각되는 선택을 하는 방식이 과정에서 얻은 선택들이 모여 전체 문제에 대한 최적의 해를 구하는알고리즘 그리디 알고리즘은 지역적최적해(Local Optimal Solution)를 찾는 과정 에서, 이를 모아 전역적 최적해(Global Optimal Solution)를 구하는 방식  다만, 모든 경우에 전역 최적해를 보장하지는않음  예를들어12100원짜리물건을구매할때내가가지고있는돈이다음과같다고해봅시다.10000원 5개 5000원 5개 1000원 5개 100원 5개 라고 했을때 가장지폐를적게내는(동전도지폐라고취급)경우의수는무엇일까요? 바로 10000원 1개. 1000원 2개. 100원 1개.를 내는 것입니다. 이렇게 우리는 가장 큰 것부터 내면 최적해라는것을..

자료구조&알고리즘/C++ 2025. 1. 21. 22:53

배열이나 리스트와 같은 선형 자료 구조에서 두 개의 포인터를 사용하여 정렬된 배열에서 특정 조건을 만족하는 부분배열또는 원하는 값을 찾는 등의 문제를 풀 때 주로 사용하는 알고리즘! 보통 정렬된 배열에서 두 수의 합찾기,연속된 부분 배열의 합 찾기 에사용투포인터알고리즘은두개의포인터를사용●  왼쪽포인터(LeftPointer) : 배열의시작지점에서시작하여오른쪽으로이동● 오른쪽포인터(Right Pointer):배열의끝지점에서시작하여왼쪽으로이동 또는 왼쪽포인터와함께배열의시작지점에서시작하여오른쪽으로이동 #include // C++ 표준 라이브러리 헤더using namespace std;int n, ret, x; // n: 배열 크기, ret: 조건을 만족하는 쌍의 개수, x: 목표 합int main() { ..

자료구조&알고리즘/C++ 2025. 1. 21. 14:29

postOrder, preOrder, inOrder #include // C++ 표준 라이브러리 사용using namespace std;vector adj[1004]; // 트리의 인접 리스트 표현 (1-based index)int visited[1004]; // 노드 방문 여부를 저장하는 배열// **후위 순회 (PostOrder)**void postOrder(int here) { if (visited[here] == 0) { // 현재 노드가 방문되지 않았다면 if (adj[here].size() == 1) // 자식이 1개인 경우 postOrder(adj[here][0]); // 왼쪽 자식을 순회 if (adj[here].size() == ..

자료구조&알고리즘/C++ 2025. 1. 21. 10:41

인접 리스트는 메모리 사용이 효율적이며, 노드와 연결된 간선만 저장합니다.인접 행렬은 구현이 간단하며 노드 간의 연결 여부를 빠르게 확인할 수 있지만, 메모리 사용량이 많아질 수 있습니다.두 구현 모두 DFS를 수행하며, 출력 결과는 동일합니다.  1. 인접 리스트#include #include using namespace std;void DFS(int node, vector>& adjList, vector& visited) { visited[node] = true; cout > n >> m; vector> adjList(n + 1); // 인접 리스트 (1-based index) for (int i = 0; i > u >> v; adjList[u].push_back(v..

자료구조&알고리즘/C++ 2025. 1. 20. 21:26

기본 아이디어현재 상태에서 **가장 좋은 선택(최적의 선택)** 선택이 선택이 이후 문제에 영향을 미칠지 고민하지 않고, 현재 문제만 고려이렇게 탐욕적인 선택을 반복하면 전체 문제를 해결할 수 있음그리디 알고리즘의 특징탐욕적 선택 속성 (Greedy Choice Property):현재의 탐욕적 선택이 나중에 영향을 미치지 않고, 전체 문제의 최적 해를 보장합니다.부분 최적해 (Optimal Substructure):부분 문제의 최적해가 전체 문제의 최적해로 이어질 수 있어야 합니다.중요: 그리디 알고리즘은 모든 문제에 적합하지는 않음적용 가능한 문제의 조건탐욕적 선택 속성:각 단계에서의 최적의 선택이 전체 문제의 최적해를 보장해야 함최적 부분 구조:문제를 부분 문제로 나누었을 때, 각 부분 문제의 최적해..

자료구조&알고리즘/C++ 2025. 1. 19. 20:48

그래프(Graph)와 트리(Tree)는 컴퓨터 과학과 자료구조에서 중요한 개념으로, 트리는 그래프의 한 특수한 형태1. 그래프의 정의구조: 정점(Vertex)과 간선(Edge)으로 이루어진 데이터 구조.종류:방향 그래프(Directed Graph): 간선에 방향이 있는 그래프.무방향 그래프(Undirected Graph): 간선에 방향이 없는 그래프.특성:사이클(Cycle)을 가질 수 있음.연결 그래프(Connected Graph)일 수도 있고, 아닐 수도 있음.루프(Self-loop)와 다중 간선(Multiple edges)을 허용할 수 있음.2. 트리의 정의구조: 트리는 그래프의 특수한 형태로, 방향성 비순환 그래프(DAG, Directed Acyclic Graph)의 한 유형.특성:루트 노드(Roo..

자료구조&알고리즘/C++ 2025. 1. 13. 20:31

벨만-포드 알고리즘은 그래프에서 **최단 경로(Shortest Path)**를 구하기 위한 알고리즘으로, 특히 음수 가중치 간선을 포함한 그래프에서도 작동합니다.이 알고리즘은 단순하면서도 강력하며, 음수 사이클(negative weight cycle)을 감지할 수도 있습니다.알고리즘의 특징음수 가중치 허용:다익스트라 알고리즘은 음수 가중치 간선이 있는 그래프에서는 사용할 수 없지만, 벨만-포드 알고리즘은 음수 가중치를 포함한 그래프에서도 작동합니다.음수 사이클 탐지:음수 사이클이 존재하는 경우, 무한히 작은 경로를 만들 수 있기 때문에 최단 경로를 계산할 수 없습니다.벨만-포드 알고리즘은 음수 사이클의 존재 여부를 확인할 수 있습니다.시간 복잡도:O(V×E)O(V \times E)O(V×E), 여기서 V..

자료구조&알고리즘/C++ 2025. 1. 13. 19:00