https://lunuy.tistory.com/4

처음에 전에 접근했던 2차원 배열로 2293 문제를 풀어보려니, 메모리 초과가 났다. 이는 제한이 4MB 로 되어 있는데 dp10001 을 할당 받으니까, 10000 100 4 를 초과하기 때문.. 따라서 1차원 배열로 풀어야 했다. 15989 의 문제접근 방식을

다이내믹으로 풀 수 있다. Ds = 길이가 s일때 올바른 괄호 문자열의 개수

다이나믹으로 접근. dpik = scv 가 i 체력이 있고, scv 두번째가 j 체력이 있고, scv 세번째가 k 체력이 있을 때 공격해야 하는 최소 값. 이는 1,3,9 dpi-1k-9 + 1;1,9,3 dpi-1k-9 + 1;3,1,9 dpi-3k-9 + 1;3,9

1,2,3 더하기 문제와 다르게, 오름차순 정렬 된 것만 따진다. 따라서 다이내믹 배열을 1차원이 아닌 2차원으로 선언한다. di 은 i 의 합을 끝자리 1로 채웠다는 뜻이다. 따라서 i-1 원소에다가 +1 만 더해주면 된다. 따라서 식이 di = di-1 가 된다.

해결 방법

DP 문제로 해결한다.n이 15000000 까지 가므로, 기존에 이용한 o(n^2) 시간복잡도 해결 방법으로는 풀리지 않았다. 상담을 할 때와 상담을 안할때를 구분하여 구한다. ti = i 날 까지 왔을 때 최대 이익이므로, 상담을 하게된다면 t\[i+ai] 날로

가장 왼쪽끝에 위치하고 가장 오른 쪽으로 가려고 할 때, 최소 점프 횟수 -> DP 다이내믹 프로그래밍을 이용한다. di = 위치 i 까지 이동했을때 걸리는 최소 점프 횟수따라서 1~ ai을 더한 만큼 i 가 이동할 수 있고 이를 j 로 놓았다.d i + j =

나는 DP 가 너무 약하다.. 그래서 일단 저번에 풀던걸 복습하는 겸 풀어보았다. 문제

버블 소트가 몇 번째 횟수 만에 완성되는지 찾는 것인데, 문제에 있는 코드로는 버블 소트의 시간 복잡도가 O(N^2) 이므로 시간 초과가 난다. sort 를 O(nlogn) 만에 하고 인덱스 차이를 통해 비교한다. 즉, 뒤에 있던 숫자가 앞에 어느정도 까지 앞당겨 졌

https://rasino.tistory.com/307

같은 것이 있는 경우에 정렬하기 전의 순서가 유지되는 정렬 알고리즘. 시간복잡도가 nlogn 인 알고리즘에는 병합정렬이 있다. stable sorting 이 아닌 정렬 알고리즘은, 원래 순서를 의미하는 변수를 하나 더 저장해서 Stable sort 의 효과를 만들 수

https://www.acmicpc.net/board/view/72995

Linux program 의 profiling 을 위한 application.다음과 같이 디버깅이 되도록 option 을 적용한다.

변수 line : 반환 하게 될 라인.backup : 라인 탐색의 시작을 의미하는 곳. line 의 버퍼라고 생각하면 됨.buf : buf사이즈 만큼 읽어서 반환.알고리즘backup 이 이미 존재한다면, backup을 split_line 함수로 나눠서 개행기준으로 앞쪽

벨만포드 알고리즘이다long long 으로 해주어야 한다. aa\[edgesi.from] != INF 라는 조건을 추가해 줘야한다. 이어 지지 않았는데 만약 cost 가 음수면 INF+ cost 가 값이 더 작으므로 값이 업데이트된다. 음수 사이클을 체크 해줘야 한다.

다익스트라를 다시 구현해 보고 싶어서 풀어봤는데 시간초과로 되게 해맸다...;;입출력에 의해 시간 초과가 날 수 있다. 이 코드를 추가 시켜 줘야 한다. https://www.acmicpc.net/problem/15552우선순위 큐에 { 노드번호, 가중치 }

a -> b 의 최단 경로는 정점의 개수를 n이라고 했을 때, 최대 n-1 개의 간선으로 이루어져 있다. from -> to (cost)

우선순위 큐를 이용하여 선택되지 않은 정점을 연결하는 가장 작은 간선을 뽑는다.우선순위 큐의 작동 방식의 시간 복잡도가 O(log E) 이므로, 모든 간선을 push , pop 한다는 가정하에, 전체 시간 복잡도는 O(ElogE) 가 나온다.

priorty_queue<자료형, Container ,비교 함수> 변수명.https://travelbeeee.tistory.com/126