본문 바로가기

공부 정리/알고리즘10

[js] 배열돌리기 종종 2차원 배열 돌리기를 해야하는 문제가 나오곤 합니다. 그것을 위해 정리 했습니다. 1. x축 뒤집기 const arr = [[1,2,3],[4,5,6],[7,8,9]]; console.log(arr.reverse()); [7, 8, 9] [4, 5, 6] [1, 2, 3] 각 배열의 순서만 바꿔주면 됩니다. 2. y축 뒤집기 const arr = [[1,2,3],[4,5,6],[7,8,9]]; for(let i=0; i 3,2,1 3. 90도 회전 const arr = [[1,2,3],[4,5,6],[7,8,9]]; for(let i=0; i 2023. 1. 9.
[알고리즘] 누적합 prefix sum 누적합? 누적 합(prefix sum) 알고리즘은 계산양을 줄여서 시간적으로 많은 이득을 볼 수 있는 알고리즘 입니다. 예를 들어 1.그냥 더하기 arr[0]~arr[5]까지 입력을 받은 후, arr[0]부터 arr[5]까지 합을 구해야 될때 5번 더하기를 해야 합니다. 2.누적합 이용 누적합을 이용하면 arr[0]~arr[5]에 각각 누적합을 더해서 넣어 줍니다. 그 후에, arr[0]부터 arr[5]까지 합을 구하려면 따로 연산없이 바로 바로 불러 올 수 있습니다. arr[0]~arr[5]의 합은 arr[5] 또한 arr[2]~arr[5]의 값 또한 arr[5] - arr[1]계산 1번을 통해 구할 수 있습니다. 얼핏 보면 시간차가 별로 안날 수도 있다고 생각할 수도 있지만, ex) 배열 수가 매우 .. 2022. 4. 5.
[알고리즘] 다익스트라 알고리즘 다익스트라 알고리즘(데이크스트라) 그래프에서 어떠한 점(A)에서 어떠한 점(B)으로 가는 최단 거리를 구할 때 사용하는 알고리즘입니다. 핵심 1. 다익스트라는 BFS의 확장 같은 느낌.(현재 점에서 연결되어 있는 모든 점 검사,,, 그러나 이미 거리가 확정된 곳은 제외) 2.거리 배열을 하나 만들어서 각 점을 할당한다. 각 배열이 의미하는 바는 시작지점에서 해당 지점까지 얼마나 걸리는지 기록. 3.가중치에 음수가 있다면 알고리즘 성립안됨!! (1) S1에서 시작하여, 배열 안 S2,S3 값을 1,5로 초기화합니다. (2) 현재 위치에서 가까운 S2로 갑니다. (3) S2에서 S3로 가는데 3의 비용이 듭니다. 현재 누적된 S2의 비용(1) + S3로 가는 비용(2) VS 기존에 있는 S3의 값(S1->S.. 2022. 2. 25.
[알고리즘] 유니온-파인드 (자바) 유니온 파인드란? 말 그대로 union-find 알고리즘을 의미합니다.(주로 트리구조를 이용합니다.) 즉 집합-찾기 입니다. 같은 말로 disjoint-set이 있습니다. 사용 이유 1) 서로 다른 2개의 노드를 입력받아서 그 노드들을 합치거나, 2) find함수로 서로 다른 2개의 노드가 현재의 그래프에 속하는지 판별할 수 있습니다. 예제 코드 find 코드 public static int find(int x) { if( x == result[x]) { return x; } return result[x] = find(result[x]); } union 코드 public static void union(int x, int y) { x = find(x); y = find(y); if( x != y ) { .. 2021. 10. 19.
[알고리즘] 에라토스테네스의 체 에라토스테네스의 체란? 에라토스테네스가 만든 소수 판정방법으로, 쉽게 얘기해서 숫자들 중 소수를 체에 걸러서 찾아내는 방법입니다. 사용 이유 10까지의 소수는 그냥 찾기 쉽지만, 10000000까지의 소수는 찾기 쉽지 않다. 이럴 때 에라토스테네스의 체를 이용해서 효율적으로 소수를 찾아냅니다. 사용방법 특정한 수 n까지 소수를 구하고 싶다면, 2부터 n까지 2의 배수를 모두 제거한다...(자신인 2를 제외하고) 3부터 n까지 3의 배수를 모두 제거한다...(자신인 3을 제외하고) 4부터 n까지 4의 배수를 모두 제거한다....(자신인 4를 제외하고) .... ... n부터 n까지 n의 배수를 모두 제거한다.. (자신인 n은 제거하지 않으므로 아무것도 제거하지 않음) 모두 제거하고 남은 수가 소수입니다. .. 2021. 7. 31.
[알고리즘] 큐 queue 큐란? 큐는 자료구조 중 하나로, 알고리즘에 종종 사용됩니다. 주로 BFS에 사용되었습니다. 큐는 스택과는 다르게 스택모형에서 구멍이 뚫려있다고 생각하면 편합니다. 들어간 데이터는 그대로 제일 먼저 나옵니다. 실생활에서는 가게에서 계산대가 되겠습니다. 먼저 온 손님이 먼저 계산하듯이... 이를 FIFO(FIRST IN FIRST OUT)이라 합니다. 저는 자바로 큐를 구현해보았습니다. 큐 선언 Queue queue = new LinkedList(); Queue queue = new LinkedList(); Queue queue = new LinkedList(); 큐 값 추가 queue.add(1); queue.add(3); 큐 값 제거 queue.remove(); 큐 값 초기화 queue.clear();.. 2021. 3. 14.
반응형

티스토리툴바