2022.11.24.THU

ronglong·2022년 11월 24일
0

코드스테이츠 Day26

  • 알고리즘(문제 해결 방법) 작성 순서
    - 문제 파악 -> 슈도 코드 작성(구체적으로) -> 코드 구현
  1. 시간 복잡도 (Time Complexity)
  • 입력값이 커질 때 연산 시간이 얼마나 드는가. 입력값과 연산 시간의 관계.
  • 표기법
    - Big-O(빅-오) : 최악. O(1), O(n), O(log n), O(n^2), O(2^n)
    계수나 상수는 n이 커질수록 무의미해지므로, 무시.
    - Big-Ω(빅-오메가) : 최선
    - Big-θ(빅-세타) : 평균
  1. 탐욕 알고리즘(Greedy)
  • 조건
    • 앞의 선택이 이후 선택에 영향 주지 않을 것
    • 부분 문제를 최적으로 해결하면 최종 문제도 최적으로 해결될 것
  1. 구현(implementation)
    1) 시뮬레이션 : 제시된 조건/로직을 코드로 구현.
    2) 완전 탐색 (Brute-Force Algorithm) : 시행 착오. 무차별 대입.
  2. 탐색 알고리즘(Binary Search Algorithm)
  1. 아침 데일리 코딩에서 내가 만든 코드
public class Solution { 
	public String insertDash(String str) {
		// 연속된 홀수 한 자리가 나오면 그 사이에 - 추가.
		// 연속된 홀수가 나오면 뒷자리 홀수 앞에 - 추가. 

		if(str.length()==0) return null;
		for(int i=0; i<str.length()-1; i++){
			if((str.charAt(i)-'0')%2==1 && (str.charAt(i+1)-'0')%2==1){
				str = str.substring(0,i+1) + "-" + str.substring(i+1);
			}
		} 
		return str;
	} 
}
public class Solution { 
	public String[] removeExtremes(String[] arr) {
    // 공백 입력시 반환부터 조건문으로 쳐내기
    if(arr.length==0) return null;

    // 각 요소의 길이를 가장 짧은 것과 긴 것의 인덱스를 받아서, 본 배열에서 삭제한다. 
    List<String> list = new ArrayList<>(Arrays.asList(arr));
    
    String max = ""; 

    for(int i=0; i<arr.length; i++){
      if(max.length()<=arr[i].length()) max = arr[i];
    }

    String min = max;

    for(int i=0; i<arr.length; i++){
      if(min.length()>=arr[i].length()) min = arr[i];
    }

    list.remove(min);
    list.remove(max);

    return list.toArray(new String[0]);
	} 
}

<느낀 점>
오늘은 알고리즘에 대해 공부했다.
아직은 그냥 이런 게 있구나, 정도다. 실제로 문제에 적용해서 푸는 건 연습이 필요할 것 같다. '이진'으로 시작하는 자료구조와 알고리즘들,, 이름 비슷해서 헷갈림.. ㅋㅋㅋㅋ 위 링크 보고 차이점을 잘 기억해둬야겠다.

알고리즘 문제 풀다가 맨 처음에 노가다로 풀고 민망해서 배열짜서 다시 만듦 ㅋㅋㅋㅋ
밑에 내가 작성했던 코드를 첨부한다.

int count = 0;

    count += k/500 + (k%500)/100 + ((k%500)%100)/50 + (((k%500)%100)%50)/10
    + ((((k%500)%100)%50)%10)/5 + ((((k%500)%100)%50)%10)%5;

    return count;

거스름 동전 개수 문제였는데, 이렇게 풀고 민망해서

int count = 0;
    int[] arr = {500, 100, 50, 10, 5, 1};

    for(int i=0; i<arr.length; i++){
      count += k/arr[i];
      k = k%arr[i];
      if(k==0) break;
    }
    return count;

이렇게 다시 풀었음. ㅋㅋㅋㅋㅋ

0개의 댓글