본문 바로가기

분류 전체보기

파이썬으로 웹 크롤러(Web Crawler) 만들기 (1) 웹 크롤러(Web Crawler)는 웹 페이지의 정보를 탐색하여 수집하는 역할을 하는 프로그램을 의미합니다. 만일 우리가 비트코인이라는 이름이 들어간 뉴스가 어떤 것이 올라와 있는지 매일 검색하여 그 타이틀을 수집한다고 가정해보겠습니다. 일반적으로 많이들 사용하는 포탈 사이트에 접속후 뉴스 카테고리에 접속한 다음 비트코인이라는 검색어를 입력하고 그 결과로 나온 수많은 뉴스 제목을 하나씩 긁어서 어딘가에 붙여넣기를 하고 또 페이지를 넘겨서 다른 페이지의 제목들도 수집합니다. 그렇게 매일 작업해줘야하는 비로소 목적에 맞는 결과물을 얻을 수 있을 것입니다. 이 귀찮은 작업을 매일 사람이 한다는 것은 상상하기 어렵습니다. 시간낭비와 인력낭비가 아닐 수 없습니다. 이러한 단순 반복적 작업을 대체해줄 수 있는 것이..
1654번: 랜선 자르기 - Baekjoon Online Judge 1654번: 랜선 자르기 - Baekjoon Online Judgehttps://www.acmicpc.net/problem/1654 랜선 자르기 문제는 이분 탐색을 이용하여 범위 내에서 원하는 개수의 랜선을 만들되 그 길이는 최대값이 되도록 하는 문제이다. 원하는 값을 찾기에는 너무 많은 값을 하나씩 대입해야 하기 때문에 이분 탐색을 이용하여 가능한 후보군을 줄임으로써 시간내에 원하는 값을 찾을 수 있다. 이분 탐색 문제를 푼다고 했을 때 구현에서 차이가 나는 부분은 어떤 기준으로 중앙값을 옮겨줄 것인가이다. 이 문제의 경우 주어진 랜선을 적절하게 잘라서 원하는 개수를 맞춰주는 것이기 때문에 랜선의 길이가 중앙값 이동의 기준이 된다. 처음 중앙값은 0에서 int의 max값 사이에 있다는 것을 가정하고 그..
13. 이분 탐색 (Binary Search) 이진 탐색이라고도 부르는 이분 탐색은 간단하면서도 강력한 알고리즘입니다. 기본적인 알고리즘의 아이디어는 이미 정렬이 되어 있는 자료구조에서 특정 값을 찾을 때에 탐색 범위를 절반씩 나눠가면서 해당 값을 찾아가는 것입니다. 절반씩 나눠가면서 탐색하는 것에서 이분 탐색이라는 이름이 나왔다는 것을 알 수 있습니다. 이진 탐색 - 나무위키https://namu.wiki/w/%EC%9D%B4%EC%A7%84%20%ED%83%90%EC%83%89 예를 들어 설명해보도록 하겠습니다.아래와 같이 배열이 하나 주어졌다고 해봅시다. 0 1 2 3 4 5 6 7 8 9 2 5 6 10 12 13 15 17 19 23 여기서 우리가 알고 있는 것은 이 배열이 작은 수부터 큰 수까지 오름차순으로 정렬이 되어 있다는 것 뿐이고,..
Base64 컴퓨터 분야에서 쓰이는 Base 64 (베이스 육십사)란 8비트 이진 데이터(예를 들어 실행 파일이나, ZIP 파일 등)를 문자 코드에 영향을 받지 않는 공통 ASCII 영역의 문자들로만 이루어진 일련의 문자열로 바꾸는 인코딩 방식을 가리키는 개념이다. 베이스64 - 위키백과, 우리 모두의 백과사전https://ko.wikipedia.org/wiki/%EB%B2%A0%EC%9D%B4%EC%8A%A464 Base64는 암호화, 복호화하는 툴이다. 하지만 여기서 암호화라는 것은 정말 다른 사람들이 해독하지 못하게 막는다는 의미보다는 바로 어떤 의미인지 읽어낼 수 없게 만든다는 것에 초점이 맞춰져있을 것이다. 인코딩과 디코딩의 방법이 이미 공개되어있고 조금만 구글링해도 웹상에서 인코딩된 Base64 문자열을 ..
2162번: 선분 그룹 - Baekjoon Online Judge 선분 그룹이라는 문제는 기하 알고리즘 문제풀이의 기초이자 꽃이라고 할 수 있는 CCW를 이용하는 동시에 유니온 파인드를 섞어 놓은 문제였다. 문제를 보면서 대충 어떤 식으로 풀면되겠다는 것이 머리 속에 그려져서 로직도 금방 세우고 코딩도 금방했는데 의외로 계속 오답이 나서 짜증나는 문제였다. 문제를 살펴보면 여러 선분이 주어졌을 때, 만일 선분끼리 교차되거나 겹치게 되면 그 선분들은 하나의 그룹이 된다. 이 때 선분들을 몇 개의 그룹으로 묶을 수 있고 그룹 중에 가장 많은 선분을 포함하고 있는 그룹에 속한 선분이 몇 개인지 출력하면 된다. 문제를 보고 생각난 것은 CCW였다. 기하 문제를 풀어본 사람은 알겠지만, CCW를 이용하면 두 선분의 교차 여부를 쉽게 파악할 수 있다. 만일 CCW가 익숙하지 않은..
스태틱(static) 점프 투 자바: 07-3 정적 변수와 메소드 (static)https://wikidocs.net/228 Java로 개발하면서 많이 사용하지만 그 의미에 대해서는 깊이 이해하지 못하는 많은 표현들이 있다. 그중 하나가 static이다. 맨처음 Java를 배우게 되었을 때 가장 처음 해보는 것이 바로 "Hello, World!"를 출력해보는 것인데 이때도 우리는 static을 사용하고 있다. 바로 main 메서드에 기본적으로 포함되기 때문이다. public class HelloWorld { public static void main(String[] args) { System.out.println("Hello, Wolrd!"); } } 이 짧은 코드에도 static이 들어가있다. 그렇다면 static은 왜 사..
CCW(CounterClockWise) 알고리즘 CCW(CounterClockWise)는 외적을 이용해서 두 벡터의 상대적 위치를 파악하는 알고리즘이다. 좀더 구체적으로 설명하자면 하나의 정점을 기준으로 다른 두 정점으로 향하는 벡터가 존재할 때 각 정점의 상대적 위치를 판단하는 공식이다. 만일 하나의 정점에서 다른 정점으로 향하는 벡터를 기준으로 왼쪽에 존재하는 정점의 경우 외적은 양의 값을 갖게 되고, 상대적으로 우측에 있게 되면 외적은 음의 값을 갖게된다. 마지막으로 세 점이 하나의 직선 위에 놓이게 되었을 때 외적은 0이 된다. 이를 이용하여 다각형의 넓이 구하기, 정점의 위치판단(다각형 내부/외부 위치 구분), 볼록다각형 그리기(Convex Hull) 등 다양한 기하 문제를 풀어낼 수 있다. 2차원 평면상에 각각 x, y 좌표를 갖고 있는 세..
사이클 찾기: DFS 유향 그래프에서 사이클이 있는지 판단하고, 사이클에 포함되는 노드의 개수가 몇 개인지 세는 알고리즘으로 백준 알고리즘 저지의 9466번: 텀 프로젝트 문제가 이에 해당한다. 9466번: 텀 프로젝트 - Baekjoon Online Judge https://www.acmicpc.net/problem/9466 구글링만 해봐도 해당 문제에 대한 많은 풀이가 존재하지만, 아무래도 이런 로직은 내 코드로 정리하는게 제일 이해도 잘가고 나중에 봐도 이해하기 쉬울 것 같아서 풀이 위주로 정리해봤다. 문제에서는 프로젝트를 함께하고 싶은 학생을 선택하는 것이 나오는데 선택은 한명씩 하게 되있으므로, 각 노드에서 나가는 간선은 하나씩이라는 것을 알 수 있다. 주의해야할 것은 자기 자신도 선택할 수 있으므로 나가는 간선이 ..

티스토리툴바