보관/자료구조-예제&실습10 순환-거듭제곱 계산 알고리즘(2) https://sysouthelloworld.tistory.com/81 순환-거듭제곱 계산순환을 사용하지 않고 x의 n제곱 값을 구하는 함수 작성double slow_power(double x, int n) { int i; double result = 1.0; for (i = 0; i - 루프 1회당 한 번의 곱셈이 필요하고 루프의 횟수는 n회- O(n)의 시간복잡도 sysouthelloworld.tistory.com위 글에 적지 않은 다른 방법이 더 있다.double pow(int x, int n) { int res = 1; int a = x; while (n > 0) { if (n % 2 == 1) { //excluded when remainder is 0 res = res * a; } a .. 2024. 9. 19. 히프 응용-LPT 알고리즘 LPT(Longest Processing Time first): 가장 긴 작업을 우선적으로 할당하는 방법- 서로 다른 소요 시간을 가지는 작업들을 가장 짧은 시간 내에 마무리해야 할 때 LPT를 이용해 근사의 해를 찾을 수 있다. m개의 기계와 n개의 작업이 있고, 각 작업에 걸리는 기계의 사용 시간이 다르다고 가정하자. 모든 기계를 가동하여 최소의 시간 내에 작업들을 모두 끝내는 문제를 머신 스케줄링(machine scheduling)이라 한다. 이때 LPT를 활용해 문제를 해결할 수 있다. 아래와 같이 기계 사용 시간에 따라 정렬된 7개의 작업이 있고 동일한 기계가 3대 있을 때,J1J2J3J4J5J6J78765321 LPT 알고리즘은 각 작업들을 가장 먼저 사용 가능하게 되는(=이전 작업이 가장 빨.. 2024. 8. 26. 큐의 응용: 버퍼 큐는 서로 다른 속도로 실행되는 두 프로세스 간의 상호 작용을 조화키는 버퍼의 역할을 할 수 있다. 대개 데이터를 생산하는 생산자 프로세스가 있고, 데이터를 소비하는 소비자 프로세스가 있을 때 이 사이에 큐로 구성되는 버퍼가 존재한다. 생산자-소비자 프로세스 외에도 신호등을 순차적으로 제어하는 교통 관리 시스템, 프로세스들을 저장하는 CPU 스케줄링 등의 큐 응용 분야가 있다. 프로그램 5-3 큐 응용 프로그램- 큐에 일정한 비율(20%)로 난수를 생성하여 입력하고, 일정한 비율(10%)로 큐에서 정수를 꺼내는 프로그램 - 생산자(20%)가 소비자(10%)보다 빠르므로 큐가 포화 상태가 될 가능성이 높아짐#include #include #define MAX_QUEUE_SIZE 5typedef int el.. 2024. 7. 15. 스택의 응용: 미로 문제 미로의 출구를 찾는 가장 기본적인 방법은 시행착오 방법으로서, 하나의 경로를 선택하여 한 번 시도해 보고 안 되면 다시 다른 경로를 시도하는 것이다. 문제는 현재의 경로가 출구로 이어지지 않을 때 다른 경로를 선택해야 한다는 것으로, 이를 위해 다른 경로들이 어딘가에 저장되어 있어야 한다. 현재 위치에서 가능한 경로 중 가장 가까운 경로를 쉽게 추출해야 하므로, 스택을 사용하는 것이 적합하다. 현재 위치에서 갈 수 있는 방들의 좌표를 스택에 기억하였다가 막다른 길을 만나면 아직 가보지 않은 방들 중 가장 가까운 방으로 돌아가 새로운 경로를 찾아보는 것이다. 또, 한번 지나간 방을 다시 지나가면 안 되므로 각 방들을 지나갈 때마다 방문했다는 사실을 저장해야 한다. 문제 해결을 위하여 하나의 스택을 가정할.. 2024. 7. 12. 스택의 응용: 후위 표기 수식 계산 중위(infix): 연산자가 피연산자 사이에후위(postfix): 연산자가 피연산자 뒤에전위(prefix): 연산자가 피연산자 앞에인간은 주로 중위표기법을 사용하지만 컴파일러는 후위표기법을 사용한다. 프로그래머가 수식을 중위표기법으로 작성하면 컴파일러는 이를 후위표기법으로 변환한 뒤 스택을 사용해 계산한다.중위 표기법전위 표기법후위 표기법2+3*4+2*34234*+a*b+5+*ab5ab*5+(1+2)*7*+12712+7* 중위표기법에서는 먼저 계산할 부분을 나타내기 위해 괄호를 사용해야 하는 데 비해, 후위표기법에서는 괄호가 필요 없다. 또, 이미 식 자체에 우선순위가 표현되어 있어 연산자의 우선순위도 고려할 필요가 없으므로 수식을 읽으면서 바로 계산이 가능하다. 후위 표기 수식을 계산하려면, 수식을 왼.. 2024. 7. 11. 스택의 응용: 괄호 검사 문제 괄호가 올바르게 사용되었는지 스택을 사용하여 검사한다. 괄호의 검사 조건은 아래와 같다.조건 1: 왼쪽 괄호의 개수와 오른쪽 괄호의 개수가 동일조건 2: 같은 종류의 괄호에서 왼쪽 괄호는 오른쪽 괄호보다 먼저 나와야 함조건 3: 서로 다른 종류의 왼쪽 괄호와 오른쪽 괄호 쌍은 서로를 교차할 수 없음{A[(i + 1) = 0]} ->오류 없음if ((i == 0) && (j == 0) ->오류: 조건 1A[(i + 1]) = 0 ->오류: 조건 3 이러한 괄호 사용 오류 검사에 스택을 사용할 수 있다. 가장 가까운 거리에 있는 괄호들끼리 서로 쌍을 이루어야 하므로, 스택을 사용하여 왼쪽 괄호들('(', '{', '[')을 만나면 계속 삽입하다가 오른쪽 괄호들(')', '}', ']')이 나오면 스택에.. 2024. 7. 11. 이전 1 2 다음
