그래서 스프링 어플리케이션을 실행하면 객체를 찾을 수 없어 당연히 오류발생

따라서 프록시 패턴, 가짜 객체를 생성해놓는 방법으로 해결가능 어노테이션은 다음과 같음 @Component @Scope(value = "request",proxyMode = ScopedProxyMode.TARGET_CLASS)

대상이 클래스라면 TARGET_CLASS 대상이 인터페이스라면 INTERFACES

가짜 프록시 객체는 진짜 request요청이 들어오면 그때 진짜 빈을 요청하는 로직을 실행함. 그래서 해당 빈의 logic을 실행하는건 사실 가짜 프록시 객체의 메서드를 실행하는 것임. 하지만 내부동작으로 실제 빈의 메서드를 실행하는 것과 마찬가지로 동작함.

• 싱글톤 : 기본 스코프, 컨테이너의 시작과 종료까지 유지되는 가장 넓은 범위
• *프로토타입 *: 스프링컨테이너가 빈의 생성과 의존관계 주입까지만 관여하고 더는 관리하지 않는 매우 짧은 범위의 스코프

+ 웹 관련 스코프

• request : 웹 요청이 들어오고 나갈 때까지 유지
• session : 웹 세션이 생성되고 종료될 때까지 유지되는 스코프
• application : 웹의 서블릿 컨텍스와 같은 범위로 유지

싱글톤 스코프인 빈을 조회하면 항상 같은 인스턴스를 반환 : 싱글톤

프로토타입의 경우에는 스프링 컨테이너가 항상 새로운 인스턴스를 생성하고 의존관계를 주입한 후 반환, 그리고 더이상 관리하지 않음 따라서 생성 콜백, 의존관계 주입, 초기화에는 스프링 컨테이너가 관여하지만, 반환 후에는 더 이상 관리하지 않기 때문에 소멸 콜백은 동작하지 않음

프로토타입 빈을 싱글톤 빈과 함께 사용할 때 문제점 : 싱글톤 빈에 프로토타입 빈이 주입되었을 때, 프로토타입 빈의 메소드를 호출한다면 어떻게 될까? 다른 클라이언트가 싱글톤 빈을 통해 프로토타입 빈을 사용한다면, 이미 과거에 주입이 끝난 빈이기 때문에 계속 같은 프로토타입 빈을 유지함 => 의도와는 다른 결과

만약 싱글톤 빈이 프로토타입 빈을 사용할 때마다 컨테이너에 새로 요청을 한다면? : 매번 ac.getBean()을 통해서 계속 새로운 빈이 생성됨 : 의존관계를 외부에서 주입(DI)받는게 아니라 직접 필요한 의존관계를 찾는 것을 Dependency Lookup, 의존관계 조회 라고 한다.

하지만 위와 같은 방법을 쓰면, 스프링 컨테이너에 종속적인 코드가 되고 테스트도 어려워진다. 문제 해결에는 지정한 프로토타입 빈을 컨테이너에서 대신 찾아주는 DL 기능만 필요하다.

해결법 1 : ObjectFactory, ObjectProvider 지정한 빈을 컨테이너에서 대신 찾아주는 DL 서비스를 제공한다.

특징 : 스프링이 제공하는 기능이지만, 기능이 단순해서 단위 테스트, mock코드를 만들기 훨씬 쉬워짐 : ObjectProvider는 Factory의 상속 옵션임. 스트림 처리등 편의 기능이 많고 별도의 라이브러리 필요 없음

해결법 2 : JRS-330 Provider 자바 표준 라이브러리를 사용하는 방법 import jakarta.inject.Provider

특징 : 별로 라이브러리 필요 : 자바표준이므로 스프링이 아닌 컨테이너에서도 사용 가능 : 기능이 매우 단순, get()을 통한 DL기능만 제공

빈의 이벤트 라이프 사이클은 스프링 컨테이너 생성 -> 빈 생성 -> 의존관계 주입 -> 초기화 콜백 -> 사용 -> 소멸 전 콜백 -> 스프링 종료

객체의 생성과 초기화는 불리하는 것이 좋다. 생성자는 필수정보를 파라미터로 바도, 메모리를 할당해서 객체를 생성하는 책임을 가진다. 초기화는 생성된 값들을 활용해서 외부 커넥션을 연결하는 등 무거운 동작을 수행한다. 따라서 무거운 동작은 별도의 메서드에서 수행하는 것이 유지보수 관점에서 더 좋은 방법임. (의도적으로 지연) -------------------------------------------- 스프링은 3가지 방법으로 빈 생명주기 콜백을 지원한다.

1. 인터페이스 : Initializing Bean, Disposable Bean 방법 : 위 인터페이스들을 implements하고 초기화, 소멸 메소드를 오버라이딩한다.

단점 ** : 초기화, 소멸 메소드의 이름 변경 불가능 : 해당 코드가 스프링 전용 인터페이스에 의존하게 됨 : 내가 코드를 고칠 수없는 외부 라이브러리에 적용할 수 없다. 2. **빈 등록 초기화, 소멸 메서드 방법 : 설정 정보에 @Bean(initMethod = "init", destroyMethod = "close") 와 같이 작성 특징 : 메서드 이름을 자유롭게 할 . 수있음 : 스프링 빈이 스프링 코드에 의존하지 않음 : 코드가 아니라 설정정보를 사용하므로 외부 라이브러리에도 적용 가능 종료메서드 추론 라이브러리는 대부분 close, shutdown 이라는 이름의 종료 메서드를 사용함, 그래서 추론기능을 통해 close, shutdown 이라는 이름의 메서드를 자동으로 호출해준다. 단, 공백문자열로 지정해놓으면 추론기능을 수행하지 않음. 3. 애노테이션 @PostConstruct, @PreDestroy 방법 : 초기화, 소멸 메서드에 애노테이션만 붙이면 됨 특징 : 스프링에 종속적인 기술이 아님, 자바표준 방법임. 따라서 스프링이 아닌 다른 컨테이너에서도 동작함. : 컴포넌트 스캔과 잘 어울림. 단점 : 외부 라이브러리에 적용불가능, 외부라이브러리에 초기화, 종료를 넣으려면 2번 방법을 사용

1. 생성자 주입 특징 : 생성자 호출 시점에 딱 1번만 호출 보장 불변, 필수 의존관계에 사용함 스프링 빈 등록시에 호출됨
2. 수정자 주입 특징 : setter 메서드로 의존관계 주입 선택, 변경 가능성이 있는 의존관계에 사용
3. 필드 주입 필드에 바로 주입하는 방법, 추천되지 않음 특징 : 외부에서 변경이 불가능해서 테스트가 힘듬 DI프레임워크가 없으면 어플리케이션 실행과 관계없는 테스트에는 사용가능 스프링 설정하는 Configuration에서 특별한 목적으로 사용
4. 일반 메서드 주입 특징 : 한번에 여러 필드를 주입 받을 수 있다. 거의 사용하지 않음

옵션처리

주의할 스프링 빈이 없어도 동작해야 할 때가 있다.

1. Autowired(required = false)
2. SpringFramework - @Nullable
3. Optional

생성자 주입을 선택

장점

1. private final을 사용 가능 -> 혹시 모를 생성자에서의 오류 검출
2. 데이터 누락시에 컴파일 오류가 발생해서 검출가능
3. 프레임워크에 의존하지 않고 순수 자바 언어의 특징을 잘 살릴 수 있는 방법

롬복

생성자 주입을 사용할 때, 테스트 작성할 때 너무 이것저것 작성할 것이 많다.

