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

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)
  • 방명록

HackerRank (2)
[HackerRank w7] The crazy helix

문제: HackerRank 이 문제는 초기 배열 [1, 2, 3, ..., n]에서 구간을 flip 하는 연산과 i번째 위치에 있는 수를 구하는 연산, 수 i의 위치를 구하는 연산에 대해 처리 빠르게 처리해야되는 문제다. Balanced Binary Search Tree라는 것이 있다. 잘 알려진 것으로는 AVL tree, Red-black tree 등등이 있다. 이러한 자료구조로 구현 된 것으로는 STL container의 set과 map이 있다. STL의 응용으로 Balanced BST를 이용해야 풀 수 있는 문제는 거의 존재하지 않는데, 이 문제는 Balanced BST 중 Splay tree라는 자료구조를 이용하면 쉽게 풀린다. Splay tree에 대한 자세한 설명은 여기를 참고한다. 간단히 소..

해법 2014. 7. 22. 17:32
[HackerRank w7] Savita And Friends

문제: HackerRank or hongjun7's blog 이 문제는 $N$개의 정점과 그들 사이를 잇는 $M$개의 간선이 있는 무방향성 그래프에서 $K$번째 간선 상에 임의의 점 $P$를 잡아 $P$에서 각 정점으로 가는 최단 거리들 중 최대를 최소화 시키는 문제다. 우선 직관적으로 답의 소수점은 x.0 혹은 x.5 꼴임을 알 수 있다. 실수 연산을 피하기 위해 각 간선의 길이에 2를 곱해서 처리한다. 답(최단 거리들 중 최대 값)을 정하여, 가능한지 불가능한지 결정 문제로 바꾸어 이분 검색(혹은 Parametric search)를 통해 해결한다. 답을 $d$라 정했다고 가정하고, 각 지점으로 가는 최단 거리가 $d$ 이하가 될 수 있도록 점 $P$를 잡을 수 있는지 결정하는 방법을 설명하겠다. 문제..

해법 2014. 7. 21. 21:32
이전 1 다음
이전 다음
공지사항
최근에 올라온 글
  • Bostan Mori 알고리즘
  • 선형점화식 빠르게 계산하기
  • 다항식 나눗셈의 몫을 빠르게 구하는 방법
  • Nexon Youth Programming Cha⋯
최근에 달린 댓글
  • shortcut 만점 코드의 반례가 존재하는 것 같습니⋯
  • 왜 이렇게 되는지 정말 궁금했는데 깔끔하게 정리해주셔서⋯
  • 네, 확인하였습니다. 윗 분께서 말씀해주신 것처럼 원래⋯
  • 댓글 확인이 매우 늦었네요. 네, 확인해보니 그래프 디⋯
Total
257,040
Today
43
Yesterday
52
링크
TAG
  • z-trening
  • dynamic programming
  • majority
  • IOI2012
  • moore
  • Greedy Method
  • Algorithm
  • Tree
  • HackerRank
  • BOI
  • IOI2013
  • ioi
  • Dynamic Pramming
  • TRIE
  • idea
  • vote
  • IOI2014
  • IOI2011
  • Boyer
  • USACO
  • Parametric Search
  • optimization
  • Boyer-Moore Majority Vote Algorithm
  • Splay Tree
  • Knuth Optimization
  • Segment tree
  • BOI 2009
  • BOI 2001
  • Dijkstra
  • Divide & Conquer
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

티스토리툴바