문제 해석

처음에는 그냥 단순하게 ArrayList로 만들어 enter면 넣고 leave면 빼는 형식으로 구현했다. 그 결과는..

오열

아마 List로 할 시에는 너무 오래걸려서 그랬을까..? 예외 상황을 찾아보려고 했는데 실패했다 ㅠ

그래서 HashMap으로 구현하여, 이미 가지고 있는 name이면 제거하고, 아니라면 넣었다. 굳이 cmd(enter 또는 leave)로 비교할 필요가 없어 위와 같이 구현하였다. 그 뒤 출력할 list를 위해 새로운 ArrayList를 만들어서 넣어주고 이름을 사전의 역순으로 출력하기 위해 Collections.sort에서 reverseOrder를 통해 역순으로 정렬하였다.

풀이

import java.util.*;
import java.io.*;

public class prob7785 {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st;

        int n = Integer.parseInt(br.readLine());

        HashMap<String,String> map = new HashMap<>();

        for (int i = 0; i < n; i++) {
            st = new StringTokenizer(br.readLine());
            String name = st.nextToken();
            String cmd = st.nextToken();
            if (map.containsKey(name)) {
                map.remove(name);
            } else {
                map.put(name, cmd);
            }
        }
        List<String> list = new ArrayList<>(map.keySet());
        Collections.sort(list, Collections.reverseOrder());

        for (int i = 0; i < list.size(); i++) {
            bw.write(list.get(i) + "\n");

        }
        bw.flush();
    }

}

클라이언트

서버로 요청하는 프로그램을 모두 일컬어 말함. 웹 브라우저가 대표적인 클라이언트 중 하나. 정보를 요청하는 행위를 '서버에 요청한다'. 그러면 서버는 그에 맞는 화면으로 응답.

서버

클라이언트의 요청을 받아 처리하는 주체. 클라이언트가 데이터를 요청하면 데이터, 서버 내에서 처리만 해달라는 요청을 하면 해당 요청만 처리.

데이터베이스

여러 사람이 데이터를 한 군데에 모아놓고 여러 사람이 사용할 목적으로 관리하는 데이터 저장소. MySQL, 오라클, postgreSQL 등은 데이터베이스 관리 시스템. 클라이언트에서 SQL(데이터베이스를 조작하기 위한 언어)로 데이터베이스 관리 시스템에 데이터를 요청하면 데이터베이스 관리 시스템은 데이터베이스에서 데이터를 꺼내 응답.

RDB

Relational Database의 약자로, 관계형 데이터베이스 라는 뜻. RDB가 아닌 데이터베이스를 NoSQL 또는 NewSQL로 구분. RDB는 데이터를 행 과 열로 이루어진 테이블로 관리, 기본 키(Primary Key)를 사용해 각 행을 식별. 또한 각 테이블 간의 관계를 지을 수 있음.

SQL

Structured Query Language의 약자. 쿼리, 즉 데이터 검색을 하는 언어.

NoSQL

SQL을 안 쓴다는 의미로 사용되기도 하지만, 최근에는 Not Only SQL의 의미로도 쓰임. RDB는 데이터 저장, 질의, 수정, 삭제가 용이하지만 반면에 성능 개선이 쉽지 않음. 데이터베이스의 성능을 높이기 위해서는 머신의 성능을 좋게 하는 스케일 업 또는 머신을 여러 대로 분리하는 스케일 아웃이 필요. 스케일 업은 장비를 업그레이드 하면 되지만, 스케일 아웃은 데이터베이스를 분산하고, 이때 트랜잭션을 사용하면 성능이 떨어지게 됨. RDB의 이러한 문제를 해결하기 위해 NoSQL이 등장. 데이터 모델링을 어떻게 하느냐에 따라 다이나모디비, 카우치베이스, 몽고디비등이 존재.

아이피와 포트

아이피는 인터넷에서 컴퓨터 또는 기기들이 서로를 식별하고 통신하기 위한 주소. 아이피를 통해 서벌르 찾음. 포트는 그 서버에서 운용되고 있는 서비스를 구분하기 위한 번호.

라이브러리와 프레임워크

라이브러리

애플리케이션 개발에 필요한 기능인 클래스, 함수등을 모아놓은 코드의 모음을 뜻함. 개발자가 소프트웨어를 만들 때 필요에 따라 원하는 기능을 구현하기 위해 코드의 모음을 가져다 쓸 수 있는 일종의 도구 역할.

프레임워크

소프트웨어 개발을 수월하게 하기 위한 소프트웨어 개발 환경. 프레임워크는 애플리케이션을 개발할 때 전체적인 구조를 잡기 위해 사용, 라이브러리는 개발을 하는 과정에서 필요한 기능을 구현하기 위해 사용.

백엔드 개발자 업무

1. 과제 할당
2. 과제 분석
3. 개발
4. 테스트(리뷰)
5. QA 및 버그 수정
6. 배포
7. 유지 보수

자바 어노테이션

자바로 작성한 코드에 추가하는 표식을 말함. 보통 어노테이션은 @ 기호를 사용하며, JDK 1.5 버전부터 이용 가능. 어노테이션은 다양한 목적으로 사용하지만 보통은 메타 데이터로 사용하는 경우가 많음.

슬라이딩 윈도우는 일정한 길이의 범위를 이동하여 조건에 맞는 값을 찾는 알고리즘이다. 한 칸씩 이동 하기 때문에 공통된 부분은 유지하고 처음과 끝 원소만 갱신하여 유용하게 사용할 수 있다.

• 슬라이딩 윈도우는 데이터의 정렬여부와 관계없이 사용 가능하다.

• 고정 사이즈의 윈도우가 이동하면서 윈도우 내에 있는 데이터를 이용해 문제를 풀이하는 알고리즘을 말합니다.
• 교집합의 정보를 공유하고, 차이가 나는 양쪽 끝 원소만 갱신하는 방법입니다.
• 배열이나 리스트의 요소의 일정 범위의 값을 비교할 때 사용하면 매우 유용합니다.
• 투 포인터(two poitners) 알고리즘과 연동하여 많이 쓰입니다.
  • 1차원 배열이 있고 이 배열에서 각자 다른 원소를 가리키는 2개의 포인터를 조작하며 원하는 값을 얻는 형태

투 포인터

투 포인터는 데이터에 순차적으로 접근해야 할 때 두 개의 점 위치를 조절하여 조건에 부합하는지 판단하는 알고리즘이다. 공통 부분을 제외하고 포인터로 이동하는 원소의 처리만 하면 되므로 유용하게 쓰일 수 있다.

• java.lang 패키지

java.lang 패키지는 자바에서 가장 기본적인 동작을 수행하는 클래스들의 집합입니다. 따라서 자바에서는 java.lang 패키지의 클래스들은 import 문을 사용하지 않아도 클래스 이름만으로 바로 사용할 수 있도록 하고 있습니다.

• java.lang.Object 클래스

java.lang 패키지 중에서도 가장 많이 사용되는 클래스는 바로 Object 클래스입니다. Object 클래스는 모든 자바 클래스의 최고 조상 클래스가 됩니다. 따라서 자바의 모든 클래스는 Object 클래스의 모든 메소드를 바로 사용할 수 있습니다.

이러한 Object 클래스는 필드를 가지지 않으며, 총 11개의 메소드만으로 구성되어 있습니다.

toString() 메소드

toString() 메소드는 해당 인스턴스에 대한 정보를 문자열로 반환합니다.

이때 반환되는 문자열은 클래스 이름과 함께 구분자로 '@'가 사용되며, 그 뒤로 16진수 해시 코드(hash code)가 추가됩니다.

16진수 해시 코드 값은 인스턴스의 주소를 가리키는 값으로, 인스턴스마다 모두 다르게 반환됩니다.

equals() 메소드

equals() 메소드는 해당 인스턴스를 매개변수로 전달받는 참조 변수와 비교하여, 그 결과를 반환합니다.

이때 참조 변수가 가리키는 값을 비교하므로, 서로 다른 두 객체는 언제나 false를 반환하게 됩니다.

Object 메소드

• protected Object clone() : 해당 객체의 복제본을 생성하여 반환함.
• boolean equals(Object obj) : 해당 객체와 전달받은 객체가 같은지 여부를 반환함.
• protected void finalize() : 해당 객체를 더는 아무도 참조하지 않아 가비지 컬렉터가 객체의 리소스를 정리하기 위해 호출함.
• Class<T> getClass() : 해당 객체의 클래스 타입을 반환함.
• int hashCode() : 해당 객체의 해시 코드값을 반환함.
• void notify() : 해당 객체의 대기(wait)하고 있는 하나의 스레드를 다시 실행할 때 호출함.
• void notifyAll() : 해당 객체의 대기(wait)하고 있는 모든 스레드를 다시 실행할 때 호출함.
• String toString() : 해당 객체의 정보를 문자열로 반환함.
• void wait() : 해당 객체의 다른 스레드가 notify()나 notifyAll() 메소드를 실행할 때까지 현재 스레드를 일시적으로 대기(wait)시킬 때 호출함.
• void wait(long timeout) : 해당 객체의 다른 스레드가 notify()나 notifyAll() 메소드를 실행하거나 전달받은 시간이 지날 때까지 현재 스레드를 일시적으로 대기(wait)시킬 때 호출함.
• void wait(long timeout, int nanos) : 해당 객체의 다른 스레드가 notify()나 notifyAll() 메소드를 실행하거나 전달받은 시간이 지나거나 다른 스레드가 현재 스레드를 인터럽트(interrupt) 할 때까지 현재 스레드를 일시적으로 대기(wait)시킬 때 호출함.

실제 적용한 예시

제가 프로젝트에서 작성한 코드 중에, Object 클래스를 활용하여 코드를 작성한 부분이 있습니다. 코드를 작성할 때도 공부하며 되게 신기했는데, 이번 기회에 정리하게 되었습니다.

//게시판 별 게시글 개수 조회
    public BoardList getBoardList() {
        //BoardList 객체 생성
        BoardList boardList = new BoardList();
        //전체 게시글 개수
        boardList.setBoardCount(boardRepository.countAllByStateIsTrue());
        //MBTI별 게시글 개수
        List<Object[]> boardCountList = boardRepository.countBoardsByMbtiAndStateIsTrue();
        //조회한 데이터를 해당하는 MBTI에 할당
        for (Object[] row : boardCountList) {
            MbtiEnum mbti = (MbtiEnum) row[0];
            Long count = (Long) row[1];

            switch (mbti) {
                case INFJ -> boardList.setINFJ(count);
                case INFP -> boardList.setINFP(count);
                .
                .
                .
            }
        }
        return boardList;
    }

    @Query("select b.mbti, count(b) from Board b where b.state = true group by b.mbti")
    List<Object[]> countBoardsByMbtiAndStateIsTrue();

    Long countAllByStateIsTrue();

위의 코드를 작성하게 된 배경은, 저희가 진행하는 프로젝트에 MBTI별 게시판이 있습니다. 해당 게시판별로 작성된 게시글 수를 출력하기 위해, mbti별로 게시글 수와 그에 해당하는 mbti를 받아와야 했습니다.

이걸 한번에 받아오는 방법이 고민이였는데, 기능을 구현하기 위해 Object로 이루어진 List를 활용하여 구현하였습니다.

해당 Object[] 에 row[0] 에는 mbti가, row[1]에는 count 수가 저장되어 있어, for문을 돌며 해당하는 mbti 별로 게시글 수를 내려주도록 하였습니다.

컬렉션(Collection)이란, 데이터의 집합, 그룹을 뜻합니다.

자바에서 컬렉션 프레임워크(collection framework)란 다수의 데이터를 쉽고 효과적으로 처리할 수 있는 표준화된 방법을 제공하는 클래스의 집합을 의미합니다.

즉, 데이터를 저장하는 자료 구조와 데이터를 처리하는 알고리즘을 구조화하여 클래스로 구현해 놓은 것입니다.

