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

PS 이야기

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

PS 이야기

검색하기 폼
  • 분류 전체보기 (134)
    • 문제 (1)
    • 해법 (15)
    • IOI (42)
      • IOI2011 (6)
      • IOI2012 (5)
      • IOI2013 (7)
      • IOI2014 (8)
      • IOI2015 (3)
      • IOI2016 (2)
      • 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)
    • 공부 (21)
    • 잡담 (1)
  • 방명록

Google Code Jam 2022 Round 2 풀이 및 후기

오랜만에 풀이 및 후기 글을 적는다. Google Code Jam은 매년 꾸준히 참가해왔다. 그동안 PS 공부할 시간적 여유가 없어서, 참가만 해왔었고, 다행히 최근에는 육아휴직으로 시간이 생겨서 밀린 PS 공부를 했다. 주로 최근에 well-known이 된 알고리즘/자료구조들을 공부하고 익히는 시간이었다. 다만, 최근 Round 2 성적이 최근에 공부한 것을 감안했을 때 아쉬움이 많이 남는 결과라 현재 심경과 풀이를 정리할 겸 포스팅을 시작한다. A. Spiraling Into Control Spiral 모양의 $N \times N$ 크기의 행렬이 있을 때, 원하는 만큼 shortcut을 놓아 정확히 $K$ 번의 이동으로 출발점 $1$에서 도착점 $N^2$으로 가는 문제다. Shortcut이 하나도 없..

해법 2022. 5. 16. 00:41
Hu-Tucker Algorithm

유용한 링크: MIT 강의 자료 어떤 문자열이 있고, 각 알파벳에 바이너리를 할당한다. 할당된 바이너리는 어떤 것이 다른 것의 prefix가 되면 안 된다. 문자열을 알파벳에 할당된 바이너리로 표현할 때 바이너리의 크기를 최소화하는 문제가 있다. 이는 매우 일반적인 압축 알고리즘을 필요로 하는 상황이다. Huffman Coding은 이 문제에 대한 최적해를 $O(N \lg N)$ 시간에 구한다. 각색은 다르지만, Huffman Coding과 같은 상황인 문제는 BOJ 13975번 파일 합치기 3이 있다. Huffman coding - Wikipedia From Wikipedia, the free encyclopedia Jump to navigation Jump to search Technique to c..

공부 2022. 5. 3. 03:23
Skew Heap

유용한 링크: 위키백과, Skew heap visualization, NTU 강의자료 Skew heap(혹은 self-adjusting heap)은 이진트리로 구현된 힙 자료구조다. 우리가 배운 기본적인 힙은 완전이진트리이므로 배열과 인덱스를 이용하여 편하게 구현이 가능하다. 그러나, Skew heap은 완전이진트리가 아닌 그냥 이진트리이므로 배열을 이용한 구현을 할 수 없다. 그렇다면, 일반 힙이 아닌 Skew heap이 필요한 순간은 언제일까? 바로, 서로 다른 두 힙을 하나로 빠르게 합치고 싶은 순간에 쓸 수 있다. 서로 다른 두 힙을 하나로 합치는 것을 merge 연산이라고 한다. Skew heap은 merge 연산 중간, 왼쪽 자식과 오른쪽 자식을 무조건적으로 바꿔주어 균형을 유지한다. 이 me..

공부 2022. 5. 3. 02:00
이전 1 2 3 4 ··· 45 다음
이전 다음
공지사항
최근에 올라온 글
  • Google Code Jam 2022 Rou⋯
  • Hu-Tucker Algorithm
  • Skew Heap
  • Nexon Youth Programming⋯
최근에 달린 댓글
  • gumgood 님이랑 ㅇㅇ 님이 말⋯
  • 왜 4N개가 되는지 잘 모르겠⋯
  • 그 부분은 서브태스크2에 대⋯
  • 지금 적혀있는 것이 맞습니다.
Total
227,245
Today
106
Yesterday
92
링크
TAG
  • USACO
  • Parametric Search
  • BOI
  • moore
  • BOI 2009
  • Dynamic Pramming
  • Divide & Conquer
  • idea
  • Dijkstra
  • TRIE
  • Tree
  • Splay Tree
  • IOI2012
  • Algorithm
  • Boyer
  • BOI 2001
  • IOI2011
  • dynamic programming
  • IOI2014
  • IOI2013
  • Knuth Optimization
  • ioi
  • vote
  • z-trening
  • Boyer-Moore Majority Vote Algorithm
  • Greedy Method
  • Segment tree
  • HackerRank
  • majority
  • optimization
more
«   2022/05   »
일 월 화 수 목 금 토
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/05 (3)
  • 2021/08 (1)
  • 2021/03 (2)
  • 2020/09 (7)
  • 2019/05 (2)

Blog is powered by Tistory / Designed by Tistory