참고 - 후위 표기식 만들기 https://ttl-blog.tistory.com/629 [알고리즘] 후위 표기법 만들기 (Infix를 Postfix로 바꾸기) 수식의 표기법 Infix (중위 표기법) Infix 표기법은 연산자가 연산값 사이에 들어 있으며, 연산의 순서를 지정하기 위해 괄호가 필요합니다 예시 : 3 * (7 - 5) Prefix (전위 표기법) Prefix 표기법은 연산 ttl-blog.tistory.com 후위 표기식을 계산하는 알고리즘은 매우 간단합니다. 후위 표기식 계산법 후위 표기식의 계산에는 스택을 사용하는 것이 쉽고 효율적입니다. 과정은 다음과 같습니다. 연산자가 나타날 때까지 스택에 연산값(피연산자)을 삽입합니다. 연산자가 나타나면 다음 과정을 진행합니다. 스택에서 연산자에 ..
Algorithm/이론
수식의 표기법 Infix (중위 표기법) Infix 표기법은 연산자가 연산값 사이에 들어 있으며, 연산의 순서를 지정하기 위해 괄호가 필요합니다 예시 : 3 * (7 - 5) Prefix (전위 표기법) Prefix 표기법은 연산자가 연산값 앞에 등장하며 괄호가 불필요합니다 예시 : * 3 - 7 5 Postfix (후위 표기법) Postfix 표기법은 연산자가 연산값 뒤에 등장하며 괄호가 불필요합니다. 또한 이는 컴파일러가 수식을 계산하는데 사용하는 표기법입니다. 예시 : 3 7 5 - * Infix를 Postfix로 바꾸기 사람은 대부분 Infix 방식의 표기법이 익숙하고 편할 것입니다. 그러나 컴퓨터는 Postfix 방식의 표기법을 쉽게 이해하고 계산할 수 있기에, 컴퓨터에게 계산을 맡길 때에는 P..
분할 정복 알고리즘(Divide and Conquer) 분할 정복 알고리즘은 그대로 해결할 수 없는 문제를 작은 문제로 분할하여 문제를 해결하는 알고리즘을 의미합니다. 분할 정복 알고리즘은 다음 세 단계로 설계됩니다. Divide : 문제가 분할이 가능한 경우에, 2개 이상의 문제로 나누는 방법을 의미합니다. Conquer : 나누어진 두개의 문제를, 각각 다시 새로운 하나의 문제로 보고, 이 또한 Divide가 가능하다면, Divide를 수행합니다. 그렇지 않으면 문제를 해결합니다. Combine : Conquer 한 문제들을 통합하여, 기존 문제의 답을 얻어냅니다. 분할 정복 알고리즘은 보통 재귀함수를 통해 구현되며 재귀호출이 아닌 스택, 큐 등의 자료구조를 이용하여 구현할 수도 있습니다. 재귀함수는..
알고리즘은 컴퓨터에게 편한 관점이 아닌 사람에게 유용한 관점에서, 원하는 일을 처리하는 방법을 표현한 것을 의미합니다. 알고리즘을 결국은 프로그램으로 구현하여야 컴퓨터가 처리할 수 있기에 알고리즘과 프로그램은 서로 불가분의 관계에 있다고 볼 수 있습니다. 알고리즘 어떠한 문제를 해결하기 위한 여러 명령어들의 유한집합입니다. 언젠가는 끝나야 하는 속성을 지닙니다. 알고리즘의 조건 알고리즘은 다음 조건을들 만족해야 합니다. 입력 (Input) : 일방적으로 외부에서 주어지며, 0개 이상이어야 합니다. 출력 (Output) : 결과가 한 개 이상 있어야 합니다. 명확성 (Definiteness) : 명령은 명확하고 모호하지 않아야 하며, 결과를 예측 가능해야 합니다. 유한성 (Finiteness) : 명령을 ..
LIS - Longest Increasing Subsequence LIS는 '최장 증가 부분 수열'이란 뜻으로 어떠한 수열 내의 부분 수열들 중, 이전의 원소보다 다음 원소가 큰 원소들로만 이루어진 수열을 '증가 부분 수열' 이라고 하고, 이러한 증가 부분 수열들 중 가장 길이가 긴(원소의 개수가 많은) 수열을 최장 증가 부분 수열이라고 한다. (참고 - LCS란?) LCS는 Longest Common Subsequence 혹은 Longest Common Substring으로, S가 무엇을 뜻하냐에 따라 의미가 달라진다. Longest Common Subsequence 는 최장 공통 부분수열, Longest Common Substring는 최장 공통 문자열을 뜻하며, 둘의 차이는 아래 그림을 보면 쉽게 ..
맨날 이분탐색 문제를 풀 때마다 while문의 탈출 조건으로 start > 1; if (arr[mid] > target) //중간값이 원하는 값보다 클 경우, 중간값이 작아져야 하므로 end를 줄인다 end = mid - 1; else //만약 중간값과 같다면? -> 더 우측 범위를 탐색하기 위해 start를 늘린다. start = mid + 1; } return end+1;//or start..