이러한 컬렉션 프레임워크는 자바의 인터페이스(interface)를 사용하여 구현됩니다.

다음은 Java 컬렌션 프레임워크의 상속구조를 나타내는 그림입니다.

컬렉션 프레임워크 주요 인터페이스

컬렉션 프레임워크에서는 데이터를 저장하는 자료 구조에 따라 다음과 같은 핵심이 되는 주요 인터페이스를 정의하고 있습니다.

1. List 인터페이스

2. Set 인터페이스

3. Map 인터페이스

이 중에서 List와 Set 인터페이스는 모두 Collection 인터페이스를 상속받지만, 구조상의 차이로 인해 Map 인터페이스는 별도로 정의됩니다.

따라서 List 인터페이스와 Set 인터페이스의 공통된 부분을 Collection 인터페이스에서 정의하고 있습니다.

• 주요 인터페이스 간의 상속 관계 자바에서 컬렉션 프레임워크를 구성하고 있는 인터페이스 간의 상속 관계는 다음 그림과 같습니다. 위의 그림에서 <E>나 <K, V>라는 것은 컬렉션 프레임워크를 구성하는 모든 클래스가 제네릭으로 표현되어 있음을 알려줍니다.

• 주요 인터페이스의 간략한 특징

1. List<E> : 순서가 있는 데이터의 집합으로, 데이터의 중복을 허용함.
   • 구현 클래스 : Vector, ArrayList, LinkedList, Stack, Queue
2. Set<E> : 순서가 없는 데이터의 집합으로, 데이터의 중복을 허용하지 않음.
   • 구현 클래스 : HashSet, TreeSet
3. Map<K, V> : 키와 값의 한 쌍으로 이루어지는 데이터의 집합으로, 순서가 없음. 이때 키는 중복을 허용하지 않지만, 값은 중복될 수 있음.
   • 구현 클래스 : HashMap, TreeMap, Hashtable, Properties

• 컬렉션 클래스 컬렉션 프레임워크에 속하는 인터페이스를 구현한 클래스를 컬렉션 클래스(collection class)라고 합니다. 컬렉션 프레임워크의 모든 컬렉션 클래스는 List와 Set, Map 인터페이스 중 하나의 인터페이스를 구현하고 있습니다. 또한, 클래스 이름에도 구현한 인터페이스의 이름이 포함되므로 바로 구분할 수 있습니다. Vector나 Hashtable과 같은 컬렉션 클래스는 예전부터 사용해 왔으므로, 기존 코드와의 호환을 위해 아직도 남아 있습니다. 하지만 기존에 사용하던 컬렉션 클래스를 사용하는 것보다는 새로 추가된 ArrayList나 HashMap 클래스를 사용하는 것이 성능 면에서도 더 나은 결과를 얻을 수 있습니다.

Collection 인터페이스

List와 Set 인터페이스의 많은 공통된 부분을 Collection 인터페이스에서 정의하고, 두 인터페이스는 그것을 상속받습니다.

따라서 Collection 인터페이스는 컬렉션을 다루는데 가장 기본적인 동작들을 정의하고, 그것을 메소드로 제공하고 있습니다.

Collection 인터페이스에서 제공하는 주요 메소드는 다음과 같습니다.

• boolean add(E e) : 해당 컬렉션(collection)에 전달된 요소를 추가함. (선택적 기능)
• void clear() : 해당 컬렉션의 모든 요소를 제거함. (선택적 기능)
• boolean contains(Object o) : 해당 컬렉션이 전달된 객체를 포함하고 있는지를 확인함.
• boolean equals(Object o) : 해당 컬렉션과 전달된 객체가 같은지를 확인함.
• boolean isEmpty() : 해당 컬렉션이 비어있는지를 확인함.
• Iterator<E> iterator() : 해당 컬렉션의 반복자(iterator)를 반환함.
• boolean remove(Object o) : 해당 컬렉션에서 전달된 객체를 제거함. (선택적 기능)
• int size() : 해당 컬렉션의 요소의 총 개수를 반환함.
• Object[] toArray() : 해당 컬렉션의 모든 요소를 Object 타입의 배열로 반환함.

List

순서가 있는 데이터의 집합, 데이터의 중복을 허용

LinkedList

• 양방향 포인터 구조로 데이터의 삽입, 삭제가 빈번할 경우 데이터의 위치정보만 수정하면 되기에 유용
• 스택, 큐, 양방향 큐 등을 만들기 위한 용도로 쓰임

Vector

• 과거에 대용량 처리를 위해 사용했으며, 내부에서 자동으로 동기화처리가 일어나 비교적 성능이 좋지 않고 무거워 잘 쓰이지 않음

ArrayList

• 단방향 포인터 구조로 각 데이터에 대한 인덱스를 가지고 있어 조회 기능에 성능이 뛰어남

Set

순서가 없는 데이터의 집합으로, 데이터의 중복을 허용하지 않음.

HashSet

• 가장빠른 임의 접근 속도
• 순서를 예측할 수 없음

TreeSet

• 정렬방법을 지정할 수 있음

Map

키(Key)와 값(Value)의 한 쌍으로 이루어지는 데이터의 집합으로, 순서가 없음. 이때 키는 중복을 허용하지 않지만, 값은 중복될 수 있음.

Hashtable

• HashMap보다는 느리지만 동기화 지원
• null불가

HashMap

• 중복과 순서가 허용되지 않으며 null값이 올 수 있다.

TreeMap

• 정렬된 순서대로 키(Key)와 값(Value)을 저장하여 검색이 빠름

자바에서 제네릭(generic)이란 데이터의 타입(data type)을 일반화한다(generalize)는 것을 의미한다. 조금 더 부연설명을 하자면 '데이터 형식에 의존하지 않고, 하나의 값이 여러 다른 데이터 타입들을 가질 수 있도록 하는 방법'이다.

제네릭은 클래스나 메소드에서 사용할 내부 데이터 타입을 컴파일 시에 미리 지정하는 방법이다.

우리가 흔히 쓰는 ArrayList, LinkedList 등을 생성할 때 어떻게 쓰는가?

객체<타입> 객체명 = new 객체<타입>(); 이렇게 쓰지 않는가? 즉, 아래와 같이 여러 생성방식이 있다.

ArrayList<Integer> list1 = new ArrayList<Integer>();
ArrayList<String> list2 = new ArrayList<Integer>();

LinkedList<Double> list3 = new LinkedList<Double>():
LinkedList<Character> list4 = new LinkedList<Character>();

이렇게 <> 괄호 안에 들어가는 타입을 지정해준다.

생각해보자. 만약에 우리가 어떤 자료구조를 만들어 배포하려고 한다. 그런데 String 타입도 지원하고싶고 Integer타입도 지원하고 싶고 많은 타입을 지원하고 싶다. 그러면 String에 대한 클래스, Integer에 대한 클래스 등 하나하나 타입에 따라 만들 것인가? 그건 너무 비효율적이다. 이러한 문제를 해결하기 위해 우리는 제네릭이라는 것을 사용한다. 이렇듯 제네릭(Generic)은 클래스 내부에서 지정하는 것이 아닌 외부에서 사용자에 의해 지정되는 것을 의미한다. 한마디로 특정(Specific) 타입을 미리 지정해주는 것이 아닌 필요에 의해 지정할 수 있도록 하는 일반(Generic) 타입이라는 것이다.

제네릭의 장점

1. 제네릭을 사용하면 잘못된 타입이 들어올 수 있는 것을 컴파일 단계에서 방지할 수 있다.

2. 클래스 외부에서 타입을 지정해주기 때문에 따로 타입을 체크하고 변환해줄 필요가 없다. 즉, 관리하기가 편하다.

3. 비슷한 기능을 지원하는 경우 코드의 재사용성이 높아진다.

제네릭 사용방법

보통 제네릭은 아래 표의 타입들이 많이 쓰인다.

열거형(Enum)

Enum은 서로 연관된 상수들의 집합을 의미한다. 자바에서 Enum은 특수한 자바 클래스로 상수, 메서드 등이 포함될 수 있다.

Enum의 장점

1. 코드가 단순해지며, 가독성이 좋음

2. 인스턴스 생성과 상속을 방지하여 상수값의 타입안정성이 보장

3. enum class를 사용해 새로운 상수들의 타입을 정의함으로 정의한 타입이외의 타입을 가진 데이터값을 컴파일시 체크

4. 키워드 enum을 사용하기 때문에 구현의 의도가 열거임을 분명하게 알 수 있다.

열거형 enum은 상수를 의미별로 묶어 사용할 때 쓴다. 요일별로 일, 월, 화, 수...를 묶던지 mbti를 ENTJ, ENFP 등 으로 묶을 수 있다. 데이터 값의 의미를 명확히 하는 장점이 있다.

열거형은 보통 첫 글자를 대문자로 하여 시작한다.

    enum Week{SUN, MON, TUE ... }

메소드

• valueOf(String str) : 문자열 str과 일치하는 열거값을 반환한다.
• values() : 열거값 전부를 배열로 반환한다.
• ordinal() : 열거값의 순서를 반환한다.(0부터 시작)
• name() : enum타입의 값이 가지고 있는 문자열를 리턴한다.

상속이란?

상속(inheritance)이란 기존의 클래스에 기능을 추가하거나 재정의하여 새로운 클래스를 정의하는 것을 의미한다. 이러한 상속은 캡슐화, 추상화와 더불어 객체 지향 프로그래밍을 구성하는 중요한 특징 중 하나이다.

상속을 이용하면 기존에 정의되어 있는 클래스의 모든 필드와 메소드를 물려받아, 새로운 클래스를 생성할 수 있다.

이때 기존에 정의되어 있던 클래스를 부모 클래스(parent class) 또는 상위 클래스(super class), 기초 클래스(base class)라고도 한다.

그리고 상속을 통해 새롭게 작성되는 클래스를 자식 클래스(child class) 또는 하위 클래스(sub class), 파생 클래스(derived class)라고도 한다.

클래스 간의 상속은 여러 개의 부모의 정보를 상속하는 다중 상속 방식을 제외하고는 모두 허용하고 있다. 주로 다단계 상속, 계층적 상속 두 가지 방식이다. 부모 클래스를 통해 자식, 손자까지 내려가는 방식을 다단계 상속, 하나의 부모가 여러 개의 자식을 가지는 것을 계층적 상속이라고 한다.

자바에서 다중상속이 안 되는 이유

예를 들어 만약, 상속받은 여러 개의 부모 클래스들에서 동일한 명칭의 필드나 메소드가 있으면?

• 어떤 부모 클래스의 필드와 메소드를 상속받아야 하는가?
• 어떤 부모 클래스에 어떻게 접근해야 하는가?

위와 같은 모호함이 발생한다.

자바 상속 방법

//부모 클래스 생성
class 부모{

}

//부모 클래스 상속
class 자식 extends 부모{

}

자바에서 상속은 extends라는 키워드를 통해 할 수 있다. 위와 같이 상속받을 자식 클래스 뒤에 extends 키워드를 사용하고 부모 클래스를 적어주면 된다.

자바 상속 예시

class People{
    //필드(Feild)
    String name; //이름
    int age; //나이

    //메소드(Method)
    public void printMyself(){
        System.out.println("이름 : " + name);
        System.out.println("나이 : " + age);
    }
}

class Student extends People{
    //필드(Field)
    int my_grade; //내 학년

    //생성자(Constrouct)
    Student(String name, int age, int my_grade){
        super.name = name; //부모 필드 
        super.age = age; //부모 필드
        this.my_grade = my_grade;
    }

    //메소드(Method)
    public void printGrade() {
        System.out.println("내 학년 : " + my_grade);
    }
}

public class Main {
    public static void main(String[] args) {
        Student student = new Student("송민혁", 26, 4);
        student.printMyself(); //부모 메소드 호출
        student.printGrade(); //자식 메소드 호출
    }
}

super 키워드