롬복

1. @Getter, @Setter, @ToString 등 다양한 기능 지원(개편함)
2. @RequiredArgsConstructor : 생성자 자동으로 생성

-> 생성자 직접 안만들어도됨 ㄷ;

최근에는 생성자를 딱 1개 두고, @Autowired를 생략하는 방법을 주로 사용

조회할 빈이 두 개 이상

하위타입을 빈으로 지정하는 것은 DIP를 위배하고 유연성이 떨어짐. 그리고 이름만 다르고, 완전히 똑같은 타입의 빈이 2개 있을 때 해결이 안된다.

@Autowired 필드명, @Qualifier, @Primary

1. @Autowired fieldName @Autowired 는 타입매칭을 시도하고, 이때 여러빈이 있으면 필드명, 파라미터 이름으로 빈이름을 추가한다.

-> 타입매칭 시도하고, 결과가 2개 이상이면 필드명, 파라미터 명으로 빈 이름을 매칭

2. @Qualifier 그냥 Qualifier를 찾는 용으로만 사용하는게 좋음 단점 : 모든 코드에 어노테이션을 붙여야 함

3. @Primary 우선순위를 정해줌

@Primary 보다 @Qualifier가 더 세세하게 동작함 스프링은 항상 자동보다 수동이 우선순위가 높음 따라서 primary < qualifier

Annotation 직접 만들기

@Qualifier를 쉽게 사용할 수 있는 방식 @Qualifier("이름")에서 문자를 잘못 입력해서 발생하는 오류 방지 가능

조회한 빈이 모두 필요할 때 List, Map

의도적으로 정말 해당 타입의 빈이 모두 필요할 때 => test.autowired.AllBeanTest

그래서 스프링부트는 빈 중복시 아예 오류를 발생시킴(중복방지)

컴포넌트 스캔은 @Component가 붙은 클래스를 스캔해서 빈으로 등록 이때 빈의 기본 이름은 클래스명을 사용하되 맨 앞글자만 소문자로 사용함 빈 이름을 직접 지정할 수도 있음

basepackages = 탐색시작 위치 지정. 해당 패키지의 하위 패키지를 모두 탐색, 지정하지 않으면 @ComponentScan이 붙은 클래스의 패키지가 시작위치

따라서 시작위치에 AppConfig같은 메인 설정정보 파일을 두고 @ComponentScan을 붙이고, basePackages 지정 생략

• 스프링부트 사용시에는 프로젝트 시작 루트위에@SpringBootApplication을 붙이는게 관례

컴포넌트 스캔 대상 : @Component @Service : 비즈니스 로직에서 사용 @Repository : 스프링 데이터 접근 계층에서 사용, 데이터 계층의 예외를 스프링의 추상화된 예외로 변환해준다. @Controller : 스프링 MVC 컨트롤러에서 사용 @Configuration : 스프링 설정 정보에서 사용

@Autowired : 자동으로 해당 스프링빈을 찾아서 의존관계 주입

싱글톤 패턴 문제점

• 싱글톤 패턴을 구현하는 코드 자체가 길다
• 의존관계상 클라이언트가 구체 클래스에 의존해야 함 -> DIP X
• OCP위반 가능성 높음
• 테스트하기 어려움
• 내부 속성을 변경하거나 초기화하기 어려움
• private 생성자로 자식클래스 만들기 어려움
• 결론적으로 유연성 떨어짐
• 안티패턴으로 불리기도 한다.

스프링 컨테이너는 알아서 싱글톤으로 객체를 관리함 스프링 컨테이너는 객체를 하나만 생성해서 싱글톤 객체로 빈을 관리하는 싱글톤 레지스트리 역할을 함.

설사 하나의 빈 생성자가 여러번 호출될 것 같은 상황에서도 싱글톤을 유지함 -> CGLIB라는 라이브러리를 통해 AppConfig클래스를 상속받은 임의의 다른 클래스를 만들고, 그 클래스를 스프링 빈으로 등록함. 실제로 내가 만든 객체를 인스턴스로 만드는게 아니라는 것. 그래서 AppConfig의 @Configuration을 제거하면 생성자가 중복해서 호출되는 것을 확인할 수 있음 (Test.ConfigurationSingletonTest 확인)

+싱글톤 방식의 주의점

• 읽기만 가능해야 함 : 여러 클라이언트가 한 객체 인스턴스를 공유하기 때문에 특정 클라이언트에 의존적이거나 특정 클라이언트가 수정할 수 있는 필드가 있으면 안됨
• 필드 대신 자바에서 공유되지 않는 지역변수, 파라미터, ThreadLocal 등을 사용

이 관점에서 프레임워크와 라이브러리는 다음과 같이 구분된다.

프레임워크 : 내가 작성한 코드를 제어하고, 대신 실행한다. 즉 프로그램의 흐름을 내가 아닌 프레임워크가 제어한다.

라이브러리 : 프로그램에서 코드의 실행 흐름을 내가 제어한다.

+DI 컨테이너 : 객체를 생성하고 의존관계를 연결하는 역할 수행 ex)스프링

public class OrderServiceImpl implements OrderService {
    private final MemberRepository memberRepository = new MemoryMemberRepository();

    //실행코드
    memberRepository.run();
}

위 코드에서 OrderServiceImpl은 인터페이스인 memberRepository의 메소드를 호출하므로 인터페이스에 의존하는 것이 맞다. 하지만 문제는 자신이 사용할 구현체를 본인이 생성하고 선택함으로써 동시에 구현체에 의존하게 되는 것과 마찬가지다.

public class OrderServiceImpl implements OrderService {
    private final MemberRepository memberRepository;

    public OrderServiceImpl(MemberRepository memberRepository) {
        this.memberRepository = memberRepository;
    }
    //실행코드
    memberRepository.run();
}

이 코드에서는 할당을 생성자로 넘기고 어떤 객체를 생성하거나 사용할지 선택하는 것을 본인이 직접 수행하지 않는다. 그 책임은 온전히 OrderServiceImpl 객체를 생성할, 외부 어딘가에게 전가되는 것이다. 다시말해 OrderServiceImpl 입장에서는 자신이 의존하게 될 대상을 외부에서 정해주는, 의존관계가 주입당하는 것 이다. OCP, DIP를 지키기위한 방법이면서도, 하나의 책임만을 수행해야 한다는 SRP의 관점에서도 더 나은 구현 방식인 것으로 생각된다.

1. 상속, 다형성에 대한 시선

흔히 클래스를 처음 배울때 가장 먼저 설명하는 것이 상속을 통한 구현이다. 예를 들어 자동차 클래스를 상속받아 다양한 자동차들, 아반떼, 그랜져 클래스 등등을 만들 수 있다는 것이다. 나도 그랬고, 대부분의 학생들은 여러개의 클래스를 쉽게 구현할 수 있게 되는 것에 집중한다. 하지만 개발자 입장에서의 본질은 그게 아니라, 동일한 사용법으로 여러 개의 클래스를 사용할 수 있다는 것이다. 새로운 클래스를 만들더라도, 이를 사용하는 클라이언트의 코드는 변경할 필요가 없다는 것. 그것이 가져다주는 장점을 생각해보니 단순히 여러 개의 클래스를 구현할 수 있다는 것보다 훨씬 중요하다고 생각하게 되었다. -> 인터페이스를 구현한 객체를 실행시점에 변경할 할 수 있다 -> 따라서 클라이언트를 변경하지 않으면서 구현기능을 유연하게 변경할 수 있다.

