전체 글33 n의 거듭제곱 구하기 (큰 수의 큰 제곱수 구하기) n의 제곱을 구할 때 for문을 이용하여 n번 제곱하면 시간복잡도가 O(n)이다. (아래의 코드는 5를 1000제곱 했을 때의 계산을 구하고자 하는데, 이럴 경우 for문으로 1000번을 돌려야 한다.) int n = 5, k = 1000; long long result = 1; for(int i = 0; i < k; i++) result *= n; k가 작은 수라면 문제가 없지만 k가 1000도 아닌 100,000,000처럼 큰 수이면 어떻게 될까? 그럴 때에는 아무리 O(n)이라도 시간이 꽤 오래 걸릴 것이다. 이럴 때 연산 시간을 O(logn)까지 줄이는 방법이 있다. 재귀함수 등 여러가지 방법이 있으나 이번에는 지수 계산을 이용한 방법으로 해결해보았다. 간단한 예시로 2를 10번 제곱한다고 생각해.. 2020. 1. 6. VS Code gdb 실행시 파라미터 값 넣기 디버깅 탭에서 톱니바퀴 모양을 눌러 launch.json 파일에 들어간다. (F1키를 누르고 launch.json이라고 쳐도 된다.) launch.json에 아래 내용을 추가하고 원하는 인자들을 넣어주면 GDB 사용 시에도 파라미터값들을 넣을 수 있다. "args": ["-s", "0", "10", "32"] 2019. 10. 14. VS Code GDB not working (-g) GDB를 이용하기 위해서는 파일을 컴파일 할 때 -g 인자를 붙여 컴파일을 해야한다. -g 인자로 컴파일이 된 실행파일 만이 정상적으로 디버깅이 된다. gcc test.c -o test 위 코드를 아래와 같이 수정한다. gcc -g test.c -o test 2019. 10. 13. VS code GDB 사용 시 -environment-cd 에러 윈도우 환경에서 VS Code의 GDB를 사용하고자 했을 때, 아래와 같은 에러가 발생했다. 경로 중의 한글이름을 없애주자 에러가 해결됐다. 2019. 10. 13. Prim algorithm (프림 알고리즘) Prim algorithm (프림 알고리즘) 프림 알고리즘은 greedy algorithm의 일종이며, 최소신장트리 문제를 해결하기 위한 알고리즘이다. Greedy algorithm과 최소신장트리에 관한 개념은 앞 글에서 다루었다. 앞에서 그래프를 G=(V,E)로, 신장 트리를 T=(V,F)로 표기하기로 했다. 우리는 최소신장트리가 되는 F를 찾는 것이 목표다. 그래프 G는 다음과 같다. 프림 알고리즘은 한 점에서 시작하여 계속 최적의 선택을 해나간다. 그 시작점을 v1이라고 해보자. v1을 담고있는 새로운 집합 Y(최소신장트리의 vertex를 담는다.)를 만들고, 집합 F(최소신장트리의 edge를 담는다.) 는 공집합으로 초기화를 해준다. 앞으로 최적의 선택을 해가며 Y와 F를 채워나갈 것이며, 집합 .. 2019. 5. 15. Greedy algorithm(탐욕 알고리즘)/ Minimum spanning tree(최소 신장 트리) Greedy algorithm(탐욕 알고리즘) Greedy algorithm은 그 당시 "가장 최고"라고 생각되는 것을 선택한다. 각 선택은 지역적으로 최적(locally optimal)이 되는 것이다. 하지만 그 것이 전체적으로 최적(globally optimal)이 아닐 수 있다. 따라서 알고리즘이 정말로 최적의 답을 주는지 체크해야 한다. Greedy algorithm을 해결하는 방법은 총 세 가지의 단계로 이루어진다. 1. 선택과정 : 지역적으로 가장 최선의 선택을 한다. 2. 적정성 검사 : 그 선택이 문제의 조건을 벗어나지 않는 지 확인한다. 3. 해답검정 : 방금 한 선택으로 문제가 해결되었는지 확인한다. 이렇게만 설명을 하면 감이 오지 않을 수 있으니 예시를 함께 보자. 가령 500원, 1.. 2019. 5. 14. 이전 1 2 3 4 다음