super 키워드는 자식 클래스에서 부모 클래스를 가리킬 때 사용하는 키워드이다. 주로 부모 클래스의 필드에 접근, 메소드를 호출할 때 사용한다.

부모 클래스에서 상속되지 않는 것

• 부모 클래스의 private 접근 제한을 갖는 필드 및 메소드는 자식이 물려받을 수 없다.
• 부모와 자식 클래스가 서로 다른 패키지에 있다면, 부모의 default 접근 제한을 갖는 필드 및 메소드도 자식이 물려받을 수 없다.

상속을 하더라도 자식 클래스가 부모의 모든 것들을 물려받는 것은 아니다. 필드나 메소드의 접근제어자가 public이거나 protected일 때만 상속이 가능하다.

인터페이스

인터페이스란?

자바에서 인터페이스는 클래스들이 필수로 구현해야 하는 추상 자료형이다. 쉽게 말하자면 객체의 사용방법을 가이드라인 하는 것이라고 생각하시면 이해가 쉽다. 자바의 인터페이스는 추상 메서드와 상수로만 이루어져 있다. 구현된 코드가 없기 때문에 당연히 인터페이스로 인스턴스도 사용할 수 없다.

인터페이스 특징

• 다중 상속 가능 인터페이스는 껍데기만 존재하여 클래스 상속 시 발생했던 모호함이 없다. 고로 다중 상속이 가능.

• 추상 메서드와 상수만 사용 가능 인터페이스에는 구현 소스를 생성할 수 없다. 고로 상수와 추상 메서드만 가질 수 있다.

• 생성자 사용 불가 인터페이스 객체가 아니므로 생성자를 사용하실 수 없다.

• 메서드 오버라이딩 필수 자식클래스는 부모 인터페이스의 추상 메서드를 모두 오버라이딩해야 한다.

인터페이스 사용 이유

• 추상 클래스를 통해 객체들 간의 네이밍을 통일할 수 있고 이로 인해 소스의 가독성과 유지보수가 향상
• 확장에는 열려있고 변경에는 닫혀있는 객체 간 결합도(코드 종속성)를 낮춘 유연한 방식의 개발이 가능

자바 인터페이스 사용법

자바에서 인터페이스를 선언할 때는 interface라는 키워드를 붙여서 만들면 된다. 단 이렇게 interface라는 키워드를 붙여 인터페이스로 만들게 되면 오직 implements라는 키워드를 통해 객체들을 구현하는 용도로만 사용이 가능하다. 또한 인터페이스에는 구체적인 대상을 생성할 수 없고 오로지 상수와 추상 메서드만 사용할 수 있다. 이 메서드는 추상 클래스에서 껍데기만 생성하고 상속하는 자식 클래스에서 오버라이딩하여 사용한다.

출처 https://coding-factory.tistory.com/865 https://coding-factory.tistory.com/867

문제

n × n의 크기의 대나무 숲이 있다. 욕심쟁이 판다는 어떤 지역에서 대나무를 먹기 시작한다. 그리고 그 곳의 대나무를 다 먹어 치우면 상, 하, 좌, 우 중 한 곳으로 이동을 한다. 그리고 또 그곳에서 대나무를 먹는다. 그런데 단 조건이 있다. 이 판다는 매우 욕심이 많아서 대나무를 먹고 자리를 옮기면 그 옮긴 지역에 그 전 지역보다 대나무가 많이 있어야 한다.

이 판다의 사육사는 이런 판다를 대나무 숲에 풀어 놓아야 하는데, 어떤 지점에 처음에 풀어 놓아야 하고, 어떤 곳으로 이동을 시켜야 판다가 최대한 많은 칸을 방문할 수 있는지 고민에 빠져 있다. 우리의 임무는 이 사육사를 도와주는 것이다. n × n 크기의 대나무 숲이 주어져 있을 때, 이 판다가 최대한 많은 칸을 이동하려면 어떤 경로를 통하여 움직여야 하는지 구하여라.

입력

첫째 줄에 대나무 숲의 크기 n(1 ≤ n ≤ 500)이 주어진다. 그리고 둘째 줄부터 n+1번째 줄까지 대나무 숲의 정보가 주어진다. 대나무 숲의 정보는 공백을 사이로 두고 각 지역의 대나무의 양이 정수 값으로 주어진다. 대나무의 양은 1,000,000보다 작거나 같은 자연수이다.

출력

첫째 줄에는 판다가 이동할 수 있는 칸의 수의 최댓값을 출력한다.

문제 해석

DP와 DFS를사용해 중복되는 부분을 배제하기 위해 DP를 이용해 메모이제이션 하면서 풀어야 한다.

dp에 저장되는 값은 다른 위치에서 현재 위치까지 이동할 수 있는 거리 중 최대값을 의미한다. 그러므로 이동하면서 계속 갱신해 주어야 한다.

즉 현재위치가 x, y이고 이동할 위치가 nx, ny라고 할 때

dp[x][y] = dp[nx][ny] + 1과 dp[x][y]중의 최댓값이 된다.

풀이

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class prob1937 {

    static int[] dx = {0, 1, 0, -1};
    static int[] dy = {-1, 0, 1, 0};
    static int max = 0;
    static int[][] map; //대나무 숲
    static int[][] dp;
    static int n;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        n = Integer.parseInt(br.readLine());
        map = new int[n][n];
        dp = new int[n][n];

        for (int i = 0; i < n; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 0; j < n; j++) {
                map[i][j] = Integer.parseInt(st.nextToken());
            }
        }

        int ans = 0;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                ans = Math.max(ans, DFS(i, j));
            }
        }
        System.out.println(ans);

    }

    public static int DFS(int x, int y) {
        // dp에 저장된 값이 있을 경우 그 값을 반환 (이미 갱신된 위치)
        if(dp[x][y] != 0) return dp[x][y];

        // 판다가 대나무 숲에서 최소한 1년은 살 수 있으므로
        // dp[x][y] = 1로 초기화 할 수 있음.
        dp[x][y] = 1;
        // 상하좌우 검사.
        for(int i = 0; i < 4; i++) {
            int nx = x + dx[i];
            int ny = y + dy[i];
            if(nx >= 0 && ny >= 0 && nx < n && ny < n) {
                // 현재 대나무 숲보다 더 많은 양의 대나무가 있는 경우
                if(map[nx][ny] > map[x][y]) {
                    // 상하좌우 중에서 가장 오랫동안 생존할 수 있는 기간을 계산
                    dp[x][y] = Math.max(dp[x][y],  DFS(nx, ny) + 1);
                }
            }
        }
        return dp[x][y];
    }
}

• 가장 짧은 경로를 찾는 알고리즘 (ex 길 찾기 문제)
• 문제를 그래프로 표현하고, 각 지점을 노드, 지점간 연결된 도로들은 간선이라 함.
• 최단 경로 알고리즘에는 그리디 알고리즘과 다이나믹 프로그래밍이 그대로 적용

1 : N (One-To-All)

한 지점에서 다른 모든 지점까지의 최단경로 구하기 (단일 시작점으로 부터 각 정점에 이르는 최단 경로)

• 다익스트라
  • 음의 가중치를 허용하지 않는 최단 경로
• 벨만 포드 (Bellman Ford)
  • 음의 가중치를 허용하는 최단 경로

N : N (All-To-All)

모든 지점에서 모든 지점까지의 최단경로 구하기 (모든 정점 쌍 사이의 최단경로를 모두 구하기)

• 플로이드 워셜 (Floyd Warshall)

다익스트라 알고리즘

그리디와 동적 계획법이 합쳐진 형태입니다. 그래프에서 특정 노드에서 출발하여 다른 모든 노드로 가는 각각의 최단 경로를 구해주는 알고리즘입니다. 단, 모든 링크의 가중치(길이)는 양의 정수 값이어야 합니다.

• 기능 : 출발 노드와 모든 노드 간의 최단 거리 탐색
• 특징 : 엣지는 모두 양수
• 시간 복잡도(노드 수:V, 에지 수: E) : O(ElogV)

특정 노드에서 다른 노드들의 최단 거리를 구하는 문제가 주어졌을 때 다익스트라 알고리즘을 사용하면 문제를 해결할 수 있습니다.

동작 방식

1. 인접 리스트로 그래프 구현하기
   • 인접 행렬도 가능하지만, 크기가 클 것을 대비해 인접 리스트로 구현하기
2. 최단 거리 배열 초기화하기
   • 출발 노드는 0, 이외의 노드는 무한대로 설정
3. 값이 가장 작은 노드 고르기
4. 최단 거리 배열 업데이트하기
   • 선택된 노드에 연결된 에지의 값을 바탕으로 다른 노드의 값 업데이트
   • 1단계에서 저장해 놓은 연결 리스트를 이용해 현재 선택된 노드의 엣지들을 탐색하고 업데이트
   • 연결 노드의 최단 거리는 두 값 중 더 작은 값으로 업데이트
   • Min(선택 노드의 최단 거리 배열의 값 + 엣지 가중치, 연결 노드의 최단 거리 배열의 값)
5. 과정 3~4를 반복해 최단 거리 배열 완성하기
   • 모든 노드가 처리될 때까지 과정 3~4를 반복
   • 과정 4에서 선택 노드가 될 때마다 다시 선택하지 않도록 방문 배열을 만들어 처리
   • 모든 노드가 선택될 때까지 반복하면 최단 거리 배열이 완성

다익스트라 알고리즘은 출발 노드와 그 외 노드간의 최단 거리를 구하는 알고리즘입니다. 엣지는 항상 양수여야 한다는 제약이 있습니다. 다익스트라는 출발 노드와 도착 노드간의 최단 거리를 구하는 알고리즘이 아니라, 출발 노드와 이외의 모든 노드 간의 최단 거리를 표현하는 알고리즘 입니다.

예시 문제

https://www.acmicpc.net/problem/1753

C++ 풀이

#include <stdio.h>
#include <vector>
#include <queue>
#define INF 987654321
using namespace std;

vector<pair<int,int> > node[20005];
priority_queue<pair<int,int>,vector<pair<int,int> >,greater<pair<int,int> > >pq;
int value[20005];

int main(){
    int n,e,k;
    int u,v,w;

    scanf("%d %d",&n,&e);
    scanf("%d",&k);

    for(int i=0;i<e;i++){
        scanf("%d %d %d",&u,&v,&w);
        node[u].push_back(make_pair(v,w));
    }

    for(int i=1;i<=n;i++)
        value[i] = INF;

    value[k] = 0;

    pq.push(make_pair(0,k));

    while(!pq.empty()){
        int x = pq.top().first;
        int U = pq.top().second;
        pq.pop();

        for(int i=0;i<node[U].size();i++){
            int V = node[U][i].first;
            int W = node[U][i].second;

            if(x+W<value[V]){
                value[V] = x+W;
                pq.push(make_pair(x+W,V));
            }
        }
    }

    for(int i=1;i<=n;i++)
        if(value[i]==INF) printf("INF\n");
        else printf("%d\n",value[i]);

    return 0;
}

Java 풀이

public class P1753_최단경로 {

