전체 글 썸네일형 리스트형 2900 프로그램 시간복잡도를 신경써서 풀어야 하는 문제 마지막에 l부터 r까지 구하는 부분은 부분합으로 시간 복잡도를 줄일 수 있는데 jump 만큼 건너뛰는 부분을 어떻게 줄여야 할지 몰랐다. 고민하다가 다른 사람 풀이를 보니 음?? 그냥 somthing 함수를 호출했다?? 1씩 * 5번 뛰는 걸 한번에 더하긴 했지만 그래도 10^6 * 10^6이라 시간복잡도가 터지지 않을까 싶었다. 계산해보니 NlogN이 돼서 안 터진다.. 신기했다 #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include.. 더보기 6574 새로운 과일 실패~ 하나씩 비교해서 가장 짧은 문자열을 구하려고 했다 그런데 1a2b3c4 와 5a6b3c2이런 경우를 통과 못 했다 a b c 를 사이에 두고 1 5 a 2 6 b 3 c 4 2 이런 경우 막힌다.... 모르겠다 포기 #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #define xx first #define yy second #define all(x) (x).begin(), (x).end() #define MAXV 987654321 using .. 더보기 12909 그래프 만들기 골드 상위 풀기 대작전... 이제는 플레 가고 싶어서 토요라운드에 어려운 문제 위주로 풀려고 한다. 그런데? 너무너무 어렵다 처음에는 반복문 쭉 순회만 하면 풀 수 있을 줄 알았다. 가장 최대가 될 수 있게 노드를 붙이다가 0 0 0 10 예시에서 틀렸다는 걸 알았다. 결국 모든 상태를 확인해야 하고 그 상태를 dp로 저장해야 겠다 싶었다. 눈물의 옛날코드 #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #define xx first #define y.. 더보기 24524 아름다운 문자열 뭔가 한번 읽으면서 확인하면 될 것 같았는데 다른 문제 먼저 풀고 라운드 마친 뒤에 풀이 들었다. t가 a, b, c라고 하면 각각의 개수를 세주면 되는데 a는 앞에 아무런 조건이 없으므로 그냥 개수를 센다. b는 앞에 a가 무조건 있어야 하므로 a > b일 경우에만 b의 개수를 더했다. c는 앞에 b가 무조건 있어야 하므로 b > c일 경우에만 c의 개수를 더했다. #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #define xx first #de.. 더보기 23083 꿀벌 승연이 신난다 노타빌리티에 육각 노트 써봤다 예전에 정사각형 개수 구하는 문제랑 비슷했다. 재귀로 n, m부터 한 칸씩 돌아가면서 구했다. 1, 1부터 n, m까지 경로를 구해야 하므로, 1, 1 위치만 1로 지정해서 더하게끔 했다. 참고로 y가 짝수냐 홀수냐 따라서 움직일 수 있는 좌표가 달라진다. #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #define xx first #define yy second #define all(x) (x).begin(),.. 더보기 1242 소풍 아 정말 너무너무 어렵다. 처음에 나이브하게 풀었더니 시간초과가 났다. (예상했다) 시간을 줄이기 위해 삭제 할 때마다 상대적인 좌표를 사용해서 풀려고 했다. 그런데 틀렸다..... 뭔가 생각이 꼬여서 틀린 것 같다. #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #define xx first #define yy second #define all(x) (x).begin(), (x).end() #define MAXV 1000000007 using na.. 더보기 세그먼트 트리 마주하고 말았다. 세그먼트 트리 세그먼트 트리 구간을 반복해서 2등분 한 뒤 각각의 잘린 구간이 자신의 구간인 대푯값을 저장하고 관리하게 만드는 자료구조 query: O(logN) update: O(logN) query는 정확히는 O(2logN) 레벨당 2개의 노드만 건드리게 된다. 구현 full binary tree 형태를 가지기 때문에 힙처럼 구간의 모든 값을 배열에 저장할 수 있다. 어떤 노드의 번호가 idx면 왼쪽 자식은 2 * idx, 오른쪽 자식은 2 * idx + 1 배열의 크기는 4 * n 이상으로 설정해야 한다 int query(int l, int r, int node, int nodeL, int nodeR) { if (l nodeR) return v[node]; if (nodeL == .. 더보기 플로이드 와샬 알고리즘 https://m.blog.naver.com/PostView.naver?blogId=kks227&logNo=220797649276&referrerCode=0&searchKeyword=%ED%94%8C%EB%A1%9C%EC%9D%B4%EB%93%9C 플로이드 와샬 알고리즘(Floyd-Warshall Algorithm) 마지막으로 알려드릴 최단경로 알고리즘입니다. 참 많기도 하죠. 이번엔 플로이드 와샬 알고리즘(Floyd-W... blog.naver.com 아직 전부 이해는 못했지만.. - 모든 정점 쌍 사이의 최단 경로를 한번에 구할 수 있다 - 시간복잡도 O(V^3) - i, j, k - i번 정점에서 j번 정점까지, 1~k번 정점만 사용할 떄의 최단 거리를 구하라 - dist에는 1 ~ k-1번 정점만.. 더보기 이전 1 2 3 4 5 6 7 ··· 79 다음