2.SOLID

SRP

단순히 단일책임이라는 것은 모호함; 책임의 크기, 범위가 다르기 때문. 중요한 것은 변경. 어떤 변경을 해야만 할 때 그 파급효과가 얼마나 큰지를 따져야 함

OCP

다형성을 통해 편리한 확장(ex. 인터페이스로 부터 새로운 기능의 클래스를 구현) 하지만 정확한 설계를 통해 핵심은 변경되지 않도록. --> 그런데 사용하는 클래스를 바꾸려면, 클라이언트의 코드를 변경? --> 이를 위해 별도의 연결고리가 필요 : 스프링의 컨테이너 기능?

LSP

하위클래스는 인터페이스 규약을 꼭 지켜야 한다는 것. 단순히 메소드를 다 구현해서 컴파일이 되는 것을 넘어서, 같은 기능을 수행하도록.

ISP

단일책임과 비슷. 여러개의 인터페이스(특정 기능만 수행하는)를 통한 구현 -> 작은 여러개의 인터페이스 --> 명확성, 대체가능성 UP

DIP

추상화에 의존해야한다. 구체화에 의존하면 안된다. 즉, 클라이언트가 클래스에 의존하는 것이 아니라 인터페이스에 의존해야 한다. 구현체에 의존하게 되면 수정이 힘들어짐. --> 하지만 사용할 객체를 클라이언트가 직접 선택하는 순간 의존하는 것과 마찬가지

스프링의 다형성

DI 컨테이너 를 통해 위에서 말한 OCP와 DIP 위배를 막는다. -> 더욱 유연한, 특히 클라이언트의 변경없이 확장이 가능하게 함.

자료구조 특강이라곤하지만, 사실 알고리즘을 이해하기 위한 필수과정이라고 말할 수 있을 것 같습니다. 왜냐하면 거의 모든 알고리즘에서 하나이상의 자료구조를 사용하기 때문입니다. 일단 저희는 알고리즘 소모임이니까 알고리즘에 대해서 말해보지 않을 수가 없습니다.

알고리즘

'알고리즘'이라는 단어를 어떻게 설명할 수 있을까요? 사람마다, 책마다 차이는 있겠지만 한 문장으로 설명한다면 "어떤 문제를 해결하기 위한 단계적인 절차"라고 할 수 있겠습니다. 단순히 컴퓨터나 기계적인 절차들뿐만 아니라 맛있는 파스타 레시피, 천안에서 홍대까지 가는 길찾기 등과 같이 일상적인 절차들 또한 알고리즘이라고 할 수 있겠습니다.

예를 들어봅시다. 만약에 우리학교가 있는 병천에서 홍대까지 가고 싶다면 어떻게 해야 할까요?

1. 택시를 타고 홍대까지 가는 방법
2. 셔틀버스를 타고 교대역에서 내린 후, 지하철을 타는 방법
3. 청주공항에서 비행기를 타고 김포공항에서 내린 후, 공항철도를 타는 방법

위 3가지 방법은 모두 실행 가능한 방법들입니다. 그런데 이 중에 어떤 방법이 가장 좋은 방법일까요?

장단점을 이해해야 한다

철수는 돈이 아주 많습니다. 그 대신 차멀미가 심해서 차를 탈 수가 없습니다. 그렇다면 철수에게는 세 번째 방법이 괜찮아보이죠.

반대로, 민호라는 친구는 수중에 만원밖에 없습니다. 그래서 두 번째 방법을 이용해야 홍대까지 갈 수 있을 겁니다.

이처럼 각자 어느정도의 자원(돈, 시간 등)을 가지고 있는 지, 어떤 특성을 가지고 있는 지에 따라서 선택해야할 방식이 결정됩니다.

이는 컴퓨터나 프로그램에게도 마찬가지입니다. 속도, 용량, 보안, 편리성 등등 어떤 특성을 얼만큼 요구하냐에 따라 해결방법, 즉 알고리즘은 다르게 설계되어야 합니다.

컴퓨터의 자원

컴퓨터의 자원은 크게 시간과 공간으로 나뉩니다. 다시 말하면 속도와 용량을 말합니다.

과거에는 메모리의 성능이 현재만큼 뛰어나지 못했기에 공간자원의 중요성이 비교적 많이 강조되었으나 현재는 공간보다는 시간의 중요성이 더 많이 강조되고 있습니다.

시간 복잡도

시간복잡도에 대해서 모두 알고계신다면 얘기가 바로 본론으로 들어가면 되겠지만 아닌 분들도 분명 계실 것이므로 설명을 하도록 하겠습니다.

어떤 알고리즘의 속도, 즉 얼마나 빠른 지를 어떻게 말할 수 있을까요? A라는 알고리즘은 동작하는데 3초가 걸린다. 이런식으로 말하면 될까요? 물론 그것도 틀렸다고 할 순 없습니다.

하지만 누군가는 컴퓨터실에서 굉장히 낡은 컴퓨터를 이용할 수도 있고, 다른 누군가는 피시방에서 최신 사양의 컴퓨터를 이용할 수도 있습니다. 제가 굳이 설명하지 않더라도, 그 두 컴퓨터의 성능차이가 프로그램의 실행속도 차이를 야기할 수 있다는 것을 우리는 알고 있습니다.

따라서 알고리즘의 시간적인 성능을 평가하기 위해선 객관적인 지표가 필요하고 우리는 그것을 시간복잡도라고 부릅니다.

우선 시간 복잡도의 정의는 '입력의 크기에 따라 실행되는 연산의 횟수'입니다. 이때 입력이란 '해당 알고리즘을 수행하기 위해 외부로부터 제공되는 자료'를 말하죠. "A + B = ?" 라는 식에서는 A와 B가 입력에 해당하고, "정수배열 C에서 가장 큰 값을 구하세요" 라는 문제에서는 C가 입력이 됩니다.

우리가 다룰 대부분의 알고리즘들은 입력의 크기가 커지게 되면 연산의 개수도 함께 커지게 됩니다. 그 때, 연산의 횟수가 얼마나 커지느냐 가 곧 알고리즘의 성능, 시간 복잡도인 것입니다.

어떤 알고리즘의 실제 실행시간은 연산의 개수에 의해 결정됩니다. 1개의 연산이 실행되는데 필요한 시간은 굉장히 작겠지만 연산횟수가 매우 커진다면 시간도 굉장히 많이 필요해질 것입니다.

개수가 매우 크다? 얼마나 클까요? 1억? 아니면 1조? 굉장히 애매합니다. 그렇다면 아예 무한대로 보내버리는 건 어떨까요?

점근적 표기법

그래서 고안된 것이 바로 점근적 표기법 입니다.

입력의 크기, N이 무한대로 커질 때 그 알고리즘의 연산개수를 N에 대한 식으로 나타낸 것을 말합니다.

lim, 극한에 대해서 배우셨다면 금방 이해하실 수 있을 겁니다. 100 + 1은 간단히 101이라고 쓰겠지만 ∞에 1을 더한다면? 그저 무한대일뿐입니다.

예를 들어, 어떤 알고리즘의 연산횟수가 f(n) = 2n + 1 이라면 n = ∞ 에서의 연산횟수는 그냥 n이라고 표기하게 됩니다.

다시 말하면 점근적 표기법은 입력이 무한히 클 때, 알고리즘의 시간 성능을 평가하는 방법인 것입니다. 그리고 입력의 질에 따라서 세 가지의 상황으로 점근적 표기를 분류합니다.