    public static int V, E, K;
    public static int distance[];
    public static boolean visited[];
    public static ArrayList<Edge_1753> list[];
    public static PriorityQueue<Edge_1753> q = new PriorityQueue<Edge_1753>();

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        st = new StringTokenizer(br.readLine());
        V = Integer.parseInt(st.nextToken());
        E = Integer.parseInt(st.nextToken());
        K = Integer.parseInt(br.readLine());
        distance = new int[V + 1];
        visited = new boolean[V + 1];
        list = new ArrayList[V + 1];
        for (int i = 1; i <= V; i++) {
            list[i] = new ArrayList<Edge_1753>();
        }
        for (int i = 0; i <= V; i++) {
            distance[i] = Integer.MAX_VALUE;
        }
        for (int i = 0; i < E; i++) { // 가중치가 있는 인접 리스트 초기화
            st = new StringTokenizer(br.readLine());
            int u = Integer.parseInt(st.nextToken());
            int v = Integer.parseInt(st.nextToken());
            int w = Integer.parseInt(st.nextToken());
            list[u].add(new Edge_1753(v, w));
        }
        q.add(new Edge_1753(K, 0)); // K를 시작점으로 설정
        distance[K] = 0;
        while (!q.isEmpty()) {
            Edge_1753 current = q.poll();
            int c_v = current.vertex;
            if (visited[c_v]) {
                continue; // 기 방문 노드는 다시 큐에 넣지 않습니다.
            }
            visited[c_v] = true;
            for (int i = 0; i < list[c_v].size(); i++) {
                Edge_1753 tmp = list[c_v].get(i);
                int next = tmp.vertex;
                int value = tmp.value;
                if (distance[next] > distance[c_v] + value) { // 최소 거리로 업데이트
                    distance[next] = value + distance[c_v];
                    q.add(new Edge_1753(next, distance[next]));
                }
            }
        }
        for (int i = 1; i <= V; i++) { // 거리 배열 출력
            if (visited[i]) {
                System.out.println(distance[i]);
            } else {
                System.out.println("INF");
            }
        }
    }
}

class Edge_1753 implements Comparable<Edge_1753> {

    int vertex, value;

    Edge_1753(int vertex, int value) {
        this.vertex = vertex;
        this.value = value;
    }

    public int compareTo(Edge_1753 e) {
        if (this.value > e.value) {
            return 1;
        } else {
            return -1;
        }
    }
}

벨만 포드 알고리즘

• 기능 : 특정 출발 노드에서 다른 모든 노드까지의 최단 경로 탐색
• 특징 : 음수 가중치 엣지가 있어도 수행 가능, 전체 그래프에서 음수 사이클의 존재 여부를 판단할 수 있음
• 시간 복잡도(노드 수:V, 에지 수: E) : O(VE)

특징

• 음의 가중치를 가지는 간선도 가능하다.
• 음의 사이클의 존재 여부를 확인할 수 있다.
• 최단거리를 구하기 위해서 V-1번 E개의 모든 간선을 확인한다.
• 음의 사이클 존재 여부를 확인하기 위해서 한 번 더 E개의 간선을 확인한다.
• 총 연산횟수는 V*E이다. 따라서 시간복잡도는 O(VE)이다.
• V번째 모든 간선을 확인하였을 때 거리 배열이 갱신되었다면, 그래프 G는 음의 사이클을 가지는 그래프이다.
  • 그래프 모든 엣지에 대해 edge relaxation을 시작노드를 제외한 전체 노드수 만큼 반복 수행한 뒤, 마지막으로 그래프 모든 엣지에 대해 edge relaxation을 1번 수행해 준다. 이때 한번이라도 업데이트가 일어난다면 음의 사이클이 존재한다는 뜻이 되어서 결과를 구할 수 없다는 의미의 false를 반환하고 함수를 종료한다.

이러한 문제점을 해결하기 위해 나온 알고리즘이 벨만 포드 입니다. 기본적으로 다익스트라와 동일하지만 핵심 차이점은 간선의 가중치가 음일 때도 최소 비용을 구할 수 있습니다. 다만 시간복잡도가 늘어나기 때문에 가중치가 모두 양수일 경우 다익스트라를 사용하는 것이 좋습니다. 시간 복잡도가 늘어나는 이유는 그리디하게 최소 비용 경로를 찾아가는 다익스트라와 달리, 벨만 포드는 모든 경우의 수를 고려하는 동적 계획법이 사용되기 때문입니다.

그렇다면 모든 경우의 수를 어떻게 고려할까? 그 방법은 매 단계 마다 모든 간선을 전부 확인하는 것입니다. 다익스트라는 출발 노드에서만 연결된 노드를 반복적으로 탐색하며 다른 모든 노드까지의 최소 거리를 구했습니다. 하지만 벨만 포드는 모든 노드가 한번씩 출발점이 되어 다른 노드까지의 최소 비용을 구합니다.

동작 방식

1. 엣지 리스트로 그래프를 구현하고 최단 경로 배열 초기화하기
   • 벨만 포드 알고리즘은 엣지를 중심으로 동작하므로 그래프를 엣지 리스트로 표현
   • 최단 경로 배열은 출발 노드는 0, 나머지 노드는 무한대로 초기화
2. 모든 엣지를 확인해 정답 배열 업데이트하기
   • 최단 거리 배열에서 업데이트 반복 횟수는 노드 개수 -1 입니다.
   • 노드 개수가 N이고, 음수 사이클이 없을 때 특정 두 노드의 최단 거리를 구성할 수 있는 엣지의 최대 개수는 N - 1 이기 때문입니다.
   • 특정 엣지 E = (s,e,w) 에서 다음 조건을 만족하면 업데이트를 실행합니다.
   • D[s] != 무한대 이며 D[e] > D[s] + w 일 때 D[e] = D[s] + w 로 배열 업데이트
   • 음수 사이클이 없을 때 N - 1번 엣지 사용 횟수를 반복하면 출발 노드와 모든 노드 간의 최단 거리를 알려주는 배열 완성
3. 음수 사이클 유무 확인하기
   • 음수 사이클 유무를 확인하기 위해 모든 엣지를 한번씩 다시 사용해 업데이트 되는 노드가 발생하는지 확인
   • 만약 업데이트 되는 노드가 있다면 음수 사이클이 있다는 뜻 -> 2번에서 찾은 배열이 무의미하고 최단 거리를 찾을 수 없는 그래프라는 뜻

벨만 포드 알고리즘을 사용해 최단 거리를 구하는 문제보다 음수 사이클을 판별하는 문제가 더 빈번하게 출제됩니다. 따라서 마지막에 한 번 더 모든 엣지를 사용해 업데이트 되는 노드가 존재하는 지 확인해야 합니다.

예시 문제

https://www.acmicpc.net/problem/11657

import java.io.*;
import java.util.Arrays;
import java.util.StringTokenizer;

public class P11657_타임머신 {

    private static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    private static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
    static int N, M;
    static long distance[];
    static Edge edges[];

    public static void main(String[] args) throws IOException {
        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        edges = new Edge[M + 1];
        distance = new long[N + 1];
        Arrays.fill(distance, Integer.MAX_VALUE); // 최단거리 배열 초기화
        for (int i = 0; i < M; i++) { // 간선 리스트에 데이터 저장하기
            st = new StringTokenizer(br.readLine());
            int start = Integer.parseInt(st.nextToken());
            int end = Integer.parseInt(st.nextToken());
            int time = Integer.parseInt(st.nextToken());
            edges[i] = new Edge(start, end, time);
        }
        // 벨만포드 알고리즘 수행
        distance[1] = 0;
        for (int i = 1; i < N; i++) {  //N보다 하나 적은 수만큼 반복
            for (int j = 0; j < M; j++) {
                Edge edge = edges[j];
                // 더 작은 최단거리 가 있는 경우 갱신
                if (distance[edge.start] != Integer.MAX_VALUE
                    && distance[edge.end] > distance[edge.start] + edge.time) {
                    distance[edge.end] = distance[edge.start] + edge.time;
                }
            }
        }
        boolean mCycle = false;
        for (int i = 0; i < M; i++) { // 음수 cycle 확인
            Edge edge = edges[i];
            if (distance[edge.start] != Integer.MAX_VALUE
                && distance[edge.end] > distance[edge.start] + edge.time) {
                mCycle = true;
            }
        }
        if (!mCycle) { // 음의 cycle이 없는 경우
            for (int i = 2; i <= N; i++) {
                if (distance[i] == Integer.MAX_VALUE) {
                    System.out.println("-1");
                } else {
                    System.out.println(distance[i]);
                }
            }
        } else { // 음의 cycle이 있는 경우
            System.out.println("-1");
        }
    }
}

class Edge { // 간선리스트를 편하게 다루기 위해 클래스로 별도 구현

    int start, end, time;  // 시작점, 도착점, 걸리는 시간

    public Edge(int start, int end, int time) {
        this.start = start;
        this.end = end;
        this.time = time;
    }
}

플로이드 워셜 알고리즘

• 기능 : 모든 노드간에 최단 경로 탐색
• 특징 : 음수 가중치 엣지가 있어도 수행 가능, 동적 계획법의 원리를 이용해 알고리즘에 접근
• 시간 복잡도(노드 수: V) : O(V^3)

플로이드 워셜 알고리즘은 모든 노드 간의 최단거리를 구할 수 있습니디. 플로이드 워셜 알고리즘은 그래프 상에서 음의 가중치가 있더라도 최단 경로를 구할 수 있습니다. 하지만 음의 가중치와 별개로 음의 사이클이 존재한다면 벨만 포드 알고리즘을 사용해야 합니다.

플로이드 워셜 알고리즘은 모든 노드 간의 최단거리를 구하고 이 때, 점화식이 사용되기에 동적 계획법에 해당합니다. 동적 계획법에 해당하므로 최단 거리를 업데이트할 테이블이 필요합니다. 이 때 모든 노드간의 최단 거리이므로 2차원 배열이 사용됩니다. 특정 한 노드에서 출발하는 다익스트라가 1차원 배열을 사용하는 것과 차이점이 있습니다.

가장 핵심적인 원리는 A 노드에서 B 노드까지 최단 경로를 구했다고 가정했을 때, 최단 경로 위에 K 노드가 존재한다면 그것을 이루는 부분 경로 역시 최단 경로라는 것 입니다.

즉, 전체 경로의 최단 경로는 부분 경로의 최단 경로의 조합으로 이루어진다는 의미입니다. (즉, 정점 A와 정점 B 사이의 최단 경로는 A-B이거나 A-K-B 입니다. 만약 경유지(K)를 거친다면 최단 경로를 이루는 부분 경로 역시 최단 경로입니다. 다시 말해, 만약 A-B의 최단 경로가 A-K-B라면 A-K와 K-B도 각각 최단 경로입니다.) 다음과 같은 점화식을 도출할 수 있습니다.

D[S][E] = Min(D[S][E] , D[S][K] + D[K][E])

for k in range(1, V+1): # via
    graph[k][k] = 0 # 사이클 없으므로 자기 자신 0
    for i in range(1, V+1): # src
        for j in range(1, V+1): # dst
            graph[i][j] = min(graph[i][j], graph[i][k]+graph[k][j])

동작 방식

1. 배열을 선언하고 초기화하기
   • D[S][E] 는 노드 S에서 노드 E 까지의 최단 거리를 저장하는 배열이라 정의
   • S와 E의 값이 같은 칸은 0, 다른 칸은 무한대로 초기화 (S == E 는 자기 자신에게 가는 데 걸리는 최단 경로 값)
2. 최단 거리배열에 그래프 데이터 저장하기
   • 출발 노드는 S, 도착 노드는 E, 이 엣지의 가중치는 W라고 했을 때 D[S][E] = W 로 엣지의 정보를 배열에 입력 -> 인접 행렬로 표현
3. 점화식으로 배열 업데이트하기
   • 점화식을 3중 for문의 형태로 반복함녀서 배열의 값 업데이트

예시 문제

https://www.acmicpc.net/problem/11404

import java.io.*;
import java.util.StringTokenizer;

public class P11404_플로이드 {

    private static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    private static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
    static int N, M;
    static int distance[][];

