반응형 파이썬6 [알고리즘] 백준. ATM #11399, 검문 #2981 단계적으로 풀기에서 그리디 알고리즘 파트의 문제인 "ATM"과 수학3 파트 문제인 "검문"을 풀어보았다. ATM 예를 들어 다음과 같이 사람들이 ATM 앞에서 업무를 처리하기 위해 줄을 섰다고 하자. 그리고 밑의 숫자는 각 사람들이 업무를 보는 데 걸리는 시간이다. 각 사람들이 자신의 업무를 마치는 데까지 걸리는 시간은 다음과 같다. 이를 단순화 시켜보면, "기다리는 시간+자신의 업무 시간"만큼의 시간이 걸린다. 문제에서 요구하는 것은 모든 사람이 자신의 업무를 마치는 데 걸리는 시간을 최소화 시키도록 사람들을 줄 세우고 싶은 것이고, 그렇게 줄을 섰을 때 마지막 사람이 자신의 업무를 마칠 때까지 걸린 시간을 구하고자 하는 것이다. 위에서 "기다리는 시간+자신의 업무 시간"을 살펴보면, 결국 우리가 줄일.. 2020. 6. 28. [알고리즘] 백준. #1904 01타일 동적 계획법 파트의 또 하나의 문제이다. 알고리즘 수업을 수강한 아는 형의 말이 떠올랐다. 알고리즘은 결국 '점화식'만 잘 짜면 되는거야.. 알고리즘을 잘 알지 못하는 나로서는 이게 맞는 말인지 아닌지 감이 잘 오지 않는다 하하.. 근데 적어도 동적 계획법에 한해서는 점화식만 잘 짜도 반은 먹고 들어가는 거 같다. 이번 문제는 이렇다. 00과 1이라는 타일이 있는데 n이라는 수가 주어졌을 때 이 두 종류의 타일을 이어 붙일 수 있는 경우의 수를 말한다. 00은 타일 2개가 붙어있는 꼴이다. 표로 정리해 보면 다음과 같다. n 1 2 3 4 타일 연속체 1 00, 11 001, 100, 111 0011, 1001, 1111, 0000, 1100 붙일 수 있는 타일 종류의 수 1 2 3 5 뭔가 패턴이 보일.. 2020. 6. 8. [알고리즘] 백준. #15649 N과M(1) 이번 문제는 "백트래킹(backtracking)"에 관한 문제라는데, 솔직히 백트래킹이 뭔지 몰랐다. *한국어로는 '퇴각 검색'이라고 한다. 어감에서 느껴지는 의미로는 뒤로 추적해가면서 뭔갈 풀어내는 거 같긴 한데,, 찾아보니 문제를 푸는 모든 경우의 수를 고려하되, check point를 잡아 놔서 풀다가 막히면 check point로 돌아가 다른 풀이를 모색하는 것 같다. 모든 경우의 수를 하나의 트리 형태로 구현해 놓고, 트리를 깊이 우선 탐색(dfs)을 하다가 막히면 부모 노드로 가서 다시 탐색을 하는 식인 것 같다. 여기서 부모노드가 일종의 check point 역할을 한다. 주로 재귀, 큐, 스택을 이용해서 푼다고 한다. 다시 check point로 돌아가기 위해 재귀적인 방식이나 스택을 쓰는.. 2020. 6. 4. [알고리즘] 백준. 정렬 #2750 요즘 백준 문제 풀이를 하루에 하나 정도 해 나가고 있다. 단계별로 풀이 중에서 하루에 한 단계씩, 그 중에 하나를 골라서 하고 있다. 오늘은 정렬이 주제였는데, 시간복잡도가 O($n^2$)인 정렬을 수행하는 문제였다. 파이썬을 사용하니 확실히 코드가 간결하고 짜기 쉽다. list를 이용해서 쉽게 구현할 수 있었다. 삽입 정렬과 비슷하게 구현된 거 같은데, 숫자가 하나씩 주어져서 이런 식으로 구현하는 게 나을 거 같았다. 예제 입력은 다음과 같다. 처음에 숫자의 개수를 입력 받고 그 뒤에 숫자가 하나씩 입력된다. 5 5 4 3 2 1 이에 대한 출력값은 오름차순으로 정렬된 다음과 같아야 한다. 1 2 3 4 5 다음은 구현한 코드이다. ### 정렬 n = int(input()) ls = [] for i .. 2020. 6. 1. 네이버 웹툰 베스트 댓글 크롤링-3 원래 2편 정도로 끝내려 했는데 3편까지 오게 되었다. 3편에서는 본격적으로 코드를 살펴보며 크롤링을 진행하고자 한다. 먼저 2편에서 chrome driver와 selenium, bs4 패키지 설치가 되었다면 다음과 같은 모듈들을 import 해 잘 설치가 되었는지 확인한다. import os from bs4 import BeautifulSoup from selenium import webdriver #import requests #request+bs4 조합만으로도 crawling가능 import time 여기까지 별 이상이 없다면 이제 크롤링을 위한 준비물은 다 챙긴 것이다. base_url = 'https://comic.naver.com/webtoon/weekday.nhn' #chrome_dirver.. 2020. 3. 2. 네이버 웹툰 베스트 댓글 크롤링-1 필자가 파이썬을 배우고 난 후 가장 처음 해 본 프로젝트가 크롤링이었다. 지금은 웬만큼 익숙해 져서 크롤링 코드를 짜는 데 그리 오래 걸리지 않게 되었다. 그냥 무작정 코드를 따라하는 것보다 기본적으로 어떤 원리로 동작하는 지에 대한 배경 지식이 있다면, 그저 코드를 따라하는 것을 넘어서 자신만의 크롤러를 만드는 데에도 도움이 될 거라 생각된다. 따라서 1편에서 먼저 기본 개념과 작동 원리에 대해 설명한 후에 2편에서 준비 사항, 3편에서 코드에 대한 자세한 설명을 하고자 한다. 크롤링을 위해 필요한 기본 개념 우선, 크롤링이란, crawl: 기어간다. 라는 뜻인데, 거미와 거미줄의 비유를 생각해보면 되겠다. 우리가 인터넷을 'web'이라 부르는 것처럼 거미줄을 떠올려 보면 그 web을 기어다니며 정보를.. 2020. 3. 1. 반응형 이전 1 다음
