2.675를 반올림하면 2.68인데, Python에서는 2.67로 나온다. f = 2.675 round(f, 2) # 2.67 소수점을 사용하는 알고리즘 문제에서 곤혹을 치렀는데, decimal module을 사용하여 해결할 수 있다. import decimal decimal.getcontext().rounding = decimal.ROUND_HALF_UP f = 2.675 round(decimal.Decimal(str(f)), 2) # Decimal('2.68')
# List comprehension을 사용한 알고리즘 def rotate_90_degree_1(arr): col_len = len(arr) ret = [] for i in range(col_len): ret.append(list(reversed([l[i] for l in arr]))) return ret # 일반적으로 작성하는 알고리즘 def rotate_90_degree_2(arr): row_len, col_len = len(arr), len(arr[0]) ret = [[0] * row_len for _ in range(col_len)] for i in range(col_len): for j in range(row_len): ret[i][j] = arr[row_len - j - 1][i] return..
문제 링크 : https://codeforces.com/contest/1300 A. Non-zero 문제 요약 입력된 배열을 모두 곱하거나 더해도 0이 되지 않도록 하게 만드는 최소 횟수를 출력하는 문제이다. 접근 방법 입력에 0이 있으면 곱해서 0이 되므로 0이 있는 만큼 카운트를 해주고, 더했을 때 0이 되면 1만큼 카운트를 해준다. 시간복잡도 O(n) #include using namespace std; int main(void) { int c; cin >> c; while(c--) { int n; cin >> n; int ret = 0, sum = 0; for(int i = 0; i > input; sum += input; if(input == 0..
문제 링크 : http://codeforces.com/contest/1287 A. Angry Students 문제 요약 Angry Students와 Patient Students가 있을 때, 최대의 Angry Student를 만들기까지 걸리는 시간을 구하는 문제이다. 접근 방법 P가 A보다 앞에 있으면 앞의 P는 절대 A로 변하지 않으므로, 이것을 제외한 후 P 앞에 있는 A를 대상으로 A 뒤에 있는 P의 개수 중 최댓값을 구하였다. 시간복잡도 O(n) #include using namespace std; int solution(string& S) { int init = 0; for(int i = 0; i < S.length(); i++) { init = i+1; if(S[i] == 'A') break;..
문제 링크 : https://codeforces.com/contest/1270 A. Card Game 문제 요약 숫자가 적혀 있는 N개의 카드(1~N, 중복 없음)로 카드 게임을 하는데, 카드 패에 따른 승자를 출력하는 문제이다. 접근 방법 결국 승자는 제일 높은 수가 적힌 카드를 가진 사람이므로, N을 누가 가지고 있는지 체크하여 문제를 풀면 된다. 시간복잡도 입력을 받으면서 확인을 했으니, O(n)이라고 해야할지 O(1)이라고 해야할지 모르겠지만, O(n)이 맞는 것 같다. #include #include #include using namespace std; int main(void) { int test_cases; cin >> test_cases; for(int i = 0; i < test_case..
문제 링크 : https://codeforces.com/contest/1282 A. Temporarily unavailable 문제 요약 어떤 범위 안의 직선에서 기지국이 커버를 할 수 없는 범위의 길이를 반환하는 문제이다. 접근 방법 직선의 양 끝 점을 a, b라고 하고, 기지국을 c라고 하면 3가지의 경우가 나온다. c-a-b, a-c-b, a-b-c의 경우가 되는데, 이에 맞추어서 공식을 유도하여 접근하면 된다. 시간복잡도 단순 공식 사용이므로 O(1) #include #include using namespace std; int solution(int a, int b, int c, int r) { //c의 커버리지 r이 a-b 직선에 닿지 않으면 원하지 않는 값이 출력되므로 min 사용 return..
문제 링크 : https://codeforces.com/contest/1281 A. Suffix Three 문제 요약 문장의 접미사를 체크하여 어느 나라 언어인지 출력하는 문제이다. 접근 방법 string을 reverse한 후 맨 앞에서부터 차례대로 체크하면 해결될 것 같았다. 시간복잡도 계산하기 복잡하지만, std::reverse 가 O(n)이라고 가정하고(O(1)이라는 이야기도 있지만 어떻게 구현되었는지 몰라 O(n)이라고 두자..) std::string::find도 아래의 코드 상에선 O(n)보다는 작을 것이라 생각하면(무조건 접미사가 일치할 것이라고 문제에서 주어졌으므로) O(n) 정도 될 것 같다. #include #include #include using namespace std; void s..
문제 링크 : https://codeforces.com/contest/1265 A. Beautiful String 문제 요약 '?'을 'a', 'b', 'c' 중 하나로 치환하여 인접한 두 문자가 같지 않도록 만들 수 있는지 확인하고, 가능하면 그 값을 출력하는 문제이다. 접근 방법 문자열이 A[1]부터 A[N]까지 있다고 하면(N은 입력받은 문자열의 길이), A[0]과 A[N+1]에는 더미 문자를 미리 삽입하면 A[1]과 A[N]에서도 양 옆의 문자열을 확인하면 되므로 따로 처리를 할 필요가 없어진다고 생각하였다. 시간복잡도 이미 입력 받은 값이 불가능한 값인지 체크하는 부분이 O(n)이고, 값을 생성하는 부분이 O(n)이므로 총 O(n)이 걸린다고 생각한다. #include #include using..