윤깡패 블로그

세그먼트 트리(Segment Tree) 자료구조 주어진 데이터의 질의값 구하기(구간 합, 최대・최소)나 데이터 업데이트를 빠른 시간 복잡도 안에서 수행하기 위해 고안해 낸 자료구조 * 더 큰 범위는 '인덱스 트리'라고 불린다. 세그먼트 트리 종류 구간 합 A[N] = A[2N] + A[2N + 1] 최대 A[N] = max(A[2N], A[2N + 1]) 최소 A[N] = min(A[2N], A[2N + 1]) 세그먼트 트리 핵심 이론 트리 배열의 크기 2ᵏ ≥ N을 만족하는 k의 최솟값을 구한 후 2ᵏ * 2를 트리 배열의 크기로 정의 (N : 데이터의 개수) [ 예시 ] N = 8의 경우, 2³ ≥ 8 ⇒ 배열의 크기 : 2³ * 2 = 16 시작 인덱스 : 2ᵏ [ 예시 ] k = 3의 경우 시작 ..

이진 트리(Binary Tree) 자료구조 각 노드의 자식 노드(차수)의 개수가 2 이하로 구성된 트리 이진 트리의 종류 편향 이진 트리 노드들이 한쪽으로 편향돼 생성된 이진 트리 - 탐색 속도가 저하되고 공간이 많이 낭비된다. 포화 이진 트리 트리의 높이가 모두 일정하며 리프 노드가 꽉 찬 이진 트리 완전 이진 트리 마지막 레벨을 제외하고 완전하게 노드들이 채워져 있고, 마지막 레벨은 왼쪽부터 채워진 트리 이진 트리의 순차 표현 1차원 배열의 형태로 표현 트리의 노드와 배열의 인덱스 사이 상관관계 (N = 노드 개수) 루트 노드 : index = 1 부모 노드 : index = index / 2 (제약 조건 : 현재 노드가 루트 노드가 아님) 왼쪽 자식 노드 : index = index * 2 (제약 ..

최소 신장 트리(Mininum Spanning Tree) 자료구조 그래프에서 모든 노드를 연결할 때 사용된 에지들의 가중치의 합을 최소로 하는 신장 트리 * 신장 트리(Spanning Tree) : 하나의 그래프가 있을 때 모든 노드를 포함하면서 사이클이 존재하지 않는 부분 그래프 그래프(Graph) 자료구조 그래프(Graph) 자료구조 그래프(Graph) 자료구조 노드와 노드 사이에 연결된 에지의 정보를 가지고 있는 자료구조 노드(Node) : 데이터를 표현하는 단위 에지(Edge) : 노드를 연결 에지 리스트(Edge List) 노드를 배열에 저장하 soobin0821.tistory.com 최소 신장 트리 특징 사이클을 포함하지 않는다. (사이클이 포함되면 가중치의 합이 최소가 될 수 없기 때문) N..

순열과 조합 핵심 이론 순열(Permutation) : 서로 다른 n개의 숫자에서 r개를 선택하여 순서를 고려해 나열할 경우의 수 (순서 고려 O) 조합(Combination) : 서로 다른 n개의 숫자에서 서로 다른 r개를 선택하는 경우의 수 (순서 고려 X) 조합 점화식 D[i][j] = D[i - 1][j] + D[i - 1][j - 1] * , 을 참고하였습니다.

구간 합 알고리즘 연속적으로 나열된 수가 있을 때, 맨 앞부터 특정 위치까지의 합을 미리 구해 놓고 사용하는 알고리즘 시간 복잡도 - O(1) 구간 합 핵심 이론 합 배열 S를 만드는 공식 S[i] = A[0] + A[1] + A[2] + ... + A[i - 1] + A[i] = S[i - 1] + A[i] - A[0]부터 A[i]까지의 합 구간 합을 구하는 공식 S[j] - S[i - 1] - i에서 j까지 구간 합 * , 을 참고하였습니다.

다익스트라(Dijkstra) 알고리즘 그래프에서 출발 노드와 그 외 모든 노드 간의 최단 거리를 탐색하는 알고리즘 특징 - 에지가 모두 양수일 때 정상적으로 동작한다. - 시간 복잡도 : O(ElogV) (노드 수 : V, 에지 수 : E) 다익스트라 알고리즘 핵심 이론 1. 인접 리스트로 그래프를 구현한다. - 인접 리스트에 연결한 배열의 자료형 : (노드, 가중치) 2. 최단 거리 배열을 초기화한다. - 출발 노드는 0, 이외의 노드는 무한(∞)으로 초기화한다. * 무한(∞) : 문제에서 주어진 모든 에지의 합보다 충분히 더 큰 수 3. 방문하지 않은 노드 중에서 최단 거리가 가장 짧은 노드를 선택하여 출발 노드로 설정한다. - 값이 0인 출발 노드에서 시작한다. 4. 선택한 노드를 거쳐 다른 노드로..

문제 https://www.acmicpc.net/problem/1377 1377번: 버블 소트 첫째 줄에 N이 주어진다. N은 500,000보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에 A[1]부터 A[N]까지 하나씩 주어진다. A에 들어있는 수는 1,000,000보다 작거나 같은 자연수 또는 0이다. www.acmicpc.net 풀이 1. sort() 함수로 배열 정렬 ⇒ 시간 복잡도 O(nlogn) 2. 데이터의 정렬 전 index와 정렬 후 index를 비교해 왼쪽으로 가장 많이 이동한 값을 찾는다. ⇒ 정렬 전 index - 정렬 후 index의 최댓값 + 1 * 1 : swap이 일어나지 않는 반복문이 한 번 더 실행되는 것을 감안 정렬(Sort) 알고리즘 정렬(Sort) 알고리즘 정렬..

문제 https://www.acmicpc.net/problem/1722 1722번: 순열의 순서 첫째 줄에 N(1 ≤ N ≤ 20)이 주어진다. 둘째 줄의 첫 번째 수는 소문제 번호이다. 1인 경우 k(1 ≤ k ≤ N!)를 입력받고, 2인 경우 임의의 순열을 나타내는 N개의 수를 입력받는다. N개의 수에는 1부터 N www.acmicpc.net 풀이 0. 자릿수에 따른 순열의 경우의 수를 1부터 N자리까지 미리 계산 1. K번째 순열 출력하기 ① 주어진 값(K)과 현재 자리(N) - 1에서 만들 수 있는 경우의 수를 비교한다. ② ①에서 K가 더 작아질 때까지 경우의 수를 배수(cnt)로 증가시킨다(순열의 순서를 1씩 늘림). ③ K가 더 작아지면 순열에 값을 저장하고 K를 K - (경우의 수 * (c..

문제 https://www.acmicpc.net/problem/1328 1328번: 고층 빌딩 상근이가 살고있는 동네에는 빌딩 N개가 한 줄로 세워져 있다. 모든 빌딩의 높이는 1보다 크거나 같고, N보다 작거나 같으며, 같은 높이를 가지는 빌딩은 없다. 상근이는 학교 가는 길에 가장 왼 www.acmicpc.net 풀이 점화식 정의 D[N][L][R] : N개의 빌딩이 있고 왼쪽에서 L개, 오른쪽에서 R개가 보일 때 가능할 경우의 수 점화식 도출 : 가장 작은 빌딩 배치 D[N - 1][L - 1][R] : N - 1개의 빌딩에서 왼쪽에 빌딩을 추가할 때 왼쪽 빌딩이 1개 증가 D[N - 1][L][R - 1] : N -1개의 빌딩에서 오른쪽에 빌딩을 추가할 때 오른쪽 빌딩이 1개 증가 D[N - 1]..

📍 정렬 알고리즘 더보기 삽입 정렬(Insertion Sort) 두 번째 값부터 시작해 정렬된 영역에서 선택 데이터의 적절한 위치를 찾아 삽입하면서 정렬하는 방식 평균 시간복잡도 : O(n²) 최선의 경우 시간복잡도 : O(n) ⇒ 데이터가 거의 정렬되어 있는 경우 선택 정렬(Selection Sort) 남은 정렬 부분에서 가장 크거나 작은 데이터를 찾아가 선택을 반복하면서 정렬하는 방식 평균 시간복잡도 : O(n²) 버블 정렬(Bubble Sort) 데이터의 인접 요소끼리 비교하고, swap 연산을 수행하며 정렬하는 방식 평균 시간복잡도 : O(n²) 퀵 정렬(Quick Sort) pivot을 선정해 해당 값보다 작은 데이터와 큰 데이터로 분류하는 것을 반복해 정렬하는 방식 평균 시간복잡도 : O(nl..

📍 자료구조, 알고리즘 더보기 자료구조 : 데이터를 원하는 규칙 또는 목적에 맞게 저장하기 위한 구조 알고리즘 : 자료구조에 쌓인 데이터를 활용해 어떠한 문제를 해결하기 위한 여러 동작들의 모임 📍 스택, 큐 더보기 스택, 큐 선형 자료구조의 일종 스택(Stack) 삽입과 삭제 연산이 후입선출(LIFO : Last-In First-Out)로 이뤄지는 자료구조 후입선출(LIFO : Last-In First-Out) : 가장 나중에 삽입된 데이터를 가장 먼저 삭제한다. 큐(Queue) 삽입과 삭제 연산이 선입선출(FIFO : First-In First-Out)로 이뤄지는 자료구조 선입선출(FIFO : First In First Out) : 가장 먼저 삽입된 데이터를 가장 먼저 삭제한다. 📍 트리, 힙 더보기..

Previous Post 영상처리 알고리즘 병렬화 - [OpenCV][C++]영상에 Salt and Pepper Noise 추가 영상처리 알고리즘 병렬화 - [OpenCV][C++]영상에 Salt and Pepper Noise 추가 Previous Post 영상처리 알고리즘 병렬화 - [OpenCV][C++]영상 읽기/출력/저장 영상처리 알고리즘 병렬화 - [OpenCV][C++]영상 읽기/출력/저장 OpenCV(Open Source Computer Vision Library) : 실시간 컴퓨터 비전을 목적 soobin0821.tistory.com Goal 노이즈 추가된 영상에 Median Filter 적용 필터 적용된 영상을 출력 및 저장 Median Filter 알고리즘 이미지 내의 노이즈를 제거하는..

Previous Post 영상처리 알고리즘 병렬화 - [OpenCV][C++]영상 읽기/출력/저장 영상처리 알고리즘 병렬화 - [OpenCV][C++]영상 읽기/출력/저장 OpenCV(Open Source Computer Vision Library) : 실시간 컴퓨터 비전을 목적으로 한 라이브러리 https://opencv.org Home OpenCV provides a real-time optimized Computer Vision library, tools, and hardware. It also supports model execution for Ma soobin0821.tistory.com Goal 원본 영상에 Salt and Pepper 노이즈 추가 노이즈 추가된 영상을 출력 및 저장 Conte..

OpenCV(Open Source Computer Vision Library) : 실시간 컴퓨터 비전을 목적으로 한 라이브러리 https://opencv.org Home OpenCV provides a real-time optimized Computer Vision library, tools, and hardware. It also supports model execution for Machine Learning (ML) and Artificial Intelligence (AI). opencv.org Goal 원본 영상 읽기 원본 영상을 화면에 출력 원본 영상을 파일에 저장 Content 읽어 올 영상 파일을 실행 파일과 같은 폴더에 위치시킨다. Code #include #include using nam..