SEB_BE 26일차 - 알고리즘

Daily coding

//스플릿으로 문자 쪼개기
		//첫글자 대문자로 변환하기 toUpperCase
		if(str.length() == 0) return "";
		
		String[] word = str.split(" |  ");
    	String result = "";
		for(int i = 0; i < word.length; i++){ 
			if(word[i].isEmpty()) { //word[i] 가 공백이면 
        word[i] = word[i]; // 공백 그대로
			}else // 공백이 아니면
     word[i] = String.valueOf(word[i].charAt(0)).toUpperCase() + word[i].substring(1);
    }
		// 결과에 join으로 담기 
		//join("추가할 문자", "대상 list")
		//join("추가할 문자", "대상 Array")

		result = String.join(" ", word);
		return result;
	}

💡 오늘의 학습목표

• 시간복잡도
• 탐욕 알고리즘
• 구현-시뮬레이션
• 완전 탐색 알고리즘
• 이진 탐색 알고리즘

📔 시간복잡도(Time Complexity)

• 입력값의 변화에 따라서 연산을 실행할 때, 연산 횟수에 비해 시간이 얼마만큼 걸리는지

📜 Big-O 표기법

• 최악의 경우를 고려

  • O(1) (constant complexity)
    입력값의 크기와 관계없이, 즉시 출력값을 얻음
    
    
    
  • O(n) (linear complexity)
    입력값이 증가함에 따라 시간도 같은 비율로 증가
    같은 비율로 증가한다면 2,5배가 증가하더라도 O(n)으로 표기
    
    
    
  • O(log n) (logarithmic complexity)
    O(1)다음으로 빠른 시간 복잡도
    ex) BST의 값 탐색 (매번 경우의 수가 절반으로 줄어듬)
    
    
    
  • O(n^2) (quadratic complexity)
    입력값이 증가함에 따라서 시간이 n의 제곱수의 비율로 증가
    n^3,n^5 도 모두 O(n^2)로 표기 (n이 커질수록 지수가 주는 영향력이 퇴색되기 때문)
    
  • O(2^n)(exponential complexity)
    가장 느린 시간 복잡도 / 다른 방식을 고민해야함
    ex)재귀로 구현하는 피보나치 수열
    
    

• 예상 시간 복잡도
  

---

📙 탐욕 알고리즘(Greedy)

• 선택 순간마다 당장 최적의 상황을 쫓아 해답에 도달하는 방법

1. 선택절차: 현재 상태에서의 최적의 해답 선택
2. 적절성 검사: 선택된 해가 문제의 조건을 만족하는지 검사
3. 해답 검사: 원래 문제가 해결되었는지 검사, 해결되지 않았으면 선택 절차로 돌아가 반복

ex) 거스름돈 (동전 개수 최소한)
ex) 배낭 짐 싸기 (무게 대비 가장 비싼 물건)

• 특정한 상황이 아니면 최적의 해를 보장하지 못함.

  • 탐욕 알고리즘을 적용할 수 있는 조건

  1. 탐욕적 선택 속성(Greedy Choice Property): 앞의 선택이 이후의 선택에 영향을 주지 않는다.
     2.최적 부분 구조(Optimal Substructure): 문제에 대한 최종 해결방법은 부분 문제에 대한 최적 문제 해결방법으로 구성된다.

---

📖 구현(implementation) - 시뮬레이션(simulation)

• 구현
  완전탐색 / 시뮬레이션
• 시뮬레이션
  모든 과정과 조건이 제시되고, 그 과정을 거친 결과가 무엇인지 확인하는 유형

📖 완전 탐색 알고리즘(Brute-Force Algorithm)

• 무차별 대입 방법 (모든 가능성 시도)
• O(n)

  • 순차 검색 알고리즘
    인덱스0부터 마지막 인덱스까지 차례대로 검색
  • 문열 배칭 알고리즘
    문자열 패턴을 포함하는지 검색
  • 선택 정렬 알고리즘
    현재 요소보다 작거나 큰 요소를 교환하는 정렬 알고리즘
  • Bubble Sort / BFS / DFS / DP

📖 이진 탐색 알고리즘(Binary Search Algorithm)

• 정렬된 데이터 상태에서 절반씩 분할 정복기법으로 특정한 값을 찾아내는 알고리즘

  • 동작 단계

  1. 정렬된 배열의 가장 중간 인덱스 지정
  2. 찾으려고 하는 값이 중간 인덱스의 값이면 탐색 종료, 아니면 3단계
  3. 찾으려고 하는 값이 중간 인덱스보다 큰 값인지, 작은 값인지 확인
  4. 값이 있는 부분과 없는 부분으로 분리
  5. 값이 있는 부분에서 다시 1단계부터 반복

• O(logn) 데이터 양이 많을 수록 높은 효율
• 배열에만 구현 가능 / 정렬되어 있어야만 구현 가능