algorithms5 문자열로 나타낼 수 있는 순열의 개수(경우의 수) "duck"이라는 글자로 만들 수 있는 순열의 개수는 어떻게 구할 수 있을까? 수학적으로 생각해본다면 duck으로 만들 수 있는 순열의 개수는 첫 자리에 올 수 있는 글자 4개(d,u,c,k), 두번째 자리에 올 수 있는 글자 3개 ... 이렇식으로 계산하고 어렵지 않게 4*3*2*1이라는 결과를 얻을 수 있다. 일반화해서 표현하자면 길이가 n인 글자에 대해서는 n*(n-1)*(n-2)*...*1 이 된다는 것을 알 수 있다. 위와 같은 방식으로 코드를 작성할 수 있다. - 입력: str에는 순열을 만들고자 하는 문자를 넣고 prefix에는 새로 문자들을 넣어서 단어를 만들것이다. - 함수 작동 방법 1. 이는 재귀함수로 이루어져있다. 2. 재귀가 불릴때마다 str에 있는 글자 하나를 빼서 prefix에.. 2020. 2. 17. 세그먼트 트리(Segment tree) 왜 Segment tree를 쓰는가? Segment라는 단어를 사전에서 찾아보면 '부분, ..을 분할하다' 이런 뜻이 나온다. 말 그대로 구역을 나누어 트리를 만들겠다는 것이다. 무엇을 어떻게 구역으로 나누는가? 가장 흔히 나오는 예시로 배열의 부분합을 구하는 경우를 생각해보자. (세그먼트 트리가 부분합을 구하는데만 사용되는 것은 아니다. 다른 응용문제를 풀어보길 원한다면 BOJ 6549번을 풀어보길 바란다. 내가 세그먼트 트리를 공부하게 된 계기이기도 하다.) 배열 A는 100개의 원소를 가지며, 우리는 i번째부터 j번째 원소의 합을 구하려고한다. 그런데 테스트 케이스가 너무나도 많으므로 매번 i부터 j번째 원소를 더하는 것은 너무 낭비인듯 하다. 그래서 각각의 합(S[i]: 0번째 원소부터 i번째 원.. 2020. 1. 10. 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. 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 다음
