본문 바로가기

프로그래밍181

[알고리즘] 감추어진 자연수들을 정렬했을 때 가장 큰 Gap 찾기 조건 - 1~M 까지의 범위에서 N개의 자연수가 입력으로 감추어진다. - M은 N에 비해 매우 크다. 이 자연수들을 정렬했을 때 가장 큰 Gap(즉, 인접한 두 자연수의 차이를 찾아라) 제공 Query(x,y)를 호출하면 x부터 y까지의 범위에서 입력 자연수들 중 가장 작은 값과, 가장 큰 값을 리턴한다. 만약 n=8, m=93 알고리즘 : 1. Qurey(1,M)을 호출하여 가장 작은 값과, 가장 큰 값을 알고 시작한다. 가장 작은 값 : T1, 가장 큰 값 : Tn 2. T1 + 1 ~ Tn - 1 구간을 (N-1)개로 균일하게 나누어 Query를 호출한다. 3. 각각 호출하여 알아낸 최소, 최대값을 이용하여 가장 큰 Gap을 찾는다. 호출하지 않은 정보들은 무시해도 된다. 이게 가능한 이유는, N-.. 2021. 3. 24.
[알고리즘] 증명에 관해서 예시로 정렬된 두 배열에서 합 찾기를 들어보겠다. x = 1, 3, 5, 9, 12, 13, 15, 20 y =2, 7, 8, 10, 11, 14, 16, 17 이렇게 배열이 주어질 때, x배열, y배열의 인자를 합쳐서 23이 있는지를 확인하는 알고리즘이다. 1. 직관 2. 증명 3. 풀이 이와 같은 3단계를 거쳐서 문제를 해결해 나가야 한다. 1. 직관 x는 왼쪽부터, y는 오른쪽 부터 이동하면서 더하고, 더한 합이 33보다 크면 y를 왼쪽으로 이동시키고, 더한 합이 33보다 작으면 x를 오른쪽으로 이동시키면 되지 않을까? 2. 증명 그러면 1번과 같은 알고리즘을 적용했을 때 빠트리는 경우가 없다는 것을 어떻게 증명할 것인가? - 빠트리는 경우가 있다면 반드시 일어나야 하는 상황을 도출하고, 그 상황이.. 2021. 3. 24.
Anagram 찾기 Anagram이란? 두개의 영단어가 같은 글자로 구성되어 있는데, 순서만 다를경우. ex) wolf -> flow, elvis -> lives, monkey -> keymon 빠르게 찾는 알고리즘. 내 생각 : 각각의 단어를 ascii 문자 기준으로 xor, sum 값을 비교. 알려준 방법 : 단어를 알파벳 순으로 정렬을 함. 그리고 정렬한 알파벳을 다시 정렬함. 그러면 붙어있는 단어가 anagram. 내 생각을 구현을 해보았음. flow = 18(xor), 312(sum) wolf = 18(xor), 312(sum) anagram = 87(xor), 503(sum) managra = 87(xor), 503(sum) 역시 난 천재 2021. 3. 23.
알고리즘을 짜는 나만의 방식 2021. 3. 23.
알고리즘 시간복잡도 크게 알아야 할 것은 4가지다. 1. O(1) 2. O(n) 3. O(n^2) 4. O(log n) 1. O(1)은 함수내에서, 반복문이 없을 때 표기한다. 2. O(n)은 함수내에서, 1중 반복문이 있을 때 표기한다. 3. O(n^2)은 함수내에서, 2중 반복문이 있을 때 표기한다. 4. O(log n)은 함수내에서, 정렬알고리즘과 같은 한 조건을 수행 시 반을 수행하지 않아도 되는 경우이다. 2021. 3. 22.
[C#] 문자열 비교방법 docs.microsoft.com/ko-kr/dotnet/csharp/how-to/compare-strings 문자열 비교 방법 - C# 가이드 문화권별 순서 지정 여부나 대/소문자와 상관없이 문자열 값을 비교하고 정렬하는 방법에 대해 알아봅니다. docs.microsoft.com 굉장히 잘 설명해놨네 2021. 3. 21.

티스토리툴바