최상의 경우에서의, 빅오메가 표기법(Big-Ω Notation) 평균의 경우에서의, 빅세타 표기법(Big-θ Notation) 그리고 최악의 경우에서의, 빅오 표기법 (Big-O Notation)

최상, 평균, 최악? 이게 도대체 무슨 말일까요?

최악, 최상, 평균의 경우

여기서 말하는 최악, 최상, 평균은 사용된 입력이 해당 알고리즘에 얼마나 적합한 지를 이야기합니다. 예제를 보겠습니다.

A = [9, 8, 7, 6, 5, 4, 3, 2, 1]
#1 : A에서 10을 찾기 #2 : A에서 5를 찾기 #3 : A에서 9를 찾기

#1은 10을 찾는 알고리즘입니다. 그런데 A에는 10이 없습니다. 결국 A는 9,8,..2,1까지 모두 탐색한 후에 10이 없다는 것을 알게 됩니다. 이처럼 알고리즘의 연산횟수가 최대가 되는 입력을 최악의 입력이라고 합니다.

#2는 5를 찾습니다. 배열 A에 중간정도의 5가 위치하고 있으므로 많지도 적지도 않은, 평균정도의 연산을 통해 5가 있다는 결과를 얻을 것입니다. 이렇게 평균정도의 연산횟수를 갖게하는 입력을 평균의 입력이라고 합니다.

#3은 9를 찾는데, 가장 첫자리에 9가 있습니다. 연산 한번만에 알고리즘은 종료될 것입니다. 그러므로 배열 A가 #3의 최상의 입력입니다.

빅오 표기법을 주로 이용하는 이유

위에서 봤던 #1을 다시보죠. 배열에서 10을 찾는 이 알고리즘을 평가해봅시다.

배열의 크기가 N일때, 이 알고리즘의 연산횟수 f(N)은 뭘까요? 아마도 여러분은 N이라고 답할 것입니다.

왜냐하면 이 알고리즘은 연산을 아무리 많이 하게되도 N번보다 많이 반복하지는 않을 것이니까요.

그래서 최악의 입력에서의 성능을 평가하기 위해 빅오 표기법을 많이 이용하는 것입니다.

그렇다고 해서 최상, 평균에 대해서 아예 다루지 않는 것은 아닙니다. 실제로 사용되는 알고리즘들 중 대다수가 평균적인 입력을 기대하며 사용되고 있습니다.

하지만, 최악의 입력에서 성능이 극도로 저하되는 알고리즘을 평범하게 사용하기는 힘들 것입니다.

빅오표기법, 그래서 어떻게 사용할까?

지금까지 점근적표기법, 그리고 빅오표기법이 왜 사용되는 지에 대해서 알아봤습니다. 이제 어떻게 사용하는 지 알아보겠습니다.

먼저 어떤 알고리즘의 연산횟수를 알아야 합니다. f(n)으로 나타내겠습니다. 이 때, 빅오 표기법으로 나타내는 O(g(n)) 의 수학적 정의는 다음과 같습니다.

무슨 말인지 잘 모르겠죠? 그렇다면 아까 제가 한 말만 기억하세요.

예를 들어, 어떤 알고리즘의 연산횟수가 f(n) = 2n + 1 이라면 n = ∞ 에서의 연산횟수는 그냥 n이라고 표기하게 됩니다.

이 예시들을 보면 더 명확히 이해되실겁니다.

사실 f(n)이 나와있는 상태에서 빅오표기법으로 나타내는 것은 전혀 어렵지 않은 작업입니다. 진짜 재미(?)는 f(n)을 모르는 상황이죠.

그러나 오늘은 이미 너무 많은 것을 얘기하느라 저도 여러분도 지쳤을테니 다음에 살펴보도록 하겠습니다.

다음 글은 씨앗 정기활동 1-2 (주제 : 선형자료구조) 로 돌아오겠습니다. 감사합니다.

끝으로

혹시 글을 읽으시고 질문이나 피드백이 있으시다면 언제든지 남겨주시기 바랍니다.

더 나은 자료와 내용을 담을 수 있게끔 노력하겠습니다. 감사합니다.

참고강의: 인프런 | 스프링 입문

1. MVC + 템플릿 엔진 방식

MVC = Model + View + Controller.

view = 화면을 그리는 역할에만 집중 controller = 비즈니스 로직, 내부 기능 구현등에 집중

따라서 view와 controller를 따로 개발, 관리하는 것이 유지보수, 개발에 용이함.

2. API 방식

데이터를 전달할 때 XML or json구조({key : value})로 전달함.

@ResponseBody 메소드에서 객체를 반환하면 json형식으로 HTTP의 body부에 직접 반환함.

전달된 데이터는 viewResolver가 아닌 HttpMessageConverter가 동작. 문자의 경우는 'StringHttpMessageConverter' 객체의 경우는 'MappingJackson2HttpMessageConverter'

그 밖의 데이터 타입에 대해서도 다양한 converter가 사용되도록 Spring에서 설정해놓았음(원하는 converter로 설정을 바꿀 수 있음)

3. 고찰

Spring을 사용할 때의 기본적인 웹개발 방식들에 대해서 공부했다. 기본적인 코드 형식이나 엔진의 동작원리를 이해할 수 있어 도움이 많이 되었다.

참고강의: 인프런 | 스프링 입문

0.인트로

이틀전쯤부터 빌드툴인 maven과 스프링에 대해서 공부하기 시작했습니다. 깃헙에서 오픈 프로젝트를 클론받고 빌드 클릭! 과 동시에 실패... VM crash? 에러였고 스택오버플로우에서 1~2시간동안 헤맸지만 결국 해결하지 못했습니다..

pom.xml 설정에 대해서 좀 알고있으면 고칠 수 있는 오류인걸로 봤는데 하..하..못고쳤습니다.. 빌드툴에 대해 좀 지식이 쌓이면 재도전하려합니다.

그래서 맨땅에 헤딩은 잠시 접어두고 슬금슬금 강의를 찾다가 김영한님의 스프링 입문 강좌를 보면서 spring과 gradle에 대해 공부하기 시작했습니다.

1. 프로젝트 생성

