길자의 개발 오르막길

1. 이진 탐색 정의이진 탐색(이분 탐색) 이란 정렬되어 있거나, 단조성이 보장된 구간에서 탐색 범위를 절반씩 줄이며 답을 찾는 알고리즘이다.1부터 100 까지의 숫자 맞추기 게임(up/down) 할때 중간 부터 찾는것과 같은 원리이다.2. 이진 탐색이 가능한 조건아래 두 조건이 반드시 필요하다1. 단조성 (monotonicity)한 방향으로만 움직이려는 성질을 의미한다. 수열이나 함수의 증감형태를 유지 할 때를 말한다.예1 : (1, 2, 2, 3, 4, 5 ) , 또는 (10,8,6,4,4,2) 증가나 감소 에2 : (가능 ,가능 , 가능, 불가능 ,불가능) 또는 (불가능,불가능,가능,가능)즉 중간값을 확인 할 때 정답이 왼쪽 혹은 오른쪽 중 어디에 있는지 확신 할 수 있어야 한다는것, 뒤죽박죽 섞이..

큰 문제를 작은 문제로 나누고 작은 문제의 정답을 저장해 재사용해서 전체 문제를 최적(최소/최대/경우의 수)으로 푸는 기법. 하나의 문제는 단 한번만 풀어 여러번 다시 푸는 비효율적 중복 계산을 제거하는 알고리즘이다.성립 조건은 보통 두가지로 1. 겹치는 부분 문제 : 같은 작은 문제가 반복해서 등장한다.2. 최적 부분 구조 : 큰 문제의 최적해가 작은 문제들의 최적해로 구성된다. DP를 푸는 과정 1. 테이블 정의하기2. 점화식 찾기 3. 초기값 정하기예제 1) 피보나치 문제https://www.acmicpc.net/problem/1003위 문제를 보면 1과 0의 갯수만 세면 문제가 풀릴거 같지만 주어진 시간이 0.25초로 제한 시간 초과로 문제를 틀리게 된다 .해당 주어진 식을 그대로 쓰지 않고 dp..

