-
Web Crawling & Scraping
Web Crawling & Scraping Contents 웹 크롤링 & 스크레이핑이란? Beautiful Soup 사용법 로그인 및 크롤링 다양한 웹 데이터 형식 마치며 참고자료 웹 크롤링 & 스크레이핑 이란? 데이터 과학이나 머신러닝 분야에 관심이 많은 학생이라면 데이터를 구하는 과정에 있어서 적지 않은 어려움을 겪었던 적이 있었을 것이다. 많은 가공된 오픈 데이터들을 요즘은 쉽게 얻을 수 있지만, 막상 실제 데이터 분석작업을 해보려고 하거나, 실제 프로젝트를 진행해보려고 하면 원하는 오픈 데이터를 쉽게 찾기는 어렵기 마련이다. (오픈 데이터란 자유롭게 다운받고 사용할...
-
그래프의 간선 색칠 문제
그래프의 간선 색칠 문제 그래프 $G$가 주어질 때, 각 정점 $v$에 대해 자연수 색상 을 배정하여 간선으로 직접 연결된 정점 쌍마다 다른 색상을 배정해야 한다. 이 때, 배정된 최대 색상을 최소화해보자. 즉, 서로 다른 색의 수를 최소화해야 한다. 이 문제는 그래프의 정점 색칠 (Graph Coloring, Vertex Coloring) 문제로, NP-complete임이 잘 알려져 있다. 너무 어려우니까 다른 문제를 생각해 보자. 그래프 $G$가 주어질 때, 각 간선 $v$에 대해 자연수 색상 을 배정하여 간선으로 직접 연결된 정점 쌍마다...
-
STL set을 이용한 Convex Hull Trick 구현
소개 Convex Hull Trick은 여러 일차 함수들의 최댓값이나 최솟값을 찾고자 할 때 유용하게 쓰이는 테크닉입니다. 이미 많은 대회에 출제된 바 있어 최근에는 대회를 준비한다면 필수적으로 알아야 할 테크닉이기도 합니다. 혹시 이 기법에 대해 잘 모른다면 구글 등에 검색하셔서 공부하시는 것을 추천드립니다. 잘 설명된 글들이 많기 때문에 여기서는 기법에 대한 자세한 내용까지는 다루지 않을 것입니다. 주어지는 일차 함수들의 기울기가 증가하거나 감소한다면 스택 자료구조 하나만으로 간단하게 Convex Hull Trick을 구현할 수 있습니다. 만약 그렇지 않고 기울기가 들쑥날쑥한다면...
-
부동소수점 자료형에 대한 이해 1
서론 많은 프로그래밍 언어들에서 우리는 부동소수점 자료형을 사용하게 됩니다. 대표적으로 C, C++의 float와 double, 그리고 long double이 있습니다. 이러한 자료형들을 사용할 때에는 항상 듣는 주의사항이 있습니다. “오차가 발생할 수 있으니까 주의해야 해!” 이러한 경고는 듣는 것만으로는 잘 와닿지 않지만, 부동소수점 자료형들을 실제로 사용해보면 상식적으로는 이해되지 않는 어처구니 없는 상황을 목격하게 됩니다. 대표적으로 0.1 + 0.2 == 0.3이 거짓이라거나, 1.0 / 7.0을 7번 더했는데 1.0과 다르다고 나오는 것들을 보면서 비로소 이 자료형은 이런 간단한 연산 하나...
-
꼬리 재귀와 Trampoline In Scala
안녕하세요! 오늘은 스칼라 초심자를 대상으로 Tail Recursion (꼬리 재귀) 와 Trampoline 에 대해 포스팅하려고 합니다. 함수형 프로그래밍이나 모나드를 몰라도 이해할 수 있도록 노력해봤습니다~~ » 이 글을 좀 더 좋은 가독성으로 읽기 « 간단하게 1부터 n 까지 더해주는 함수를 아래와 같이 작성한 뒤 실행 해봅시다. 스택오버플로우 에러가 뜨는 것을 확인할 수 있습니다. def unsafeSum(n: Int): Int = if (n == 1) 1 else n + unsafeSum(n - 1) println(s"sum = ${unsafeSum(100000)}") // 실행결과 // Exception in...