알고리즘

Big-O Notation 함수의 상한을 의미한다. f(n)과 g(n)에 대하여 n>=n0인 모든 n에 대하여 |f(n)|<=c|g(n)|을 만족하는 상수 c와 n0가 존재하면 f(n)=O(g(n))이다. Big–Ω Notation함수의 하한을 의미한다.f(n)과

internal sort정렬할 자료의 양이 적어서 자료 전체가 주기억장치에 저장될 수 있는 경우에 내부정렬을 사용한다 external sort자료의 양이 많을 때는 속도가 느리고 접근 방식이 제한적인 보조기억장치에 전체 자료를 두고 자료의 일부분을 한번에 조금씩 주기억

이진 검색 트리인데 노드의 필드 중에 색깔 (red 또는 black) 을 나타내는 필드가 있다. 루트 ~ 리프 경로에 나타나는 노드의 색을 제한해서 트리가 근사적으로 균형을 이루도록 한다.모든 노드는 적색이거나 흑색루트는 흑색모든 리프는 흑색 노드가 적색이면 그 노드의

패턴 : 찾고자 하는 문자열 텍스트 : 패턴을 찾을 문자열 교재 424p KMP 알고리즘 텍스트의 위치 i에서 패턴의 j개 문자가 일치되었다고 하자 텍스트의 위치를 i->i+1로 증가 패턴의 j+1번째 문자와 비교 같으면 i,j 증가 같지 않다면 패턴에서 j개의

동적프로그래밍 분할정복 기법과 같이 부분 문제의 해를 결합해 문제를 해결함 부분 문제가 서로 중복될 때, 부분 문제가 다시 자신의 부분 문제를 공유할 때 적용 동적 프로그래밍의 적용조건 최적 부분구조 큰 문제의 최적 솔루션에 작은 문제의 최적 솔루션 포함 재귀호출시

참고링크자연수 n에 대해 그 이하의 소수를 찾는 가장 간단하고 빠른 방법 백준 1929번을 풀던 도중 시간 초과가 발생해서 찾아본 방법이다.예를 들어 1~100까지의 소수를 찾으면 1~100의 수에서 1 제거 2를 제외한 2의 배수 제거 3을 제외한 3의 배수 제거 5

골드바흐의 추측은 2보다 큰 모든 짝수는 두 소수의 합으로 나타낼 수 있다는 거임 백준 9020번 : 4<=n<=10000인 n에 대해 골드바흐 파티션 출력하기파티션이 여러개인 경우는 두 소수의 차가 적은 것을 출력하기풀이방법 : 에레토스테네스의 채를 이용해

처음에는 배열로 for문을 돌리면서 풀려고 했는데 효율성 테스트에서 떨어졌다.찾아보니 HashMap은 값에 접근할 때 빠르게 접근 가능하다. (다른 자료구조는 선형시간이 걸림) 그래서 HashMap을 사용하는 방식으로 수정하자 통과했다. 참고할 사항 , 실수했던 것탬플

참고링크Last In First Out 구조 : 나중에 넣은 데이터가 먼저 나옴Fisrt In First Out 구조 : 먼저 넣은 데이터가 먼저 나옴 앞이 front, 뒤가 rearenqueue 연산 : rear 가 이동 후 해당 자리 데이터 추가dequeue 연산

2중 for문으로 O(n^2)으로 해결할 문제를 이 두가지 알고리즘을 잘 사용하면 O(n)으로 해결할 수 있음 0302번 포인터 변수 2개를 사용해서 비교하는 방식합병정렬에서 정렬하는 과정에서 사용하는 방식 0303번window 크기를 정해놓고 한칸씩 이동하면서 그 부

i뒤에 j가 배열 끝까지 순회하면서 최솟값 찾아서 i랑 바꿈 시간복잡도 : O(n^2)

한번의 i 루프마다 남아있는 수 중 제일 큰 수가 맨 뒤에 정렬됨최악, 최선, 평균 모두 O(n^2) : 비효율적

알고리즘 도감 참고O(n^2) 의 시간복잡도

순차검색 : O(n) 이분검색(최악시간복잡도) : O(logN)

lt랑 rt 사이에 답이 있는 경우에 사용함 최적의 답을 찾아 나감 O(logn)의 시간복잡도

자기 자신을 호출하는 함수스택 프레임 복귀 라인을 기억해놓음

DFS BFS

두 양의 정수 a,b에 대하여 (a>b)a = bq+r ( 0<=r<b)라 하면 a,b의 최대공약수는 b,r의 최대공약수와 같다 이 때, r =0이라면 a,b의 최대공약수는 b가 된다출처: 나무위키즉 나머지가 0이 나올 때 까지 나머지로 계속 나눠주면 되는

문제 링크백트래킹 설명 링크풀이 참고 링크이미지 출처는 모두 풀이 참고 링크입니다백트래킹으로 풀 수 있는 대표적인 문제이다백트래킹은 해를 찾아가는 도중, 지금의 경로가 해가 될 것 같지 않으면 그 경로를 더이상 가지 않고 되돌아가는 것이다.가능한 모든 경우의 수 중에서

문제 풀이 참고 출처 동적 계획법 나무위키 동적 계획법 동적 계획법은 답을 구하기 위해 그것과 다른 범위까지의 값을 이용하여 효율적으로 값을 구하는 알고리즘 설계 방법이다. 쉽게 말해 답을 재활용하는 것이다. 동적 계획법은 주어진 문제를 나눌 때 부분 문제를 최대한

문제 링크풀이 링크합 배열을 활용해야 한다.합 배열은 입력받은 배열이 arr라면 합 배열 S\[i]=arr\[0]+arr\[1]+...arr\[i] 인 배열이다.문제의 조건을 만족하려면 아래 식이 성립해야 한다.풀이 출처의 소스 코드는 아래와 같다주의할 점은 long

회의실 문제핵심은 회의가 끝나는 시간이 빠른 것부터 정렬하는 것이다.그리고 앞에서 부터 선택하며 시작 시간이 선택된 회의의 시간보다 늦은 것 중 또 제일 빨리 끝나는 회의를 선택한다.그리고 정렬할 때 끝나는 시간이 같은 경우는 더 빨리 시작하는 것으로 정렬되도록 해야