목록전체 글 (229)
DevKim
- '하나'의 정점에서 다른 모든 정점으로 가는 최단 경로 [ 조건 ] - 음의 간선이 존재하지 않음 [ 기존의 선형탐색 방법의 다익스트라 ] - O(n^2) 의 시간 복잡도를 가짐 - 문제점은 노드의 개수가 10,000개가 넘어가는 문제라면 시간초과 가능성이 높음 [ 우선순위 큐를 이용한 다익스트라 ] - 힙을 이용하여 구현 - python 에선 heapq 라이브러리로 구현되어있음 - O(NongN) 의 시간복잡도 [ 과정 ] 최단거리 테이블을 초기화(자기 자신은 0, 직접 연결되어있지 않는건 무한대로 초기화) 처음엔 가장 가중치가 작은 값을 선택함 하나의 노드를 선택하고 해당 노드를 거쳐서 가는 경우를 모두 고려하여 가장 최소인 값으로 업데이트 (이때, 값이 새로 갱신된 경..
[ 문제점 ] * cpu는 cpu 내부 버스의 속도를 따르고 (더 빠름) , 메모리&주변장치는 시스템 버스의 속도를 따르기 때문에 둘 사이의 작업속도의 차이가 문제가 된다 이러한 장치 간 속도의 차를 개선하기위한 여러가지 기능이있다. [1] 버퍼 buffer = 바구니 ex. 귤 5개를 하나씩 도마로 옮기기
밑에 코드를 정상적으로 실행하기 위해, 별도의 data 폴더와 base path가 설정되어있어야한다. 사실상 네이버 뉴스의 모든 뉴스를 크롤링하기엔 불가능하다. 왜냐하면 네이버 뉴스를 클릭해보면 알겠지만, 연합뉴스,한국뉴스...등등 모두 다른 회사에서 만든 뉴스기사임을 볼 수 있다. 그렇다고 모~~든 회사에서 만든 다른 web 의 태깅들을 따로따로 입력할 수도 없는 노릇이다. 그래서 해결방안은 naver 뉴스에 연결되어있는 애들만 크롤링하는 방법이다. 검색어와, 뉴스가 발행된 날짜, 크롤링 할 페이지를 입력하면 자동으로 엑셀파일에 저장되게끔 코드가 짜여져있다 # -*- coding: utf-8 -*- import requests from bs4 import BeautifulSoup import panda..
www.acmicpc.net/problem/9466 9466번: 텀 프로젝트 이번 가을학기에 '문제 해결' 강의를 신청한 학생들은 텀 프로젝트를 수행해야 한다. 프로젝트 팀원 수에는 제한이 없다. 심지어 모든 학생들이 동일한 팀의 팀원인 경우와 같이 한 팀만 있을 www.acmicpc.net [코드] import sys N=int(sys.stdin.readline().rstrip()) for i in range(N): n=int(input()) List=[0]+list(map(int,sys.stdin.readline().rstrip().split())) visited=[0]*(n+1) group=1 for j in range(1,n+1): if visited[j]==0: while visited[j]==..
www.acmicpc.net/problem/1707 1707번: 이분 그래프 입력은 여러 개의 테스트 케이스로 구성되어 있는데, 첫째 줄에 테스트 케이스의 개수 K(2≤K≤5)가 주어진다. 각 테스트 케이스의 첫째 줄에는 그래프의 정점의 개수 V(1≤V≤20,000)와 간선의 개수 www.acmicpc.net +) 틀렸습니다 ! 가 반복적으로 나오는 사람들을 위한 반례 case case 1) 11 3 1 2 3 3 2 1 3 2 3 4 4 1 2 2 3 3 4 4 2 3 2 2 1 3 2 4 4 2 1 3 2 4 3 4 1 5 2 1 5 1 2 5 2 1 2 2 5 4 3 1 2 4 3 2 3 4 4 2 3 1 4 3 4 1 2 3 3 1 2 2 3 3 1 2 1 1 2 정답 : 'YES', 'YES',..
www.acmicpc.net/problem/4963 4963번: 섬의 개수 입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스의 첫째 줄에는 지도의 너비 w와 높이 h가 주어진다. w와 h는 50보다 작거나 같은 양의 정수이다. 둘째 줄부터 h개 줄에는 지도 www.acmicpc.net from collections import deque import sys def DFS(i, j): que = deque() if i = h or j = w: return None else: if List[i][j] == 1: que.append([i, j]) List[i][j] = 0 while que: p = que.popleft() xx = p[0] yy = p[1..
www.acmicpc.net/problem/2667 2667번: 단지번호붙이기 과 같이 정사각형 모양의 지도가 있다. 1은 집이 있는 곳을, 0은 집이 없는 곳을 나타낸다. 철수는 이 지도를 가지고 연결된 집의 모임인 단지를 정의하고, 단지에 번호를 붙이려 한다. 여 www.acmicpc.net 정답률이 꽤 낮은 문제이지만, dfs/bfs를 잘 이용하면 그리 어렵지않은 문제이다 from collections import deque import sys def DFS(i, j): que = deque() if i = n or j = n: return None else: cnt = 0 if List[i][j] == 1: que.append([i, j]) List[i][j] ..