슬라이딩 윈도우 고정된 배열에서 부분 배열들을 활용하여 고정된 폭만큼 움직여 값을 구하는 알고리즘이다. 같은 너비의 연속 구간들의 정보를 활용하는 것이다. 연속된 구간들 속에 정보가 겹치는 부분이 발생하는데 이 부분을 버리지 않고 재활용하는 점이 있다. 예를 들어 1 1 1 1 1 5 1 이라고 배열이 있다고 가정을 한다면 5개의 너비 만큼 한칸씩 이동을 할때 5의 크기중 첫 번째는 제거가 되고 5의 크기 중 우측에 새로 값을 추가해주면 된다. 그러므로 중간에 값이 겹치는 범위는 재활용을 하게 된다. https://www.acmicpc.net/problem/21921 21921번: 블로그 첫째 줄에 $X$일 동안 가장 많이 들어온 방문자 수를 출력한다. 만약 최대 방문자 수가 0명이라면 SAD를 출력한다..
코테/개념 정리
투 포인터 알고리즘 배열을 탐색하기 위해, 두 개의 포인터를 사용하여 배열을 순회하는 알고리즘 문제에서 이중for문으로 구하면 O(n^2)의 시간복잡도를 투 포인터 알고리즘을 활용하면 O(n)의 시간 복잡도로 풀이가 가능하다. https://www.acmicpc.net/problem/2003 수들의 합 2 시간 제한 메모리 제한 제출 정답 맞힌 사람 정답 비율 0.5 초 128 MB 51870 24979 17060 48.389% 문제 N개의 수로 된 수열 A[1], A[2], …, A[N] 이 있다. 이 수열의 i번째 수부터 j번째 수까지의 합 A[i] + A[i+1] + … + A[j-1] + A[j]가 M이 되는 경우의 수를 구하는 프로그램을 작성하시오. 입력 첫째 줄에 N(1 ≤ N ≤ 10,000..
DP - Dynamic Programming (동적 계획법) 복잡한 문제를 여러 개의 간단한 무제로 분리하여 부분의 문제들을 해결함으로써 최종적으로 복잡한 문제의 답을 구하는 방법 원리 큰문제를 작은 문제로 작은 문제들이 반복돼 나타나고 사용되며 이 작은 문제들은 결괏값은 항상 같아야함 메모이제이션(Memoization)모든 작은 문제들은 한 번만 계산해 DP 테이블에 저장하며 추후 재상요할 때는 이 DP 테이블을 이용 톱다운 방식과 바텀 업 방식으로 구현 메모제이션 원리 피보나치 수열 구하는 공식은 f(n) = f(n-1) + f(n-2)으로 n번째 수열은 n-1번째 수열과 n-2번재 수열을 더한 값이다. 즉, 5번째 피보나치 수열은 4번째 와 3번째를 더한 값이고, 작은 문제로 나누면 4번째와 3번째..
재귀(Recursion) 재귀(Recursion) - 자기 자신을 호출하여 자신을 반복적으로 호출하면서 결과를 도출 팩토리얼 - 1부터 n까지의 모든 값을 곱하는 방식 n! 는 1 * 2 * 3 * …. * (n-1) * n 이다. 여기서 맨 끝에 n만 제외하면 (n-1)! 이다. 결론적으로 n! = n * (n-1)! 이다. 또 (n-1)!는 …반복 5! = 5 * 4!; 4! = 4 * 3!; … 1! = 1 * 0!; 0! = 1; Java 코드 - 재귀 팩토리얼 // 재귀 - 팩토리얼 public static int factorial(int n) { if (n == 0) { // 기본 케이스 return 1; } else { // 재귀 케이스 return n * factorial(n - 1); }..
시간 복잡도 시간 복잡도란 알고리즘이 주어진 문제를 해결하기 위한 연산 횟수 시간 복잡도 유형 1.빅-오메가 Ω(n) : 최선일 때(best case)의 연산 횟수를 나타내는 표기법 가장 빠른 케이스, 어떤 식의 최고 차수 2.빅-세타 𝚯(n) : 보통일 때(average case)의 연산 횟수를 나타낸 표기법, 빅-오, 빅-오메가를 만족한느 교집합 평균 실행시간 3.빅-오 O(n) : 최악일 때(worst case)의 연산 횟수를 나타낸 표기법 가장 느린 케이스 상수는 무시 혹은 1로 통일 상한선을 기준으로 하여 모든 경우의 수를 포함 빅-오 표기법을 기준으로 수행 시간을 계산하는 것이 좋은 이유 프로그램은 다양한 테스트 케이스를 수행하여 모든 케이스를 만족할만한 케이스를 염두해 둬야 하는데 그 경우가..
소수를 구하는 알고리즘 - 에라토스테네스의 체 고대 그리스의 수학자 에라토스테네스가 만들어 낸 소수를 찾는 방법 알고리즘[편집] 2부터 소수를 구하고자 하는 구간의 모든 수를 나열한다. 그림에서 회색 사각형으로 두른 수들이 여기에 해당한다. 2는 소수이므로 오른쪽에 2를 쓴다. (빨간색) 자기 자신을 제외한 2의 배수를 모두 지운다. 남아있는 수 가운데 3은 소수이므로 오른쪽에 3을 쓴다. (초록색) 자기 자신을 제외한 3의 배수를 모두 지운다. 남아있는 수 가운데 5는 소수이므로 오른쪽에 5를 쓴다. (파란색) 자기 자신을 제외한 5의 배수를 모두 지운다. 남아있는 수 가운데 7은 소수이므로 오른쪽에 7을 쓴다. (노란색) 자기 자신을 제외한 7의 배수를 모두 지운다. 위의 과정을 반복하면 구하는 구간..
DFS( Depth first Search) - 깊이 우선 탐색 그래프 완전 탐색 기법 중 하나로, 그래프의 시작 노드에서 출발하여 탐색할 한 쪽 분기를 정하여 최대 깊이까지 탐색을 마친 후 다른 쪽 분기로 이동하여 다시 탐색을 수행하는 알고리즘이다. 기능 특징 시간 복잡도(노드 수 : V, 에지 수 : E) 그래프 완전 탐색 재귀함수, Stack(LIFO) 사용 O(V+E) DFS 원리 시작할 노드를 정한 후 사용할 자료구조 초기화 Stack에서 노드를 꺼낸 후 꺼낸 노드의 인접 노드를 다시 스택에 삽입 Stack 자료구조에 값이 없을 때까지 반복 DFS 구현 방법 두 가지 재귀 1 -> 2 -> 5 -> 6 -> 3 -> 4 -> 스택 1 -> 3 -> 4 -> 6 -> 2 -> 5 -> * 재귀의 ..
BFS (Breadth First Search ) - 너비 우선 탐색 그래프를 완전 탐색하는 방법 중 하나로, 시작 노드에서 출발해 시작 노드를 기준으로 가까운 노드를 먼저 방문하면서 탐색하는 알고리즘이다.(=최단 경로) 기능 특징 시간복잡도(노드 수 : V, 에지 수 : E) 완전 탐색 Queue, FIFO 사용 O(V+E) BFS 원리 시작점을 구한고 자료구조(인접행렬or 인접리스트)를 초기화 BFS 호출 (큐에서 노드를 꺼낸 후 노드의 인접 노드를 다시 큐에 삽입, 값이 없을 때까지 반복) 방문 여부 체크 코드 package com.java.coding; import java.util.LinkedList; import java.util.Queue; public class BFSExam { publi..