    public static void main(String[] args) throws IOException {
        N = Integer.parseInt(br.readLine());
        M = Integer.parseInt(br.readLine());
        distance = new int[N + 1][N + 1];
        for (int i = 1; i <= N; i++) { // 인접 행렬 초기화
            for (int j = 1; j <= N; j++) {
                if (i == j) {
                    distance[i][j] = 0;
                } else {
                    distance[i][j] = 10000001; // 충분히 큰수로 저장
                }
            }
        }
        for (int i = 0; i < M; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            int s = Integer.parseInt(st.nextToken());
            int e = Integer.parseInt(st.nextToken());
            int v = Integer.parseInt(st.nextToken());
            if (distance[s][e] > v) {
                distance[s][e] = v;
            }
        }
        for (int k = 1; k <= N; k++) { // 플로이드 워셜 알고리즘 수행
            for (int i = 1; i <= N; i++) {
                for (int j = 1; j <= N; j++) {
                    if (distance[i][j] > distance[i][k] + distance[k][j]) {
                        distance[i][j] = distance[i][k] + distance[k][j];
                    }
                }
            }
        }
        for (int i = 1; i <= N; i++) {
            for (int j = 1; j <= N; j++) {
                if (distance[i][j] == 10000001) {
                    System.out.print("0 ");
                } else {
                    System.out.print(distance[i][j] + " ");
                }
            }
            System.out.println();
        }
    }
}

객체의 멤버들에게 접근 제한을 걸 수가 있는데 자바에서는 이를 접근 제한자라 한다.

public 접근 제한자

• 단어 뜻 그대로 외부 클래스가 자유롭게 사용할 수 있도록 한다.

protected 접근 제한자

• 같은 패키지 또는 자식 클래스에서 사용할 수 있도록 한다.

private 접근 제한자

• 단어 뜻 그대로 개인적인 것이라 외부에서 사용될 수 없도록 한다.

default

• 위 세 가지 접근 제한자가 적용되지 않으면 default 접근 제한을 가진다.
• 같은 패키지에 소속된 클래스에서만 사용할 수 있도록 한다.

클래스의 접근 제한

클래스를 선언할 때 해당 클래스를 같은 패키지 내에서만 사용할 것인지, 아니면 다른 패키지에서도 사용할 수 있도록 할 것인지 결정해야 한다. 클래스는 public, default 접근 제한을 가진다.

• default 접근 제한 클래스를 선언할 때 public을 생략했다면 클래스는 default 접근 제한을 가진다. 클래스가 default 접근 제한을 가지면 같은 패키지에서는 아무런 제한 없이 사용할 수 있지만 다른 패키지에서는 사용할 수 없도록 제한.

• public 접근 제한 클래스를 선언할 때 public 접근 제한자를 붙였다면 클래스는 public 접근 제한을 가진다. 클래스가 public 접근 제한을 가지면, 같은 패키지뿐만 아니라 다른 패키지에서도 아무런 제한 없이 사용할 수 있다. 클래스를 다른 개발자가 사용할 수 있도록 라이브러리 클래스로 개발한다면 반드시 public 접근 제한을 갖도록 해야 한다. 인터넷으로 배포되는 라이브러리 클래스도 모두 public 접근 제한을 가지고 있다.

생성자의 접근 제한

객체를 생성하기 위해서는 new 연산자로 생성자를 호출한다. 하지만 생성자를 어디에서나 호출할 수 있는 것은 아니다. 생성자가 어떤 접근 제한을 갖느냐에 따라 호출 가능 여부가 결정된다.

생성자는 public, protected, default, private 접근 제한을 가진다.

• public 접근 제한: public 접근 제한은 모든 패키지에서 아무런 제한 없이 생성자를 호출할 수 있도록 한다.

• protected 접근 제한: protected 접근 제한은 default 접근 제한과 마찬가지로 같은 패키지에 속하는 클래스에서 생성자를 호출할 수 있도록 한다. 차이점으로 다른 패키지에 속한 클래스가 해당 클래스의 자식(child) 클래스라면 생성자를 호출할 수 있다.

• default 접근 제한: default 접근 제한은 같은 패키지에서는 아무런 제한 없이 생성자를 호출할 수 있으나, 다른 패키지에서는 생성자를 호출할 수 없도록 한다.

• private 접근 제한: private 접근 제한은 동일한 패키지이건 다른 패키지이건 상관없이 생성자를 호출하지 못하도록 제한한다. 오로지 클래스 내부에서만 생성자를 호출할 수 있고 객체를 만들 수 있다.

static/final

static

static은 "고정된" 이라는 의미

• 객체 생성 없이 사용할 수 있는 필드와 메소드를 생성하고자 할 때 활용
• 공용 데이터에 해당하거나 인스턴스 필드를 포함하지 않는 메소드를 선언하고자 할 때 이용

final

final은 "최종적인" 이라는 의미 즉 해당 변수는 값이 저장되면 최종적인 값이 되므로, 수정이 불가능하다는 의미

• 주로 상수로 변수를 사용하기 위해 사용하거나 오버라이딩을 막기 위해 사용

static final

static + final = "고정된 + 최종적인"의 의미로, 상수를 선언하고자 할 때 사용된다.

• 클래스 자체에 존재하는 단 하나의 상수 (클래스자체로 존재하여 접근 가능하고 불변하다)
• 따라서 클래스의 선언과 동시에 반드시 초기화가 필요한 클래스 상수

자바 버전에는 여러가지 버전이 있지만, 그 중 많이 쓰이는 버전은 8,11,17 이다. JAVA 8 이상 이라는 문구를 많이 보았을 것이다. 이러한 이유는, 해당 버전들이 LTS 이기 때문이다.

LTS

Long Term Support는 출시 후 8년이라는 긴 기간을 보안 업데이트와 버그 수정을 지원하는 버전이라는 뜻이다.

버전별 차이

JAVA 8

Java 8 (was released on March 18, 2014)

• Oracle이 Sun Microsystems 인수 후 출시한 첫 번째 LTS 버전의 자바
• 32bit를 지원하는 마지막 공식 Java 버전
• Oracle사에서 지원하는 유료 버전인 Oracle JDK와 오픈소스 기반의 무료 버전인 Open JDK로 나뉨
• new Date and Time API(LocalDateTime 등)
• Lambda, Stream API
• PermGen Area 삭제
• Static Link JNI Library
• Unsigned Integer 계산
• Annotation on Java Types
• Interface Default Method
• Optional class
• Nashorn JavaScript engine 탑재

Lamda

int max(int a, int b) {
    return a > b ? a : b;
}
//람다식으로 변환
(a, b) -> a > b ? a : b;

'람다식(Lambda Expression)'이란 함수를 간단한 식으로 표현하는 방법을 말한다. 메서드의 이름과 반환값(return)이 생략된다는 점에서 '익명 함수(anonymous function)'라고도 불린다.

Stream API

List<String> lowercase = Arrays.asList("a", "b", "c", "d", "e");
lowercase.stream()
        .map(String::toUpperCase)
        .forEach(System.out::println);

Steam은 컬렉션의 저장 요소를 하나씩 순회하면서 처리할 수 있는 코드 패턴. 람다식을 지원한다는 점과 내부 반복자를 사용하기 때문에 병렬 처리가 쉽다는 특징이 있다.

interface default method

public interface TestInterface {
    void doSomething();
    default void doSomethingDefault() {
        System.out.println("doing something default");
    }
}

//implements the interface
public class TestClass implements TestInterface {
    @Override
    public void doSomething() {
        System.out.println("doing something");
    }
}

TestClass testClass = new TestClass();
testClass.doSomething();          // Output: "doing something"
testClass.doSomethingDefault();   // Output: "doing something default"

java 8 이전의 인터페이스는 메서드 정의만 할 수 있었고 구현은 할 수 없었다. 8 버전부터 default method라는 개념이 생기면서 구현 내용도 인터페이스에 포함시킬 수 있게 되었다.

Optional class

//create an optional that contains a value
Optional<String> optional = Optional.of("Hello, world!");
//check if a value is present
if (optional.isPresent()) {
    String value = optional.get();
    System.out.println(value);    // Output: "Hello, world!"
}

//create an empty optional
Optional<String> emptyOptional = Optional.empty();
//get a default value if the optional is empty
String value = emptyOptional.orElse("default value");
System.out.println(value);    // Output: "default value"

//throw exception
emptyOptional.orElseThrow(() -> new RuntimeException("throw Exception"));

Optional는 null이 올 수 있는 값을 감싸는 Wrapper 클래스로, 참조하더라도 NPE(Null Pointer Exception)가 발생하지 않도록 도와주는 역할을 한다. 따라서 예상치 못한 Null Pointer Exception이 발생될만한 상황에서도 예시와 같이 제공되는 메서드를 통해 간단하게 예외 처리를 할 수 있다.

JAVA 11

• Oracle JDK와 Open JDK 통합되고 Oracle JDK가 구독형 유료 모델로 전환
• 람다 지역 변수 사용 방법 변경
• Third Party JDK로의 이전 필요
• HTTP 클라이언트 표준화 기능
• 앱실론 가비지 컬렉터 (Epsilon GC)

JAVA 17

• 봉인 클래스(Seald Class) 정식 추가
• 패턴 매칭 프리뷰 단계
• Incubator (Foreign Function & Memory API)
• 애플 M1 및 이후 프로세서 탑재 제품군에 대한 정식 지원
• 의사난수 생성기를 통해 예측하기 어려운 난수를 생성하는 API 추가
• 컨텐츠 기반의 역직렬화 필터링
• Record Data Class 추가

Seald class

public sealed class Shape permits Circle, Square {
    // common fields and methods
}

public final class Circle extends Shape {
    // circle-specific fields and methods
}

public final class Square extends Shape {
    // square-specific fields and methods
}

17 버전에서 추가된 Seald Class, Interface는 상속하거나(extends), 구현(implements) 할 클래스를 지정해 두고, 해당 클래스들만 상속 또는 구현을 허용하는 키워드이다. 개발자는 seald 키워드를 통해 어떤 클래스가 해당 클래스를 상속 또는 구현하는지를 쉽게 알 수 있고, 또 제한할 수 있다.

그래서 무슨 버전을 써야할까?

'그래서 무슨 버전을 쓰는 것이 좋은가?'라고 한다면, 단순히 사용할 버전만 생각하는 것이 아니라 개발 환경과 여러 요소들이 모두 고려되어야 하는 문제이기 때문에 정답은 없다고 생각된다.

하지만 스프링 부트 3.0에서 java 17 이상을 사용해야 한다는 점과 java 8의 사용 비율이 줄어들고 있는 추세를 봤을 때, 11 버전 또는 17 버전을 사용하는 것에 큰 문제가 없다면 신규 프로젝트에서는 11 이상의 버전을 도입해 보는 것도 좋을 것 같다.

JVM은 Java Virtual Machine 을 줄인 것으로, 직역하면 '자바를 실행하기 위한 가상 기계' 라고 할 수 있습니다. 다시 말하자면, '자바를 실행하기 위한 가상 컴퓨터' 라고 이해하면 좋을 것 같습니다.

자바로 작성된 애플리케이션은 모두 이 가상 컴퓨터(JVM)에서만 실행되기 때문에, 자바 애플리케이션이 실행되기 위해서는 반드시 JVM이 필요합니다.

자바 코드를 컴파일하여 .class 바이트 코드로 만들면 이 코드가 자바 가상 머신 환경에서 실행됩니다. JVM은 자바 실행 환경 JRE(Java Runtime Environment)에 포함되어 있습니다. 현재 사용하는 컴퓨터의 운영체제에 맞는 자바 실행환경 (JRE)가 설치되어 있다면 자바 가상 머신이 설치되어 있다는 뜻입니다.

JVM의 필요성

JVM이 필요한 이유에 앞서, 자바의 중요한 장점 중 하나는 다음과 같습니다.

"Write once, run anywhere." (한 번 작성하면 어디서든 실행된다.)

즉, "Java는 어떠한 플랫폼에 영향을 받지 않는다." 라는 장점을 가지는데, 이를 가능케 하는 것이 JVM 입니다. JVM을 사용하면 하나의 바이트 코드(.class)로 모든 플랫폼에서 동작하도록 할 수 있습니다.

.class 파일은 바이트 코드라고 하는데 사람이 쓰는 자바 코드에서
컴퓨터가 읽는 기계어로의 중간 단계라고 생각하시면 됩니다.

