본문 바로가기

알고리즘8

[파이썬] strip( ), lstrip( ), rstrip( ) https://programmers.co.kr/learn/courses/30/lessons/64065 코딩테스트 연습 - 튜플 "{{2},{2,1},{2,1,3},{2,1,3,4}}" [2, 1, 3, 4] "{{1,2,3},{2,1},{1,2,4,3},{2}}" [2, 1, 3, 4] "{{4,2,3},{3},{2,3,4,1},{2,3}}" [3, 2, 4, 1] programmers.co.kr 튜플 문제를 해결하면서 문자열 파싱 과정에 대해서 부족함을 느꼈다. 이제껏 strip, lstrip, rstrip에 대해서 알고는 있었지만 그저 양쪽의 공백을 없애주는 함수로 알고 있었다. strip의 정확한 기능은 인자로 들어온 특정 문자를 제거하는 기능이다. strip([chars]) : 인자로 전달된 문자.. 2021. 11. 14.
진수 변환(2진수 ,3진수 ... n진수) https://programmers.co.kr/learn/courses/30/lessons/68935 코딩테스트 연습 - 3진법 뒤집기 자연수 n이 매개변수로 주어집니다. n을 3진법 상에서 앞뒤로 뒤집은 후, 이를 다시 10진법으로 표현한 수를 return 하도록 solution 함수를 완성해주세요. 제한사항 n은 1 이상 100,000,000 이하인 자연수 programmers.co.kr 프로그래머스의 3진법 뒤집기 문제를 풀고 진법에 대한 부분이 약한 것 같다는 생각이 들어 정리하기 10진수 -> N진수로 변환하기 baseN = "" while num10: num10 , m = num1o// N , num10 % N baseN += str(m) baseN = baseN[::-1] baseN은 N진수.. 2021. 11. 6.
[파이썬] asterisk( * ) 백준 1629번 문제를 풀고 다른 사람의 답을 보았는데 신기한 답이 있었다. 단 한 줄로 문제를 해결하였다. print(pow(*map(int,input().split()))) 이것을 보고 * 에 대해 알아보기로 하였다. 기존에는 * 기호를 곱셈, 거듭제곱, 리스트 확장에만 사용하였다. 1. * 은 가변인자를 사용할 때 쓰일 수 있다. *args, **kwargs args와 kwargs는 각각 다음과 같이 쓰인다. def args(*args): print(args) def kwargs(**kwargs): print(kwargs) args(1,2,3,4) # (1,2,3,4) kwargs(a=1,b=2) # {'a'=1,'b'=1} 위의 예제의 출력결과를 보면 args는 tuple, kwargs는 dict.. 2021. 10. 19.
[파이썬] bisect 라이브러리 bisect 라이브러리를 이용하면 이진 탐색을 쉽게 구현할 수 있다. bisect 라이브러리는 정렬된 배열에서 특정 원소를 찾을 때 매우 효과적이다. bisect 내부 함수 bisect_left(a,x) : 리스트 a에서 데이터 x를 삽입할 가장 왼쪽 인덱스를 리턴한다. bisect_right(a,x) : 리스트 a에서 데이터 x를 삽입할 가장 오른쪽 인덱스를 리턴한다. 이 두 함수는 시간 복잡도 O(logN)으로 동작한다. 사용 예: from bisect import bisect_left, bisect_right a = [1,2,4,4,8] x = 4 print(bisect_left(a,x), bisect_right(a,x)) # 2 4 2021. 9. 26.
[파이썬] heapq 라이브러리 heapq는 우선순위 큐 기능을 구현하고자 할 때 사용된다. 파이썬의 heapq 라이브러리는 최소 힙으로 구성되어 있다. 따라서 단순히 원소를 힙에 넣었다가 빼는 것만으로도 시간 복잡도 O(NlogN)의 오름차순 정렬이 완료된다. heapq의 메서드 힙에 원소를 삽입할 때 -> heapq.heappush() 힙에서 원소를 꺼낼 때 -> heapq.heappop() 사용 예: def heapsort(iterable): h = [] result =[] for value in iterable: heapq.heappush(h,value) for i in range(len(h)): result.append(heapq.heappop(h)) return result result = heapsort([1,3,5,7,9.. 2021. 9. 26.
[파이썬] itertools 라이브러리 itertools는 파이썬에서 반복되는 데이터를 처리하는 기능을 포함하는 라이브러리다. itertools 중에서 유용하게 사용할 수 있는 클래스에 대하여 알아본다. 1. permutations iterable 객체에서 r개의 데이터를 뽑아 일렬로 나열하는 모든 경우를 계산한다. 사용 예: from itertools import permutations data = [ 1,2,3] print(list(permutations(data,2))) #[(1, 2), (1, 3), (2, 1), (2, 3), (3, 1), (3, 2)] 2. product iterable 객체에서 중복을 허용하여 r개의 데이터를 뽑아 일렬로 나열하는 모든 경우를 계산한다. 사용 예: from itertools import produ.. 2021. 9. 26.
[파이썬] Counter 클래스 사용법 collections 모듈의 Counter 클래스 사용법을 알아본다. Counter 클래스는 데이터의 개수를 셀 때 사용하면 편리하다. Counter 클래스를 알기 전에는 dictionary를 이용하여 카운팅을 하였다. 예를 들어 "collections"라는 문자열에 있는 각 알파벳의 수를 구해보자. def counter(word): word_count= {} for s in word: if s not in word_count: word_count[s] = 1 else: word_count[s] += 1 return word_count print(counter("collections")) #{'c': 2, 'o': 2, 'l': 2, 'e': 1, 't': 1, 'i': 1, 'n': 1, 's': 1}.. 2021. 9. 8.
정수에 대한 유클리드 호제법 a >= b이고 a를 b로 나눈 나머지를 r 이라고 하자 유클리드 호제법의 가장 핵심은 다음과 같다. a, b의 최대공약수를 (a, b) b, r의 최대공약수를 (b ,r) 이라고 하면 (a, b) = (b, r) 이 성립한다. 예를 들어, (48, 18) = (18, 12) = (12 , 6) = (6, 0) = 6 처럼 쓸 수 있다. 즉 , 뒤의 자리가 0이 될 때 까지 연산을 진행한다. 만약 두 수가 서로소라면 (17, 13) = (13, 4) = (4, 1) = (1, 0) = 1 다음과 같이 나타남을 알 수 있다. 서로소 또한 결과가 잘 나타남을 알 수 있다. 이제 유클리드 호제법을 코드로 나타내면 다음과 같다. def gcd(m, n): if m < n : m,n = n, m if n == 0.. 2021. 9. 7.

티스토리툴바