가장 먼저, spring 프로젝트 스타터 사이트(https://start.spring.io/) 를 통해서 프로젝트를 생성합니다. 라이브러리는 Spring Web과 Thymeleaf 를 추가해줍니다.

정확히 어떤 역할의 라이브러리들인지는 잘 모르겠으나 설명을 읽어보니 Spring Web은 웹개발에 필요한 것으로 보입니다. Tomcat을 기본 웹 서버로 사용한다고 합니다.

Thymeleaf은... 어... 웹과 단독 환경 모두에서 사용할 수 있는 템플릿 엔진이고 HTML이 올바르게 브라우저에 출력되게하고, 정적 부모 객체..? 죄송합니다. 잘 모르겠습니다. 암튼 HTML을 사용하기 위해 필요한 것 같습니다. 제대로 알게되면 다뤄보겠습니다.

2. localhost 연결확인

프로젝트 생성 후 메인 클래스를 실행하여 연결여부를 확인합니다. 아무것도 작성하지 않은 상태이기 때문에 오류 페이지가 나오는 것이 정상입니다.

지난 학기에 Xampp를 이용해서 APM(apache + php + MySQL)을 이용해봤는데 그 때는 당연하게도 하나부터 열까지 직접 코딩하고 설정도 일일이 수정해서 사용했습니다.

spring을 통해 라이브러리 몇개 추가하니 바로 웹서버가 연동되는 것은 매우 신기했고, 일일이 연동하고 코드를 밀어넣는 것보다 훨씬 편리해보였습니다.

그렇게 입문 15분만에 프레임워크의 중요성을 깨닫게 된 뉴비였습니다.

3. 라이브러리 살펴보기

그 이후에 프로젝트에 추가된 라이브러리를 살펴봤습니다. 여기서 의존관계라는 중요한 개념에 대해서 언급되는데 사실 아직 잘 이해하지는 못한 것 같습니다.

쉽게 말하자면 gradle이 A라는 라이브러리를 다운로드할 때 A와 의존관계에 있는 라이브러리 B,C,.. 을 함계 다운로드받는 것이라고 합니다.

그래서 grable의 Dependencies 디렉토리를 확인해보면, 프로젝트 생성시에 추가했던 Spring Web과 Thymeleaf외에도 tomcat, webmvc 등등 많은 라이브러리가 함께 다운로드된 것을 확인할 수 있습니다.

4. 고찰

일단 대략 10시간정도를 spring에 입문하기위해 헤매고 나니, 의도치않게 다양한 지식을 얻게되어 참 기쁘다...

아무래도 java도 오랜만이고, InteliJ IDE 도 처음, 프레임웤도 처음이다보니 모든게 어렵고 눈에 익숙하지가 않다.

사실은 파이썬에 훨씬 자신이 있어서 Django를 배워볼까싶기도 했었지만 기왕 Spring을 시작했으니 최대한 노력해서 많이 배울 수 있도록 노력해야겠다.

일단 내일 2시에는 현대모비스 알고리즘 대회 온라인 예선에 참가예정인데 PS에 손 못댄지도 오래됐고, 경쟁률이 높은 대회라서 큰 기대없이 경험삼아 참가하려고 합니다.

일단 향후 진로는 SSAFY나 우테코를 준비해보려하는데 이제 파이썬은 손 떼고 자바,스프링 쪽을 공부해보려 합니다.

이거랑은 별개로 PS,CT는 계속 공부할 예정이고.. 씨앗에서 할 강의도 준비해야합니다. 이번에는 방학 중에 강의자료를 다 준비해서 학기 중에 덜 고생하도록 해봐야겠습니다.

그러면 이번학기 할 일이

1. PS,CT 공부
2. 자바, 스프링, 백엔드 업무에 대한 공부
3. 알바(먹고 살기 위해서..)
4. 씨앗 강의 준비

이 정도인 것 같은데 사이드 프로젝트로 하려고 했던 웹페이지 개발은 잠시 접어야 될 것 같습니다...ㅠ

그럼 현대모비스 대회 후기로 돌아오겠습니다.

학교공부를 핑계로 개발공부도..PS도.. 놔버린 것 같아서 죄책감이 큽니다.

암튼 최근 근황으로는 1.알고리즘 소모임 씨앗 1학기 활동을 모두 종료했습니다. 비기너 4회, 시니어4회, 공통 1회, 총 9회 수업을 진행하였고 평균 10~20명 정도의 학생들이 참여했습니다.

강의 내용은 아래와 같습니다.

• Dynamic Programming
• Greedy
• Python Language
• Brute Force
• Graph Search(BFS, DFS)
• Binary Search
• Algorithm Complexity
• Data Structure

아직 업로드하지 않고 강의자료와 코드만 작성해놓은 것들이 많은데 시간이 나는대로 더 개선해서 포스팅할 수 있도록 하겠습니다.

2.PHP 웹개발 전공과목으로 웹프로그래밍 수업을 듣고 있는데, PHP를 사용한 웹페이지 개발을 하고 있습니다. xampp에서 APM을 이용하고 있고, 교재에서 제공하는 기본 웹페이지를 수정해서 씨앗에서 사용할 수 있는 문제공유 커뮤니티를 개발하는 걸 목표로 하고 있습니다. HTML, CSS, JS는 다뤄봐서 어렵지 않게 생각했는데 생각보다 어려워서 꽤 고생하고 있습니다. 기왕 공부를 시작한거 프로젝트 제출 이후에도 계속 개선해서 2학기때 실제로 사용할 수 있을 정도로 개발하려고 합니다.

개발과정은 방학중에 꾸준히 업로드할 예정입니다.

3.진로 걱정 아무래도 전공생이다보니 여기저기 주워듣는 정보도 많고 주변에 이미 개발 커리어를 시작하고 있는 지인들도 많은데 정작 나 자신은 무엇을 해야할지도, 떳떳하게 기술 스택에 적을만한게 하나도 없다는 생각에 부끄럽기도 하고, 초조하다는 생각이 많이 듭니다.

전공생임에도 개발자분들 유튜브 보면 뭔지도 모를 기술들이 한가득이고...

그래서 남은 2023년의 절반은 그냥 여기저기 갖다 박으려 합니다. 여기저기 갖다 박는 과정들은 열심히 기록하겠습니다.

4.아무도 이 글은 안봤으면 좋겠다.ㅋ

씨앗은 알고리즘 소모임으로, 주 마다 하나의 주제를 선정하고 강의를 진행합니다. 강의 후엔 주제에 맞는 예제를 풀어보고 연구하는 시간을 갖습니다.

Binary Search

이분탐색은 정렬되어 있는 자료들을 탐색범위를 절반씩 좁혀가며 원하는 자료를 탐색하는 방법을 말합니다. Up Down 게임을 상상해보면 쉽습니다.

1 ~ 100까지의 숫자중 63을 찾는 방법은?

1. 완전탐색 brute force
1,2,3...63 순으로 차례대로 63번의 비교를 거쳐 찾아봐야 합니다. 찾는 숫자가 100이였다면, 100번의 비교를 해야합니다.
2. 이분탐색 binary search
1 ~ 100 : 50 up 51~ 100 : 75 down 51 ~ 74 : 62 up 62 ~ 74 : 68 down 62 ~ 68 : 65 down 62 ~ 65 : 63 탐색완료
63번의 비교 연산을 해야하는 완전탐색에 비해 훨씬 적은 횟수로 63을 찾은 것을 볼 수 있습니다.

자료의 크기가 커지면 커질수록 이분탐색의 시간효율성은 더욱 부각되게 됩니다. 만약 10억개의 자료 중 하나를 찾아야 한다면,

완전탐색의 경우, 최악의 경우 : 10억 의 연산횟수를 가집니다. 이분탐색의 경우, 최악의 경우 : 약 30회 (2의 30제곱 = 약10억)

이분탐색은 범위를 절반씩 좁혀가며 탐색을 이어가기 때문에 아무리 탐색이 오래걸려도 log N 을 넘어가지 않습니다.(여기서 log의 밑은 2입니다.)

이제 이분탐색을 구현하는 방법을 알아보겠습니다.

이분탐색의 구현

위에서 나온 UP & DOWN게임을 코드로 옮긴다고 생각하면 쉽습니다. 가능한 숫자의 범위가 0 부터 N이고 (N은 양의 정수) 찾아야하는 숫자가 S라고 하면
1. left(한쪽 끝)를 0으로, right(반대쪽 끝)을 N으로 지정합니다.
2. mid (left와 right의 평균) 와 S를 비교합니다.
3 - 1. 만약 S가 mid보다 크다면, left부터 mid사이엔 S가 없기 때문에 left를 mid + 1로 수정합니다.
3 - 2. 만약 S가 mid보다 작다면 mid부터 right사이엔 S가 없기 때문에 right를 mid - 1로 수정합니다.
4. 과정 2, 3을 S와 mid가 같을 때 or left와 right가 역전될 때까지 반복한다.

코드로 살펴볼까요?

#arr안에 num을 찾는 이분탐색 함수 
def biSearch_isNum(num, arr):
    left = 0 #작은 쪽의 끝
    right = len(list) - 1 #큰 쪽의 끝
    #left가 right보다 작을 동안 반복
    while left <= right:
        #mid는 양 끝의 평균
        mid = (left + right) // 2
        #num이 mid번째 수 보다 큰 경우
        if arr[mid] < num:
            left = mid + 1
        #num이 mid번째 수 보다 작은 경우
        elif arr[mid] > num:
            right = mid - 1
        #num == arr[mid]
        else :
            #탐색성공
            return True
    #탐색실패 => 리스트안에 num없음
    return False

위 코드는 제가 생각하는 이분탐색을 활용한 가장 기본적인 알고리즘입니다. 이분탐색을 활용한 알고리즘은 매우 다양한데, right를 찾는 경우, left를 찾는 경우, 그리고 매개변수 탐색 등등.. 정말 다양하게 활용할 수 있습니다.

한마디로 이분탐색의 활용방법을 정리하자면, 완전탐색으로 제한시간내에 연산을 끝내지 못하는 경우에 이분탐색을 적용한다 입니다.

지금까지 배웠던 DP와 그리디에서도 비슷한 말을 했었는데 그 둘과는 정말 큰 차이점이 있습니다.

바로, 코드의 형태가 어느정도 정해져있다는 점입니다.

DP와 그리디는 정해진 형태가 딱히 없습니다. 설계단계에서 아이디어를 얻는 것이 끝이기 때문입니다.

하지만, 이분탐색은 찾으려는 값과 mid를 비교, left와 right 갱신
이라는 뚜렷한 패턴이 존재하기 때문에 한번 익혀놓으면
이분탐색을 활용하는 문제들은 거의 구현할 수 있게 됩니다.

이분탐색을 사용하는 문제유형으로는 다음과 같은 것들이 있습니다.

1. S가 입력된 자료안에 존재하는 지?
2. S가 입력된 자료안에 몇 개 존재하는 지?
3. 어떤 조건을 만족하는 가장 큰(가장 작은) 수는 무엇인지? => 매개변수 탐색
4. 자료의 어떤 부분수열(연속할 수도, 안할수도) 의 합
5. LIS(가장 긴 증가하는 부분수열)을 구하는 문제
6. 기타등등..

제 경험상, 이분탐색은 학습 효과가 정말 빠르게 나타납니다. 처음엔 마냥 어렵다가, 몇 문제 찾아보다보면 조금씩 풀이법이 보이기 시작하고 몇 시간 후엔 문제 해결 속도가 정말 빨라졌다는 것을 느낄 수 있었습니다. 그러니 처음엔 어렵더라도 조금씩 해보시면 좋을 것 같습니다.

오늘 준비한 문제들은 유형 1 ~ 4 중 하나로 선정했습니다. (LIS는 제 개취라서 언젠가 따로 강의를 할 예정입니다.)

예제

Basic

• 백준 1920번 : 수 찾기 정답 코드 링크
• 백준 10816번 : 숫자카드2 정답 코드 링크

  Advanced

• 백준 2805번 : 나무 자르기 정답 코드 링크
• 백준 1300번 : K번째 수
• *1300번 해설**

  Hard

• 백준 2110번 : 수 찾기 정답 코드 링크
• 백준 1208번 : 부분 수열의 합2 정답 코드 링크

백준 1300번 : 링크 문제를 이해해보자면, N x N 배열의 i행 j열의 들어있는 수는 i x j 라고 한다. 이 수들을 모두 1차원 배열에서 오름차순 정렬을 할 때, 1차원 배열의 K번째 수가 무엇인지 찾는 문제이다.

설계

꽤 까다로운 문제인 것 같다는 생각이 든다. 브루탈적인 접근(일일이 비교탐색) 은 당연히 시간초과일 것이고 DP로 구현하자니 점화식이 도저히 안보인다.

먼저, 임의의 수 Num을 배열과 비교하는 방법에 대해 생각했다. i번째 행은 i의 배수들로 이뤄져있다. i x 1, i x 2,..., i x N 행의 특징은 확실히 알고 있으니, 일단 행 단위로 Num과 비교해보자.

Num을 특정 행과 비교한다면 어떤 정보를 얻을 수 있는가. 가장 먼저 떠오르는 것은 Num보다 작은 수가 몇 개 있는지 찾는 것이다.

만약 num이 i의 배수라면, num을 i로 나눈 몫이 i번째 행에 존재하는 num보다 작거나 같은 수의 개수와 같다. ex1) num = 14, i = 2 이면, 14 // 2 = 7이고 2, 4, 6, 8, 10, 12, 14 가능.
ex2) num = 9, i = 3 이면, 9 // 3 = 3이고 3, 6, 9 가능.

