Python/알고리즘
[자료구조] 그래프 DFS/BFS Python pseudo코드로 이해하기
Understanding DFS/BFS Algorithm through python pseudo-code 비전공자로서 자료구조를 공부하다보면 실제 문제에 적용하기 힘든 경우가 많다. 특히 입문자로서 코딩테스트 빈출 유형인 DFS / BFS는 단순히 이론을 공부하거나 다른 사람들의 코드를 보는 것으로 실력을 쌓는 것은 꽤나 먼 일처럼 느껴진다. 필자의 경우 Graph문제에 대해 깊이 우선 탐색(DFS) / 너비 우선 탐색(BFS) pseudo-code를 이해하는 것이 효과적이었어서 정리할 겸 포스팅하게 되었다. DFS 깊이 우선 탐색의 경우 두 가지 방법이 존재한다. 재귀적으로 문제를 해결하는 방식과, 반복 구조로 문제를 해결하는 방식이다. 재귀적으로 깊이 우선 탐색을 수행하는 방법 def recursiv..
N개의 연속된 자연수 리스트에서 인접하지 않은 m개 뽑기
From N consecutive lists of natural numbers, pick m that are not adjacent. 코딩테스트 대비를 위해 Heap / Queue / Stack의 선형 자료구조 문제를 풀다 보면 대부분은 0번째와 마지막 인덱스만의 예외 처리로 해결되는 경우가 많다. 문제를 풀면서 많이 나오는 듯한 느낌인데, 비슷한 유형의 예외처리가 쉽지 않아 공유해보고자 포스팅하게 되었다. [1,2,3,4,5,6,7] 과 같이 연속된 N개의 자연수에서 m개를 뽑을 때 연속된 자연수가 없는 경우만 뽑아내기 여러번 등장하는 알고리즘인 것 같은데, 생각보다 해결하기가 쉽지 않아 해당 주제에 대해 여러번 고민하다 문제를 해결했다. from collections import deque from ..
[collections] Python namedtuple 사용하기
데이터 사이언스를 하다보면, 데이터를 딕셔너리 형태로 만드는 경우가 많다. 그런데 tuple형태의 자료를 다루는 것이 불가피할 때, 일반적인 튜플의 경우 key값 할당이 불가능하므로 곤란할 때가 많다. 이 때, 내장된 collections 패키지의 namedtuple은 유용한 기능을 수행한다. tuple로 정렬된 여러 x,y좌표들에 대해 거리를 계산하는 공식을 만들었다고 가정하자. 일반적인 tuple로 값을 할당하여 계산 로직을 짜면 아래와 같이 코드가 작성 될 것이다. 일반적인 tuple pt1 = (1.0, 5.0) pt2 = (2.5, 1.5) from math import sqrt line_length = sqrt((pt2[0] - pt1[0]) ** 2 + (pt2[1] - pt1[1]) ** ..
Python의 concurrent.futures 활용하여 병렬 실행 결과 return하기
공장의 여러 tag들로 데이터를 한꺼번에 긁어와야 할 일이 생겼다. 문제는, tag 갯수가 많은데 함수가 list를 받아들이지 못해 for문으로 일일히 데이터를 받아와야 하는 상황이 생겼다. 시간을 단축시키는 일이 중요한 업무인지라 이를 병렬로 실행시키는 방법을 알아보게 되었다. 원리를 쉽게 설명하면 컴퓨터의 cpu에는 코어가 존재하고, 코어 안에는 스레드가 있다. 작업을 실행시키면, 스레드에 작업을 할당하여 실행시키는데 Python의 thread를 할당하는 함수를 사용하여 작업을 할당시켜 반복문을 돌게 하는 것이다. 알아본 결과, Python의 thread를 할당하는 패키지는 threading, multiprocessing, subprocess 등이 있는데 병렬 실행은 성공하였지만 결과를 return하..
Python 내장 패키지 itertools 도장깨기
코딩 테스트를 볼 때 내장 패키지를 알면 도움이 되는 경우가 적지 않다. 외부 패키지를 import할 수 없기 때문에, 내장 패키지를 최대한 활용하는 것이 좋다. 특히 Python의 경우 언어가 단순한 만큼 input이 커지면 시간복잡도가 다른 언어에 비해 높다. 따라서 직접 짠 모듈을 쓰는 것보다 기존의 내장 패키지를 import하는 것이 좋다. 오늘은 그 중 itertools라는 iterable한 객체를 처리할 수 있는 패키지에 대해 정리해보려 한다. 공식 package guideline은 아래와 같다. https://docs.python.org/ko/3/library/itertools.html itertools — 효율적인 루핑을 위한 이터레이터를 만드는 함수 — Python 3.9.6 문서 doc..