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

ACM-ICPC 상 탈 사람

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

ACM-ICPC 상 탈 사람

검색하기 폼
  • 분류 전체보기 (360)
    • 서버 관련 (9)
      • JS (5)
      • AmazonWebService (1)
      • Backend 지식 (3)
    • 일상 (13)
      • Daliy (1)
      • 잡담 (10)
      • 개인 (2)
    • 알고리즘 관련 (337)
      • BOJ (303)
      • UVaOJ (8)
      • SPOJ (1)
      • 알고리즘&이론 (25)
  • 방명록

partial sum (5)
BOJ)2104 부분배열 고르기

문제: icpc.me/2104 주어지는 배열에서 i~j까지의 부분 배열을 선택했을 때 (a[i]+a[i+1]+...+a[j])*(min(a[i],a[i+1]),....,a[j]) 가 최대가 되도록 i j를 선택하는 문제이다. 나이브한 풀이법으로는 i,j를 선택하는데만 O(N^2)으로 시간초과다 .. 따라서 좀 더 그리디하게 생각해보면 만약에 어떤 구간에 대해 정할 때 한 점 X를 기준으로 그 점이 최솟값이 되게 구간을 선택한다면 X를 기준으로 좌우로 최대한 X보다 큰값을 가지는 범위롤 포함하도록 배열을 선택할 수 있다. 이러한 아이디어에서 출발하여 모든 점에 대해서 이 범위를 볼건데 정렬을 해주어 작은 값부터 보면서 set에 업데이트해주어 이동가능한 lower_bound와 upper_bound를 찾아준다..

알고리즘 관련/BOJ 2017. 8. 20. 17:26
BOJ)11974 Subsequences Summing to Sevens

문제: icpc.me/11974 N마리의 소가 각각의 고유 ID를 가지고 있을 때 연속된 소의 고유 ID의 합이 7의 배수인 구간의 길이를 출력하는 문제이다. 소를 입력 받은 후에 소의 partial sum을 저장한 뒤 partial sum을 7로 나눈 나머지를 저장한다면 해당 값이 같은 가장 긴 구간이 답이될 것이다. 123456789101112131415161718192021222324252627282930313233#include #include using namespace std;typedef long long ll;ll n, a[50000], p[50000], r;int main() { scanf("%lld", &n); for (int i = 0; i

알고리즘 관련/BOJ 2017. 1. 18. 19:39
BOJ)4948 베르트랑 공준

문제: icpc.me/4948 n~2n 사이의 소수의 개수를 출력하면 되는 문제이다. 에라토스테네스의 체로 소수들을 구해 준 뒤 파셜섬의 차를 구해주면 된다. 12345678910111213141516171819202122232425#include #include using namespace std;bool p[270000];int s[270000];int n;int main() { p[0] = p[1] = true; for (int i = 2; i

알고리즘 관련/BOJ 2017. 1. 6. 13:53
BOJ)12841 정보대 등산

문제: icpc.me/12841 왼쪽 1번 지점에서 오른쪽 n번 지점까지 가는 최단 거리를 구하는데 이 때 횡단보도는 한번 밖에 못 건넌다는 전제가 있다. N개의 횡단보도를 건너는 케이스를 전부 확인을 해줘야 하는데 N이 10만이나 되기 때문에 모든 케이스를 직접 더해줄 경우 TLE를 받을 수 있다. 하지만 Partial sum을 이용한다면 왼쪽 오른쪽길의 횡단보도 기준으로 위 아래는 쉽게 구할 수 있다. 주의 할 점은 10만개의 횡단보도에 거리가 10만 까지 들어올 수 있으므로 long long을 사용해줘야 한다. 12345678910111213141516171819202122232425262728293031#include #include #define INF 999999999987654321using..

알고리즘 관련/BOJ 2017. 1. 5. 20:32
BOJ)11895 속이기

문제: icpc.me/11895 XOR의 원리에 의해서 답이되는 X그룹과 Y그룹이 존재한다면 X그룹과 Y그룹을 각각 XOR한 결과는 같으므로 결국 모든 원소들을 XOR을 한 결과는 0이 되어야 한다. 따라서 전체를 XOR했을 때 0이 아닌 다른 수가 나온다면 X그룹과 Y그룹이 존재할 수 없으므로 0을 출력하면 되고 X그룹과 Y그룹이 존재하는 경우에는 전체를 XOR한 경우가 0이므로 A^0 = A에 의하여 그룹을 어떻게 나누더라도 XOR한 결과가 같을 것이다. 문제에서는 최댓값을 출력하라고 하였으므로 파셜섬 한 값에서 가장 작은 값을 빼준 값을 출력해주면 된다. 1234567891011121314151617181920#include #include using namespace std;int n, x, Ps..

알고리즘 관련/BOJ 2017. 1. 3. 00:45
이전 1 다음
이전 다음
공지사항
최근에 올라온 글
  • Node.js로 DynamoDB 시작⋯
  • Node.js로 DynamoDB 시작⋯
  • Express와 Apollo server⋯
  • GraphQL 스키마 작성하기⋯
최근에 달린 댓글
  • 도움이 많이 되었습니다 굳굳⋯
  • 간선의 방향을 다 거꾸로 받⋯
  • 넵 요즘은 거의 node js 만⋯
  • 문제 설명 감샇바니다. :) 'B⋯
Total
315,369
Today
36
Yesterday
199
링크
  • 민호형
  • 제주시민
  • 꼴뚜기
  • 김흿
  • 태양쓰
  • 정률이
  • 정이 형
  • stack님
  • 세지니
  • 매브레이커
  • 박트리님
  • 플즈런님
  • 맹킹
  • 송이 블로그
TAG
  • 세그먼트 트리
  • 이분 탐색
  • 다이나믹 프로그래밍
  • 힙
  • 그리디 알고리즘
  • LCP array
  • 플로이드 워셜
  • MST
  • lazy propagation
  • KMP
  • SCC
  • Suffix Array
  • 분할 정복
  • 라인 스위핑
  • disjoint-set
  • 트리
  • 이분 매칭
  • 디닉
  • 네트워크 플로우
  • 다익스트라
  • MCMF
  • partial sum
  • brute force
  • 위상 정렬
  • 에라토스테네스의 체
  • lca
  • BFS
  • 좌표 압축
  • dfs
  • 수학
more
«   2021/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      
글 보관함
  • 2020/05 (2)
  • 2020/04 (6)
  • 2020/03 (1)
  • 2018/07 (4)

Blog is powered by Tistory / Designed by Tistory

티스토리툴바