일반 애플리케이션의 코드는 OS만 거치고 하드웨어로 전달되는데 비해 Java 애플리케이션은 JVM을 한 번 더 거치기 때문에, 그리고 하드웨어 맞게 완전히 컴파일된 상태가 아니고 실행 시에 해석(interpret)되기 때문에 속도가 느리다는 단점을 가지고 있습니다. 그러나 요즘엔 바이트코드를 하드웨어의 기계어로 바로 변환해주는 JIT컴파일러와 향상된 최적화 기술이 적용되어서 속도의 격차를 많이 줄이게 되었습니다.

일반 애플리케이션은 OS와 바로 맞붙어 있기 때문에 OS 종속적 입니다. 그래서 다른 OS에서 실행시키기 위해서는 애플리케이션을 그 OS에 맞게 변경해야 합니다.

반면에, Java 애플리케이션은 JVM하고만 상호작용을 하기 때문에 OS와 하드웨어 독립적이라 다른 OS에서도 프로그램의 변경없이 실행이 가능합니다.

단, JVM은 OS에 종속적이기 때문에 해당 OS에서 실행가능한 JVM이 필요합니다.

JVM의 작동 원리

1. 클래스 로더(Class Loader)
2. 실행 엔진(Execution Engine)
   • 인터프리터(Interpreter)
   • JIT 컴파일러(Just-in-Time)
   • 가비지 콜렉터(Garbage collector)
3. 런타임 데이터 영역 (Runtime Data Area)

2. JRE (Java Runtime Environment)

JRE는 자바 실행 환경(Java Runtime Environment)의 약자로 자바로 만들어진 프로그램을 실행시키는데 필요한 라이브러리들과 각종 API, 그리고 자바 가상 머신 (JVM)이 포함되어 있습니다. JRE는 자바로 "개발(쓰기)은 안되고 실행(읽기)만 된다"라고 생각하면 될 것 같습니다.

3. JDK (Java Development Kit)

JDK는 자바 개발키트(Java Development Kit)의 약자로 이름 그대로 개발자들이 자바로 개발하는 데 사용됩니다. JDK안에는 개발 시 필요한 라이브러리들과 javac(자바 컴파일러), javadoc 등의 개발 도구들을 포함되어 있고 개발을 하려면 당연히 실행도 시켜줘야 하기 때문에 JRE (Java Runtime Environment)도 함께 포함되어 있습니다. 즉, JDK는 프로그램을 생성, 실행, 컴파일 할 수 있습니다.

정리하자면 Java로 프로그램을 직접 개발하려면 JDK가 필요하고 Java로 만들어진 프로그램을 실행시키려면 JRE가 필요합니다.

참고 링크 1

문제

정수 X에 사용할 수 있는 연산은 다음과 같이 세 가지 이다.

1. X가 3으로 나누어 떨어지면, 3으로 나눈다.
2. X가 2로 나누어 떨어지면, 2로 나눈다.
3. 1을 뺀다.

정수 N이 주어졌을 때, 위와 같은 연산 세 개를 적절히 사용해서 1을 만들려고 한다. 연산을 사용하는 횟수의 최솟값을 출력하시오.

입력

첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 자연수 N이 주어진다.

출력

첫째 줄에 연산을 하는 횟수의 최솟값을 출력한다.

둘째 줄에는 N을 1로 만드는 방법에 포함되어 있는 수를 공백으로 구분해서 순서대로 출력한다. 정답이 여러 가지인 경우에는 아무거나 출력한다.

문제 해석

dp[i] = min(dp[i / 3], dp[i / 2], dp[i - 1]) 을 점화식으로 세우고, bottom - up 방식으로 해결한다. DP를 이용해서 최솟값을 구하고, before 배열을 이용해 그 순간의 선택들을 저장하여 역추적할 수 있도록 한다.

dp배열을 보면 해당 숫자까지 오는데 횟수와, 해당 숫자가 2 또는 3으로 나뉠 경우에 나뉜 index의 횟수에서 + 1을 비교하고, 그중 작은 수를 해당 dp배열의 index에 저장한다. 그래서 dp[N]은 N까지 도달하는데 최소 횟수를 저장하게 된다.

before 배열의 값은 그 전의 거쳤던 경로(index)를 나타나게 된다. 예로 10을 생각해보자.

처음에 10을 str에 저장한다.

before[10] = 9이다. 그래서 이것은 전에 갔었던 곳의 index를 가리킨다. 그 index의 value는 또 그 전의 index를 나타낸다.

지금은 str에 10 9가 저장

before[9] = 3

str = 10 9 3

before[3] = 1

str = 10 9 3 1

before[1] = 0으로 반복문을 종료하게 된다.

풀이

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class prob12852 {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());

        int[] dp = new int[N + 1]; //최소 횟수 저장
        int[] before = new int[N + 1]; //최소 경로 저장(역 추적)
        String str = "";

        dp[1] = 0;
        for (int i = 2; i <= N; i++) {

            dp[i] = dp[i - 1] + 1;
            before[i] = i - 1;

            if (i % 3 == 0 && dp[i / 3] + 1 < dp[i]) {
                dp[i] = dp[i / 3] + 1;
                before[i] = i / 3;
            }
            if (i % 2 == 0 && dp[i / 2] + 1 < dp[i]) {
                dp[i] = dp[i / 2] + 1;
                before[i] = i / 2;
            }
        }
        System.out.println(dp[N]);

        while (N > 0) {
            str += N + " ";
            N = before[N];
        }
        System.out.print(str);
    }
}

문제

세계적인 도둑 상덕이는 보석점을 털기로 결심했다.

상덕이가 털 보석점에는 보석이 총 N개 있다. 각 보석은 무게 Mi와 가격 Vi를 가지고 있다. 상덕이는 가방을 K개 가지고 있고, 각 가방에 담을 수 있는 최대 무게는 Ci이다. 가방에는 최대 한 개의 보석만 넣을 수 있다.

상덕이가 훔칠 수 있는 보석의 최대 가격을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 N과 K가 주어진다. (1 ≤ N, K ≤ 300,000)

다음 N개 줄에는 각 보석의 정보 Mi와 Vi가 주어진다. (0 ≤ Mi, Vi ≤ 1,000,000)

다음 K개 줄에는 가방에 담을 수 있는 최대 무게 Ci가 주어진다. (1 ≤ Ci ≤ 100,000,000)

모든 숫자는 양의 정수이다.

출력

첫째 줄에 상덕이가 훔칠 수 있는 보석 가격의 합의 최댓값을 출력한다.

문제 해석

1. 보석을 arraylist로 입력받은 후 무게 순서대로 오름차순 정렬한다.
2. 가방에 담을 수 있는 최대 무게를 입력 받은 후 오름차순 정렬한다.
3. 가격 순서대로 내림차순 정렬을 하는 우선순위 큐를 생성한다.
4. 현재 가방이 담을 수 있는 최대 무게보다 작거나 같은 무게를 가진 보석을 우선순위 큐에 담아준다.
5. 우선순위 큐의 제일 첫 번째 값(가장 가격이 비싼 보석)을 꺼내어 더해준다.
6. 4 ~ 5를 반복해주면 된다.

풀이

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.PriorityQueue;
import java.util.StringTokenizer;

class Gem {

    int m;
    int v;

    Gem(int m, int v) {
        this.m = m;
        this.v = v;
    }
}

public class prob1202 {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        int N = Integer.parseInt(st.nextToken());
        int K = Integer.parseInt(st.nextToken());
        ArrayList<Gem> list = new ArrayList<>();
        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());
            int m = Integer.parseInt(st.nextToken());
            int v = Integer.parseInt(st.nextToken());
            list.add(new Gem(m, v));
        }
        Collections.sort(list, ((o1, o2) -> o1.m - o2.m)); //무게 순서대로 오름차순 정렬
        int[] bags = new int[K];
        for (int i = 0; i < K; i++) {
            bags[i] = Integer.parseInt(br.readLine()); //배낭 무게 입력
        }
        Arrays.sort(bags); //배낭 무게 오름차순 정렬

        PriorityQueue<Gem> pq = new PriorityQueue<>((o1, o2) -> o2.v - o1.v); //가격 순서대로 내림차순 정렬
        long total = 0;
        int idx = 0;
        for (int i = 0; i < K; i++) {
            //현재 가방이 담을 수 있는 최대 무게보다 작거나 같은 무게를 가진 보석을 우선순위 큐에 담아준다.
            while (idx < N && list.get(idx).m <= bags[i]) {
                Gem current = list.get(idx++);
                pq.add(new Gem(current.m, current.v));
            }
            // 우선순위 큐에 있는 요소를 하나 빼서 가방에 넣음.
            // 이 때, 우선순위 큐는 내림차순 정렬이 되어있으므로
            // 첫 번째 요소는 가장 가격이 비싼 보석을 의미함.
            if (!pq.isEmpty()) {
                total += pq.poll().v;
            }
        }
        System.out.println(total);
        br.close();
    }

}

세준이는 크기가 N×N인 배열 A를 만들었다. 배열에 들어있는 수 A[i][j] = i×j 이다. 이 수를 일차원 배열 B에 넣으면 B의 크기는 N×N이 된다. B를 오름차순 정렬했을 때, B[k]를 구해보자.

배열 A와 B의 인덱스는 1부터 시작한다.

입력

첫째 줄에 배열의 크기 N이 주어진다. N은 105보다 작거나 같은 자연수이다. 둘째 줄에 k가 주어진다. k는 min(109, N2)보다 작거나 같은 자연수이다.

출력

B[k]를 출력한다.

문제 해석

풀이

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;

public class prob1300 {

    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        int K = Integer.parseInt(br.readLine());

        //B[k] = x 라 하자.
        // x는 left <= x <= right 의 범위를 갖는다. x 의 범위는 K까지 이다.
        long left = 1;
        long right = K;

        // lower-bound
        while(left < right) {

            long mid = (left + right) / 2;    // 임의의 x(mid)를 중간 값으로 잡는다.
            long count = 0;

            /*
             *  임의의 x에 대해 i번 째 행을 나눔으로써 x보다 작거나 같은 원소의 개수
             *  누적 합을 구한다.
             *  이 때 각 행의 원소의 개수가 N(열 개수)를 초과하지 않는 선에서 합해주어야 한다.
             *  ex) X가 8이 된다면, 1단에서 8 / 1 은 8이 된다. 하지만 1단에서는 최대 3개 이므로 불가능하다.
             */
            for(int i = 1; i <= N; i++) {
                count += Math.min(mid / i, N);
            }

            // count가 많다는 것은 임의의 x(mid)보다 작은 수가 B[K]보다 많다는 뜻
            if(K <= count) {
                right = mid;
            }
            else {
                left = mid + 1;
            }
        }

        System.out.println(left);
    }
}

2007년 KOI에 N명의 학생들이 참가하였다. 경시일 전날인 예비소집일에, 모든 학생들은 자신이 N명 중에서 몇 등을 할 것인지 예상 등수를 적어서 제출하도록 하였다.

KOI 담당조교로 참가한 김진영 조교는 실수로 모든 학생의 프로그램을 날려 버렸다. 1등부터 N등까지 동석차 없이 등수를 매겨야 하는 김 조교는, 어쩔 수 없이 각 사람이 제출한 예상 등수를 바탕으로 임의로 등수를 매기기로 했다.

자신의 등수를 A등으로 예상하였는데 실제 등수가 B등이 될 경우, 이 사람의 불만도는 A와 B의 차이 (|A - B|)로 수치화할 수 있다. 당신은 N명의 사람들의 불만도의 총 합을 최소로 하면서, 학생들의 등수를 매기려고 한다.

각 사람의 예상 등수가 주어졌을 때, 김 조교를 도와 이러한 불만도의 합을 최소로 하는 프로그램을 작성하시오.

입력

첫째 줄에 자연수 N이 주어진다. (1 ≤ N ≤ 500,000) 둘째 줄부터 N개의 줄에 걸쳐 각 사람의 예상 등수가 순서대로 주어진다. 예상 등수는 500,000 이하의 자연수이다.

