목록알고리즘 (49)

기술 블로그

쿼리(연산)를 누적하여 마지막 한 번에 연산하기(feat. 누적합)

https://hsdevelopment.tistory.com/772 배열이 주어지고, 배열의 구간에 수를 더하고 빼는 쿼리가 있다. 세그먼트 트리를 이용해도 되지만, 우리는 연산 중간에 배열의 값을 알 필요가 없고, 모든 쿼리(연산) 이후에 마지막 단 한 번만 구하면 되기 때문에, 누적합을 이용할 수 있다.
알고리즘 2021. 9. 14. 08:22
KMP

문자열 매칭 알고리즘 : KMP KMP 알고리즘은 접두사와 접미사의 개념을 활용하여 ‘반복되는 연산을 얼마나 줄일 수 있는지’를 판별하여, 매칭할 문자열을 빠르게 건너뛰는 기법이다. makeTable() : 접두사와 접미사의 개념을 활용한 최대 일치 길이를 찾는 함수 연습 문제 boj 5525번 IOIOIboj 1786번 찾기 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374757677787980818283848586878889909192939495969798991001011021031041051061071..
알고리즘 2020. 6. 23. 16:05
단절점과 단절선

https://bowbowbow.tistory.com/3
알고리즘 2020. 3. 6. 15:47
Exchange arguments (sorting with dp)

https://codeforces.com/blog/entry/63533 Exchange arguments (sorting with dp) Greedy그리디탐욕
알고리즘 2020. 2. 28. 17:06
고속 거듭제곱 알고리즘(18291번 비요뜨의 징검다리 건너기, 1629번 곱셈)

https://www.acmicpc.net/problem/18291 https://www.acmicpc.net/problem/1629 n이 4일 경우, 1001110110111111 이렇게 4개를 생각할 수 있다. 여기에서 시작과 끝을 제외하면, 00100111 이고, 이것은 bit 연산을 생각할 수 있다. 즉, bit가 2일 때, 나올 수 있는 총 경우의 수는 2^2이고, 2^(n-2)이 답임을 알 수있다. (예시)000100010001011110101111비트 수 = 3, 총 개수 = 2^3 하지만 숫자가 워낙 클 경우 단순히 2^(n-2)의 작업을 할 때, Stack Over Flow나 O(n)의 시간이 걸리게 된다. 하지만, 나머지를 적용할 수 있고, O(log n)의 알고리즘이 있다. 여기에서 ..
알고리즘 2020. 2. 27. 15:03
MSA(Micro Service Architecture)

https://velog.io/@tedigom/MSA-%EC%A0%9C%EB%8C%80%EB%A1%9C-%EC%9D%B4%ED%95%B4%ED%95%98%EA%B8%B0-1-MSA%EC%9D%98-%EA%B8%B0%EB%B3%B8-%EA%B0%9C%EB%85%90-3sk28yrv0e msamicro service architecture마이크로 서비스 아키텍쳐
알고리즘/면접 및 공부 2020. 2. 7. 17:12
다익스트라, 벨만포드, SPFA

https://www.acmicpc.net/board/view/40701#post [벨만 포드]1. 어떤 노드를 방문했는지 따지지 않음.2. 모든 정점을 방문해서 거리를 갱신해야되기 때문임.3. dist[here] != INF 조건은 필요함.(시작점에서 here까지의 길이 없고, 시작점→here→next까지의 거리가 갱신되버리기 때문임) [SPFA]1. queue와 inQ 배열에는 시작점에서 here까지 길이 존재해야 queue에 here이 push 될 수 있기 때문에dist[here] != INF 조건이 필요하지 않음.2. 기본 원리는 벨만 포드이기 때문에 방문 했는지 안 했는지는 중요 하지 않음.3. 벨만 포드와 마찬가지로 작은 값이 들어올 수 있기 때문에 계속 갱신해야 됨. [다익스트라]1. 이미 ..
알고리즘/면접 및 공부 2020. 1. 28. 15:01
직사각형에서 대각선이 통과하는 정사각형의 개수는?

https://blog.naver.com/orbis1020/220664563768
알고리즘 2020. 1. 10. 14:32
이전 Prev 1 2 3 4 ··· 7 Next 다음