레프네 약방

레프네 약방

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

레프네 약방

컨텐츠 검색

태그

화학 경시수학 더블카운팅 함수방정식 물리 Russian Code Cup 열역학 수학 수학문풀 대수학 정수론 IMO 현대대수학 물리화학 Codeforces AOPS ps-hell 조합론 그래프이론 Problem Solving

최근글

댓글

공지사항

아카이브

알고리즘 문풀(59)

  • 7/27~7/28 연습

    2017.07.29
  • 7/26 연습

    2017.07.27
  • 7/25 연습

    2017.07.26
  • 7/24 연습

    2017.07.25
  • APIO 2015 Jakarta Skyscrapers 풀이

    2017.07.13
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
7/24 연습

*이 문제 set은 백준 온라인 저지에서 랜덤을 돌려서 푼 문제들입니다. 풀이를 좀 포멀하게 적고 싶어서 쉬운 문제라도 모두 풀이를 상세하게 기록할 예정이니, 그게 마음에 들지 않으신 갓갓분들은 살포시 뒤로가기를 눌러 주세요. 1. 수열 축소 문제 : http://icpc.me/2237 풀이 : 얘는 고1때 정올을 딱 시작할 때쯤 풀지 못하고 넘겨버린 문제. 사실 CON이란 연산이 전혀 대단하지 않다는 것만 알면 된다. CON연산을 수행한 결과는 수열의 인접한 원소 사이에 + 또는 -의 부호를 적절히 삽입하여 계산한 식이다. (단, \(a_2\)앞에는 반드시 -가 붙는다) 그래서 \(n \times (2\sum{a_{i}}+1)\) dp table을 잡고,\(dp(i,j) : a_{1}~a_{i}\)까지..

2017. 7. 25. 16:39
APIO 2015 Jakarta Skyscrapers 풀이

문제 보기http://acmicpc.net/problem/10847http://oj.uz/problem/view/APIO15_skyscraper 1. Problem Statement \(N\) 개의 건물 위에 \(M\)마리의 도게가 있는데, 각 도게는 한 번의 움직임으로 정확히 \(p_{0},p_{1},...p_{M-1}\)만큼 이동할 수 있다.이 때 건물 \(s\)에서 시작해서 \(e\)로 릴레이하면서 갈 때, 점프의 최소 횟수를 알고 싶다. 2. Subtask2 - 36점 (\(N,M \le 2,000\)) Subtask1은 백트래킹이다. 짠 적도 없고, 설명하기 까다로운 만큼 넘어가자. 기본적으로 이 문제의 풀이는 다익스트라 알고리즘이다.겨울학교에서 이 문제랑 비슷하게 생긴 문제를 못 푼 기억이 있..

2017. 7. 13. 08:56
1 ··· 7 8 9 10
Tistory Blog (here) Naver Blog
© 2018 T-Story. All right reserved.