레프네 약방

레프네 약방

  • 분류 전체보기 (147)
    • 알고리즘 문풀 (62)
      • AtCoder 연습 (6)
      • BOJ 연습 (27)
      • Codeforces Problemset 연습 (4)
      • Others (25)
    • 수학 이론 (39)
      • 정수론 (10)
      • 미적분학 (3)
      • 추상대수학 (11)
      • 선형대수학 (2)
      • 이산수학 (10)
      • 경시 테크닉 (3)
    • 수학 문풀 (20)
      • 경시 (내 풀이) (5)
      • 경시 (남의 풀이) (2)
      • 대입 스타일 (4)
      • 기타 (9)
    • CS 이론 (14)
      • 자료구조 (3)
      • 알고리즘 (11)
    • 통계학 (1)
      • 2019-1 일반통계학 (1)
    • 물리학 이론 (3)
      • 전자기학 (1)
      • 양자역학 (2)
    • 화학 이론 (3)
      • 물리화학 (3)
      • 계산화학 (0)
    • Misc. (0)
      • Computational Number Theory (0)
  • 홈
  • 태그
  • 미디어로그
  • 위치로그
  • 방명록
RSS 피드
로그인
로그아웃 글쓰기 관리

레프네 약방

컨텐츠 검색

태그

더블카운팅 조합론 물리화학 그래프이론 수학문풀 열역학 경시수학 AOPS 수학 Codeforces 함수방정식 Russian Code Cup ps-hell 물리 정수론 computer-algebra 화학 computer_algebra approximation approx

최근글

댓글

공지사항

아카이브

알고리즘 문풀(62)

  • 8/1 연습

    2017.08.02
  • 7/30 ~ 7/31 연습

    2017.08.01
  • 7/29 연습

    2017.07.30
  • 7/27~7/28 연습

    2017.07.29
  • 7/26 연습

    2017.07.27
  • 7/25 연습

    2017.07.26
8/1 연습

2820. 자동차 공장 문제 : http://icpc.me/2820 세그먼트 트리의 클래식한 활용 문제. 사실 suhgyuho가 준 문제집에 있던 건데 이제서야 풀었다(...) 이 문제의 아이디어는 트리를 Segment Tree나 Fenwick Tree같은 구간 자료구조와 엮을 때 자주 쓰는 트릭 중 하나인데, 어떤 노드 \(v\)의 서브트리 (\(v\) 포함) 를 DFS-numbering에서 붙은 번호 \([d[v], f[v]]\)의 구간으로 처리하는 것이다. 이 트릭을 적용하고 나면 문제의 쿼리는 이렇게 바뀐다 : p 쿼리 : 구간 \((d[a],f[a])\)의 원소에 \(x\)를 더한다. (range update)u 쿼리 : 구간의 \(d[a]\)번째 원소의 값을 구한다. (point query) ..

2017. 8. 2. 01:23
7/30 ~ 7/31 연습

3584. 가장 가까운 공통 조상 문제 : http://icpc.me/3584 옛날 ICPC문제여서 그런지 진짜 LCA를 대놓고 묻는 문제. 이 때는 아직 LCA가 고ㅡ급 알고리즘이었나보다. 테스트 케이스마다 배열 초기화에 주의하도록 하자. LCA에 대해서는 더 잘 설명해놓은 글들이 천지빽가리.http://blog.naver.com/PostView.nhn?blogId=kks227&logNo=220820773477 Time Complexity : \(O(Tn)\) 8984. 막대기 (KOI '13)문제 : http://icpc.me/8984http://oj.uz/problem/view/KOI13_game BOJ AC 기준으로 게시.문제 조건을 잘못 이해해서 이거 완전 NP 아니냐? 하고 풀이를 깠다. 이해..

2017. 8. 1. 02:04
7/29 연습

