시간복잡도 / 공간복잡도,, 복잡하다,,

하루에 4개씩 기초 지식!

1. 제어의 역전(IoC, Inversion of Control)!

 

• 제어의 역전(IoC)란 모든 객체에 대한(생성, 라이프 사이클 등) 제어권을 개발자가 아닌 IoC 컨테이너에게 넘긴 것을 의미!
  
  
• 스프링에서는 IoC 컨테이너에 객체들을 생성하면 객체끼리 의존성을 주입(DI, Dependency Injection)하는 역할을 하고 컨테이너에 등록한 객체들을 'Bean'이라고 한다!
  
  

---

2. 스프링 Bean을 등록하는 방법은 뭘까?

 

• 기본적으로 2가지가 있다!
  
  • @Component 어노테이션을 사용하는 것!
    
    @Controller, @Service, @Repository는 모두 @Component를 포함하고 있다!
    
    
  • 설정 클래스를 따로 만들어 @Configuration 어노테이션을 붙이고, 해당 클래스 안에서 빈으로 등록할 메서드를 만들어
    
    @Bean 어노테이션을 붙여주면 자동으로 해당 타입의 빈 객체가 생성된다!

---

3. 의존성 주입(DI, Dependency Injections)!

• 의존성 주입은 필요한 객체를 직접 생성하는 것이 아닌 외부로부터 객체를 받아서 사용하는 것!
  
  이를 통해 객체간의 결합도를 줄이고 코드의 재사용성을 높일 수 있다!
  
  의존성 주입은 생성자 주입, 필드 주입, 세터 주입의 3가지 방법이 있다!
  
  이 중 Spring에서 가장 권장하는 의존성 주입 방법은 생성자를 통한 주입 방법!
  
  이유는 순환 참조를 방지하고, 불변성을 가지며, 테스트에 용이하기 때문이다!
  
  

---

4. Spring Bean의 리사이클은 어떻게 관리될까?

• Spring Bean의 리사이클이 뭐지?
  
  스프링 IoC 컨테이너 생성 -> Spring Bean 생성 -> 의존 관계 주입 -> 초기화 콜백 메서드 호출 -> 사용 -> 소멸 전 콜백 메서드 호출 -> 스프링 종료
  
  
• 스프링은 크게 3가지 Bean 생명주기 콜백을 관리
  
  

1. 인터페이스(InitializingBean, DisposableBean)
2. 설정 정보에 초기화 메서드, 종료 메서드 지정
   
   
3. @PostConstruct, @PreDestory 언테이션 지원

---

Code Kata

1. 코드 처리하기 / Programers

문제 설명

문자열 code가 주어집니다.code를 앞에서부터 읽으면서 만약 문자가 "1"이면 mode를 바꿉니다. mode에 따라 code를 읽어가면서 문자열 ret을 만들어냅니다.mode는 0과 1이 있으며, idx를 0 부터 code의 길이 - 1 까지 1씩 키워나가면서 code[idx]의 값에 따라 다음과 같이 행동합니다.

mode가 0일 때

code[idx]가 "1"이 아니면 idx가 짝수일 때만 ret의 맨 뒤에 code[idx]를 추가합니다.

code[idx]가 "1"이면 mode를 0에서 1로 바꿉니다.

mode가 1일 때code[idx]가 "1"이 아니면 idx가 홀수일 때만 ret의 맨 뒤에 code[idx]를 추가합니다

code[idx]가 "1"이면 mode를 1에서 0으로 바꿉니다.

문자열 code를 통해 만들어진 문자열 ret를 return 하는 solution 함수를 완성해 주세요.

단, 시작할 때 mode는 0이며, return 하려는 ret가 만약 빈 문자열이라면 대신 "EMPTY"를 return 합니다.

제한사항

1 ≤ code의 길이 ≤ 100,000

code는 알파벳 소문자 또는 "1"로 이루어진 문자열입니다.

class Solution {
    public String solution(String code) {
        String answer = "";
        int mode = 0;
        for(int i = 0; i<code.length(); i++){
            if(code.charAt(i) == '1' && mode == 0){
                mode = 1;
            } else if(code.charAt(i) =='1'&& mode ==1){
                mode = 0;
            }
            
            if(mode == 0){
                if(code.charAt(i) != '1' && i%2 == 0){
                    answer += code.charAt(i);
                }
            } else if( mode == 1){
                if(code.charAt(i) != '1' && i % 2 != 0){
                    answer += code.charAt(i);
                }
            }
        }
        if(answer.isEmpty()){
            return "EMPTY";
        }
        return answer;
    }
}

 

코드 로직 :

 

 

• 문자열을 한 글자씩 순회하면서, 현재 문자가 '1'이면 mode를 전환합니다.
  
  
  • mode가 0일 때 '1'을 만나면 mode를 1로 변경합니다.
    
    
  • mode가 1일 때 '1'을 만나면 mode를 0으로 변경합니다.
    
    
• 현재 mode에 따라 조건을 달리해 문자를 answer에 추가합니다:
  
  
  • mode가 0일 때: 짝수 인덱스에서 '1'이 아닌 문자를 answer에 추가합니다.
    
    
  • mode가 1일 때: 홀수 인덱스에서 '1'이 아닌 문자를 answer에 추가합니다.
    
    
• 최종적으로, answer가 비어있으면 "EMPTY"를 반환하고, 그렇지 않으면 answer를 반환합니다.

 

---

시간 복잡도,,, 공간 복잡도,, 복잡허다,, 과연 이게 뭘까??

• 시간 복잡도란? 
  
  • 시간복잡도는 코드가 실행되는 데 걸리는 시간의 증가율을 나타내는 것이다!
    
    입력 데이터의 크기 n에 따라 얼마나 많은 시간이 걸리는지 분석한다!
    
    
  • 시간 복잡도는 주로 빅오 표기법으로 표현!
    
    
    • O(1): 상수 시간. 입력 크기에 상관없이 항상 동일한 시간이 걸린다.
      
      
    • O(n): 선형 시간. 입력 크기에 비례해서 시간이 증가한다!
      
      
    • O(log⁡ n): 로그 시간. 입력 크기가 커질수록 조금씩만 시간이 증가한다!
      
      
    • O(n2): 제곱 시간. 입력 크기에 제곱 비례해서 시간이 증가한다!
      
      
• 그럼 공간 복잡도는..?
  
  
  • 공간 복잡도는 코드가 실행되면서 사용하는 메모리 양의 증가율을 나타내는 것!
    
    
  • 입력 데이터의 크기 n에 따라 얼마나 많은 메모리를 사용하는지 분석한다!.
    
    
  • 공간 복잡도도 시간 복잡도처럼 빅오 표기법으로 표현합니다.
    
    
  • O(1): 상수 공간. 입력 크기에 상관없이 항상 동일한 메모리만 사용한다.
    
    
  • O(n): 선형 공간. 입력 크기에 비례해서 메모리 사용량이 증가한다!
    
    
  • O(log⁡ n): 로그 공간. 입력 크기에 비례하지 않고, 조금만 메모리 사용량이 증가한다!
    
    

자바에서 공간 복잡도는 데이터를 어떻게 저장하고 처리할지 결정할 때 중요하다!

예를 들어, 배열을 사용하면 모든 데이터를 한 번에 메모리에 저장해야 하니까 O(n)의 공간 복잡도가 있지만,

링크드 리스트를 사용하면 요소 하나씩 추가될 때마다 메모리가 필요하다.