본 게시물은 Maximizing the Spread of Influence through a Social Network, David Kempe, Jon Kleinberg, Ev´ a Tardos를 읽고 작성한 글입니다. 1. TitleMaximizing the Spread of Influence through a Social Network 2. Abstract알고리즘의 근본 문제, 만약 개인이 새로운 제품을 사도록 설득하고, 연쇄 반응을 촉발하고 싶다면 어떤 개인 집합을 대상으로 할까.'가장 영향력 있는 노드' 선택 문제는 NP-난해, 하위 모듈러 함수 기반 분석 프레임워크 사용으로 접근할 것'근사 알고리즘'이 증명 가능한 것 외에도 성능이 좋다는 점이 있다. 3. 목표SNS 영향력 최대화를 위한 타겟 ..
전체 글
본 게시물은 On k-Path Covers and their Applications, Stefan Funke, Andre Nusser, Sabine Storandt을 읽고 작성한 글입니다. 1. TitleOn k-Path Covers and their Applicationsk-Path Cover와 그 응용에 대한 글 2. Abstract 번역더보기vertex(정점)의 집합인 V가 있는 방향 그래프 G가 있는데, 이에 대해만약 C가 k개의 node로 구성된 경로에서 어떤 node를 포함하고 있다면, 부분집합 C ⊆ V를 모두 k-Path Cover라고 한다. 이 논문은 수백만 개의 노드와 간선을 가진 도로 네트워크의 맥락에서,작은 k-Path Cover를 구성하는 것에 대한 문제를 다룬다. 많은 응용 시..
처음 목표는 운영체제 공부였지만, 공부량이 워낙 많고 혼자 공부하기에 버거운 느낌이 있어 스택 및 큐에 대한 공부를 하는 것으로 목표를 바꿨다.이후 백준에서 스택과 큐에 관련한 문제를 찾아 풀어보면서 사용법을 익혔다.꾸준히 공부하니 더 익숙해진 것 같아 다시 백준을 열심히 풀어보겠다는 다짐을 하게 되었다.
[공부 내용]백준 2164, 카드2 규칙적으로 옮겨지는 카드의 이동 후, 마지막으로 남는 카드의 숫자 맞히기 from queue import Queuen = int(input())que = Queue()for _ in range(n): que.put(_ + 1)while True: que.get() a = que.get() que.put(a) if que.qsize() == 1: print(que.get()) break 처음에는 이렇게 queue.Queue를 이용해 구현했었는데, 99%까지 채점이 되다가 시간초과가 떠서, collections.deque를 이용해 다시 구현해보았다.from collections import dequen = int(input())que = deque(..
[공부 내용]백준 18258, 큐2https://www.acmicpc.net/problem/18258 큐 연산 실행 import sysfrom collections import dequedef process_queue(cmd, q, val): if cmd == "push": q.append(val) # 큐의 뒤에 추가 elif cmd == "pop": print(q.popleft() if q else -1) # 큐의 앞에서 제거 elif cmd == "size": print(len(q)) # 큐 크기 출력 elif cmd == "empty": print(1 if not q else 0) # 큐가 비었는지 확인 elif c..
.[공부 내용]백준 4949, 균형잡힌 세상 소괄호와 대괄호를 포함한 VPS 찾기 문제 import sysdef is_balanced(sentence): stack = [] for char in sentence: if char in "([": # 여는 괄호는 스택에 추가 stack.append(char) elif char == ')': if len(stack)==0 or stack[-1] != '(': # 스택이 비었거나 짝이 안 맞으면 return "no" stack.pop() # 짝이 맞으면 pop elif char == ']': if len(..
[공부 내용]백준 9012, 괄호https://www.acmicpc.net/problem/9012 괄호 문자열이 VPS인지 아닌지 판단 import sysi = int(input())for _ in range(i): tmp = sys.stdin.readline() tmp_ = 0 for j in tmp: if j=='(': tmp_ += 1 elif j==')': tmp_ -= 1 else: continue if tmp_ 여기서도 시간초과 방지를 위해 sys를 사용했고,VPS 판단을 위해 앞에서부터 (가 나오면 +1, )가 나오면 -1을 해서만약 음수가 된다면 VPS를 실패한 것이기에 break를 해준다.최종 결과가 음수이거나 양수라면 VPS..
[공부 내용]백준 10773, 제로https://www.acmicpc.net/problem/10773 돈 관리 중 실수를 고치는 문제(?).. import sysmoney = []n = int(input())for _ in range(n): tmp = int(sys.stdin.readline()) if tmp == 0: money.pop() else: money.append(tmp)print(sum(money)) 여기서도 입력이 많기에 시간초과 방지를 위해 sys를 사용하였다.