2969. 메뚜기 (COCI 08/09 Contest #1 5번) 문제 : http://icpc.me/2969 오래전에 친구가 교내 대회에 냈던 문제인데, 그때 아무생각없이 \(O(n^4)\)이랑 \(O(n^3)\) 생각하고 끝냈던 문제. 일단 \(dp[i][j]\)를 \((i,j)\)에서의 최장 경로라고 하자. 이제 각각 \(n\)개씩의 행/열에 대해서 \(dp\)값과 좌표를 저장해두는 자료구조를 만든다. 높이가 낮아지는 순서대로 탐색하면서, i+1열, i-1열, j-1열, j+1열에 저장된 dp값들 중 조건을 만족하면서 가장 큰 dp값을 \(D\)라고 하면, \(dp[i][j]=D+1\)이 된다. 자료구조를 맨 처음에는 set으로 했는데, set을 허투루 썼더니 메모리 초과가 났다(...) 여윽시 s..

2017. 7. 30. 10:50
7/27~7/28 연습

어제 올리려고 하다가 9시에 자버렸다 ㅁㄴㅇㄹ... 이번에는 MWT 특집.2011. 암호코드문제 : icpc.me/2011 간단한 dp인데, 0인 경우를 생각해주지 않으면 가버릴 수 있다. 입력 문자열을 \(S\)라고 하고, \(D[i]\)를 \(S_1 \cdots S_{i-1} \)를 해석할 수 있는 경우의 수라고 두자. 입력이 0으로 시작하지 않는다는 것이 보장되어 있으므로 \(D[2]=1\)이다. 이제 dp를 앞에서 뒤로 뿌려주자.\(S_i \neq 0\)인 경우, \(S_i\)를 하나의 암호문으로 해석할 수 있으므로 \(D[i+1]+=D[i]\).\(S_i \neq 0 \wedge 10S_i + S_{i+1} < 27\)인 경우, \(S_iS_{i+1}\)를 하나의 암호문으로 해석할 수 있으므로 ..

2017. 7. 29. 08:32
7/26 연습

#1. 중량제한 문제 : icpc.me/1939 굉장히 다양한 풀이가 가능한 문제인데, description을 잘못 이해해서 ㅂㄷㅂㄷ하다가 결국 풀이를 까봤다. 1. BFS 물건을 보내는 공장을 \(s\), 받는 공장을 \(t\)라고 하자.또 각각의 정점까지 수송할 수 있는 최대의 비용을 \(F[v]\)라고 하자.(정점 \(v\), c=\(s\)에서 \(v\)까지 옮길 수 있는 최대 비용)의 순서쌍을 저장할 수 있는 큐 \(Q\)를 잡고, \(Q\)에 \((s,F[s]\leftarrow \infty)\)를 넣으면서 BFS 개시. \(Q\)가 빌 때까지, \(Q\)의 front \(k\)에 대해서 \(k.v\)에 연결되어 있는 점 \(u\)들을 보는데, \(min(k.c,bridge\_capacity[v\..

2017. 7. 27. 18:51
7/25 연습

1. 이상한 수열 (OJUZ #10) http://icpc.me/11917 http://oj.uz/problem/view/OJUZ10_bizarre 풀이 : oj.uz에서 처음 봤을 때 아무 생각 없이 62점을 받고 넘겼던 문제다. 100점 풀이 생각 못한 뚝배기를 매우 쳐라 \(M\)이 비상식적으로 크므로, \(B_i\)의 값을 거의 닫힌 꼴로 구할 수 있을 것이라는 생각을 해야 한다. \(S\)를 오름차순으로 정렬한 뒤, \(B_{n+1}\)의 값 (\(S_1, S_2, \cdots S_n\) 중 서로 다른 수의 개수)이 어떤 \((S_i,S_{i+1}]\)에 있게 되면 이 값은 \(S_{i+1}\)로 수렴하고(편의상 \(S_{n+1} = \infty\)라 두자), 그 전까지는 값이 1씩 증가하게 됨..

2017. 7. 26. 11:00
1 ··· 7 8 9 10 11
Tistory Blog (here) Naver Blog
© 2018 T-Story. All right reserved.