가장 짧은 경로를 탐색하는 과정에서 최소 비용의 정점을 빠르게 선택하는것, 이를 효율적으로 처리하기 위해 힙(우선순위 큐)을 사용한다. [STL] 우선순위 큐 (priority_queue)우선순위가 높은 데이터가 먼저 나오는 자료구조,기본 구현은 힙 이며 기본 설정은 최대 힙(max-Heap) 이다.내부적으로 Heap 자료 구조를 사용한다삽입,삭제(pop)은 항상 O(log N)이고 top()(가장 우선 순codehortus.tistory.com [알고리즘] 힙정렬(Heap Sort)우선순위 큐 (priority_queue)우선순위가 높은 데이터가 먼저 나오는 자료구조,기본 구현은 힙 이며 기본 설정은 최대 힙(max-Heap) 이다.내부적으로 Heap 자료 구조를 사용한다삽입,삭제(pop)은 항상 O..

트리(Tree)트리는 계층적(hierarchical) 데이터 구조로 여러개의 노드 가 부모-자식 관계로 연결 되 있는 자료 구조마치 나무가 땅에 뿌리를 내리고 가지를 뻗어나가는 것 처럼 트리도 하나의 root노드에서 시codehortus.tistory.com마지막 레벨을 제외한 모든 레벨이 꽉 차 있고 마지막 레벨의 노드들도 왼쪽부터 빈칸 없이 순서대로 채워지는 이진트리.배열을 이용한 구현 : 중간에 빈 공간이 없기 때문에 배열을 사용하여 효율적으로 저장 할 수 있다.힙 자료 구조의 기본 구조가 된다.힙이 완전 이진 트리를 유지하는 이유는 배열로 효율적으로 저장하고 높이를 최소로 유지해 연산을 빠르게 하려는 목적이다.레벨 순서대로 왼쪽 부터 빈칸 없이 채워지므로 노드를 배열에 0/1 번 부터 연속으로 담..

우선순위 큐 (priority_queue)우선순위가 높은 데이터가 먼저 나오는 자료구조,기본 구현은 힙 이며 기본 설정은 최대 힙(max-Heap) 이다.내부적으로 Heap 자료 구조를 사용한다삽입,삭제(pop)은 항상 O(log N)이고 top()(가장 우선 순codehortus.tistory.com힙 정렬은 힙(Heap) 자료구조를 이용해 정렬하는 방식.우선 순위 큐를 구현하는데 사용된다.이 힙 에는 최대 힙 (Max Heap) 과 최소 힙(Min Heap)이 있다최대힙 : 항상 큰 값을 루트에 위치하게 한다.최소힙 : 항상 작은 값을 루트에 위치하게 한다. 최대 힙 1. 부모 노드가 항상 자식 노드 보다 큰 값을 가진다.2. 루트 노드는 항상 최대값이 된다.최소 힙 1. 부모 노드가 자식 노드보다 ..

DFS(Depth First Search) 깊이 우선 탐색, 트리나 그래프를 최대한 깊이 들어가서 탐색하는 방법,폭 넓은 지식 보다 깊이 있는 지식을 우선시 한다. DFS 기반의 탐색은 재귀나 스택 자료구조를 이룔해서 구현 할 수 있다.DFS를 수행 할 때 루트 노드에서 시작해서 한쪽의 최대한 깊이 들어 간 후 에 자식 노드를 모두 방문후 다시 부모로 돌아와 다른 자식을 방문하는 방식, 위와같은 순회 방식을 Pre-order traverse, 전위 순회 라고 한다. In-order traverse. 중위 순회, 왼쪽 → 루트 → 오른쪽 순서로 노드를 방문한다.Post-order traverse. 후위 순회, 왼쪽 → 오른쪽 → 루트 순서로 노드를 방문한다. 탐색 : 어떠한 값을 발견하기 위한 행위, 순..

CPU는 여러 요소로 이루어져 있어 서로 협력해 명령어를 처리하고 데이터를 연산한다.주요 구성 요소로는 산술 논리 장치, 제어 장치, 레지스터가 있다.이 외에도 캐시 메모리와 버스 같은 부가 적인 요소도 포함되 있고 각 요소는 독립적인 기능을 수행하지만 서로 긴밀 하게 협력해 CPU가 정상적으로 동작 할 수 있도록 한다.1. 산술 논리 장치 (ALU, arithmetic login unit)CPU 의 핵심 구성 요소로 연산을 수행하는 역할을 한다.ALU는 명령어와 데이터를 받아 연산을 수행 후 결과를 출력 하는 구조로 이루저여 있다.1-1 ALU의 구성요소 1-1-1. 연산 선택기(operation selecot)ALU에서 어떤 연산을 수행할지 결정하는 역할을 한다.제어 장치에서 명령을 전달 받으면 연산..

그래프는 정점(vertex)와 간선(edge)으로 이루어진 비선형 데이터 구조이다.트리는 특정한 계층 구조를 가졌지만 그래프는 트리보다 더 자유로운 형태를 가지고 있다.트리는 하나의 루트에서 시작하여 계층적으로 뻗어 나가는 구조지만그래프는 모든 방향으로 연결 될 수 있는 구조,2025.11.28 - [CS(computer Science)/자료구조(Data Structures)] - 트리(Tree) 트리(Tree)트리는 계층적(hierarchical) 데이터 구조로 여러개의 노드 가 부모-자식 관계로 연결 되 있는 자료 구조마치 나무가 땅에 뿌리를 내리고 가지를 뻗어나가는 것 처럼 트리도 하나의 root노드에서 시codehortus.tistory.com1. 그래프의 기본 개념정점(Vertex, 노드) : ..

배열이나 리스트와 같은 선형 구조에서 일정 범위(윈도우)를 유지하며 옆으로 밀면서 데이터를 처리하는 기법,주로 연속된 부분 배열의 최대합 이나 특정 조건을 만족하는 구간찾기 등에서 중복 계산을 피하기 위해 사용 되며 시간 복잡도를 O(n²) 에서 O(n) 으로 획기적으로 줄여준다. 슬라이딩 윈도우의 핵심 원리윈도우가 옆으로 한칸 이동할 때 윈도우 안에 있는 모든 요소를 더할 필요 없다.나가는 요소(맨앞) 는 빼고 들어오는 요소(맨뒤) 는 더해주기만 하면 된다.1. 고정 윈도우 (Fixed Sliding Window)쓰는 상황연속된 길이 K가 고정예: “연속 K개 합 최대/최소”, “길이 K 구간의 평균”, “길이 K에서 조건 만족 개수”원리첫 구간 [0..K-1]을 한 번 계산다음 구간으로 갈 때는..

가능한 모든 경우를 탐색하되, 조건을 위반하는 순간 즉시 되돌아가는 탐색 기법이다.브루트포스의 비효율을 줄이기 위한 방법으로 다음 단계로 나아가는 것이 의미가 없다고 판단하면 가지치기해서 다시 되돌아가 다른 경로를 찾는 탐색 알고리즘이다.유망함(promising) : 현재 경로가 해답이 될 가능성이 있는 상태가지치기(pruning) : 유망하지 않은 경로를 더이상 탐색하지 않고 차단하는것보통 재귀(Recursion) 와 DFS(깊이 우선 탑색) 을 결합하여 구현한다. [알고리즘] 부르트 포스(Brute Force)가능한 모든 경우를 전부 시도하여 정답을 찾는 알고리즘 기법,핵심개념모든 경우를 빠짐 없이 검사한다.논리적으로 단순하며 구현이 쉽다.시간 복잡도가 크기 쉬워 입력 크기가 작을 때만 실codeh..