출력

첫째 줄에 불만도의 합을 최소로 할 때, 그 불만도를 출력한다.

문제 해석

불만도의 합이 최소가 되기 위해서는, 예상한 등수와 실제 등수가 최솟값이 되도록 정해주면 된다. 예상 순위가 높은 사람은 실제로도 높은 순위에 위치시켜야 한다. 따라서 예상 등수를 오름차순으로 정렬한 뒤, 순차적으로 1등부터 실제 등수를 부여할 때 불만도의 합이 최소가 된다.

현재 주어진 예상 등수를 바로 오름차순으로 정렬한다. 그리고 첫번째 배열부터 1등이므로, 해당 등수와의 차의 절댓값을 sum에 저장한다.

불만도의 자료형을 Long 으로 선언해야한다 !

• 문제에서 N의 범위가 500,000 인데, 만약 모든 학생이 자신의 등수를 1로 예상할경우, |1-500,000| x 500,500 이 되어서 int의 범위를 벗어난다.

풀이

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;

public class prob2012 {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        int[] arr = new int[N];

        for (int i = 0; i < N; i++) {
            arr[i] = Integer.parseInt(br.readLine());
        }
        //오름차순 정렬
        Arrays.sort(arr);

        //불만도 합
        long sum = 0;
        for (int i = 0; i < N; i++) {
            sum += Math.abs(arr[i] - (i + 1));
        }
        System.out.println(sum);
    }
}

문제

평소에 질문을 잘 받아주기로 유명한 중앙대학교의 JH 교수님은 학생들로부터 재귀함수가 무엇인지에 대하여 많은 질문을 받아왔다.

매번 질문을 잘 받아주셨던 JH 교수님이지만 그는 중앙대학교가 자신과 맞는가에 대한 고민을 항상 해왔다.

중앙대학교와 자신의 길이 맞지 않다고 생각한 JH 교수님은 결국 중앙대학교를 떠나기로 결정하였다.

떠나기 전까지도 제자들을 생각하셨던 JH 교수님은 재귀함수가 무엇인지 물어보는 학생들을 위한 작은 선물로 자동 응답 챗봇을 준비하기로 했다.

JH 교수님이 만들 챗봇의 응답을 출력하는 프로그램을 만들어보자.

입력

교수님이 출력을 원하는 재귀 횟수 N(1 ≤ N ≤ 50)이 주어진다.

출력

출력 예시를 보고 재귀 횟수에 따른 챗봇의 응답을 출력한다.

문제 해석

간단한 문제다.

입력으로 재귀 횟수를 입력한다.

재귀 횟수가 0이 되었을 때, 최종 답을 출력하도록 한다.

String line 이라는 변수를 따로 선언하여, 재귀를 호출할 때마다 StrinBuilder 의 값을 String 으로 변환하여 line 에 따로 저장하도록 한다. 그래야 해당 재귀가 끝났을 때 기존의 _ _ _ _ 를 출력할 수 있다.(단계별로 구분이 되도록)

그 외에는 같은 부분을 계속해서 출력하도록 하며, StrinBuilder sb에 _ _ _ _ 를 계속해서 붙여가며 재귀함수를 호출한다. 재귀가 깊어질 때마다 _ _ _ _ 가 단계별로 구분이 되도록 한다.

재귀함수 호출에서 인자로 n-1 을 주며 0에 도달 했을 때 종료하도록 한다.

풀이

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class prob17478 {

    static int n;
    static StringBuilder sb = new StringBuilder();

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        n = Integer.parseInt(br.readLine());
        System.out.println("어느 한 컴퓨터공학과 학생이 유명한 교수님을 찾아가 물었다.");
        func(n);
    }

    static void func(int n) {
        //따로 저장해야함.
        //두가지 방법이 있다!
        //String line = String.valueOf(sb);
        String line = sb.toString();
        System.out.println(line + "\"재귀함수가 뭔가요?\"");
        if (n == 0) {
            System.out.println(line + "\"재귀함수는 자기 자신을 호출하는 함수라네\"");
            System.out.println(line + "라고 답변하였지.");
            return;
        }
        System.out.println(line + "\"잘 들어보게. 옛날옛날 한 산 꼭대기에 이세상 모든 지식을 통달한 선인이 있었어.");
        System.out.println(line + "마을 사람들은 모두 그 선인에게 수많은 질문을 했고, 모두 지혜롭게 대답해 주었지.");
        System.out.println(line + "그의 답은 대부분 옳았다고 하네. 그런데 어느 날, 그 선인에게 한 선비가 찾아와서 물었어.\"");
        sb.append("____");
        func(n - 1);
        System.out.println(line + "라고 답변하였지.");
    }
}

• 알고리즘이나 함수가 수행 도중에 자기 자신을 다시 호출하여 문제를 해결하는 기법
• 정의자체가 순환적으로 되어 있는 경우에 적합한 방법
  • 같은 코드를 반복적으로 사용해야할 때에, 유용하게 사용 -> 보다 간단하게 문제 해결
• 유의점 : Break Point
  • 계속해서 반복호출하다보면 스택오버플로우(Stack Overflow) 오류가 발생할 수 있다. 용량은 한정되어있는데, 계속해서 호출하고 리턴하지 않으니 용량을 많이 차지하고 그러다보니 일어나는 것이라고 생각하면 되겠다. (사탕을 비닐에 넣는데, 계속해서 사탕을 넣기만하면 비닐이 터져버리는 것과 같다고 생각하면 된다.)
  • 함수가 멈추지 않고 무한대로 실행되는 것을 방지하기 위해 종료 조건을 반드시 명시 해주도록 한다.
• 팩토리얼, 피보나치 수열, 하노이의 탑과 같은 문제에서 이용

재귀함수의 특성

1. 재귀의 호출은 같은 문제 내에서 더 범위가 작은 값, 즉, 하위 문제에 대해 이루어져야 한다.
2. 재귀함수 호출은 더 이상 반복되지 않는 base case에 도달해야 한다.

Base Condition (종료 조건)

재귀 함수는 특정 입력에 대해서 자기 자신을 호출하지 않고 종료해야 한다. 또한 모든 입력은 base condition 으로 수렴해야만 한다. 이를 지키지 않으면 무한루프에 빠져 에러가 발생한다.

함수의 명확한 정의

• 함수의 인자로 어떤 것을 받을 것인지
• 어디까지 계산하고 자기 자신에게 넘겨줄 것인지

재귀함수와 반복문

모든 재귀함수는 재귀구조 없이 반복문 만으로 동일 동작을 수행하는 함수를 구현할 수 있다. 재귀를 적절하게 잘 사용하면 코드가 간결해진다는 장점이 있지만, 메모리와 시간적 측면에서 어느정도 손해를 보게 된다. 따라서 반복문으로도 간단하게 해결이 가능한 문제라면 반복문을 사용해 구현하고, 반복문 만으로는 너무 코드가 복잡해질 것 같다면 재귀 구조를 이용하는 것이 좋다.

재귀의 장점

• 직관적이며 간단하게 구현할 수 있다.
• DFS, 백트래킹, 분할정복과 같은 알고리즘에 사용되기도 하여 기초가 되는 개념
• 변수 사용을 줄여준다.

재귀의 단점

• 재귀함수의 종료 조건을 잘 설정하지 않으면 재귀함수를 빠져나오지 못하게 되어 무한루프에 빠질 수 있다.
• 재귀 호출의 깊이가 너무 깊어지면 너무 많은 메모리를 사용하게 된다. 즉, 수행시간이 길어질 수 있다.
• 불필요한 반복 연산을 하게 될 가능성이 있다.
• 시간 복잡도가 반복문에 비해 계산하기 어렵다.

위와 같은 단점으로 인해 입력값이 정말 많은 알고리즘 문제를 재귀함수로 푸는 것은 매우 좋지 않다. 정지 조건을 아무리 잘 잡았다고 해도 무조건 시간초과가 걸린다.

요즘 코딩테스트에서는 어느 정도 난이도가 있으면 입력값이 100,000으로 주어지는 경우가 대부분이다. 이 데이터를 재귀함수로 다룬다고 생각해보면 매우 까다로울 것이다. 특히나 코드 효율성을 중요시하는 요즘 코테에서는 잘 안맞는 경우가 많을수도 있을 것이라 생각된다.

즉 문제를 풀기 전에 입력되는 값으로부터 시간복잡도를 미리 예상을 하고 알맞은 알고리즘을 생각하여 코드를 작성해야 하는 경우에 꼭 재귀함수를 사용해야 하는가?에 대해서 고민해보아야 한다.

우리가 사용할 수 있는 컴퓨터 자원은 한정되어 있기 때문에, 이를 고려한 코드가 중요하다고 생각된다.

재귀 알고리즘의 구조

• 순환 알고리즘은 다음과 같은 부분들을 포함한다.
  • 순환 호출을 하는 부분
  • 순환 호출을 멈추는 부분

• 만약 순환 호출을 멈추는 부분이 없다면?
  • 시스템 오류가 발생할 때까지 무한정 호출하게 된다.

int factorial(int n)
{
    printf("factorial(%d)\n",n);
    // if( n == 1 ) return 1;
    // else
    return (n * factorial(n-1) );
}

재귀 함수 예시

HelloWorld 출력 예시

public class Main {
    public static void main(String[] args)  {
        HelloWorld(5); // HelloWorld 출력 메서드 호출
    }

    // HelloWorld 출력 메서드 선언
    public static void HelloWorld(int n)
    {
        // n이 0인 경우 return
        if(n == 0)
            return;

        System.out.println("HelloWorld"); // HelloWorld 출력
        HelloWorld(n-1); // 재귀함수 시작
    }
}

팩토리얼 함수 예시

public class Main {

    public static void main(String[] args) {

        int result = factorial(3);
        System.out.println(result);
    }

    public static int factorial (int num) {
        if (num == 1)
            return 1;

        return num * factorial ( num - 1 );
    }
}

재귀 호출 순서

• 팩토리얼 함수의 호출 순서 factorial(3) = 3 * factorial(2) = 3 * 2 * factorial(1) = 3 * 2 * 1 = 3 * 2 = 6

재귀 <-> 반복

• 재귀(Recursion) : 순환 호출 이용
  • 순환적인 문제에서는 자연스러운 방법
  • 함수 호출의 오버헤드
• 반복(Iteration) : for 나 while 을 이용한 반복
  • 수행속도가 빠르다.
  • 순환적인 문제에서는 프로그램 작성이 아주 어려울 수도 있다.
• 대부분의 재귀는 반복으로 바꾸어 작성할 수 있음

재귀(Recursion)

1. 기본 경우에 도달하면 종료한다.
2. 각 재귀 호출은 스택 프레임(즉, 메모리) 에 부가 공간을 필요로 한다.
3. 무한 재귀에 들어가게 되면 메모리 용량을 초과해서 스택 오버플로우를 초래하게 된다.
4. 어떤 문제들의 해답은 재귀적인 수식으로 만들기 쉽다.

반복(Iteration)

1. 조건이 거짓일 때 종료한다.
2. 각 반복이 부가 공간을 필요로 하지 않는다.
3. 무한 루프는 추가 메모리가 필요하지 않으므로 무한히 반복된다.
4. 반복적 해법은 재귀적 해법에 비해 간단하지 않을 때가 있다.

ex) 팩토리얼의 반복적 구현

int factorialIter( int n )
{
    int result=1;
    for( int k=n ; k>0 ; k-- )
        result = result * k;
    return result;
}

분할 정복 (divide and conquer)

분할 정복(Divide and Conquer)은 재귀 알고리즘의 일종으로, 큰 문제를 작은 부분 문제로 분할하고, 각 부분 문제를 독립적으로 해결한 후 그 결과를 결합하여 원래 문제의 해답을 구하는 방법이다. 분할 정복 방식이 하위 문제를 재귀적으로 해결하기 때문에 하위 문제 각각은 원래 문제보다 범위가 작아야 하며 하위 문제는 각 문제마다 탈출 조건이 존재해야 한다.

