본문 바로가기

Python191

[프로그래머스] 사라지는 발판(Python) https://programmers.co.kr/learn/courses/30/lessons/92345 코딩테스트 연습 - 사라지는 발판 [[1, 1, 1], [1, 1, 1], [1, 1, 1]] [1, 0] [1, 2] 5 [[1, 1, 1], [1, 0, 1], [1, 1, 1]] [1, 0] [1, 2] 4 programmers.co.kr minimax 알고리즘 문제였다 옛날에 다른 회사 지원할 때 코딩 테스트에서 승리할 때 최대한 빨리 이기고 질 때 최대한 늦게 지는 문제를 만났었는데 그때도 못 풀었는데 지금도 못 풀었다.. 일단 완전 탐색 문제고, 모든 경우에서의 값을 구하는 것은 성공했는데, 어떤 사람이 무조건 이기는지에 대해 구현하는 데에 어려움을 겪었다. 나중에 비슷한 문제가 나왔을 때 참.. 2022. 1. 30.
[프로그래머스] 파괴되지 않은 건물(Python) https://programmers.co.kr/learn/courses/30/lessons/92344 코딩테스트 연습 - 파괴되지 않은 건물 [[5,5,5,5,5],[5,5,5,5,5],[5,5,5,5,5],[5,5,5,5,5]] [[1,0,0,3,4,4],[1,2,0,2,3,2],[2,1,0,3,1,2],[1,0,1,3,3,1]] 10 [[1,2,3],[4,5,6],[7,8,9]] [[1,1,1,2,2,4],[1,0,0,1,1,2],[2,2,0,2,0,100]] 6 programmers.co.kr 누적합을 활용한 문제 - 2차원 배열상에서 누적합을 어떻게 사용하는지 배웠다 def solution(board, skill): n,m = len(board), len(board[0]) change = [[0].. 2022. 1. 30.
[프로그래머스] 양과 늑대(Python) https://programmers.co.kr/learn/courses/30/lessons/92343 코딩테스트 연습 - 양과 늑대 [0,0,1,1,1,0,1,0,1,0,1,1] [[0,1],[1,2],[1,4],[0,8],[8,7],[9,10],[9,11],[4,3],[6,5],[4,6],[8,9]] 5 [0,1,0,1,1,0,1,0,0,1,0] [[0,1],[0,2],[1,3],[1,4],[2,5],[2,6],[3,7],[4,8],[6,9],[9,10]] 5 programmers.co.kr 쉽지 않았던 문제다. 풀면서 생겼던 문제는 현재 상태에서 갈 수 있는 노드를 찾는 과정에서 객체를 같이 참조하면서 무한루프를 돌았다. 그 부분을 어떻게 할지 고민했다. 알고리즘은 다음과 같다. 1. 루트 노드부터 .. 2022. 1. 28.
[프로그래머스] 주차 요금 계산(Python) https://programmers.co.kr/learn/courses/30/lessons/92341 코딩테스트 연습 - 주차 요금 계산 [180, 5000, 10, 600] ["05:34 5961 IN", "06:00 0000 IN", "06:34 0000 OUT", "07:59 5961 OUT", "07:59 0148 IN", "18:59 0000 IN", "19:09 0148 OUT", "22:59 5961 IN", "23:00 5961 OUT"] [14600, 34400, 5000] programmers.co.kr 주어진 조건대로 구현하면 되는 전형적인 구현 문제다 dict를 활용하여 풀었다. 00:00 입차하는 경우를 처리하기 위해 defaultdict를 -1로 초기화해줬다 나의 풀이 from .. 2022. 1. 23.
[프로그래머스] 양궁대회 (Python) https://programmers.co.kr/learn/courses/30/lessons/92342 코딩테스트 연습 - 양궁대회 문제 설명 카카오배 양궁대회가 열렸습니다. 라이언은 저번 카카오배 양궁대회 우승자이고 이번 대회에도 결승전까지 올라왔습니다. 결승전 상대는 어피치입니다. 카카오배 양궁대회 운영위원 programmers.co.kr combinations_with_replacement 를 활용해서 풀었다 나의 풀이 from itertools import combinations_with_replacement from collections import Counter def solution(n, info): max_score = 0 answer = [] for i in combinations_with.. 2022. 1. 23.
[프로그래머스] k진수에서 소수 개수 구하기 (Python) https://programmers.co.kr/learn/courses/30/lessons/92335 코딩테스트 연습 - k진수에서 소수 개수 구하기 문제 설명 양의 정수 n이 주어집니다. 이 숫자를 k진수로 바꿨을 때, 변환된 수 안에 아래 조건에 맞는 소수(Prime number)가 몇 개인지 알아보려 합니다. 0P0처럼 소수 양쪽에 0이 있는 경우 P0처럼 소 programmers.co.kr 처음에 문제를 제대로 이해 못 해서 당황했다 그냥 해당 진수로 변경하고, 0이 나올 때마다 그 앞자리가 소수인지 확인하면 된다. 나의 풀이 import math def is_prime_number(x): if x < 2 : return False for i in range(2, int(math.sqrt(x)) .. 2022. 1. 19.
[프로그래머스] 신고 결과 받기 (Python) https://programmers.co.kr/learn/courses/30/lessons/92334 코딩테스트 연습 - 신고 결과 받기 문제 설명 신입사원 무지는 게시판 불량 이용자를 신고하고 처리 결과를 메일로 발송하는 시스템을 개발하려 합니다. 무지가 개발하려는 시스템은 다음과 같습니다. 각 유저는 한 번에 한 명의 programmers.co.kr 딕셔너리를 활용하는 문제다 뭔가 더 깔끔하게 풀 수 있을 것 같긴 하다. 나의 풀이 from collections import defaultdict def solution(id_list, report, k): # 신고 당한 횟수 기록 # 해당 유저 신고한 사람 기록 # 신고 한 리스트 report_dict = defaultdict(list) report_.. 2022. 1. 19.
python 비교 연산자와 is 연산자 파이썬에서는 두 값을 비교할 때 == 연산자를 사용하게 된다. 이는 두 값이 같은지를 비교한다. 동일한 주소에 할당된 객체임을 비교하려면 is 연산자를 사용하면 된다. >>> a = 1000 >>> b = 1000 >>> a == b True >>> a is b False >>> id(a), id(b) (4399073552, 4399073584) 좀 더 작은 정수 값인 256을 바인딩하게 되면 ==와 is 연산자 모두 True를 리턴한다. 이는 a 와 b 모두 동일 객체를 바인딩하고 있다. >>> a = 256 >>> b = 256 >>> id(a), id(b) (140399467366080, 140399467366080) >>> a == b True >>> a is b True 파이썬은 정수 256까지.. 2022. 1. 11.
#10 해시 테이블 구현 dict를 직접 구현 해 보았다. open addressing 으로 구현했는데 손 가는데로 짜서 remove에서 살짝 에러가 있는 것 같다. 추후에 수정해야겠다 class Dict: def __init__(self,size=8): self.hashtable = list([None for _ in range(size)]) self.size = size self.item = 0 def get_key(self,key): return self.hash_function(key) % self.size def hash_function(self,key): return hash(key) def get_loadfactor(self): return self.item / self.size def check_cluster(se.. 2022. 1. 9.
#08 파이썬 내장 정렬(Tim Sort) 파이썬의 내장 정렬은 Tim sort 알고리즘으로 구현되어있다. tim sort는 삽입 정렬과 병합 정렬을 합쳐서 구현한 알고리즘이다. 최악에 경우에 O(nlogn) 최선의 경우에 O(n)을 보장하는 알고리즘이다. 1. 리스트가 주어졌을때 이를 run 단위로 나눈다 (원소의 개수는 32 ~ 64개) 2. run 단위로 나눈 후에 run 단위로 insertion sort를 한다. -> 원소의 개수가 적기 때문에 효율적으로 동작함 O(n) 시간 3. 정렬된 단위별로 merge sort를 진행함. 4. 어떤 순서로 run들을 merge sort 하는지에 대해 stack을 이용하여 결정한다. 추가 메모리를 사용하기 때문에 in-place 알고리즘은 아님, 안정 정렬임 2022. 1. 8.
#08 계수 정렬(Counting Sort) 계수 정렬은 특정한 조건이 부합할 때만 사용할 수 있지만 매우 빠르게 동작하는 정렬 알고리즘 데이터의 크기 범위가 제한되어 정수 형태로 표현할 수 있을 때 사용 가능. 최악의 경우에도 수행 시간O(N + K)를 보장 def count_sort(arr): counting = [0] * (max(arr)+1) sorted_arr = [] for i in arr: counting[i] +=1 for i in range(len(counting)): sorted_arr += [i]*counting[i] for i in range(len(arr)): arr[i] = sorted_arr[i] 수행 시간 비교 파이썬 내장 정렬은 정말 빠르다. 다음 포스팅에 python 구현되어있는 내장 sort인 tim sort에 대.. 2022. 1. 7.
#07 기수 정렬(Radix Sort) 기수 정렬은 각각의 자릿수를 기반으로 정렬해나가는 알고리즘이다. 안정 정렬에 속하고, 비교 정렬을 수행하지 않아서 조건이 맞는 상황에서 빠른 정렬 속도를 보장하는 알고리즘이다. 장점 : 문자열, 정수 정렬 가능 , 일부에서 nlogn 보다 빠르게 동작(비교 연산을 하지 않음) 단점 : 자릿수가 없는 것은 정렬할 수 없음. (부동 소숫점) 중간 결과를 저장할 bucket 공간이 필요함. 기수 정렬의 방법으로는 LSD와 MSD 두 방법이 있는데 MSD (Most-Significant-Digit)과 LSD (Least-Significant-Digit)을 비교 MSD는 가장 큰 자릿수부터 Counting sort 하는 것을 의미하고, LSD는 가장 낮은 자리수부터 Counting sort 하는 것을 의미함. (.. 2022. 1. 7.
#06 힙 정렬(Heap Sort) 2021.12.31 - [Comuter Science/Data Structure] - 힙 자료구조 힙 자료구조 힙 자료구조 전에 트리 자료구조의 표현법에 대해 좀 더 알아보자. 위와 같은 표현법을 사용하면 인덱스가 정해지게 된다. 즉. 왼쪽, 오른쪽 자식노드와 부모노드를 상수시간안에 접근 가능하다 hkim-data.tistory.com 힙 자료구조는 트리를 기반으로 설계된 자료구조이다. 힙 정렬은 어떤 max 값을 꺼내고 다시 정렬하는 데에 O(logn)의 시간 복잡도가 소요된다. 이를 활용해서 n개의 원소를 매번 logn을 통해 불러오므로 O(nlogn)의 시간이 소요되는 정렬 알고리즘이다. 1. 주어진 배열을 최대 힙으로 만든다(heapify) 2. n번만큼 반복하며 루트 노드와 맨 끝 노드를 바꾼 .. 2022. 1. 7.
#05 병합 정렬(Merge Sort) 합병 정렬이라고도 부르며, 분할 정복 방법을 통해 구현 퀵 정렬과는 다르게 안정 정렬에 속함 시간 복잡도는 최악, 평균, 최선 모두 O(nlogn)이며 공간 복잡도는 O(2n)이다. 입력값을 제외하면 O(n) def merge_sort(arr): if len(arr) < 2: return arr mid = len(arr)//2 low_arr = merge_sort(arr[:mid]) high_arr = merge_sort(arr[mid:]) merge_arr = [] l, h = 0, 0 while l < len(low_arr) and h < len(high_arr): if low_arr[l] < high_arr[h]: merge_arr.append(low_arr[l]) l += 1 else: merge.. 2022. 1. 6.
#04 퀵 정렬(Quick Sort) 퀵 정렬은 분할 정복을 통해 정렬을 수행하는 대표적인 정렬 알고리즘이다. 최선과 평균에서 시간 복잡도가 O(nlogn)으로 다른 정렬 알고리즘과 비교했을 때 가장 빠르다. 공간 복잡도도 주어진 배열 안에서 교환을 통해 정렬이 수행되므로 O(n)이다. - 하단에 pythonic 한 코드에서는 추가로 n의 공간을 사용하므로, O(2n)이다. 이미 오름차순, 내림차순으로 정렬되었을 때 O(n^2)이고, 또한 불안정 정렬이라는 단점이 존재한다. def quick_sort(arr, start, end): if start >= end: # 인덱스가 하나 return pivot = start left = start + 1 right = end while left arr[pivot]: # 피벗보다 작은 값이 나올때까지.. 2022. 1. 6.

티스토리툴바