시간 복잡도(Time Complexity)는 인풋 크기에 비례하는 알고리즘의 실행 시간을 나타냅니다. 시간 복잡도를 잘 이해하셨다면 공간 복잡도도 어렵지 않습니다. 공간 복잡도(Space Complexity)는 인풋 크기에 비례해서 알고리즘이 사용하는 메모리 공간을 나타냅니다. 물론 공간 복잡도도 점근 표기법으로 표현할 수 있기 때문에 간편하게 Big-O 표기법을 사용할 수 있습니다. 간단한 예시 몇 가지만 봅시다. O(1) def product(a, b, c): result = a * b * c return result 파라미터 a, b, c가 차지하는 공간을 제외하면 추가적으로 변수 result가 공간을 차지합니다. result가 차지하는 메모리 공간은 인풋과 무관하기 때문에 함수 product의 공..
다른 개발자들과 함께 알고리즘에 대한 의논을 하게 되면, 자연스럽게 “시간 복잡도” 이야기가 나올 수밖에 없습니다. 시간 복잡도를 계산할 줄 알아야 원활한 대화가 이루어질 수 있겠죠. 다행히, 알고리즘의 시간 복잡도는 대개 이 중 하나입니다. O(1) O(lgn) O(n) O(nlgn) O(n2) O(n3) O(n4) O(2n) O(n!) 이 중에서도 O(1), O(lgn), O(n), O(nlgn), O(n2), O(n3) 정도가 많이 사용되고, 나머지는 흔치 않습니다. O(1) O(1)은 인풋의 크기가 소요 시간에 영향이 없다는 뜻입니다. # O(1) 함수 def print_first(my_list): print(my_list[0]) print_first([2, 3]) print_first([2, 3..
점근 표기법으로 알고리즘을 평가할 때 주의해야 할 점 몇 가지만 알아봅시다. 점근 표기법에서 n은 무엇인가? 점근 표기법에서 n이 갖는 의미에 대해 착각하는 사람들이 많습니다. 하지만 사실 n은 점근 표기법에서 인풋 크기를 나타낼 때 가장 흔히 사용되는 문자일 뿐, 별다른 의미는 없습니다. 인풋 리스트의 크기를 x라고 부르기로 하면 O(lgx), O(x), O(x^2) 등의 표기를 하겠죠. “트리”나 “그래프” 같은 조금 특수한 자료 구조가 인풋으로 들어올 수도 있습니다. 트리와 그래프가 특수한 이유는 리스트처럼 “선형적”이지 않기 때문인데요. 예를 들어서 그래프는 꼭짓점(vertex)과 변(edge)으로 이루어져 있습니다. 꼭짓점의 개수를 V라고 하고 변의 개수를 E라고 하면, 두 꼭짓점 간 최단 경로..
우리는 일단 두 가지 정렬 방법을 살펴봤습니다. 그런데 사실 이 외에도 퀵 정렬, 힙 정렬, 거품 정렬 등 여러 정렬 알고리즘이 있는데요. 그렇다면 이 많은 정렬 알고리즘 중 어떤 게 가장 좋을까요? 이 사이트를 들어가면 여러 정렬 알고리즘의 퍼포먼스를 다양한 상황에서 살펴볼 수 있습니다. 예를 들어 이미 거의 정렬된 리스트를 정렬할 때는 삽입 정렬(Insertion Sort)이 가장 빠른 반면, 무작위 순서의 리스트를 정렬할 때는 힙 정렬(Heapsort)이 가장 먼저 끝나네요. 아예 정반대로 정렬된 리스트의 경우에는 삽입 정렬이 매우 오래 걸린다는 것도 볼 수 있죠. 선택 정렬(Selection Sort)과 합병 정렬(Merge Sort)은 상황에 영향을 받지 않고 일정한 시간이 소요된다는 점도 주목..
네비게이션 어플 두 회사에서 각각 네비게이션 어플을 출시했다고 가정해 보세요. 둘 다 디자인이 훌륭하고, 사용성도 나쁘지 않습니다. 그러면 저는 어떤 어플을 사용해야 할까요? 우선 길을 정확하게 알려주고 도착 시간도 정확하게 알려줘야 합니다. 틀린 정보를 알려주는 어플은 그냥 안 쓰게 되겠죠. 그리고 두 번째로는 길을 빨리 알려줘야 합니다. 만약 길 한 번 찾아주는 게 2분씩이나 걸리면 답답해서 못 쓰겠죠. 결론적으로 누가 더 정확하고 효율적인 알고리즘을 사용하는지가 중요합니다. 서비스의 성공 여부가 알고리즘에 달려 있는 것입니다. 영화 어플 예전에는 영화를 보고 싶으면 비디오나 DVD를 빌려 봤었는데, 요즘은 넷플릭스나 왓챠플레이 같은 서비스를 구독해서 볼 수 있습니다. 영화를 직접 검색해서 볼 수도 ..
알고리즘이란? 평소에 “알고리즘”이란 말, 많이 들으시죠? 알고리즘이란, 어떤 문제를 해결하기 위한 자세한 방법입니다. 예를 들어 라면을 만들기 위해서는 냄비에 물을 끓이고, 라면 봉지를 뜯고, 스프와 건더기를 넣고, 면을 넣고, 4분 정도 기다리면 되는데요. 여기서 우리가 해결하고 싶은 문제는 라면을 끓이는 것이고, 방금 이야기한 해결 방법이 라면을 끓이는 문제에 대한 알고리즘입니다. 그런데 친구 하나는 스프랑 건더기보다 면을 먼저 넣어야 더 맛있다고 생각합니다. 또 다른 친구는 면을 익히는 중에 면을 살짝씩 위로 들어올려서 공기에 접촉시켜주면 면이 더 탱탱해진다고 주장하네요. 모두 목적은 같은데 방법이 조금씩 다릅니다. 같은 문제를 해결하기 위해서도 다양한 알고리즘이 존재하는 거죠. 좋은 알고리즘이란..
품질이 좋은 데이터를 충분한 양으로 확보하는 것은 어려운데요. 한국어 데이터를 확보하는 것은 특히 더 어렵습니다. 거기에는 몇 가지 이유가 있는데요. 먼저 한국어는 영어, 중국어, 스페인어 등과 같은 다른 언어에 비해 한국어를 구사하는 사람이 많지 않아 리소스 자체가 적습니다. 사용하는 사람이 적기 때문에 당연하게도 해당 언어로 된 좋은 데이터가 많이 만들어지지 않은 것입니다. 또 다른 이유는 한국어의 독특한 특징들 때문입니다. 앞선 레슨들에서 한국어 자연어 처리를 더 어렵게 만드는 특징들을 알아보았습니다. 한국어의 복잡하고 어려운 특징은 전처리 작업을 까다롭게 만들기 때문에 품질이 좋은 데이터를 생산하기가 쉽지 않습니다. 이러한 어려움에도 불구하고 최근 한국어 자연어 처리에 대한 연구가 활발해지면서, ..
KoNLPy는 한국어 자연어 처리를 위한 파이썬 패키지입니다. 한국어 자연어 처리를 위한 여러 작업(문장 분리, 형태소 분석, 어간 추출, 의미역 추출, 개체명 인식 등)을 손쉽게 할 수 있도록 해 줍니다. KoNLPy에 있는 대부분의 도구들은 Java를 기반으로 만들어졌습니다. 그래서, Python으로 자연어 처리를 할 때 KoNLPy를 사용하기 위해선 컴퓨터에 Java가 설치되어 있어야 하고, Python에서 Java로 만들어진 클래스를 호출하기 위한 JPype1도 설치되어 있어야 합니다. 해당 과정을 한번 진행해 볼게요. 참고로, 저희는 아나콘다 환경에서 KoNLPy를 설치하는 과정을 살펴볼 건데요. KoNLPy 설치하기JDK 설치하기KoNLPy는 Java 기반의 자연어 처리 도구들을 사용할 수 있..
KoNLPy는 한국어 자연어 처리를 위한 파이썬 패키지입니다. 한국어 자연어 처리를 위한 여러 작업(문장 분리, 형태소 분석, 어간 추출, 의미역 추출, 개체명 인식 등)을 손쉽게 할 수 있도록 해 줍니다. KoNLPy에 있는 대부분의 도구들은 Java를 기반으로 만들어졌습니다. 그래서, Python으로 자연어 처리를 할 때 KoNLPy를 사용하기 위해선 컴퓨터에 Java가 설치되어 있어야 하는데요. 맥북에는 기본적으로 Java가 설치되어 있기 때문에 그냥 pip install konlpy 커맨드만 실행해도 설치가 잘 됩니다. 하지만 m1 맥북의 경우에는 별도로 Java를 설치하고, 환경을 설정하는 과정이 필요합니다. 이번 튜토리얼을 통해 안내해 드릴게요.KoNLPy 설치하기JDK 설치하기KoNLPy는 ..
형태소 분석 한국어는 접사와 조사가 발달되어 있어 다양한 형태의 어휘 구사가 가능합니다. 예를 들어 '공부하겠다', '공부했다', '공부시킨다', '공부하더라' 등 '공부하다'라는 하나의 동사가 문맥에 따라 다양하게 사용될 수 있습니다. 이러한 활용형의 단어들을 모두 단어 집합에 넣는다면 총 단어 수가 매우 많아질 것입니다. 그러면 코퍼스의 복잡도가 증가해 분석이 어려워지겠죠? 때문에, 자연어 전처리 과정에서 형태소 분석을 꼭 해줘야 합니다. 형태소 분석이란 단어의 어근과 접사를 분리하는 작업을 뜻하는데요. 띄어쓰기 교정과 마찬가지로 형태소 분석을 위해서도 여러 분석기가 공개되어 있습니다. 그 중 대표적으로 KoNLPy를 많이 사용합니다. KoNLPy KoNLPy는 한국어 자연어 처리를 위한 파이썬 패키..