그렇다면 num이 i의 배수가 아니라면? 그래도 성립한다. 숫자를 몇 개 대입해보면 금방 알 수 있다. ex3) num = 13, i = 2 이면, 13 // 2 = 6이고 2, 4, 6, 8, 10, 12 가능.
ex4) num = 11, i = 5 이면, 11 // 5 = 2이고 5, 10 가능.

하지만, 대충봐도 반례가 떠오른다. 바로 num // i 가 배열의 크기보다 큰 경우다.

가령, num = 14이고, i = 1이라면 num // i = 14이지만, 배열의 크기 N이 5 이면 14개가 될 수 없으니 결과는 5개가 될 것이다.

따라서 N보다 num // i가 클 때의 결과는 N이다.

모든 행에 대해서 연산을 반복하면 배열에서 num보다 작거나 같은 수의 개수를 구할 수 있게 되었다.

이제 num보다 작거나 같은 수가 K개인 num을 구하면 된다.

문제는 정확히 K번째 수를 구해야 하는데, 조건을 4만 하더라도 (2행 2열), (4행 1열), (1행 4열) 총 3번 등장한다.

그렇기 때문에 필요한 것이 매개변수 탐색이다. 매개변수 탐색까지 설명하려면 글이 너~~무 길어지니까 생략하고 핵심만 말하자면 이분탐색을 사용해서 조건을 만족하는 가장 작은(큰) 수를 찾는 과정이다.

이 문제에서 매개변수 탐색을 사용하면, 자기 자신보다 작거나 같은 수가 K개인 숫자중 가장 작은 수, 즉 K번째 수를 구할 수 있다.

구현

위에서 한참 떠들었던 num보다 작거나 같은 수를 구하는 과정부터 구현해보자.

1. 총 개수를 저장할 변수 count를 선언한다.
2. count에 각 행에 num보다 작거나 같은 수의 개수를 더한다. 2 - 1.반복문으로 모든 행에 대해 num // i를 구해서 count에 더한다. 2 - 2. num // i가 N(배열의 크기)보다 크다면 N을 count에 더한다.
3. count를 반환한다.

코드로는

# N x N배열에서 mid보다 작거나 같은 수의 개수를 반환하는 함수
def find_less(N,mid):
    count = 0
    for i in range(1,N + 1):
        tmp = mid // i
        # N보다 크다면 tmp를 N으로 수정해야 함
        if tmp > N : tmp = N
        count += tmp #tmp를 count에 더함
    return count

입력으로는 배열의 크기 N과 찾아야하는 K를 받는다.

N = int(input())
K = int(input())

이제 매개변수 탐색을 구현해보자.

이분탐색에 사용할 양 끝을 left와 right로 하면 left와 right의 초기값은 0과 N x N 이다.

