develop_C

리스트에 순차적으로 접근해야 할 때 두 개의 점의 위치를 기록하면서 처리하는 알고리즘 Two Pointers 알고리즘의 시간복잡도는 O(n) start, end라는 두 개의 포인터를 사용합니다. start는 부분배열의 앞 쪽을 가르키는 인덱스, end는 부분배열의 뒤 쪽을 가르키는 인덱스입니다. 맨 처음에 두 포인터는 0에서 시작하며 항상 start= 구해야하는 값start를 오른쪽으로 한 칸 이동하여 부분합 배열의 크기를 감소시킵니다.

문자찾기 indexOf indexOf() 는 특정 문자나 문자열이 앞에서부터 처음 발견되는 인덱스를 반환하며 만약 찾지 못했을 경우 "-1"을 반환합니다. indexOf(String str) indexOf(char ch) indexOf(char ch, int fromIndex) indexOf(String str, int fromIndex) 👉역순으로 할 때는 lastIndexOf()로 똑같이 하면된다. 매개변수에 str 값을 넣어주면 해당 문자의 위치를 알려준다. 두번 째 매개변수 fromIndex에 넣으면 해당 위치부터 str을 찾아준다. contains 문자열을 검색할 때 효율 적이며 만약 문자열이 있을 경우 true 없을경우 false를 출력 ex) String value = "abcdef" Sys..

큰 문제를 작은 문제로 나누어서 푸는 방식 처음 주어진 문제를 더 작은 문제들로 나눈 뒤 각 조각의 답을 계산 답들로 부터 원래 문제에 대한 답을 계산해 낸다는 점에서 분할 정복(Divide & Conquer, D&C)과 비슷 가장 큰 차이점은 동적 계획법에서는 쪼개진 작은 문제가 중복되지만, 분할 정복은 절대로 중복될수가 없다는 점이다 조건 두 가지 속성을 만족해야 동적 계획법으로 문제를 풀 수 있다. Overlapping Subproblem : 겹치는 부분(작은) 문제 Optimal Substructure : 최적 부분구조 겹치는 부분 문제 어떤 문제가 여러개의 부분문제(subproblem)으로 쪼개질 수 있을때 사용하는 용어이다. 이때 '부분 문제'란, 항상 새로운 부분 문제를 생성해내기 보다는 계..

"가장 맨 앞에 보이는 최적의 상황을 쫓는 알고리즘" "근사치 추정" 단순한 형태의 알고리즘 여러 경우 중 하나를 결정해야 할 때마다 그 순간에 최적이라고 생각되는 것을 선택해 나가는 방식 적용 가능한 곳 크루스칼 알고리즘 그래프의 모든 간선 중에 가중치가 가장 작은 것 부터 차례대로 선택 (사이클이 만들어지면 안됨) 프림 알고리즘 임의의 정점에서 가중치가 가장 작은 간선을 선택 (가중치가 작은 것들을 선택, Cycle X) 데이크스트라 알고리즘 가중치가 있는 방향그래프에서 임의의 두 노드 사이의 최단거리를 구하는 알고리즘 이외 거스름돈 나눠주기, 일 스케줄링 등 있다.