전공공부/알고리즘&자료구조
-
세그먼트 트리 (segment - tree)전공공부/알고리즘&자료구조 2020. 1. 12. 21:33
세그먼트 트리는 해당 포스트에 설명이 잘 돼있다. 출처: http://isukorea.com/blog/home/waylight3/216 세그먼트 트리(Segment Tree) / 인덱스 트리(Index Tree) :: 강의/IT/알고리즘 :: ISU 블로그 void update_range(int node, int begin, int end, int left, int right, int diff) { update_lazy(node, begin, end); if (end
-
최소, 최대 힙 (min & max heap)전공공부/알고리즘&자료구조 2020. 1. 12. 21:09
출처:https://gmlwjd9405.github.io/2018/05/10/data-structure-heap.html 자료구조 ‘힙(heap)’이란? 완전 이진 트리의 일종으로 우선순위 큐를 위하여 만들어진 자료구조이다. 여러 개의 값들 중에서 최댓값이나 최솟값을 빠르게 찾아내도록 만들어진 자료구조이다. 힙은 일종의 반정렬 상태(느슨한 정렬 상태) 를 유지한다. 큰 값이 상위 레벨에 있고 작은 값이 하위 레벨에 있다는 정도 간단히 말하면 부모 노드의 키 값이 자식 노드의 키 값보다 항상 큰(작은) 이진 트리를 말한다. 힙 트리에서는 중복된 값을 허용한다. (이진 탐색 트리에서는 중복된 값을 허용하지 않는다.) 최대 힙(max heap) 부모 노드의 키 값이 자식 노드의 키 값보다 크거나 같은 완전 이..
-
이진 트리 (Binary Tree)와 순회전공공부/알고리즘&자료구조 2020. 1. 12. 20:37
트리의 구성 요소 노드 트리를 구성하고 있는 각각의 요소 간선(edge) 트리를 구성하기 위해 노드와 노드를 연결한 선 루트노드 트리 구조에서 최상위에 있는 노드 단말노드(Terminal node) 하위에 다른 노드가 연결돼 있지 않은 노드 비단말노드, 외부노드(Internal node) 단말 노드를 제외한 모든 노드, 루트노드 포함 Binary tree (이진트리) 루트를 중심으로 두개의 서브트리로 나눠지고 그 두개의 서브트리도 모두 이진트리여야 한다. -> 재귀적인 정의 Full binary tree (포화이진트리) 모든 level이 꽉 찬이진트리 Complete Binary tree (완전이진트리) 위에서 아래로, 왼쪽에서 오른쪽 순서대로 차곡차곡 채워진 이진트리 순회 방식 전위 순회 전위 순회(p..
-
큐 (Queue)전공공부/알고리즘&자료구조 2020. 1. 12. 20:14
큐는 First In First Out 구조이다. 기본 동작으로는 push,pop,size,empty 등이 있다. 이 기본 동작원리는 다음 문제를 통해 구현하였다. 출처:https://www.acmicpc.net/problem/10845 10845번: 큐 첫째 줄에 주어지는 명령의 수 N (1 ≤ N ≤ 10,000)이 주어진다. 둘째 줄부터 N개의 줄에는 명령이 하나씩 주어진다. 주어지는 정수는 1보다 크거나 같고, 100,000보다 작거나 같다. 문제에 나와있지 않은 명령이 주어지는 경우는 없다. www.acmicpc.net 소스코드
-
스택 (Stack)전공공부/알고리즘&자료구조 2020. 1. 12. 20:10
스택은 Last In First Out 구조이다. 기본 동작으로 push, pop, empty, size, top 등의 연산이 있고 다음 소스코드를 통해 어떻게 스택이 동작되는지 보자. 다음은 스택의 동작 구현에 관한 기본적인 문제이다. 출처:https://www.acmicpc.net/problem/10828 10828번: 스택 첫째 줄에 주어지는 명령의 수 N (1 ≤ N ≤ 10,000)이 주어진다. 둘째 줄부터 N개의 줄에는 명령이 하나씩 주어진다. 주어지는 정수는 1보다 크거나 같고, 100,000보다 작거나 같다. 문제에 나와있지 않은 명령이 주어지는 경우는 없다. www.acmicpc.net 소스코드 또한 스택을 활용하는 대표적인 문제는 괄호계산기이다. 다음 문제를 보자 출처:https://w..
-
합병정렬 (MergeSort)전공공부/알고리즘&자료구조 2020. 1. 12. 19:52
합병정렬은 대표적인 분할 정복 알고리즘이다. start==end가 되기 직전까지 분할을 계속 하다가 즉 start,start+1,// end-1,end 와 같이 분할이 단일범위까지 진행되다가 다시 이 단일 범위서부터 분할했던 경로 그대로 역순으로 되돌아가며 정복을 하는 알고리즘이다. 분할 정복을 하는 순서는 항상 다음을 따른다. mid=(start+end)/2를 기준으로 start~mid 부분인 좌측 부분의 분할이 먼저 이루어지고 그다음 mid+1~end까지 분할이 이루어진 후 합병이 시작된다. 즉 큰 틀로보면 왼쪽분할 - 오른쪽분할 - 정복 순서를 원자단위에서부터 차례차례 수행해 나가는 구조이다. 그리고 이를 그림으로 그려보면 다음과 같다. 원자단위로 왼쪽부터 분할 해 나간 후 오른쪽부분을 분할하고 정..
-
투 포인터(Two Pointers Algorithm), 슬라이딩 윈도우(Sliding Window)전공공부/알고리즘&자료구조 2020. 1. 12. 18:38
알고리즘 설명 출처: https://m.blog.naver.com/kks227/220795165570 투 포인터(Two Pointers Algorithm), 슬라이딩 윈도우(Sliding Window) (수정: 2019-09-09) 조금 성향이 비슷하다고 생각하는 기법 2개를 함께 쓰려 합니다.첫 번째로 소개해드릴 기법은 투 포인터(tw... blog.naver.com 투포인터 혹은 스라이딩 윈도우 기법은 연속적인 구간의 합이나 경우의 수를 구할때 매우 유용하다. 처음에 두개의 포인트 P1,P2를 설정하고 예를들어 배열의 구간 합이 특정 값을 만족할때 그 값을 만족하는 구간의 수를 구하는 문제가 있다. 이떄 배열이 모두 양수라고 가정을 하면 p2가 커질수록 합은 계속 증가하게 된다. 그래서 만약 합이 커..
-
이분탐색 (Binary Search)전공공부/알고리즘&자료구조 2020. 1. 12. 18:20
이분탐색 알고리즘 참고:https://wootool.tistory.com/62 [알고리즘] 이분 탐색 이분 탐색 탐색 기법중에 하나로 원하는 탐색범위를 두 부분으로 분할해서 찾는 방식입니다. 그렇기에 원래의 전부를 탐색하는 탐색 속도에 비해 빠릅니다. 이분 탐색을 하는 방법은 left , right , mid 값으로 탐.. wootool.tistory.com 이분탐색 알고리즘은 주어진 범위 내에서 구하고자 하는 값을 절반씩 줄여나가며 탐색하는 알고리즘이다. 따라서 탐색하는데 걸리는 시간은 1/2씩 좁혀나가므로 O(logN)이 된다. 알고리즘에 대한 상세한 설명은 문제와 소스코드를 분석하며 보자. 백준: 2805 나무자르기 https://www.acmicpc.net/problem/2805 2805번: 나무..