본문 바로가기

Algorithm

 (83)
recursion tree - uneven 시간 복잡도
재귀 시간복잡도 master theorem 설명 마스터 정리 Master Theorem 알고리즘 시간 복잡도 구하기 알고리즘과 시간 복잡도알고리즘을 만드는 법만큼 알고리즘의 시간 복잡도 구하는 것 역시 중요하다고 생각... blog.naver.com
정렬된 두 배열의 중앙값 찾기 algorithm - 두 개의 정렬 된 배열로 구성된 병합 된 배열의 중앙값 찾기 크기가 n이고 m 인 2 개의 정렬 된 정수 배열이 있다고 가정합니다. 모든 m + n 숫자의 중간을 찾는 가장 좋은 방법은 무엇입니까? log(n) * log(m) 복잡성으로이 작업을 쉽게 수행 할 수 있습니다. 하지 stackoverrun.com
선택 문제 알고리즘 선택(Selection) 문제는 n개의 숫자들 중에서 k 번째로 작 은 숫자를 찾는 문제 “1000개의 숫자가 랜덤하게 존재하는 배열 A가 있다. 이 배열에서 300번째 작은 수는 얼마인가?” 이진탐색은 정렬된 입력의 중간에 있는 숫자와 찾고자 하 는 숫자를 비교함으로써, 입력을 1/2로 나눈 두 부분 중 에서 한 부분만을 검색 • 선택 문제는 입력이 정렬되어 있지 않으므로, 입력 숫자 들 중에서 (퀵 정렬에서와 같이) 피봇을 선택하여 아래와 같이 분할 Selection(A, left, right, k) 입력: A[left]~A[right]와 k, 단, 1≤k≤|A|, |A|=right-left+1 출력: A[left]~A[right]에서 k 번째 작은 원소 선택 알고리즘은 데이터 분석을 위한 중앙값 (..
Quick sort(퀵 정렬) [알고리즘] 퀵 정렬(quick sort)이란 - Heee's Development Blog Step by step goes a long way. gmlwjd9405.github.io
공부하자 문제 - 정답 참조 문제 - 스킵함 문제 - 풀었지만 미완성 입출력 - 2557, 1000, 2558, 10950, 10951, 10952, 10953,11021, 11022, 11718, 11719, 11720, 11721, 2741, 2742, 2739, 1924, 8393, 10818, 별찍기 2438, 2439, 2440, 2441, 2442, 2445, 2522, 2446, 10991, 10992 28문제 DP - 1463, 11726, 11727, 9095, 10844, 11057, 2193, 9465, 2156, 11053, 11055, 11722, 11054, 1912, 2579, 1699, 2133, 9461, 2225, 2011, 11052 2751, 11650, 11651, 10814..
에라토스테니스의 체 에라토스테네스의 체 : 범위에서 합성수를 지우는 방식으로 소수를 찾는 방법 체크할 때, 모든 수를 다 돌면서 체크할 필요 없이 체크 할 배수만큼만 반복문을 돌게하는 것이다. 그리고, 이미 0으로 체크되어버린 수의 배수는 확인하지 않는다. (왜냐면, 체크된 수의 배수들도 이미 다 체크가 되어있기 때문이다) [C++] 소수 구하기 최적의 알고리즘 (2) - 에라토스테네스의 체 소수 구하기 최적의 알고리즘 1편에서 (http://marobiana.tistory.com/89) 주어진 수보다 작은 수의 소수들로 나누는게 성능이 좋다고 했었는데, 그것보다 더 좋은 알고리즘을 찾아냈다.ㅋㅋ 이것보다 �� marobiana.tistory.com
Merge Sort 시간 복잡도 T(Divide) = 0 이다. 진짜야. Divide에 시간이 안 걸린다는 뜻이다. 지난번 탐색알고리즘에서는 탐색하는 과정에서 비교연산을 해야하기때문에 그냥 직접적으로 S[0] 부터 S[n/2] 까지, S[n/2+ 1]부터 S[n]까지 식으로 해당 인덱스만 기억하면 되는 것이다. 물론 코드로 이렇게 인덱스를 바로 기억하도록 짜려면 상당히 어려울 것이지만... 엄밀히는 Copy는 반드시 필요한 과정은 아니기 때문에 시간복잡도 분석에서 제외된다. T(Solve) = 2 * T(n/2) 이 맞다. 왼쪽, 오른쪽 자른 놈들을 다시 해결하는데 걸리는 시간을 계산하면 되기때문에 각각 T(n/2)(왼쪽) + T(n/2)(오른쪽) 을 더하면 2 * T(n/2)이 되는 것이다. ​ T(Combine) = n - 1 이다..
[관계기반] 숫자 뒤집기(p.18) 방법1 방법2 방법3
관계 기반 알고리즘 설계 탐색기반의 설계방법은 컴퓨터의 빠른 연산속도를 이용하여 짧은 시간에 가능한 해의 집합을 탐색하면서 최적 해를 구하는 기술적인 방법 관계기반 설계방법은 해를 구하는 행위를 하나의 함수로 표현하고 이 함수들의 관계를 이용하여 해를 구하는 아주 효율적인 방법이다. 관계기반 설계를 적용하기 위해서는 문제의 정의 및 상태를 함수로 정의하고 이 함수들 간의 관계를 점화식 혹은 이와 유사한 형태로 표현할 수 있어야 한다. 관계기반 설계에서는 수학적 귀납법과 점화식 등의 표현이 기반이 되므로 이번 단원에서는 수학적 귀납법에 대해서 간단히 살펴보고 관계기반으로 알고리즘을 설계하는 방법에 대해서 다룬다.
[DFS] 돌다리 건너기(p.239) f(악마/ 천사의 돌다리, 시작 인덱스, 두루마리 인덱스) 1 과 2 라인을 선택해서 시작점을 정한다. 두루마리에 있는 값과 일치한다면 다음 인덱스로 넘어간다. 마지막 점에 도착하였다면 return 1
[DFS] 좋은 수열(p.226) (a==b ? false:i==b); a=b라면 false a!=b 라면 i==b에 관한 참, 거짓 여부를 return한다. 이 방법보다 조금 더 효율적인 방법을 생각해볼 수 있다. 만들어진 수열의 좋은 수열 여부를 판단할 때, 새로 붙은 수를 포함하는 것으로만 평가해 보는 것이다. 이 때 좋은 수열을 판단하는 방법은 다음과 같다.
LIS(Longest Increasing Subsequence, 최장증가 부분 수열) 주어진 어떤 수열에서 순서대로 증가하면서 커지는 가장 긴 수열 LIS를 찾아내는 다양한 방법을 생각하고 만들어낼 수 있지만 재귀적 문제해결사고를 활 용할 수도 있다. 1. k번째 위치를 마지막으로 만들어질 수 있는 LIS의 길이를 solve(k)라고 하자. 2. 그렇다면 solve(k)는 그 이전의 solve(k-1), solve(k-2), solve(k-3), … , solve(3), solve(2), solve(1)들의 길이에 1을 더한 것이라고 생각할 수 있다.
[DFS] 저울 추
배낭 문제
오른편 절단 가능 소수 전체 탐색 f(0,0) f ( 1 , 1 ) - f ( 11 , 2 ) - f ( 12 , 2 ) 이런 구조로 길이가 n인 순열이 생성되고, 생성된 수를 4~11행의 소수 판별함수로 오른쪽부터 하나씩 절단하면서 소수인지 판단한다. 이 때 n/10으로 수를 분리하면 된다. 만약 오른쪽을 절단하면서 체크하는 과정에서 하나라도 소수가 아니면 바로 취소하고, 다음 숫자로 넘어간다. 만약 오른편 절단 가능 소수임이 판단되면 전체 개수를 저장하는 변수 cnt 값을 1증가시키고, 그 수를 화면에 바로 출력한다.
최대값 구하기 탐색하기 전 먼저 해를 저장할 변수인 ans를 0으로 초기화한다. 여기서 주의할 점은 각 원소들 중 음수값이 존재할 경우 최댓값을 구하기 위해 ans를 0으로 초기화하면 안 된다는 점이다. 이 문제는 음수값이 존재하지 않기 때문에 ans를 0으로 초기화하고 문제를 해결한다.
BFS - 너비 우선 탐색 너비우선탐색은 백트랙을 하지 않는다. 대신에 현재 정점에서 깊이가 1인 정점을 모두 방문해야 하므로 큐(queue)라는 선입선출(FIFO) 자료구조를 활용하여 현재 정점에서 깊이 가 1 더 깊은 모든 정점을 순차적으로 큐에 저장하여 탐색에 활용한다. 알고리즘 :: BFS 너비 우선 탐색 (C/C++ 구현), 탐색알고리즘 BFS 너비 우선 탐색 탐색을 할때 너비를 우선으로 탐색하는 알고리즘 BFS 탐색 알고리즘을 통해 '최단 경로'를 찾을 수 있다. 응용하면 미로찾기와 같은 알고리즘도 구현할 수 있다. BFS를 구현하기 hongku.tistory.com
[C++ / STL] sort std::sort(Size, Size+cnt, cmp) 왼쪽이 오른쪽에 비해서 크다. -> 내림차순 왼쪽에 있는 것이 더 클 수 있도록 정렬하겠다. 왼쪽에 있는 것이 오른쪽에 비해서 더 작도록 정렬하겠다. -> 오름차순 std::sort(Size, Size+cnt, cmp) std::vector() std::upper_bound() std::queue() 8. C++ STL sort() 함수 다루기 ① 지난 시간까지 선택 정렬, 버블 정렬, 삽입 정렬, 퀵 정렬, 병합 정렬의 개념에 대해 이해하고 간단한 프로... blog.naver.com
백트랙 다음 전체탐색을 위한 백트랙을 진행하면서 이전 전체탐색의 흔적을 지워야 한다는 것이다. 너비우선탐색은 백트랙을 하지 않는다. 대신에 현재 정점에서 깊이가 1인 정점을 모두 방문해야 하므로 큐(queue)라는 선입선출(FIFO) 자료구조를 활용하여 현재 정점에서 깊이가 1 더 깊은 모든 정점을 순차적으로 큐에 저장하여 탐색에 활용한다.
Graph and Tree 그래프 중 연결에 방향이 없고 순환하는 사이클이 없는 그래프를 트리라고 정의한다. 트리는 노드간에 부모- 자식의 관계를 가지는 방향이 있는 연결을 갖고 루트노드를 갖고 있다.
탐색 / 비선형구조 탐색 그래프의 구현 그래프를 구현하는 방법은 인접행렬(adjacency matrix)과 인접리스트(adjacency list)로 크게 나눌 수 있다. 트리 그래프 중 회로(cycle)가 없는 그래프를 트리라고 한다. dfs(depth first search, 깊이 우선 탐색) 가장 위에 있는 정점에서 출발하여 모든 정점들을 깊이우선으로 탐색하며, 탐색하는 순서를 알아보자. 출발 정점을 트리의 가장 위에 있는 정점으로 하고, 한 정점에서 이동 가능한 정점이 여러 개 있을 경우 왼쪽의 정점부터 방문한다고 가정하면, 단계별 탐색 과정은 다음과 같다. 깊이우선탐색과정에서 3단계 이후 더 이상 진행할 수 있는 정점이 없다. 그 이유는 간선으로 연결된 정점들 중 아직 방문하지 않은 정점을 방문하기 때문이다. 이처럼 더 ..
탐색 / 선형구조 탐색 i번째 자료를 탐색한 다음, i+1번째로 탐색해야할 자료가 유일한 형태를 의미한다. 2차원, 3차원 구 조라도 순서가 일정하게 정해져 있으면 이는 선형이라고 할 수 있다 순차탐색 자료의 특성에 관계없이 사용할 수 있는 일반적인 방법으로 전체탐색기법의 한 방법이다. 첫 번째 원소로부터 시작하여 한 원소씩 차례로 다음 원소를 탐색해 나가는 방법으로 자료가 n개 있을 때의 계산량은 O(n)이다. 이분 탐색 S 에 n개의 원소를 입력받고, 그 중에 k가 있는지를 찾는 알고리즘이다. 이 알고리즘은 오름차순이나 내림차순으로 정렬된 선형구조에서 원하는 원소를 찾는 것으로 계산량은 O(log2 n)이다. 이분탐색의 탐색순서(○는 처음 접근하는 원소이고, 사각형은 찾은 곳의 값이 찾으려는 값보다 작으면 찾는 위치, 둥근..

티스토리툴바