본문 바로가기

All Post269

[프로그래머스] 양궁대회 (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.
탑 프로그래머스 ..! 프로그래머스에서 기업 지원하며 코딩 테스트를 봤었는데 상위 5% 안에 들었나 보다. 탑 프로그래머스 멤버 하라고 메일이 왔다. 아직 잘 못하는데 탑 프로그래머스라니 좀 어색하다. 3달 전만 해도 1단계도 잘 못 풀었는데.. 아무튼 더 열심히 해야겠다. 2022. 1. 13.
python의 LEGB 규칙 파이썬에서 변수에 값을 바인딩하거나 변수의 값을 참조하는 경우 LEGB 규칙을 따른다. 1. L - Local의 약자로 함수 안을 의미한다. 2. E - Enclosed function locals의 약자로 내부 함수에서 자신의 외부 함수의 범위를 의미한다. 3. G - Global의 약자로 함수 바깥 즉, 모듈 범위를 의미한다. 4. B - Built-in의 약자로 open, range와 같은 파이썬 내장 함수들을 의미한다. a = 10 def test(): a = 20 print(a) test() 위 코드에서 test 함수가 호출되게 되면 a라는 변수가 바인딩하는 값을 출력하게 된다. 즉 변수가 바인딩하는 값을 참조해서 출력하고자 하므로 LEGB순으로 탐색한다. test 함수 안이 바로 local 영.. 2022. 1. 11.
python 함수의 생성과 호출 python에서 변수가 값에 대한 이름표라면 함수 이름은 코드에 대한 이름표이다. 함수를 정의하게 되면 실제로 아무것도 일어나지 않는다고 배웠다. 아래 코드를 실행하게 되면, def hello(): print("hello") 파이썬 인터프리터가 메모리에 함수 객체를 할당하고 이를 hello라는 함수 이름이 바인딩하게 된다. >>> id(hello) 4399217408 hello는 스택메모리, 함수는 힙 메모리 함수 이름은 함수 객체를 바인딩한다. def hello(): print("hello") f = hello f() f의 이름으로 hello 함수 객체를 바인딩한 후에 ( )를 통해 호출할 수 있다. 2022. 1. 11.
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.
#09 이진 탐색 정렬된 리스트에서 특정 값을 탐색할 때 순차 탐색보다 빠르게 탐색할 수 있는 알고리즘 순차 탐색 : O(n) 이진 탐색 : O(logn) ''' 1. start가 end보다 크다면 stop 2. mid 값을 정함 3. mid 인덱스의 값과 target이 같으면 return 4. mid 인덱스의 값보다 target이 작으면 mid 왼쪽에 있으므로 end 값을 mid -1 5. mid 인덱스의 값보다 target이 크면 mid 오른쪽에 있으므로 start 값을 mid + 1 ''' def binary_search(arr, start, end, target): if start > end: return None mid = (start + end)//2 if arr[mid] == target: return mid.. 2022. 1. 8.
정렬 알고리즘 코드(python) import time import random import sys sys.setrecursionlimit(int(1e9)) def bubblesort(arr): n = len(arr) for i in range(n): for j in range(0, n-i-1): # 매번 오른쪽부터 큰 값이 정렬됨 -> n-i-1 if arr[j] > arr[j+1]: arr[j], arr[j+1] = arr[j+1], arr[j] return def improved_bubblesort(arr): end_index = len(arr)-1 while end_index > 0 : swap = 0 for i in range(end_index): # 마지막으로 스왑 된 곳까지 정렬 되었다고 판단 가능하므로 좀 더 효율 if a.. 2022. 1. 8.
#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.

티스토리툴바