#가능한 수의 범위는 1부터 N의 제곱
left = 1
right = N ** 2

반복문의 구성

0. mid 는 left와 right의 평균
1. find_less(mid) 를 구하고
2. 이 값이 K보다 크거나 같다면 : answer를 mid로 갱신 그리고 right를 mid - 1로 갱신
3. 이 값이 K보다 작다면 : left를 mid - 1로 갱신

이 과정을 left가 right보다 작거나 같을 동안 반복하면 자연스럽게 find_less(answer) = K 를 만족하는 answer를 구할 수 있다.

코드가 이해 안갈수도 있는데 매개변수 탐색은 다양한 문제들을 보고 해결방법을 찾아보면서 익숙해지는 것이 빠른 것 같다. (글로 설명하기 너무 힘들다..죄송..)

while left <= right:
    mid = (left + right) // 2
    tmp = find_less(N,mid)

    #right를 수정하기 때문에 mid는 작아짐
    #별도의 탈출문없이 계속해서 반복문이 돌아가게 되면
    #mid는 조건을 만족하는 가장 작은 수로 맞춰지게 됨
    if tmp >= K :
        #결과갱신
        ans = mid
        right = mid - 1
    else :
        left = mid + 1

print(ans)

전체코드

# N x N배열에서 mid보다 작은 수의 개수를 반환하는 함수
def find_less(N,mid):
    count = 0
    for i in range(1,N + 1):
        tmp = mid // i
        # N보다 크다면 tmp를 N으로 수정해야 함
        if tmp > N : tmp = N
        count += tmp #tmp를 count에 더함
    return count

N = int(input())
K = int(input())

#가능한 수의 범위는 1부터 N의 제곱
left = 1
right = N ** 2

#이분탐색
while left <= right:
    mid = (left + right) // 2
    tmp = find_less(N,mid)

    #right를 수정하기 때문에 mid는 작아짐
    #별도의 탈출문없이 계속해서 반복문이 돌아가게 되면
    #mid는 조건을 만족하는 가장 작은 수로 맞춰지게 됨
    if tmp >= K :
        #결과갱신
        ans = mid
        right = mid - 1
    else :
        left = mid + 1

print(ans)

후기

1300번 해설을 해봤는데.. 설명하기 참 어렵네요.. 이진탐색과 매개변수 탐색에 대해 잘 모른다면 해결하기 어려울 것 같습니다. (해설을 봐도 이해하기 쉽지 않을듯)

누구나 이해할 수 있는 해설을 작성하고 싶었는데 한계가 있는 것 같습니다...

피드백과 질문은 언제나 환영합니다.

씨앗은 알고리즘 소모임으로, 주 마다 하나의 주제를 선정하고 강의를 진행합니다. 강의 후엔 주제에 맞는 예제를 풀어보고 연구하는 시간을 갖습니다.

Greedy Algorithm

그리디 알고리즘은 지역적인 최적해만을 쫒아 전역적인 최적해에 도달하는 것을 말합니다.
쉽게 말해 선택의 순간마다 지금 당장 제일 좋은 것만을 고르는 것이죠. 이해가 잘 가지 않으니 예를 들어보겠습니다.

거스름돈 N원을 500원, 100원, 50원, 10원짜리 동전으로 거슬러주려 한다. 동전의 개수를 최소로 하는 방법은?

동전의 개수를 최소로 하는 방법은 높은 가치의 동전을 최대한 많이 사용하는 것이죠. 따라서 500원짜리를 최대한 많이 사용하고, 그 다음은 100원, 50원, 10원순으로 많이 사용하는 것이 최적해에 도달하는 방법입니다.

이처럼 지역적인 최적해를 계속 선택하는 것이 전역적인 최적해로 이어지는 경우에 그리디 알고리즘을 적용할 수 있습니다.
혹은, 입력이나 문제 조건에 의해서 완벽한 최적해를 구할 수 없는 경우에 차선책으로
근사해를 구하기 위해 그리디 알고리즘을 사용하기도 합니다.

그때 그때 가장 좋은 것을 선택하면 된다? 그게 끝?
그렇게 생각하면 그리디 문제는 꽤 쉬워보입니다.

게다가 그리디 알고리즘은 이미 내린 선택에 대해 재고하지도 않고, 가장 최선만을 선택하기 때문에 프로그램의 성능면에서도 DP보다 월등한 경우가 많습니다.

하지만 진짜 문제는 그리디 문제를 알아보고 정당성을 증명하는 것입니다. 그러기 위해선 먼저 두 가지 속성을 살펴봐야 합니다.

1. 탐욕적 선택 속성(Greedy Choice Property)

탐욕적 선택 속성은 현재의 탐욕적인 선택이 이후의 선택에 방해가 되지 않는다는 특성입니다.
현재의 선택이 미래의 선택에 영향을 끼치지 않으며, 한번 선택한 것은 다시 재고하지 않는다 라는 것이죠. 이는 저번주에 배운 DP와는 반대되는 특성입니다.

2. 최적 부분 구조(Optimal Substructure)

최적 부분 구조는 전체문제의 최적해가 각 부분문제들의 최적해로 이뤄지는 것을 말합니다.
이 조건을 파악하는 것이 알고리즘의 정당성을 증명하는데 가장 중요한 부분입니다.

하지만, 모든 문제들에 대해 매번 위의 속성들을 파악하고 정당성을 증명한 후, 구현에 필요한 아이디어까지 생각해내는 것은 제 머리로는 불가능에 가깝습니다. 결국 문제를 많이 풀어보면서 패턴과 형태에 익숙해지는 것이 가장 좋은 공부 방법이라고 생각합니다. 우리가 수학 문제를 풀 때 특정 키워드를 보면 '어? 이거 미분해서 어떻게 어떻게 풀면 되겠는데?' 라고 생각하는 것처럼 말이죠.

그러니, 이제부터는 대표적인 유형 2가지에 대해 알아보겠습니다.

유형 1) 활동선택 (Activity Selection)

첫 번째는 활동 선택입니다. 스케줄을 짜는 문제죠.

활동 선택(Activity Selection) 각각 시작시간과 종료시간이 정해져 있는 활동들이 주어지고 주어진 시간내에서 가장 많은 활동을 선택하는 경우를 찾는 문제 ex) 1시부터 6시사이에 가장 많은 체육 수업을 듣는 방법은?

활동 선택문제는 강의실 배정, 회의실 배정, 주차장...등등 다양한 이름으로 등장합니다. 이 때 최적해의 기준은 종료시간과 시작시간입니다.

일반적으로 종료시간이 가장 빠른 활동 중에 시작시간이 가장 빠른 활동을 선택하는 방식으로 구현하면 쉽게 해결할 수 있습니다. 예제 : 백준 1931번, 회의실 배정

유형 2) 거스름돈like

N 원을 500원, 100원, 50원, 10원짜리 동전을 사용해서 거슬러주려고 한다. 동전의 개수를 최소로 하는 방법은?

N kg의 쌀을 10kg짜리 포대와 3kg짜리 포대를 사용해서 배달하려고 한다. 쌀포대의 개수를 최소로 하는 방법은?

이런 유형의 문제를 이제부터 거스름돈like 문제라고 합니다. (제가 그렇게 정했습니다) 최적해의 기준은 당연히 큰 단위부터 최대한 많이 포함하는 것이고, 구현에 실수만 하지 않으면 쉽게 해결할 수 있습니다. 예제 : 백준 2839번, 설탕배달

그리디, 어떻게 풀어야 할까?

