본문 바로가기 메뉴 바로가기

PS 이야기

프로필사진
  • 글쓰기
  • 관리
  • 태그
  • 방명록
  • RSS

PS 이야기

검색하기 폼
  • 분류 전체보기 (141)
    • 문제 (1)
    • 해법 (18)
    • IOI (42)
      • IOI2011 (6)
      • IOI2012 (5)
      • IOI2013 (7)
      • IOI2014 (8)
      • IOI2016 (2)
      • IOI2015 (3)
      • IOI2017 (3)
      • IOI2018 (2)
      • IOI2019 (0)
      • IOI2020 (6)
    • ICPC (52)
      • 2012 대전 (3)
      • 2013 인터넷예선 (11)
      • 2014 전대프연 (1)
      • 2014 인터넷예선 (10)
      • 2014 대전 (11)
      • 2015 이후 한국대회 (6)
      • 해외리저널 (6)
      • World Finals (4)
    • Codejam (2)
      • Korea 2012 (1)
    • 우분투&서버 (0)
    • 공부 (24)
    • 잡담 (2)
  • 방명록

Boyer (1)
Majority Vote Algorithm

Majority Vote Algorithm은 사람들이 투표를 했을 때 과반의 표를 받은 대상이 있는지, 그 대상은 누구인지 최소 회수의 비교를 통해 밝혀내는 방법이다.비교라는 것은 check(i, j) 라는 함수 호출을 통해 i번 사람과 j번 사람이 같은 대상에게 표를 던졌는지 확인하는 작업이다. 최소 회수의 비교라는 것은 check(i, j) 루틴을 최소의 회수로 부른다는 것을 의미한다. 두 가지 알고리즘을 소개할 것이다. 두 알고리즘 모두 check(i, j)를 최대 $\lfloor\frac{3}{2}N\rfloor$번 호출한다. Algorithm 1) Boyer-Moore majority vote algorithm 1번 사람부터 $N$번 사람까지 투표한 상황이 아래와 같다고 하자.3 1 2 2 1 ..

공부 2016. 6. 23. 13:28
이전 1 다음
이전 다음
공지사항
최근에 올라온 글
  • Bostan Mori 알고리즘
  • 선형점화식 빠르게 계산하기
  • 다항식 나눗셈의 몫을 빠르게 구하는 방법
  • Nexon Youth Programming Cha⋯
최근에 달린 댓글
  • shortcut 만점 코드의 반례가 존재하는 것 같습니⋯
  • 왜 이렇게 되는지 정말 궁금했는데 깔끔하게 정리해주셔서⋯
  • 네, 확인하였습니다. 윗 분께서 말씀해주신 것처럼 원래⋯
  • 댓글 확인이 매우 늦었네요. 네, 확인해보니 그래프 디⋯
Total
257,047
Today
0
Yesterday
50
링크
TAG
  • Tree
  • idea
  • Splay Tree
  • z-trening
  • IOI2013
  • Segment tree
  • Dijkstra
  • Divide & Conquer
  • Knuth Optimization
  • Algorithm
  • moore
  • BOI 2009
  • HackerRank
  • BOI
  • USACO
  • BOI 2001
  • IOI2014
  • TRIE
  • ioi
  • dynamic programming
  • optimization
  • IOI2012
  • IOI2011
  • Boyer
  • Parametric Search
  • Greedy Method
  • Boyer-Moore Majority Vote Algorithm
  • vote
  • majority
  • Dynamic Pramming
more
«   2023/03   »
일 월 화 수 목 금 토
1 2 3 4
5 6 7 8 9 10 11
12 13 14 15 16 17 18
19 20 21 22 23 24 25
26 27 28 29 30 31
글 보관함
  • 2022/11 (3)
  • 2022/10 (1)
  • 2022/09 (1)
  • 2022/08 (1)
  • 2022/07 (1)

Blog is powered by Tistory / Designed by Tistory

티스토리툴바