문제 https://app.codility.com/programmers/lessons/3-time_complexity/frog_jmp/ 개구리의 처음 위치는 X이다. 개구리가 한번 점프할때, 고정된 거리 D만큼 이동할 경우 Y에 도착할 수 있는 최소 점프 횟수를 구하는 문제이다. 문제 풀이 몫과 나머지를 활용하여서 문제를 풀면 쉽게 해결할 수 있다. 코드 def solution(X, Y, D): q, r = divmod(Y - X, D) return q + 1 if r else q
permutations from itertools import permutations nums = [num + 1 for num in range(3)] for cases in permutations(nums, 2): print(cases, end=' ') permutations(iterater, reapeat)를 통해 순열을 구할 수 있다. 결과 : (1, 2) (1, 3) (2, 1) (2, 3) (3, 1) (3, 2), 가능한 모든 순서로 반복을 하지 않음 combinations from itertools import combinations nums = [num + 1 for num in range(3)] for cases in combinations(nums, 2): print(cases, end..
문제 https://app.codility.com/programmers/lessons/2-arrays/odd_occurrences_in_array/ 주어진 배열에 홀수 값들은 각각 한쌍을 이루지만, 하나의 수는 쌍을 이루지 못한다. 즉, 쌍을 이루지 못하는 수를 찾으면 된다. 문제 풀이 미리 정렬해두고, 각각의 값은 쌍을 이루므로 인덱스를 2개씩 확인하면 효율성을 높일 수 있다. 코드 def solution(A): if len(A) == 1: return A[0] A = sorted(A) for i in range(0, len(A), 2): if i + 1 == len(A): return A[i] if A[i] != A[i + 1]: return A[i] 최초에 작성한 코드는 시간 복잡도로 인해 효율성이..
문제 https://app.codility.com/programmers/lessons/2-arrays/cyclic_rotation/ 주어진 배열을 K의 수만큼 오른쪽으로 shift한 후 변환된 배열을 반환하면 되는 문제이다. 문제 풀이 K가 주어진 배열 보다 클 경우, K 값을 K %= len(A)로 변경하면 K가 크더라도 주어진 배열 크기 만큼 shift한다. 코드 from collections import deque def solution(A, K): length = len(A) if not length or length == K: return A if K > length: K %= length lst = deque(A) lst.rotate(K) return list(lst) deque를 활용하면, ..
문제 https://app.codility.com/programmers/lessons/1-iterations/ 반복문을 사용하여, 이진수에서 1과 다음에 나타나는 1사이의 차가 가장 큰 경우를 찾는 문제이다. 예를 들어, 주어진 수의 이진수가 1001이면 차는 2가 되고, 1000일 경우 0이 된다. 문제 풀이 1이 등장한 이후로 1이 다시 반복될 때까지 카운트하여, 문제를 해결한다. 코드 def solution(N): answer = 0 cnt = 0 binary = format(N, 'b') for num in binary: num = int(num) if not num: cnt += 1 else: if cnt > answer: answer = cnt cnt = 0 return answ..
namedtuple from collections import namedtuple person_info = namedtuple("info", "name age address") info = person_info("kim", 12, "111-11") info.name, info.age, info.address와 같이 접근 할 수 있다. name, age, address를 인덱스 0 ~ 2(ex: info[0])로도 접근할 수 있다. defaultdict 딕셔너리를 사용하다 보면, 어떤 키에 대한 값이 없는 경우에 대한 처리를 해야하는 경우가 있다. 딕셔너리에 대한 초기값을 지정하고자 할 때 defualtdict을 사용할 수 있다. def cnt_word(words): cnt = {} for word in ..
heapq 이진트리 기반의 최소 힙 자료구조를 사용할 수 있다. 만약 자료구조를 정렬된 상태로 유지할 필요가 있을 경우 계속해서 정렬을 하는 것 보다는, heapify하는 것이 효율적이다. import heapq heap = [] heapq.heappush(heap, 7) heapq.heappush(heap, 1) heapq.heappush(heap, 5) heapq.heappush(heap, 3) heapq.heappop(heap) 리스트를 만들고 리스트에 값을 삽입 삭제 할 경우, heapq의 메소드를 사용하면 최소힙 성질을 가진다. 최소힙의 경우, 모든 원소(k)는 자식 원소들(2k+1, 2k+2) 보다 크기가 작다. 따라서 해당 예제는 [1, 3, 5, 7]로 정렬되어 최소힙이 유지되게 된다. h..
무엇을 활용하면 좋을까? 프로그래밍 언어는 각 언어마다 제공하는 기능이 조금씩 상이하다. 파이썬의 경우 다양한 built-in function을 통해 코드를 간결하게 작성하고, 빠르게 작성할 수 있는 장점이 있다. 이를 잘 숙지한다면, 코딩 테스트와 같은 상황에서 효율적으로 문제에 접근할 수 있을 것이다. List 내 각 요소 변경 기본 적으로 리스트를 활용하기 위해서는 리스트에 값을 추가, 삭제, 변경이 필요하다. (각 함수들은 반환값이 존재하지 않는다.) 1. append # 리스트 마지막 인덱스 뒤에 값 삽입 list.append(item) 2. extend # 리스트1에 리스트2의 원소들을 가져옴 list1.extend(list2) 3. insert # 원하는 인덱스 위치에 값을 삽입 list.i..
