공부/알고리즘
-
[python] Codility Lesson 7-1. Brackets공부/알고리즘 2021. 9. 3. 00:21
이전에 코딩테스트 여러곳 보면서 가끔 보았던 빈출? 문제 같다.. 코드를 작성하며 정답의 예외처리하는 부분이 아래와 같이 부분 부분있으면 좋지않은 코드라 생각한다. 어찌됫건 생각해본 흐름은 1. 예외상황으로 strStack이 비어있을때 좌측 bracket이 오면 그 순간 return 0 2. 좌측 bracket이 아닌 bracket이 들어올때 strStack에 append 3. 좌측 bracket이 들어올때 해당하는 우측 bracket이 있으면 strStack pop(), 그렇지 않다면 return 0 4. 마지막 예외로 strStack이 for문을 모두 돌고 비어있으면 return 1, 그렇지 않다면 return 0 100점이 나오긴했지만 영 코드도 더럽고 아쉬웠다. # you can write to ..
-
[python] Codility Lesson 6-3. Triangle공부/알고리즘 2021. 9. 2. 10:57
A리스트안의 원소를 이용해 각기 크기가 다른, 각각의 합이 한변의 길이보다 큰 세변의 삼각형을 구하는 문제이다. codility에서 easy태그가 달린 것은 조금만 생각해보면 술술 풀리는 문제같다. 아래 1번을 생 1. 삼각형 변 a c 이면 b+c > a, a+c > b 등을 만족한다 (핵심인듯) 2. 삼각형 변의 후보인 리스트 A를 sort 해준다. 3. for문을 돌리며 a+b > c를 만족하면 return 1, for문이 끝나면 return 0. # you can write to stdout for debugging purposes, e.g. # print("this is a debug message") def solution(A): # write your ..
-
[python] Codility Lesson 6-4. NumberOfDiscIntersections공부/알고리즘 2021. 8. 16. 13:44
1. Sorting section에 위치한 문제라 sort를 해야 시간복잡도에서 무사히 통과하리라 생각했지만 쉽게 방법이 떠오르지 않아 손 내키는데로 작성해 보았다. 원의 중심은 list에서 순차적으로 증가하니, 2중 for문을 돌면서 first_비교원의 최대값이 second_비교원의 최소값보다 크거나 같은경우 answer_count += 1 정확도는 100%를 달성했지만 performance에서 망가진 O(N*2) 코딜리티는 N*2을 가만두지 않는다 ㅠㅠ def solution(A): answer_count = 0 for i in range(len(A)-1): for j in range(i+1, len(A)): if i+A[i] >= j-A[j]: answer_count +=1 if answer_cou..
-
[python] Codility Lesson 6-2. MaxProductOfThree공부/알고리즘 2021. 7. 27. 02:48
간단하게 풀었지만, 고민을 좀 많이 해보았다. element가 모두 - 일때? 0을 포함 하는 모든 - 일때? 모두 양수일때? 양수와 음수가 썪여 있을때? 음수 하나 이고 양수 나머지? A[0]*A[1]*A[-1] 와 A[-1]*A[-2]*A[-3] 의 비교로 모든 경우의 숫자가 커버된다. def solution(A): # write your code in Python 3.6 A.sort() answer = list() answer.append(A[0]*A[1]*A[-1]) answer.append(A[-1]*A[-2]*A[-3]) return max(answer)
-
[python] Codility Lesson 5-4. PassingCars공부/알고리즘 2021. 7. 27. 01:46
앞선 문제들과 비교해 비교적 빨리, 무난히 마음에 들게 잘 푼거 같다. def solution(A): # write your code in Python 3.6 sum = 0 east_car = 0 for i in range(len(A)): if A[i] == 0: east_car += 1 else: sum += 1 * east_car if sum > 1000000000: sum = -1 break return sum 1. 동쪽으로 가는 방향의 차량을 for문을 돌면서 만날때 마다 1씩 더해주자. 2. 서쪽으로 가는 방향의 차량을 for문을 돌면서 만날때 마다 sum에다 1 * east_car를 해주자. 3. 문제에서 주어진 예외를 처리해주자.
-
[python] Codility Lesson 5-3. MinAvgTwoSlice공부/알고리즘 2021. 7. 27. 01:05
1. for문 2개 돌려 O(N^2) 알고리즘이지만, 막상 그림이 안떠올라 작성해보았다. (60점, performance 0점) def solution(A): min_average = 99999 for i in range(len(A) - 1): sum = A[i] for j in range(i + 1, len(A)): sum += A[j] average = sum /(j-i+1) if min_average > average: min_average = average start_index = i return start_index 1. 최소값을 큰 수로 놓고, 첫번째 for문에서 0 부터 len(A) - 1 까지 즉, start_index 각각의 min_average를 구한다. 2. 두번째 for문에서 0-1..
-
[python] Codility Lesson 5-2. GenomicRangeQuery공부/알고리즘 2021. 7. 26. 18:49
1. 처음 보고 prefix-sum이 아닌 나만의 풀이로 도전했다가 performance점수에서 0을 받아 62점을 받았다. def solution(S, P, Q): # write your code in Python 3.6 # A C G T 1 2 3 4 answer_list = list() for j in range(len(P)): min_val = min(set(S[P[j]:Q[j]+1])) answer_list.append(min_val) return change_To_int(answer_list) def change_To_int(answer_list: list)->list: answer = list() for i in range(len(answer_list)): if answer_list[i] =..