B_log

😅 문제 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 의 시간초과가 발생할 수밖에 없..

😅 문제 https://www.acmicpc.net/problem/6603 🤔 문제 상황 - k개 숫자들이 있는 집합에서 로또번호를 뽑기 위해 6개의 번호를 추출하는 경우를 모두 출력한다. 🧐 해결 전략 - 백트래킹을 사용해야하지만 나는 내장함수 combinations를 사용했다.. 백트래킹으로도 풀어봐야한다. 🎰 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 # main 함수 만들때 import는 안에다 써주어야 한다. def main(): from sys import stdin from itertools import combinations testcase = [] while True: n = list(map(int, stdin.read..

😅 문제 https://swexpertacademy.com/main/ SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com 🤔 문제 상황 - 여러가지 색칠을 하는데 겹치는 부분의 영역을 구하는 문제이다. 🧐 해결 전략 - 색칠할 곳을 받을때마다 해당위치에 1을 더해주어 모든 색칠 후 색깔의 수를 요소로 가지고 있는 인덱스를 찾는다. 🎰 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 T = int(input()) # testcase result = [] for _ in range(T): board = [[0 for i in range(10)] for j in..

👨‍💻 검색의 종류 - 순차검색(sequential search) - 이진검색(binary search) - 인덱싱(Indexing) 🚦 순차검색 - 일렬로 되어있는 자료를 순차적으로 검색한다. - 구현이 쉽지만 검색 대상이 많은 경우 수행시간의 증가로 비효율적이다. - O(N) 의 시간복잡도 💾 이진검색 - 효율적인 검색 방법 - 자료의 가운데 항목의 키값과 비교하여 다음 검색의 위치를 결정하고 계속 검색하는 방법 - 이진검색을 위해서는 자료가 정렬되어있어야 한다. - 자료가 추가되거나 삭제되었을 때 이진검색을 위해서는 정렬 상태를 유지하기 위한 추가 작업이 필요하다. - O(lg N)의 시간복잡도 - 출처 : https://swexpertacademy.com/

👨‍💻 관련 학습 - zip(*iterable) 함수 : 동일한 개수로 이루어진 자료형들을 묶어주는 함수 ex) a = [1,2,3], b =[4,5,6] ==> list(zip(a, b)) = [(1,4),(2,5),(3,6)] 묶은 결과는 반드시 dict이나 list로 변환해주어 사용해 야한다. 개수가 동일하지 않은 자료끼리 묶으면 개수가 작은 쪽이 들어갈 때 까지만 묶어준다. 🚦 리스트 초기화 방법 - n, m 행렬을 입력받을 경우 초기화 방법 mylist = [ list(map(int, input().split())) for _ in range(n) ] - 값이 1인 요소의 인덱스 찾기 newlist = [ (i,j) for i in range(n) for j in range(m) if mylis..

👨‍💻 특징 - key란 정렬의 기준이 되는 특정값을 의미한다. 🧮 정렬의 종류 - 버블 정렬 - 카운팅 정렬 - 선택 정렬 selection algorithm : 자료안에서 k번째로 큰, 혹은 k번째로 작은 요소를 찾는 알고리즘 정렬되지 않은 부분에서 최소값을 찾아 정렬되지 않은 부분의 가장 앞에 값과 위치를 바꿔주고 정렬된 부 분이라고 선언한다. -> 이 과정을 반복한다. (cf) 위치를 바꿀 때, a[i], a[min] = a[min], a[i]로 바꾼다.) 🚦 정렬 간 수행 속도 차이 💾 예시 - - 출처 : https://swexpertacademy.com/