그리디 문제는 어떤 과정으로 해결해야 할까요?

1. 가장 먼저 그리디를 적용할 수 있는 지 파악해야 합니다.

그리디를 적용한다면 어떻게 구현하게 될지, 무엇을 기준으로 할 것인지, 그리고 가장 중요한 알고리즘의 정당성에 대해 고려해야 합니다. (개인적으로, 저는 문제를 풀 때 완전 탐색, 그리디, DP 순으로 설계법을 구상해봅니다.
문제의 조건과 입출력을 근거로 하나씩 소거하면서 진행하는 것이 도움이 되는 것 같습니다.)

2. 무엇을 기준으로, 어떻게 최적해를 선택할 것인지 결정해야 합니다.

입력된 자료 중 기준이 무엇인지 파악하고, 어떻게 부분 최적해를 선택할 지 결정해야 합니다.
어떤 문제는 특정 키값을 기준으로 정렬을 사용하면 쉽게 해결되기도 하지만,
고려해야할 키값이 2개 이상인 경우도 있고 입력의 크기가 커서 일반적인 정렬로는 해결할 수 없는 경우도 있습니다. 그렇기 때문에 자료의 크기, 특징을 고려하여 자료구조와 탐색방식을 결정해야 합니다.

3. 설계를 마친 후 코드로 구현합니다.

씨앗활동을 진행하면서 느낀 것인데, 충분한 설계과정과 정당성 증명없이 무작정 구현부터 뛰어드는 분들이 많이 계신 것 같습니다. 어느정도 깊이가 있는 문제에서는 설계를 먼저 하고 그 후에 구현하는 것이 문제를 푸는 입장에서도, 공부를 하는 입장에서도 유익하다고 생각합니다.

예제

• 난이도 下
• 백준 11399번 : ATM*
• 백준 2839번 : 설탕배달*
• 백준 2217번 : 로프*
  
  
• 난이도 中
• 백준 1931번 : 회의실 배정* 1931번 해설 : 링크
• 백준 1715번 : 카드 정렬하기* 1715번 해설 : 링크
• 백준 2437번 : 저울* 2437번 해설 : 링크
  
  
• 난이도 上
  백준 1700번 : 멀티탭 스케줄링 1700번 해설 : 링크
• 백준 1339번 : 단어수학* 1339번 해설 : 링크

질문이나 피드백 언제나 환영합니다.

1. 일정 개수의 영단어를 입력받는다.
2. 각 알파벳에 가중치를 9부터 0까지 부여할 수 있다. 예를 들어, A = 1, B = 2, C = 3이라면,

ABC = 123, CCA = 331 로 계산된다. 3. 입력받은 단어들의 합의 최댓값을 구하라.

설계

일단 보자마자 든 생각은 '사용된 알파벳이 각각 몇개인지 모두 구해야겠다' 였다.
예를 들어, ABC 에서는 A가 100번, B가 10번, C가 1번 사용된 것을 기록하고 CCA 에서는 C가 100번 + 10번, A가 1번 사용된 것을 기록한다.

이런식으로 모든 단어들에 대해 검사를 진행하고 많이 사용된 알파벳부터
높은 가중치를 부여해서 (사용횟수 **X 가중치)** 를 모두 구하면 될 것 같다. 이렇게 쓰고나니 그리디 문제라는 것이 보이기 시작한다.

가중치가 9부터 0이고 알파벳은 최대 10개 등장하니 간단히 해결할 수 있어 보인다.

구현

일단 단어들은 리스트에 입력받으면 될 것 같고, 알파벳은 사용횟수와 함께 저장해야 하니 ( key : value ) 형태의 딕셔너리 자료형을 사용하자.

Words = [] #단어들을 저장할 리스트
DICT = {} #알파벳은 dictionary 자료형 사용

#입력
for _ in range(int(input())):
    Words.append(list(input().strip()))

입력받은 단어들에 대해서 다음의 과정을 거쳐야 한다.

1. 단어에 속해있는 문자 ch의 자릿수(10,100,1000,...)를 구한다.
2. ch가 딕셔너리 key 중에 있으면, value를 자릿수 만큼 증가시킨다.
3. 아직 딕셔너리에 없으면, 딕셔너리에 자릿수와 함께 추가한다.

말로 설명하려니 더 어려워보인다. 코드를 보자.

#입력받은 단어들에 대해
for wd in Words :
    #단어의 각 자리에 대해
    for i in range(len(wd)):
        # ex) ABCD에서 A의 tmp_value = 1000
        tmp_val = 10 ** (len(wd) - 1 - i)
        #해당 알파벳이 딕셔너리에 이미 들어있는지 확인
        if wd[i] in DICT:
            DICT[wd[i]] += tmp_val #이미 있으면 value 증가
        else :
            DICT[wd[i]] = tmp_val #아직 없으면 key:value 추가

여기까지 거치고 나면, 딕셔너리에 알파벳들과 각각의 사용횟수가 key : value 형태로 저장되어있다.

이제 사용횟수가 큰 순서대로 꺼낼 수 있게 만들어야 한다.

최댓값만 출력하면 되는 문제이니 사용횟수가 가장 큰 알파벳이 A인지 Z인지는 중요하지 않다.

그래서, 딕셔너리의 (1) value값들만 뽑아서 리스트로 만들고 (2) 내림차순 정렬을 해주면 될 것 같다. 문법을 잘 모른다면 이참에 알아두면 좋을 것 같다.

#(1) 키값들을 리스트로 변환
Values = list(DICT.values())
#(2) 내림차순 정렬
Values.sort(reverse=True)

이제부턴 해설이 딱히 필요없을 것 같다. Values의 각 요소에 가중치를 9부터 1씩 감소시키면서 곱해주고, 총합을 구하면 된다.

#가중치 mul, 9부터 0까지 1씩 감소
mul = 9
#총합이 결과
SUM = 0
for el in Values:
    SUM += el * mul
    mul -= 1
#결과출력
print(SUM)

전체코드

import sys
input = sys.stdin.readline

Words = [] #단어들을 저장할 리스트
DICT = {} #알파벳은 dictionary 자료형 사용

#입력
for _ in range(int(input())):
    Words.append(list(input().strip()))

#입력받은 단어들에 대해
for wd in Words :
    #단어의 문자들에 대해
    for i in range(len(wd)):
        #가중치 ex) ABCD에서 A는 1000의 가중치를 가짐
        tmp_val = 10 ** (len(wd) - 1 - i)
        #해당 알파벳이 딕셔너리에 들어있는지 확인
        if wd[i] in DICT:
            DICT[wd[i]] += tmp_val #이미 있으면 value 수정
        else :
            DICT[wd[i]] = tmp_val #아직 없으면 key:value 추가
#(1) 키값들을 리스트로 변환
Values = list(DICT.values())
#(2) 내림차순 정렬
Values.sort(reverse=True)

#가중치 mul, 9부터 0까지 1씩 감소
mul = 9
#총합이 결과
SUM = 0
for el in Values:
    SUM += el * mul
    mul -= 1
#결과출력
print(SUM)

끝으로

난이도 上 문제로 선정하기엔 조금 쉽지 않나 싶긴하다. 실제로 정답률도 꽤 높은 편이다.
1700번 문제가 다소 까다롭기 때문에 이 문제는 다소 가벼운 마음으로 고르긴 했다.
누구나 문법에만 익숙하다면 충분히 해결할 수 있는 문제니 다들 시도해봤으면 좋겠다.

질문과 피드백은 언제나 환영합니다.