B_log

😅 문제 - A라는 리스트를 받아 하나씩 순회하며 그 요소 값이 N보다 작으면 N번째 개수를 하나 증가시키고, N+1이면 지금까지중 가장 큰 값으로 모든 수를 조정해준다. 🤔 문제 상황 - A라는 리스트를 받아 하나씩 순회하며 그 요소 값이 N보다 작으면 N번째 개수를 하나 증가시키고, N+1이면 지금까지중 가장 큰 값으로 모든 수를 조정해준다. 🧐 해결 전략 - 첫번째 : cache를 만들어 문제 상황을 그대로 구현 - 두번째: 변수를 두개 만들어 최대값을 매번 갱신해줄 최대값, N+1이 진행되었을 때 최대값을 저장할 최대값으로 정한다. 가장 중요한 것은 마지막에 O(N)으로 전체 탐색을 하며 저장된 최대값보다 작은 값을 저장된 최대값으로 갱신하는 것이다. 이를 위해 부분 갱신을 해주기 위해 N+1 이..

😅 문제 https://app.codility.com/programmers/lessons/4-counting_elements/frog_river_one/ 🤔 문제 상황 - 문제 이해가 너무너무 어려운 문제였다. - 둑을 건너기 위해, 예를 들어 거리가 5인 둑이라면 낙엽이 1, 2, 3, 4, 5 모두에 낙엽이 있는 최소 시간을 구하는 문제이다. 🧐 해결 전략 - 배열을 선언해 그 수가 나오면 0으로 초기화 하는 방식으로 한다. 🎰 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 def solution(X, A): ck = [i for i in range(X+1)] cnt = 0 for k in range(len(A)): if A[k] O(N)로 바뀌었다.

😅 문제 https://app.codility.com/programmers/lessons/3-time_complexity/tape_equilibrium/ 🤔 문제 상황 - 리스트를 긴 테이프라고 생각하여 왼쪽, 오른쪽으로 나눈다. 기준점 P를 중심으로 왼쪽의 총 합과 오른쪽의 총합 차이가 가장 작은 경우를 찾는다. - 리스트를 스캔하며 기준점을 정하는 이중 for문을 사용하였더니 무려 O(N*N)의 말도 안되는 속도가 나왔다.. - sum 함수 역시 내부적으로 스캔이 필요하므로 for문 안에 sum 을 쓰면 이중 for문의 효과가 난다. ==> 속도 이슈 발생 - 아무리 생각하여도 생각이 안나 다른 사람의 코드를 참고하였다. 🧐 해결 전략 - 양쪽의 총 합을 이미 구해놓고, 기준점만 정하며 오른쪽에서 빼..

😅 문제 https://app.codility.com/programmers/lessons/2-arrays/odd_occurrences_in_array/ 🤔 문제 상황 - 홀수들을 요소로 가진 배열이 있는데 한 개를 제외한 모든 요소는 짝수개의 짝을 이룬다. - codility는 속도 이슈에 민감해 문제가 있었다. 🧐 해결 전략 - 처음 생각한 전략은 단순히 배열을 스캔하면서 새로운 것이 나오면 check 리스트에 넣고, 이미 check 리스트에 있는 값이 나오면 그 값을 제거하는 식으로 했다. 하지만 문제는 제거하는 과정 자체에 O(N)의 스캔이 필요하므로 N*2 의 소요시간이 발생해 시간 초과가 났다. 즉, N의 길이를 가진 for문 안에서 remove를 사용하면 N*2 의 시간초과가 발생할 수밖에 없..