본문 바로가기

Hacks

 (19)
위상정렬 개요 수많은 정렬 알고리즘 중 위상정렬은 어떤 알고리즘인 걸까? 위상정렬이란? 모든 조건이 만족될 수 있도록 정해져 있는 순서를 일직선으로 정렬시키는 것이 위상정렬이다. 즉, 이미 정해져 있는 순서의 조건에 맞춰서 정점들을 일직선으로 정렬시키는 것이다. 따라서 위상정렬은 항상 시작점이 존재한다. 위상정렬을 할 수 없는 몇 가지 상황이 있다. 1. 시작점이 정해져 있지 않다면 위상정렬을 할 수 없다. 2. 그래프에 사이클이 있다면 위상정렬을 할 수 없다. (사이클이 있으면 명확한 시작 지점이 없으니까) 위상정렬의 흐름 정렬이 이루어지는 흐름에 대해 이야기하기 전에 "진입 차수"라는 용어를 설명하고 넘어가겠다. 진입 차수란? -> 해당 정점으로 들어올 수 있는 길인 간선이 몇 개 존재하는지가 진입 차수이다...
파이썬에서 csv 파일에 데이터를 쓰고, 읽어오기 개요 csv에 인터넷에서 수집한 데이터를 저장하고 그 csv 파일에 적힌 데이터를 파이썬에서 다시 읽으려면 어떻게 해야될까? csv란? 엑셀 파일 형식처럼 데이터가 저장된 파일이다. 주의할 점은 엑셀과 같은 프로그램으로 csv를 읽을 때 유니코드 방식으로 읽어야 한다! 파이썬에서 csv 파일을 작성해보자 쓰는 건 그렇게 어렵지 않다고 생각해서 그렇게 길게 이야기하지 않으려고 한다. import csv with open("samples.csv", "w", encoding="utf8", newline='\n') as f: fieldnames = ["name", "country", "age"]# field의 제목이 되는 문자열들을 미리 저장해둔다. wr = csv.DictWriter(f, fieldnames=..
클로저 https://shoark7.github.io/programming/python/closure-in-python Python의 Closure에 대해 알아보자 Python에서 유용한 Closure에 대해 살펴봅니다. shoark7.github.io 위의 블로그에서 발견할 수 있었던 클로저를 사용한 코드이다. def in_cache(func): cache = {} def wrapper(n): print(cache) ## !!!! if n in cache: return cache[n] else: cache[n] = func(n) return cache[n] return wrapper def factorial(n): ret = 1 for i in range(1, n+1): ret *= i return ret f..
파이썬 itertools의 조합 Combinations 구현 개요 파이썬의 itertools 라이브러리에는 데이터를 셀 수 있도록 도와주는 유용한 기능들이 있다. 순열을 만들어주는 permutations도 있고 가장 긴 길이를 가진 객체를 기준으로 객체들을 인덱스 단위로 묶어주는 zip_longest도 있다. itertools에는 조합을 만들어주는 Combinations도 있는데, 이는 어떻게 작동되고 구현되는 것일까? 조합이란? 말 그대로 수학식 nCr이다. 서로 다른 n개의 원소를 가지는 어떤 집합을 조합이라고 한다. 수학식으로 보자면 아래와 같다. 그럼 이 조합이 파이썬에서는 어떻게 나타날까? 파이썬에서 조합이 기능하는 방법 from itertools import combinations arr = [1,2,3,4,5] com_arr = list(combina..
파이썬 itertools의 순열 Permutations 구현 개요 파이썬의 itertools 라이브러리에는 데이터를 셀 수 있는 좋은 기능들이 많이 들어있다. 여기에 zip_longest나 조합인 combinations도 있다. 순열? 말 그대로 수학에 등장하는 nPr 이다. 서로 다른 n개의 원소에서 r개를 중복없이 순서에 상관있게 선택하는 혹은 나열하는 것을 순열이라고 한다. 중복 없이가 키 포인트라고 생각한다. 중복 순열, 중복 조합은 따로 존재하니 말이다. 공식적인 수학식은 아래와 같다. 파이썬에서의 순열 이제 파이썬에서 순열이 어떻게 작동하는지 보자. from itertools import permutations arr = [1,2,3,4,5] per_arr = list(permutations(arr, 2)) print(per_arr) # [(1, 2),..
파이썬 내장 함수 zip 구현 개요 iterable한 객체들을 인덱스에 맞게 묶어주는 내장 함수인 zip. 이러한 파이썬의 유용한 내장 함수인 zip의 기능은 어떻게 구현된 것일까? 우선 zip의 기능을 눈으로 확인해보자. zip의 기능 arr = [1,2,3,4,5] names = ["Kim", "Lee", "Hong"] zip_arr = [data for data in zip(arr, names)] print(zip_arr) # -> [(1, 'Kim'), (2, 'Lee'), (3, 'Hong')] 위와 같이 zip은 2개 이상의 itrerable한 객체를 인덱스에 맞게 묶어준다. 중요한 건, 객체끼리 길이가 맞지 않는다면 가장 짧은 길이를 가진 객체를 기준으로 묶이기 때문에 모든 데이터가 묶이지 않을 수 있으니 유의하자. 가장..
dictionary에 값 추가하기 dictionary.get(key, default) 딕셔너리 객체의 메소드인 get을 사용하면 dictionary가 비어있더라도 key값을 새로 넣어 value를 넣어줄 수 있다. my_dict = {} participants = ["marina", "josipa", "nikola", "vinko", "filipa"] completion = ["josipa", "filipa", "marina", "nikola"] # 빈 딕셔너리에 데이터 넣기 for participant in participants: my_dict[participant] = my_dict.get(participant, 0) + 1 # 딕셔너리에서 일치하는 key가 있다면 -1 for com in completion: my_dict[com..
2차원 배열을 1차원 배열로 변환하는 방법 1. sum 함수를 사용하여 1차원 배열로 변환하기 num_list = [[0, 1, 1, 0, 1, 0, 0], [0, 1, 1, 0, 1, 0, 1] # 2차원 배열에서 1차원 배열로 num_list = sum(num_list, []) 결과값은 num_list => [0, 1, 1, 0, 1, 0, 0, 0, 1, 1, 0, 1, 0, 1] 이렇게 변환될 수 있는 이유는 sum 함수의 계산 과정에 있다. 보통 sum 함수는 sum(iterable)로 많이 사용되어, iterable 객체에 있는 요소들의 합을 반환해준다. 하지만, sum 함수에는 2개의 파라미터를 넣을 수 있다. sum(iterable, start) start는 간단히 말하면, iterable의 sum 값에 start를 더해줄 것이라는..
문자열 안에 있는 숫자를 훼손 없이 추출하는 방법 string_ex = "{{20, 111}, {111}}"에서 숫자를 형태 그대로 추출하는 방법 1. 정규문자식을 사용 import re string_ex = re.findall("\d+", string_ex) findall을 사용하는 방식은 데이터가 많으면 시간이 오래 걸릴 수 있다. 보통 선형의 시간이 소요되지만, 데이터가 많으면 지수 시간이 걸릴 수 있다. 2. for문을 사용 number = "" for data in string_ex: if data.isdigit(): number += data else: if number != "": arr.append(number) number = "" 3. 숫자 주변에 있는 문자열을 제거한 후 for문을 사용 string_ex = string_ex.repl..

티스토리툴바