분할 정복 알고리즘은 일반적으로 세 가지 단계로 구성된다.

분할(Divide): 주어진 문제를 더 작은 부분 문제로 분할한다. 이 단계에서는 주로 문제를 반으로 나누는 방식으로 분할을 수행한다. 분할된 부분 문제는 독립적으로 해결될 수 있어야 한다.

정복(Conquer): 각각의 작은 부분 문제를 재귀적으로 해결한다. 이 단계에서는 분할된 부분 문제를 재귀적으로 호출하여 해결한다. 작은 부분 문제가 충분히 작아서 쉽게 해결될 수 있는 경우에는 재귀 호출 없이 직접 해결할 수도 있다.

결합(Combine): 작은 부분 문제의 해답을 결합하여 원래 문제의 해답을 구한다. 이 단계에서는 각 부분 문제의 해답을 결합하여 전체 문제의 해답을 얻는다.

분할 정복은 주로 문제를 재귀적으로 분할하고 해결하는 방식이므로, 재귀 알고리즘과 밀접한 관련이 있다. 문제를 더 작은 부분 문제로 분할하여 각각을 해결함으로써 전체 문제를 해결하는 효과적인 방법이다. 분할 정복은 병합 정렬, 퀵 정렬, 이진 검색 등 여러 알고리즘에서 사용되며, 문제를 효율적으로 해결하는 데에 큰 도움을 준다.

분할 정복에 이용되는 문제

• 정렬 (퀵 정렬, 병합 정렬)
• 이진 탐색 (Binary Search)

분할정복과 동적 프로그래밍(Dynamic Programming)의 차이점

분할 정복과 동적 프로그래밍은 주어진 문제를 작게 쪼개서 하위 문제로 해결하고 연계적으로 큰 문제를 해결한다는 점은 같다.

차이점은, 분할 정복은 분할된 하위 문제가 동일하게 중복이 일어나지 않는 경우에 쓰며, 동일한 중복이 일어나면 동적 프로그래밍을 쓴다는 것이다. 아래와 같은 몇개의 차이점이 있다.

• 문제의 접근 방식: 분할 정복은 주로 문제를 작은 부분 문제로 분할하고 각각을 독립적으로 해결한 후, 그 결과를 결합하여 원래 문제의 해답을 구하는 방식입니다. 동적 프로그래밍은 큰 문제를 작은 하위 문제로 나누지 않고, 하위 문제의 해답을 저장하고 재사용하여 최적의 해답을 구하는 방식입니다.

• 하위 문제의 중복: 분할 정복에서는 하위 문제가 서로 중복되지 않습니다. 즉, 동일한 하위 문제가 반복해서 해결되지 않습니다. 반면에 동적 프로그래밍에서는 하위 문제가 중복될 수 있으며, 중복되는 하위 문제의 해답을 저장하고 재사용합니다.

• 하위 문제의 종속성: 분할 정복에서는 하위 문제들이 독립적으로 해결되며, 하위 문제의 해답이 다른 하위 문제의 해답에 영향을 주지 않습니다. 하지만 동적 프로그래밍에서는 하위 문제들이 종속적이며, 한 하위 문제의 해답이 다른 하위 문제의 해결에 영향을 줄 수 있습니다.

• 최적 부분 구조: 동적 프로그래밍은 최적 부분 구조(Optimal Substructure)를 가지는 문제에서 사용됩니다. 최적 부분 구조란 큰 문제의 최적 해답이 작은 부분 문제의 최적 해답으로부터 구해질 수 있는 성질을 말합니다. 분할 정복은 최적 부분 구조를 가지지 않는 문제에도 적용될 수 있습니다.

주어진 문제가 최적 부분 구조를 가지고 있고, 하위 문제들이 중복되는 경우에는 동적 프로그래밍을 사용하는 것이 효과적입니다. 반면에 문제를 작은 부분 문제로 분할하고, 하위 문제들이 독립적이며 중복되지 않는 경우에는 분할 정복을 사용하는 것이 적합합니다.

문제

N개의 수로 이루어진 수열 A1, A2, ..., AN이 주어진다. 또, 수와 수 사이에 끼워넣을 수 있는 N-1개의 연산자가 주어진다. 연산자는 덧셈(+), 뺄셈(-), 곱셈(×), 나눗셈(÷)으로만 이루어져 있다.

우리는 수와 수 사이에 연산자를 하나씩 넣어서, 수식을 하나 만들 수 있다. 이때, 주어진 수의 순서를 바꾸면 안 된다.

예를 들어, 6개의 수로 이루어진 수열이 1, 2, 3, 4, 5, 6이고, 주어진 연산자가 덧셈(+) 2개, 뺄셈(-) 1개, 곱셈(×) 1개, 나눗셈(÷) 1개인 경우에는 총 60가지의 식을 만들 수 있다. 예를 들어, 아래와 같은 식을 만들 수 있다.

1+2+3-4×5÷6 1÷2+3+4-5×6 1+2÷3×4-5+6 1÷2×3-4+5+6 식의 계산은 연산자 우선 순위를 무시하고 앞에서부터 진행해야 한다. 또, 나눗셈은 정수 나눗셈으로 몫만 취한다. 음수를 양수로 나눌 때는 C++14의 기준을 따른다. 즉, 양수로 바꾼 뒤 몫을 취하고, 그 몫을 음수로 바꾼 것과 같다. 이에 따라서, 위의 식 4개의 결과를 계산해보면 아래와 같다.

1+2+3-4×5÷6 = 1 1÷2+3+4-5×6 = 12 1+2÷3×4-5+6 = 5 1÷2×3-4+5+6 = 7 N개의 수와 N-1개의 연산자가 주어졌을 때, 만들 수 있는 식의 결과가 최대인 것과 최소인 것을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 수의 개수 N(2 ≤ N ≤ 11)가 주어진다. 둘째 줄에는 A1, A2, ..., AN이 주어진다. (1 ≤ Ai ≤ 100) 셋째 줄에는 합이 N-1인 4개의 정수가 주어지는데, 차례대로 덧셈(+)의 개수, 뺄셈(-)의 개수, 곱셈(×)의 개수, 나눗셈(÷)의 개수이다.

출력

첫째 줄에 만들 수 있는 식의 결과의 최댓값을, 둘째 줄에는 최솟값을 출력한다. 연산자를 어떻게 끼워넣어도 항상 -10억보다 크거나 같고, 10억보다 작거나 같은 결과가 나오는 입력만 주어진다. 또한, 앞에서부터 계산했을 때, 중간에 계산되는 식의 결과도 항상 -10억보다 크거나 같고, 10억보다 작거나 같다.

문제 해석

이 문제는 백트래킹 문제이다. 완전 탐색을 통해 모든 연산자의 경우의 수를 알아보아야한다.

전체적인 흐름은 수의 개수 n, 수 배열 arr[] , 그리고 연산자의 개수 operator[] 를 입력 받는다.(이때 연산자는 4개이다)

입력받은 뒤, dfs 함수에 인자로 (arr[0] , 1) 을 넘겨준다. 즉, 첫번째 수(값)과 그 다음 값을 위한 index를 넘긴다. 이 때 index는 인덱스이자 깊이를 의미한다.

dfs 함수에서는, 먼저 인덱스(깊이)가 n과 같아지면(마지막 인덱스에서 재귀호출 실행하면 여기서 걸림) 주어진 숫자를 다 사용했다는 뜻으로, 더 이상 for문에 들어갈 이유가 없으므로 최대 최소를 찾는다.

for문에서는 연산자 네개를 통해 탐색한다. 연산자 개수가 1개 이상인 경우(존재하는 경우)에만 작동하도록 한다. 먼저 해당 연산자를 1 감소하고, 각 case에 대해 계속해서 계산한 값과 index + 1을 인자로 넘기며 재귀호출을 한다. 재귀 호출이 끝나면, 해당 연산자 개수를 복구한다. 예를 들어, + * 의 조합뿐만 아니라, * + 의 조합도 있기 때문이다.

이 부분은 두번째 입력 예시를 통해 설명하겠다.

3 3 4 5 1 0 1 0

를 입력 받는다. 먼저 처음 인자로 3과 1을 넘긴다. (arr[0] 과 1)

그 다음, 연산자 개수가 1 0 1 0 이므로 for문에서 연산자 크기만큼 반복한다. +가 1 이므로 if문에 해당되어 i = 0 일때 연산자를 -1 해주므로 연산자의 개수는 0 0 1 0 이 된다. 그렇게 되면 case 0 에서 3 + 4 해주고, 그 값을 dfs(7,2)로 념겨준다. 그 다음 break 하고 다시 연산자 +를 1 더해준다.

i = 1 일때 pass

i = 2 일때 * 에 해당하므로 3 * 4 해주고, dfs(12,2)를 넘겨준다. 연산자는 1 0 0 0 그 다음 break 하고 다시 연산자 *를 1 더해준다.

i = 3 일때 pass

이 다음, 생각해야할 것은 dfs(7,2) 와 dfs(12,2) 이다. 그때의 연산자 값을 생각해본다면, dfs(7,2) : 0 0 1 0 dfs(12,2) : 1 0 0 0 만약 여기서 아까 연산자에 +1 를 해주지 않았다면, dfs(12,2) 에서 연산자 값은 0 0 0 0 이 되어 제대로 연산이 되지 않는다.

이런 식으로 진행하다가 인덱스의 값이 n과 같아지면(if문) dfs가 종료된다.

제일 중요하다고 생각되는 점은,

1. dfs 함수에 인자로 어떤 값을 넘겨줄 것인가
2. dfs 의 for문을 어떻게 작성할 것인가

가 제일 중요하다고 생각된다. 어떠한 값을 인자로 넘겨줘야하는 지 생각하는 부분이 어려웠다.

풀이

import java.io.*;
import java.util.StringTokenizer;

//연산자 끼워넣기
public class prob14888 {

    static int max = Integer.MIN_VALUE;
    static int min = Integer.MAX_VALUE;

    //수의 개수
    static int n;
    //수
    static int arr[];
    //연산자 개수
    static int[] operator = new int[4];

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        //수의 개수 입력
        n = Integer.parseInt(br.readLine());

        StringTokenizer st = new StringTokenizer(br.readLine());

        //수 입력
        arr = new int[n];
        for (int i = 0; i < n; i++) {
            arr[i] = Integer.parseInt(st.nextToken());
        }

        //연산자 개수 입력
        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < 4; i++) {
            operator[i] = Integer.parseInt(st.nextToken());
        }
        //첫번째 값과 그 다음값을 위한 index(깊이)를 인자로 넘겨준다.(깊이는 1부터 시작)
        dfs(arr[0], 1);

        System.out.println(max);
        System.out.println(min);

    }

    static void dfs(int num, int index) {
        //인덱스(깊이)가 n과 같아지면 주어진 숫자를 다 사용했다는 뜻. 해당 값이 최대인지 최소인지 확인하여 교체
        if (index == n) {
            max = Math.max(num, max);
            min = Math.min(num, min);
            return;
        }

        //연산자 네개
        for (int i = 0; i < 4; i++) {
            //연산자 개수가 1개 이상인 경우(존재하는 경우)
            if (operator[i] > 0) {

                //해당 연산자 1 감소
                operator[i]--;
                switch (i) {
                    // +
                    case 0:
                        dfs(num + arr[index], index + 1);
                        break;
                    // -
                    case 1:
                        dfs(num - arr[index], index + 1);
                        break;
                    // *
                    case 2:
                        dfs(num * arr[index], index + 1);
                        break;
                    // /
                    case 3:
                        dfs(num / arr[index], index + 1);
                        break;
                }
                //재귀 호출이 끝나면 해당 연산자 개수 복구
                operator[i]++;
            }
        }
    }
}