Algorithm/Theory
-
후위표기식 변환Algorithm/Theory 2021. 4. 26. 23:43
안녕하세요 :) 오늘은 사람들이 일반적으로 사용하는 중위표기식(infix)을 후위표기식(postfix)으로 변환하는 방법에 대해 알아보겠습니다. 후위표기식? 먼저 중위표기식과 후위표기식에 대해 알아볼까요? 사람들이 계산할 때 사용하는 수식을 중위표기식이라고 하는데, 3*5와 같이 피연산자 사이에 연산자를 두는 방법이에요. 이와달리 연산자를 피연산자 뒤에 놓는 방법을 후위표기식이라고 합니다. 위의 중위표기식을 후위표기식 35* 로 바꿀 수 있어요. 후위표기식을 사용하면 연산자 우선순위에 따라 사람이 머리 속에서 왔다갔다 하는 계산 대신 왼쪽부터 순서대로 계산할 수 있어서 컴퓨터에게 시킬 수식으로 적합하다고 합니다. 연산자는 기본적으로 사용하는 사칙연산(+, -, /, *)을 포함해 괄호, %, == 등 말..
-
SegmentTreeAlgorithm/Theory 2021. 4. 8. 13:47
구간별로 특정한 결과 값을 관리할 때 사용하는 자료구조. 이진트리로 재귀적 구현이 특징. - query (특정 구간의 결과) O(logN) - replace (특정 인덱스 교체) O(logN) 안녕하세요 :) 오늘은 SegementTree에 대해 알아보려고 합니다. 먼저 SegemetTree 는 언제, 왜 사용할까요? SegemtTree 라는 이름이 나타내듯이 구간별로 특정한 결과값을 관리하고 싶을 때 사용하는 자료구조 입니다. 주로 구간 합을 구할 때 많이 사용하죠! 세그먼트 트리는 이진트리로 leaf 노드가 해당 인덱스의 값을 가지고 있습니다. 아래 그림처럼 전체 구간부터 반씩 잘라서 구간을 나눠 놓은 자료구조에요! 세그먼트 트리의 핵심은 재귀적 반복에 있습니다. 생각보다 어렵지 않아요 :) Sege..
-
RingBufferAlgorithm/Theory 2021. 4. 7. 10:48
안녕하세요! deque 관련된 문제를 풀다가 간만에 자료구조를 하나 정리해볼까 합니다. 아시다시피 array에서는 뒤에 추가하거나 빼는 작업은 O(1) 이지만, 앞 또는 중간에 추가하거나 빼는 작업은 O(n)의 시간 복잡도가 소요됩니다. 배열의 크기는 고정되어 있기 때문에 앞이나 중간에 작업을 하려면 그 뒤의 나머지 원소들을 모두 옮겨주는 작업이 필요하기 때문이에요. 그럼 원소들을 옮기지 않고 인덱스만 조절하면 되지 않을까? 하는 데서 시작된 아이디어가 RingBuffer가 아닐까 싶어요. RingBuffer는 read / write 포인터를 둬서 배열의 원소들을 움직이지 않고 인덱스만 조절해 덮어쓰는 방식을 사용합니다. 예시를 보면서 살펴볼게요. 처음엔 Read, Write 모두 0번째 인덱스에서 출발..
-
선택문제 Quick SelectAlgorithm/Theory 2021. 1. 7. 15:44
- 선택문제: n개의 값 중에서 k번째로 크거나 작은 수를 찾는 문제 - Quick Select: pivot과 작은 값, 같은 값, 큰 값으로 나누어서 찾고자 하는 수가 어디에 속해있는지 찾아나가는 방법 1. pivot 고르기 2. 3부분으로 나누기 ( n-1번 수행 ) S = { P보다 작은 값 } L = { P보다 큰 값 } M = { P와 같은 값 } 3. k가 어디에 속해 있는지 찾기 |S| : 배열 S의 개수, (S에 속함) if |S| >= k { return 재귀(S, k) } (L에 속함) else if |S| + |M| < k { return 재귀(L, k - |S| - |M| } (M에 속함) else { return P } - 시간복잡도 최선의 경우 O(n), 최악의 경우 O(n^2)..
-
Combination 조합Algorithm/Theory 2020. 8. 25. 14:26
- n개의 원소에서 r 개의 원소를 순서에 상관없이 뽑는 경우의 수 - nCr = n! / (n-r)! * r! - nCr = n-1Cr-1 + n-1Cr 조합? 조합은 n 개의 원소 중에서 순서를 고려하지 않고 원하는 개수만큼 뽑는 경우의 수를 말합니다. 순서를 고려해서 뽑는 순열에서 중복을 제거해준 형태로 볼 수 있죠. 따라서 순열에서 r! 만큼 더 나눠준 형태를 띕니다. nCr = nPr / r! = n! / (n-r)! * r! 조합에는 기억해야 할 중요한 성질이 있습니다. 결론부터 보면, nCr = n-1Cr-1 + n-1Cr 의 공식인데요, 이 의미를 살펴보면, 하나의 원소를 선택할 경우 + 하나의 원소를 선택하지 않을 경우를 나타냅니다. 예를 들어, [1, 2, 3] 에서 2개를 뽑는 경우의..
-
Floyd Wharshall 플로이드 와샬Algorithm/Theory 2020. 6. 18. 13:24
목표 - 하나의 정점에서가 아닌 모든 정점에서 모든 정점으로 가는 최단 경로를 구하고 싶을 때 사용한다. - 거쳐가는 정점을 기준으로 알고리즘을 수행한다. - 삼중 for문을 사용해 구현하므로 O(n^3)의 시간 복잡도를 갖는다. 플로이드 와샬 알고리즘 ? 플로이드 와샬 알고리즘은 한 정점에서 시작해 모든 정점을 탐색하는 최단 방법을 다룬 다익스트라나 다른 그래프 탐색 알고리즘과 달리 모든 정점에서 모든 정점의 최단 경로를 구하고 싶을 때 사용합니다. 핵심 아이디어는 A -> B 노드로 갈 때, A -> B 로 바로 가는 경우 와 A -> K -> B 로 어떤 노드 k를 거쳐가는 방법 을 비교해서 최소값을 구하자는 것입니다. 구현은 가중치 테이블을 이용합니다. 아직 연결이 되지 않은 노드는 ∞으로 두고 ..
-
Binary Search 이진탐색(2) Lower/Upper boundAlgorithm/Theory 2020. 6. 12. 15:07
이진탐색이 정확히 원하는 값을 찾는 거라면, lower/upper bound는 원하는 값보다 처음으로 크거나 작은 값이 나오는 위치를 찾는 방법으로 중복된 요소나 타겟의 상한 하한을 찾는 경우 등 다양한 방식으로 활용될 수 있습니다. 이진 탐색에서 약간의 변형이 들어간 것으로 이진탐색을 이해하셨다면 어렵지 않게 이해할 수 있습니다. 이진탐색이 궁금하다면? --> 여기로 코드를 보기 전에 lower와 upper의 차이를 간략하게 정리해보고 가겠습니다. lower bound는 타겟보다 같거나 큰 값이 나오는 처음 위치를 찾습니다. upper bound는 타겟보다 처음으로 큰 값이 나오는 위치를 찾습니다. [1, 2, 2, 3, 3, 3, 4, 6] LowerBound(3) --> 3 UpperBound(3)..
-
Binary Search 이진탐색Algorithm/Theory 2020. 6. 12. 12:21
이진탐색 - 배열에서 원하는 원소를 찾는 탐색 방법이다. - 이미 정렬이 되어있는 상태에서만 사용할 수 있다. - 반씩 끊어가며 찾는 방법으로 O(logN) 의 시간복잡도를 갖는다. 이진 탐색은 이미 정렬이 되어있는 배열에서 원하는 원소를 효율적으로 찾을 수 있는 알고리즘입니다. 원리는 간단합니다. 이미 정렬이 되어있는 상태이기 때문에 반을 뚝 짤라서 찾는 원소가 왼쪽인지 오른쪽인지 확인해 아닌 부분은 버립니다. 조금 더 살펴보면, 시작 부분을 low, 끝 부분을 high라고 해볼게요. array = [1, 5, 7, 15, 22, 65, 80, 100] 배열이 이런식으로 있고 65를 찾고 싶다면, 시작할 때 low = 0, hight = 6 (array.count-1) 이고 mid = 3 = (0 + ..