작업공간

Daily Object - 정점이 주어졌을 때 최단 거리를 구하는 알고리즘( 다익스트라 )을 다시 공부해보며 익힌다. - 지난 5주 간 독학해온 웹 크롤링법으로 멜론 차트의 음원의 제목, 가수를 출력해본다. Review - 평소에 자주 사용한 음원사이트의 차트 정보를 직접 뽑아보니 재미있었고, 앞으로도 다양한 웹사이트에서 정보를 뽑아야 할 때 필요한 스킬을 배워 만족스럽다. Dijkstra Algorithm - 그래프에서 정점 간 최단 거리를 찾는 알고리즘 - 동적계획법의 관점에서 보면, 다익스트라 알고리즘은 도달 방법에서 생겨난 최단 경로 문제에 대한 동적 계획법 함수적 방정식을 푸는 연속적 근사 계획법이다. - 시간복잡도 ( 간선 E , 정점 V ) : O( |E| log|V| ) 이번 시간에 풀어본..

Daily Object - Floyd-Warshall, Topological Sort 알고리즘을 복습하고 예제를 통해 적용한다. Review - Floyd-Warshall은 학기 수업 때 시험 비중이 낮아서 중요하게 보지 않았다. 그래서 이번 모각코에서 복습을 하며 전보다 확실히 체득된 것이 느껴졌다. - Topological Sort는 학기 수업 때 과제로도 수행했었던 알고리즘이라 개념 숙지는 따로 필요없었지만 문제가 난이도가 있어 시간이 오래걸렸다. 타인의 코드를 참고하였다. Floyd-Warshall ( 백준 11404 ) 그래프에서 모든 정점 사이의 최단 거리를 구하기 위한 알고리즘 다익스트라 알고리즘과는 달리 사이클이 없는 경우 음수 가중치 처리가 가능하다. Time Complexity : O ..

Daily Object - Greedy 알고리즘을 복습하고 예제를 통해 적용한다. Review - 코드 시간복잡도를 줄이느라 애썼다. 코드의 간결화도 노력이 필요하다. Greedy Algorithm 매 순간마다 최적의 해를 찾아 진행하는 알고리즘 -> 전체적인 문제로 보았을 때 최적의 답이 아닐 수 있다. 이번 시간에 풀어본 예제 11000번: 강의실 배정 첫 번째 줄에 N이 주어진다. (1 ≤ N ≤ 200,000) 이후 N개의 줄에 Si, Ti가 주어진다. (1 ≤ Si < Ti ≤ 109) www.acmicpc.net 처음 생각한 풀이방법 1 ) N개의 수업 시작과 종료시각을 2차원 배열 time[][]에 저장 2 ) 단순화하기위해 time을 시작시각을 기준으로 오름차순으로 정렬 3 ) Worst ..

Daily Object - 동적계획법 개념을 정리하고, 예제를 풀며 응용한다. - 웹 크롤링한 데이터를 리스트로 정리한다. Review - 동적 계획법을 사용할 때 점화식을 세우는 것이 중요하다고 생각되어 N과 N+1의 상관관계를 파악하도록 노력했다. - 크롤링한 데이터를 단어 단위로 분류해봤는데 다음 시간엔 목적에 맞는 단위로 분류해봐야겠다. Dynamic Programming 작은 문제를 풀며 나아간다 -> 앞 전 시간에 했던 분할 정복법과 비슷해보인다. But 작은 문제들의 솔루션이 중복되어 사용된다는 점이 다르다. 이번 시간에 풀어본 예제 1149번: RGB거리 첫째 줄에 집의 수 N(2 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 각 집을 빨강, 초록, 파랑으로 칠하는 비용이 ..

Daily Object - 분할정복법 예제를 풀어보고, 지난 주 학습했던 시간복잡도를 예제에 적용해서 구해본다. - 웹크롤링 코드를 따라쳐보며 어떤 식으로 동작하는 지 알아본다. Review - 알고리즘 예제를 풀며 시간과 메모리 비용을 줄이기 위해 메모리 할당 방법, 조건문 설정 등을 생각하며 했더니 효율성이 훨씬 좋아졌다. - 시간이 부족해 네이버 홈페이지를 크롤링하는 데에서 멈추었다. 다음 모각코엔 크롤링한 데이터를 분석하는 시간을 가져야겠다. Divide And Conquer 문제의 크기가 작다면 풀이가 쉽다. + 문제의 크기를 최소한으로 줄여 최소 크기의 문제를 풀어 나아간다. -> 작은 서브 문제를 만들고 이를 큰 문제에 적용함으로써 문제를 해결한다. 이번 시간에 풀어본 예제 1074번: Z ..

Daily Object - 여러 알고리즘의 시간복잡도를 계산해보고 처리속도가 우수한 알고리즘을 선별할 수 있다.. - 웹 크롤링이 무엇인지 알아본다. Review - 웹 크롤링 기법을 찾아본 후, 다양한 오픈 API에서 크롤링을 해보고 싶단 생각이 들었다. 1 - Time Complexity Exercise 2 - What is Web Crawling ?

- 목표 - 2020-2학기 수강과목 알고리즘의 복습 및 JAVA를 이용한 웹 크롤링 학습 - 설명 - 총 6주에 걸쳐 Time Complexity, Divide and Conquer, Dynamic Programming, Greedy 이론 복습과 예제 풀이 - 강의자료를 참고하여 이론을 복습하고 백준 예제를 풀며 진행함 웹에서 필요한 정보들을 추출할 수 있는 웹 크롤링 학습 - 목표는 음원사이트에서 모든 곡에 대해 각각의 속성들을 받아온다. Github 201702083 - Overview 201702083 has 2 repositories available. Follow their code on GitHub. github.com - 일정 - ..