항승이는 품질이 심각하게 나쁜 수도 파이프 회사의 수리공이다. 항승이는 세준 지하철 공사에서 물이 샌다는 소식을 듣고 수리를 하러 갔다.

파이프에서 물이 새는 곳은 신기하게도 가장 왼쪽에서 정수만큼 떨어진 거리만 물이 샌다.

항승이는 길이가 L인 테이프를 무한개 가지고 있다.

항승이는 테이프를 이용해서 물을 막으려고 한다. 항승이는 항상 물을 막을 때, 적어도 그 위치의 좌우 0.5만큼 간격을 줘야 물이 다시는 안 샌다고 생각한다.

물이 새는 곳의 위치와, 항승이가 가지고 있는 테이프의 길이 L이 주어졌을 때, 항승이가 필요한 테이프의 최소 개수를 구하는 프로그램을 작성하시오. 테이프를 자를 수 없고, 테이프를 겹쳐서 붙이는 것도 가능하다.

제한 조건

• 시간 제한 : 2초
• 풀이 시간 : 30분

입력 조건

• 첫째 줄에 물이 새는 곳의 개수 N과 테이프의 길이 L이 주어진다.
• 둘째 줄에는 물이 새는 곳의 위치가 주어진다.
• N과 L은 1,000보다 작거나 같은 자연수이고, 물이 새는 곳의 위치는 1,000보다 작거나 같은 자연수이다.

출력 조건

• 첫째 줄에 항승이가 필요한 테이프의 개수를 출력한다.

예시

풀이

먼저 테이프는 왼쪽에서 시작해서 오른쪽으로 붙이기 때문에 입력받은 물이 새는 지점을 오름차순으로 정렬해야 한다. 또한 테이프를 자를 수 없고, 테이프를 겹쳐서 붙이는 것도 가능하다라는 조건은 테이프를 자르지 않고 사용하지만 연속해서 붙일 수 있다는 말이다.

물을 막을 때, 적어도 그 위치의 좌우 0.5만큼 간격을 줘야한다라는 조건이 나온다. 이 말은 물이 새는 지점을 테이프로 막기 위해서는 1만큼의 테이프 길이가 필요하다는 말이다. 즉, 길이가 1인 테이프를 사용하면 물이 새는 지점의 수 N만큼의 테이프가 필요하다는 것을 알 수 있다.

테이프의 길이가 1보다 클 경우에는 최초 물이 새는 지점 + L(테이프 길이)를 계산한다. 이후 물이 새는 지점 < 최초 물이 새는 지점 + L일 경우에는 테이프 1개로 막을 수 있다는 것을 알 수 있다. 이 조건을 충족하지 못할 경우에는 추가 테이프가 더 필요하다는 것이므로 테이프 개수를 카운트하고 해당 지점에 L을 다시 더한 값을 기준으로 위 과정을 반복한다.

코드

• 코드

세준이는 양수와 +, -, 그리고 괄호를 가지고 식을 만들었다. 그리고 나서 세준이는 괄호를 모두 지웠다. 그리고 나서 세준이는 괄호를 적절히 쳐서 이 식의 값을 최소로 만들려고 한다. 괄호를 적절히 쳐서 이 식의 값을 최소로 만드는 프로그램을 작성하시오.

제한 조건

• 풀이 시간 : 30분
• 시간 제한 : 2초

입력 조건

• 첫째 줄에 식이 주어진다.
• 식은 ‘0’~‘9’, ‘+’, 그리고 ‘-’만으로 이루어져 있고, 가장 처음과 마지막 문자는 숫자이다.
• 연속해서 두 개 이상의 연산자가 나타나지 않고, 5자리보다 많이 연속되는 숫자는 없다.
• 수는 0으로 시작할 수 있다.
• 입력으로 주어지는 식의 길이는 50보다 작거나 같다.

출력 조건

• 첫째 줄에 정답을 출력한다.

예시

풀이

덧셈, 뺄셈 연산식에서 최소값을 만드는 방법은 - 뒤에 오는 +들을 다 묶어주면 된다. 하지만 이 것을 더 단순하게 표현하면 최초에 -가 나온 뒤의 모든 숫자들을 빼버리면 된다는 것이다. 또한 연산식의 길이가 50자 이하이므로 O(N)의 시간 복잡도로 풀이해도 문제가 없다. 그래서 다음과 같이 코드를 작성하기로 했다.

1. 연산식의 char를 순서대로 받아서 +, -가 아니면 StringBuilder에 append한다.
2. +가 나오면 StringBuilder의 값을 Integer로 변환하여 더한다.
3. -가 나오면 flag를 세워 이후의 값들을 모두 뺄 수 있도록 한다.
4. 마지막 값은 숫자이므로 for loop가 끝난 후 StringBuilder의 값을 flag에 맞춰 더하거나 뺀다.

• flag는 -가 최초로 나온 시점을 구별하기 위함

하지만 이 논리는 단순한 것 같지만 실제로 코드를 구현하는 것은 생각보다 어려웠다. 불필요하게 반복되는 로직들이 발생했고, 고려해야하는 경우의 수가 많아져 코드를 작성하는데 애를 먹었다.

다른 사람들의 코드를 보니 split을 활용하여 문제를 풀이하고 있었다. 생각해보니 이 문제는 괄호를 쳐주는 것이 목표고, -를 기준으로 split을 하는 것이 곧 괄호를 쳐주는 것과 같다는 것을 깨달았다. 그래서 다음과 같이 코드를 수정하였다.

1. -를 기준으로 split을 한다.
2. split된 문자열이 empty일 경우, flag를 세우고 다음 문자열로 넘어간다.
3. split된 문자열이 empty가 아닐 경우, +를 기준으로 split하여 다 더한다.
4. flag가 안 세워졌을 경우, flag를 세우고 3의 값을 더한다.
5. flag가 세워졌을 경우, 3의 값을 뺀다.

• flag는 처음 작성한 로직과 동일한 역할을 한다

이렇게 작성하니 불필요하게 반복되는 로직들이 사라졌고, 단계별 코드의 목적이 명확해졌다. 그래서 코드를 작성하기 훨씬 편했고, 문제를 찾거나 수정하는 것 또한 훨씬 편해졌다.

코드

• 코드

행복 유치원 원장인 태양이는 어느 날 N명의 원생들을 키 순서대로 일렬로 줄 세우고, 총 K개의 조로 나누려고 한다. 각 조에는 원생이 적어도 한 명 있어야 하며, 같은 조에 속한 원생들은 서로 인접해 있어야 한다. 조별로 인원수가 같을 필요는 없다.

이렇게 나뉘어진 조들은 각자 단체 티셔츠를 맞추려고 한다. 조마다 티셔츠를 맞추는 비용은 조에서 가장 키가 큰 원생과 가장 키가 작은 원생의 키 차이만큼 든다. 최대한 비용을 아끼고 싶어 하는 태양이는 K개의 조에 대해 티셔츠 만드는 비용의 합을 최소로 하고 싶어한다. 태양이를 도와 최소의 비용을 구하자.

제한 조건

• 풀이 시간 : 30분
• 제한 시간 : 1초

입력

• 입력의 첫 줄에는 유치원에 있는 원생의 수를 나타내는 자연수 N(1 ≤ N ≤ 300,000)과 나누려고 하는 조의 개수를 나타내는 자연수 K(1 ≤ K ≤ N)가 공백으로 구분되어 주어진다.
• 다음 줄에는 원생들의 키를 나타내는 N개의 자연수가 공백으로 구분되어 줄 서 있는 순서대로 주어진다.
• 태양이는 원생들을 키 순서대로 줄 세웠으므로, 왼쪽에 있는 원생이 오른쪽에 있는 원생보다 크지 않다.
• 원생의 키는 109를 넘지 않는 자연수이다.

출력

• 티셔츠 만드는 비용이 최소가 되도록 K개의 조로 나누었을 때, 티셔츠 만드는 비용을 출력한다.

예시

풀이

최소 비용이 되도록 조를 짜기 위해서는 키 차이가 곧 티셔츠 제작 비용이라는 점에 주목해야 한다. 결국 최소 비용이 되도록 하기 위해서는 인접 인원의 키 차이가 가장 큰 인원을 기준으로 (k - 1)개만큼 분리하여 k개의 조를 짜면 된다.

우선 인접 인원의 키 차이를 계산하고 정렬하여 k개의 조를 만들고, 각 조원의 max, min 키 차이를 구해야 한다고 생각했다. 그래서 인접 인원의 번호와 키 차이를 가지는 객체를 만들고 정렬을 위해 Comparable을 상속받아 compare 메서드를 구현하여 키 차이 값을 통해 정렬될 수 있도록 했다. 하지만 이런 접근 방식을 통해 조를 만들고 키 차이를 구하는 방식을 매우 복잡하게 만들었고, 제한 시간 안에 풀이를 하지 못했다.

다른 사람의 풀이를 확인해보니 굳이 조를 만들어서 키 차이를 계산할 필요가 없었다. 그냥 각 인원의 키 차이의 합이 결국 해당 조의 가장 키가 큰 사람과 작은 사람의 키 차이가 되기 때문이었다. 풀이를 매우 단순하게 각 인원 간 키 차이 값들 중 차이가 가장 많이 나는 (k - 1)개를 제외한 나머지 값들을 모두 더하면 된다.

그리디 문제들을 풀어보면서 느끼는 중요한 점은 문제에서 제시한 조건 그대로 풀이하는 것이 아닌 최대한 단순하게 해결할 수 있는 방법을 찾는 것 같다.

코드

• 코드

Enum Class는 상수들의 집합이며, 열거형 Class라고도 불린다. 이 Class의 상수를 호출하면 자동으로 생성자가 실행되며, 개발자가 직접 생성자를 호출할 수 없다.

우리는 사람이기 때문에 Error Code나 UserRole 같은 값들을 매번 String이나 int와 같은 값으로 직접 작성하거나 변경을 한다고 생각해보자. 이렇게 작성된 코드는 가독성이 떨어지는 것은 물론이고 오타가 나거나 특정 값을 누락하는 실수가 발생할 확률이 매우 높다. Enum Class는 이러한 값들을 상수들로 미리 정의하여 Human Mistake를 방지할 수 있도록 한다. 이를 통해 비즈니스 로직을 간단하고 견고하게 만드는데 유리하다.

이 Class는 다음과 같이 활용할 수 있다.

• 데이터의 연관 관계 표현
• 상태에 따른 행위 표현
• 데이터 그룹 관리
• DB의 메타 테이블을 객체로 관리

이러한 특징들로 허용 가능한 값을 제한하고 리팩토링 변경 범위를 최소화 할 수 있다. 이 Class의 값을 정의할 때는 대문자로 작성하며, 언더바_를 활용하여 글자를 구분한다.

데이터의 연관 관계 표현

아래와 같이 ErrorType과 ErrorCode를 묶어서 연관성을 표현해줄 수 있다.

public enum ErrorCode {
    UNAUTHORIZED(401),
    NOT_FOUND(404),
    INTERNAL_SERVER_ERROR(500),
    EXPECTATION_FAILED(417),
    SERVICE_UNAVAILABLE(503);

    private final int code;

    public String getCode() {
        return code;
    }
}

상태에 따른 행위 표현

만약 회원의 등급마다 할인가가 다르게 적용된 서비스를 제공한다고 가정하자. 단순히 if문을 사용한다면 회원 할인가가 적용된 가격이란 동일 관심사임에도 불구하고, 각 등급마다 분기하여 처리해야 한다. 결국 불필요하게 반복되는 내용들을 작성하게 되어 코드가 길어지게 된다.

public enum MembershipGrade {
    NON_MEMBER,
    FAMLIY,
    SILVER,
    GOLD,
    VIP;
}

public int calculateMembershipPrice(MembershipGrade membershipGrade, int price) {
    if (membershipGrade == MembershipGrade.NON_MEMBER) {
        return price;
    }

    if (membershipGrade == MembershipGrade.FAMLIY) {
        return price - 1000;
    }

    ...
}

이러한 문제를 회원 등급에 할인가를 적용하는 연산을 Enum Class에 정의하여 해결할 수 있다.

public enum MembershipGrade {
    NON_MEMBER(price -> price),
    FAMLIY(price -> price - 1000),
    SILVER(price -> price - 5000),
    GOLD(price -> price * 0.8),
    VIP(price -> price * 0.7);

    private Function<Integer, Integer> expression;

    MembershipGrade(Function<Integer, Integer> expression) {
        this.expression = expression;
    }

    /*
    * price : 실제 가격
    * return : 할인가
    */
    public int calculateMembershipPrice(int price) {
        return expression.apply(price);
    }
}

일반적으로 회원 등급은 DB의 회원 정보에 같이 저장한다. 그렇기 때문에 회원 등급을 Enum 형태로 DB에 저장해 두면, 이후 꺼내왔을 때 Enum Class에 정의된 연산 로직만 호출하기만 하면 된다.

public int getServicePriceByUid(int uid) {
    UserInfo userInfo = UserInfoRepository.findUserInfoByUid(uid);

    return userInfo.getMembershipGrade
            .calculateMembershipPrice(userInfo.UsingService.getPrice());
}

• Enum이 DB에 저장될 때는 VARCHAR로 저장되며 Enum에 정의된 값과 동일한 형태로 저장된다.

데이터 그룹 관리

패션 쇼핑몰에서 카테고리는 대략 다음과 같이 분류될 것이다.

여기서 구매자가 구매한 옷들을 그룹별로 분류하고, 해당 그룹별 기능을 만들 때, if문을 활용하게 된다면 다음과 같이 될 것이다.

public String getClothesGroup(String clothesType) {
    if ("Sweatshirt".equals(clothesType) || "Knitwear".equals(clothesType)
            || "Shirt".equals(clothesType) || "Hoodie".equals(clothesType) {
        return "Top";
    } else if ("DenimPants".equals(clothesType) || "TrainingPants".equals(clothesType)
            || "CottonPants".equals(clothesType) || "Slacks".equals(clothesType) {
        return "Bottoms";
    } else if ("Sneakers".equals(clothesType) || "Loafer".equals(clothesType)
            || "Sandals".equals(clothesType) || "Sports".equals(clothesType) {
        return "Shoes";
    } else {
        return "Empty";
    }
}

public void pushClothesGroup(String clothesType) {
    if ("Top".equals(clothesType)) {
        pushTopMethod();
    } else if ("Bottom".equals(clothesType)) {
        pushBottomMethod();
    } else if ("Shoes".equals(clothesType)) {
        pushShoesMethod();
    } else {
        throw new RuntimeException("clothesType이 존재하지 않습니다.")
    }
}

public void printClothesGroup(String clothesType) {
    if ("Top".equals(clothesType)) {
        printTopMethod();
    } else if ("Bottom".equals(clothesType)) {
        printBottomMethod();
    } else if ("Shoes".equals(clothesType)) {
        printShoesMethod();
    } else {
        throw new RuntimeException("clothesType이 존재하지 않습니다.")
    }
}

이런 코드는 관리하기가 어렵기 때문에, 추후 새로운 타입, 그룹 또는 기능을 추가하기 어려워 확장성이 저하된다. 또한 입력값이 값이 정해지지 않은 String 형태로 들어오기 때문에 출력값 또한 예측할 수 없다.

Enum Class로 변환하게 되면 이러한 문제점들을 해결할 수 있게 된다.

public enum ClothesType {
    SWEATSHIRT("스웨트셔츠"),
    KNITWEAR("니트"),
    SHIRT("셔츠"),
    HOODIE("후드"),
    DENIM_PANTS("데님 팬츠"),
    COTTON_PANTS("코튼 팬츠"),
    SLACKS("슬랙스"),
    TRAINING_PANTS("트레이닝 팬츠"),
    SNEAKERS("스니커즈"),
    LOAFER("로퍼"),
    SANDALS("샌들"),
    SPORTS("스포츠"),
    EMPTY("없음");

    private final String title;

    ClothesType(String title) {
        this.title = title;
    }

    public String getTitle() {
        return title;
    }
}

public enum ClothesGroup {
    TOP("상의", 
            Arrays.asList(
                    ClothesType.SWEATSHIRT, ClothesType.KNITWEAR, 
                    ClothesType.SHIRT, ClothesType.HOODIE
            )
    ),
    BOTTOMS("하의", 
            Arrays.asList(
                    ClothesType.DENIM_PANTS, ClothesType.COTTON_PANTS, 
                    ClothesType.SLACKS, ClothesType.TRAINING_PANTS
            )
    ),
    SHOES("신발", 
            Arrays.asList(
                    ClothesType.SNEAKERS, ClothesType.LOAFER, 
                    ClothesType.SANDALS, ClothesType.SPORTS
            )
    ),
    EMPTY("없음", Collections.emptyList());

    private final String title;
    private final List<ClothesType> clothesTypeList;

    ClothesGroup(String title, List<ClothesType> clothesTypeList) {
        this.title = title;
        this.clothesTypeList = clothesTypeList;
    }

    public static ClothesGroup findByClothesType(ClothesType clothesType) {
        return Arrays.stream(ClothesGroup.values())
                .filter(clothesGroup -> clothesGroup.hasPayCode(clothesType))
                .findAny()
                .orElse(EMPTY);
    }

    public boolean hasPayCode(ClothesType clothesType) {
        return clothesTypeList.stream()
                .anyMatch(type -> type == clothesType);
    }

    public String getTitle() {
        return title;
    }
}

우선 옷 종류와 그룹이 Enum으로 모두 정의되어 있으므로 입력값과 출력값이 예측 가능해진다. 또한 모든 값들이 Enum으로 관리되고 있어 편하고 새로운 타입이나 그룹을 추가하기 편하다. 또한 새로운 기능을 추가할 때도 그룹은 신경쓰지 않고 기능 구현에 필요한 내용만 작성하면 된다.

public void getClothesGroup(String productId) {
    Product product = productRepository.findByProductId(productId);
    ClothesGroup clothesGroup = ClothesGroup.findByClothesType(product.getClothesType);
}

public void pushClothesGroup(ClothesGroup clothesGroup) {
    pushShoesMethod();
}

public void printClothesGroup(ClothesGroup clothesGroup) {
    printShoesMethod();
}

DB의 메타 테이블을 객체로 관리

도서 정보를 위한 DB 테이블을 설계할 때, 책의 카테고리를 분류하는 id가 포함될 것이고, 이 id에 대한 명세를 가진 테이블을 만들게 될 것이다. 이 테이블은 다음과 같은 특징을 가진다.

• 변경될 일이 거의 없다.
• UI에 표시할 때만 테이블을 조회한다.

이러한 경우에는 Enum Class로 대체하여 관리해줄 수 있다.

public enum BookCategory {
    BC101("소설"),
    BC102("시/에세이"),
    BC103("예술/대중문화"),
    BC104("사회과학"),
    BC105("역사와 문화");

    private final String title;

    BookCategory(String title) {
        this.title = title;
    }

    public String getTitle() {
        return title;
    }
}

그리고 UI 상에서 필요할 때만 이 Enum 값을 받아서 사용할 수 있게 해준다. 이 Enum Class가 Controller를 통해 반환할 수 있도록 다음과 같이 Class를 작성해준다.

public interface EnumMapperType {
    String getCode();
    String getTitle();
}

public class EnumMapperValue implements Serializable {
    private static final long serialVersionUID = 6230704194885989241L;

    private String code;
    private String title;

    public EnumMapperValue(EnumMapperType enumMapperType) {
        this.code = enumMapperType.getCode();
        this.title = enumMapperType.getTitle();
    }

    public String getCode() {
        return code;
    }

    public String getTitle() {
        return title;
    }

    @Override
    public String toString() {
        return "EnumMapperValue{" +
                "code='" + code + '\'' +
                ", title='" + title + '\'' +
                '}';
    }
}

그리고 Enum Class에도 EnumMapperType을 상속받도록 변경한다.

public enum BookCategory {
    BC101("소설"),
    BC102("시/에세이"),
    BC103("예술/대중문화"),
    BC104("사회과학"),
    BC105("역사와 문화");

    private final String title;

    BookCategory(String title) {
        this.title = title;
    }

    public String getTitle() {
        return title;
    }

    @Override
    public String getCode() {
        return name();
    }

    @Override
    public String getTitle() {
        return name;
    }
}

이제 필요할 때 요청을 받아 Enum 값을 반환할 수 있도록 Controller에 추가해준다.

@GetMapping("/bookCategoryList")
public List<EnumMapperValue> getBookCategoryList() {
    return Arrays.stream(BookCategory.values())
                .map(EnumMapperValue::new)
                .collect(Collectors.toList());
}

하지만 여기서 또 하나의 아쉬운 점이 발생한다. 바로 Enum은 상수값이기 때문에 변경될 일이 없는데, Controller를 통해 반환할 때마다 EnumMapperValue 객체를 생성하게 되는 것이다. 이러한 점을 해결하기 위해 Enum Value들을 담을 팩토리 클래스를 작성한다.

public class EnumMapper {
    private Map<String, List<EnumMapperValue>> factory = new LinkedHashMap<>();

    public EnumMapper() {}

    public void put(String key, Class<? extends EnumMapperValue> e) {
        factory.put(key, toEnumValues(e));
    }

    private List<EnumMapperValue> toEnumValues(Class<? extends EnumMapperValue> e) {
        return Arrays.stream(BookCategory.values())
                .map(EnumMapperValue::new)
                .collect(Collectors.toList());
    }

    public List<EnumMapperValue> get(String key) {
        return factory.get(key);
    }

    public Map<String, List<EnumMapperValue>> get(List<String> keyList) {
        if (keyList == null || keyList.isEmpty()) {
            return new LinkedHashMap<>();
        }

        return keyList.stream()
                .collect(Collectors.toMap(Function.identity(), key -> factory.get(key)));
    }

    public Map<String, List<EnumMapperValue>> getAll() {
        return factory;
    }
}

이 팩토리에서 get을 할 때 파라메터 인자값으로 Class<? extends EnumMapperType> e를 받게 하는 이유는 EnumMapperType을 상속받아 구현한 Class만 접근할 수 있도록 제한하기 위함이다. 마지막으로 이 팩토리를 bean으로 등록해주고 필요한 곳에서 이 bean을 DI하여 사용할 수 있도록 한다.

@Bean
public EnumMapper enumMapper() {
    EnumMapper enumMapper = new EnumMapper();

    enumMapper.put("BookCategory", BookCategory.class);

    return enumMapper;
}

@GetMapping("/bookCategoryList")
public List<EnumMapperValue> getBookCategoryList() {
    return enumMapper.get("BookCategory");
}

정리

Enum Class는 특정값들을 상수값으로 정의하여 휴먼미스테이크를 방지한다는 점만 알고 있었다. 하지만 이 블로그를 읽어보며 이 Enum Class를 훨씬 다양하게 활용하여 코드를 더욱 명확하고 견고하게 작성할 수 있게 해준다는 것을 알게 되었다. 하지만 이 Enum Class는 변경이 어렵기 때문에 무조건적으로 활용하기보다 상황에 맞게 유연하게 사용해야 한다고 한다.

정확히 어떤 점들이 유리하고 불리한지, 어떤 상황에 활용하는 것이 적절한지는 아래 블로그 링크에 설명되어 있다. 해당 내용들을 여기에 작성하기에는 직접 활용한 경험이나 이해도가 아직 많이 부족하기 때문에 여기서 언급할 내용은 아닌 것 같다...

참고

• 우아한형제들 - Java Enum 활용기

인하은행에는 ATM이 1대밖에 없다. 지금 이 ATM앞에 N명의 사람들이 줄을 서있다. 사람은 1번부터 N번까지 번호가 매겨져 있으며, i번 사람이 돈을 인출하는데 걸리는 시간은 Pi분이다.

사람들이 줄을 서는 순서에 따라서, 돈을 인출하는데 필요한 시간의 합이 달라지게 된다. 예를 들어, 총 5명이 있고, P1 = 3, P2 = 1, P3 = 4, P4 = 3, P5 = 2 인 경우를 생각해보자. [1, 2, 3, 4, 5] 순서로 줄을 선다면, 1번 사람은 3분만에 돈을 뽑을 수 있다. 2번 사람은 1번 사람이 돈을 뽑을 때 까지 기다려야 하기 때문에, 3+1 = 4분이 걸리게 된다. 3번 사람은 1번, 2번 사람이 돈을 뽑을 때까지 기다려야 하기 때문에, 총 3+1+4 = 8분이 필요하게 된다. 4번 사람은 3+1+4+3 = 11분, 5번 사람은 3+1+4+3+2 = 13분이 걸리게 된다. 이 경우에 각 사람이 돈을 인출하는데 필요한 시간의 합은 3+4+8+11+13 = 39분이 된다.

줄을 [2, 5, 1, 4, 3] 순서로 줄을 서면, 2번 사람은 1분만에, 5번 사람은 1+2 = 3분, 1번 사람은 1+2+3 = 6분, 4번 사람은 1+2+3+3 = 9분, 3번 사람은 1+2+3+3+4 = 13분이 걸리게 된다. 각 사람이 돈을 인출하는데 필요한 시간의 합은 1+3+6+9+13 = 32분이다. 이 방법보다 더 필요한 시간의 합을 최소로 만들 수는 없다.

줄을 서 있는 사람의 수 N과 각 사람이 돈을 인출하는데 걸리는 시간 Pi가 주어졌을 때, 각 사람이 돈을 인출하는데 필요한 시간의 합의 최솟값을 구하는 프로그램을 작성하시오.

입력

• 첫째 줄에 사람의 수 N(1 ≤ N ≤ 1,000)이 주어진다.
• 둘째 줄에는 각 사람이 돈을 인출하는데 걸리는 시간 Pi가 주어진다. (1 ≤ Pi ≤ 1,000)

출력

• 첫째 줄에 각 사람이 돈을 인출하는데 필요한 시간의 합의 최솟값을 출력한다.

예시

풀이

이 문제는 최소합을 구하는 문제로 오름차순 정렬을 하여 간단하게 해결 가능하다. 정렬을 하기 위해서 자료구조 List가 필요하다.

이 풀이 방식에는 정렬에 필요한 O(NlogN), 합을 구하기 위한 O(N) 시간 복잡도가 존재한다. 결과적으로 이 풀이 방법은 O(NlogN)의 시간 복잡도를 가진다.

이슈

이번에는 문제의 난이도를 낮추고 대신 알고리즘 순서도를 작성하는 방식을 적용해 보았다. 순서도를 작성하며 내가 문제를 풀이할 때 어떤 점이 부족한지 조금 더 자세하게 알게 되었다.

첫번째로 미리 변수를 선언해보면서 깨닫게 된 점은 문제에서 주어지는 입력 조건과 출력 조건을 보지 않았다는 것이다. 이로 인해 순서도를 작성하다가 입력 받아야 할 포멧이 어떻게 되는지 몰라서 입력 조건을 다시 보고 추가로 순서도에 필요한 변수를 추가로 작성했다는 점이다.

두번째로는 순서도를 작성해야 한다는 생각에 빠져 정작 중요한 합을 구하는 방식을 어떻게 처리할 것인지에 대한 고민을 빼먹었다는 것이다. 단순히 더했던 값에 현재 값을 더해주면 되겠지라고 생각해버린 것이다.

이 두가지 문제점을 종합하면 크게 어떻게 접근할지까지는 생각을 하는데 디테일한 내용까지는 이미 알고 있다라고 착각해버리고 넘긴다는 것이다.

1. 문제를 정확하게 읽고
2. 입출력 조건을 정확하게 파악하고
3. 내가 작성할 알고리즘을 명확하게 정의하자

코드

• 코드

L2 스위치는 이더넷 프레임을 전송하기 위해 이더넷 헤더의 MAC 주소를 확인하고 전달하는 역할을 한다. 또한 이더넷 네트워크로 들어가는 입구 역할도 하므로 액세스 스위치라고 표현하기도 한다. 이 스위치의 용도는 이더넷을 이용하여 하나의 네트워크를 구성하는 것이며, 여러 대를 연결해도 하나의 네트워크가 된다.

L2 스위치는 별다른 설정없이 전원, 케이블이 연결되면 사용할 수 있다. 그리고 MAC 주소 테이블에는 하나의 포트에 여러 개의 MAC 주소가 등록될 수 있으며, 한 번 요청에 약 5분의 제한 시간을 가진다.

초기 L2 스위치는 전송매체를 1개만 사용하여 1번에 송신 혹은 수신만 하는 반이중 통신을 했다. 현재는 전송매체를 송신용, 수신용으로 나눠 한 번에 통신할 수 있는 전이중 통신을 한다.

전송 과정

1. 수신한 이더넷 프레임의 출발지 MAC 주소를 MAC 주소 테이블에서 자신이 연결된 포트 번호에 등록

2. MAC 주소 테이블에서 목적지 MAC 주소를 가진 포트를 찾아 프레임을 전송

3. 목적지 MAC 주소를 가진 포트가 없으면 수신 포트를 제외한 모든 포트에 프레임 전송하는 플러딩 동작

4. 관계없는 이더넷 인터페이스는 수신한 프레임을 파기

5. 다른 L2 스위치가 수신하면 수신한 포트 번호에 출발지 MAC 주소를 등록

6. MAC 주소 테이블에서 목적지 MAC 주소를 가진 포트가 있다면 프레임 전송. 없으면 다시 플러딩

7. 응답할 때는 자신의 MAC 주소 테이블에 등록된 출발지 MAC 주소를 가진 포트를 보고 전송(되돌아 갈 때 등록되지 않았던 MAC 주소 테이블을 업데이트 하며 진행)

로봇을 좋아하는 세희는 로봇동아리에서 카메라와 센서, 라즈베리 파이, 집게발을 이용해 로봇을 완성하였다. 이 로봇을 통해서 오셀로 재배치라는 작업을 하려고 한다. 오셀로 말은 앞면이 검정, 뒷면이 흰색으로 된 말이다. 세희의 목표는 로봇을 이용하여 처음 배치된 오셀로 말을 주어진 형태로 바꾸는 일을 하는 것이다. 아래의 예시를 참고하자.

세희는 로봇을 이용해 2가지 작업 중 하나를 골라 진행할 수 있다.

1. 배치된 말 중 임의의 2개의 말을 골라 서로의 위치를 바꾼다.
2. 말 1개를 들어 뒤집어 놓아 색상을 변경한다.

위의 예시에서, 3번째와 4번째 말을 2번 작업을 통해 각각 뒤집으면 2번의 작업으로 목표 상태를 만들 수 있다. 하지만 1번 작업을 통해 3번째와 4번째 말을 골라 서로의 위치를 바꾸어주면 1번 만에 목표 상태에 도달할 수 있다. 초기 상태의 말과 목표 상태의 말이 주어질 때, 목표 상태에 도달할 수 있는 최소 횟수를 구하는 프로그램을 작성하시오.

제한 조건

• 제한 시간 : 2초
• 풀이 시간 : 30분

입력

• 입력 데이터는 표준 입력을 사용한다.
• 입력은 T개의 테스트 데이터로 구성된다.
• 각 입력의 첫 번째 줄에는 오셀로 말의 개수 N(1 ≤ N ≤ 100,000)이 주어진다.
• 각 입력의 두 번째 줄과 세 번째 줄에는 각각 오셀로 말의 초기 상태와 목표 상태가 주어진다.
• 초기 상태와 목표 상태의 말의 개수는 항상 N과 일치한다.
• 흰색 면이 보이는 경우에는 W, 검은색 면이 보이는 경우에는 B로 주어진다.

출력

• 출력은 표준 출력을 사용한다.
• 입력받은 데이터에 대해, 한 줄에 1개씩 초기 상태에서 목표 상태를 만들기 위한 작업의 최소 횟수를 구한다.

예시

풀이

이 문제는 2가지에 초점을 잡고 풀이할 수 있다.

1. 모든 말이 동일한 상태를 가지고 있는가?
2. 목표하는 말의 배치와 다른 상태를 가진 말들은 얼마나 있는가?

우선 1번의 접근은 매우 간단하다. 모든 말들이 동일한 상태를 가질 경우 위치를 바꿀 수 있는 말이 존재하지 않기 때문에 작업 2번만 진행하면 된다.

2번의 경우도 생각보다 단순하게 해결된다. 먼저 목표하는 말과 다른 상태를 가진 말들 중에서 W, B 상태 각각 말의 개수를 파악한다. 예를 들어 W가 3개, B가 2개일 경우, B 2개와 W 2개는 서로 위치를 변경하는 1번 작업을 수행할 수 있다. 남은 W 1개는 위치를 변경할 대상이 없으므로 2번 작업을 수행하게 되므로 총 3번 작업하게 된다. 이 예시를 통해 알 수 있는 것은 상태 W, B를 가진 말들 중 개수가 더 많은 것이 최소 작업의 횟수가 된다는 것이다.

이 풀이는 시간 복잡도 O(N)을 가지며, 말의 최대 개수인 10만개를 가진 T가 1000을 넘지 않을 경우 풀이가 가능하다.

이슈

처음 코드를 작성하려고 했을 때, T번 입력을 받을 때마다 알고리즘을 처리하게 했다. 하지만 이렇게 하면 마지막 readLine에 \n이 입력되지 않은 상태이므로 마지막 연산의 결과에 enter를 한 번 더 입력해줘야 한다. 결과적으로 마지막 케이스의 결과가 한 줄 띄우고 출력하게 되므로 문제가 원하는 양식에 맞지 않게 된다. 여러번 입력받아야 할 경우에는 초기에 한 번에 다 입력받은 후에 알고리즘을 처리하도록 하자.

코드

• 코드

민식이는 다음과 같은 폴리오미노 2개를 무한개만큼 가지고 있다. AAAA와 BB

이제 '.'와 'X'로 이루어진 보드판이 주어졌을 때, 민식이는 겹침없이 'X'를 모두 폴리오미노로 덮으려고 한다. 이때, '.'는 폴리오미노로 덮으면 안 된다.

폴리오미노로 모두 덮은 보드판을 출력하는 프로그램을 작성하시오.

제한 조건

• 제한 시간 : 2초
• 풀이 시간 : 30분

입력

• 첫째 줄에 보드판이 주어진다. 보드판의 크기는 최대 50이다.

출력

• 첫째 줄에 사전순으로 가장 앞서는 답을 출력한다.
• 만약 덮을 수 없으면 -1을 출력한다.

예시

풀이

이 문제는 연속된 X의 개수를 체크하며 보드판을 만들어나가면 된다. 다만 문제에 제시된 것처럼 폴리오미노를 사전 순으로 덮아야 한다는 조건을 지켜야 한다.

'X'가 나왔을 경우에는 '.'이 나오거나 종료될 때까지 X의 개수를 체크한다. '.'이 나왔을 때는 'X'의 개수가 0일 경우와 0이상일 경우 2가지로 나눠서 진행한다.

if (0 이상일 경우):
    'X'의 개수를 4로 나눈 몫만큼 A를 보드판에 추가 # A로 덮을 수 있는 개수

    if ('X'의 개수를 4로 나눈 나머지가 2나 0이 아닐 경우): 
        폴리오미노로 다 덮을 수 없는 문자열이므로 -1을 출력
    else:
        나머지만큼 B를 보드판에 추가 # 2면 B로 한번 덮을 수 있고, 0이면 B로 덮을 것이 없음

else: 
    '.'을 보드판에 추가

이 풀이의 시간 복잡도는 O(N)이고 보드판의 최대 길이가 50이므로 풀이가 가능하다.

이슈

1. 보드판이 'X'로만 이뤄질 경우 루프가 끝나면 '.'을 체크하는 조건문을 거치지 않게 되므로 빈 보드판을 출력됨.
   • 루프가 끝난 후에도 'X'의 길이가 0 이상이면 폴리오미노로 변환하는 로직을 추가함.
2. 보드판을 출력할 때 처음 보드판 형태에서 'X'만 폴리오미노로 변환하여 출력해야 하는데, '.'이 먼저 찍힌 후 폴리오미노가 출력됨.
   • StringBuilder에 '.'을 append하는 구문을 'X' 길이를 체크하는 조건문 이후에 하도록 변경.

코드를 작성하고 나서 발생한 2가지 이슈는 사소한 부분들인데, 문제를 풀이하는데 정신이 팔려 놓치고 말았다. 수도 코드를 작성해보며 생각하지 못한 엣지 케이스가 존재하는지 확인해 볼 필요가 있다.

코드

• 코드

상근이는 오락실에서 바구니를 옮기는 오래된 게임을 한다. 스크린은 N칸으로 나누어져 있다. 스크린의 아래쪽에는 M칸을 차지하는 바구니가 있다. (M<N) 플레이어는 게임을 하는 중에 바구니를 왼쪽이나 오른쪽으로 이동할 수 있다. 하지만, 바구니는 스크린의 경계를 넘어가면 안 된다. 가장 처음에 바구니는 왼쪽 M칸을 차지하고 있다.

스크린의 위에서 사과 여러 개가 떨어진다. 각 사과는 N칸중 한 칸의 상단에서 떨어지기 시작하며, 스크린의 바닥에 닿을때까지 직선으로 떨어진다. 한 사과가 바닥에 닿는 즉시, 다른 사과가 떨어지기 시작한다.

바구니가 사과가 떨어지는 칸을 차지하고 있다면, 바구니는 그 사과가 바닥에 닿을 때, 사과를 담을 수 있다. 상근이는 사과를 모두 담으려고 한다. 이때, 바구니의 이동 거리의 최솟값을 구하는 프로그램을 작성하시오.

제한 조건

• 시간 제한 : 1초
• 풀이 시간 : 30분

입력

• 첫째 줄에 N과 M이 주어진다. (1 ≤ M < N ≤ 10)
• 둘째 줄에 떨어지는 사과의 개수 J가 주어진다. (1 ≤ J ≤ 20)
• 다음 J개 줄에는 사과가 떨어지는 위치가 순서대로 주어진다.

출력

• 모든 사과를 담기 위해서 바구니가 이동해야 하는 거리의 최솟값을 출력한다.

예시

풀이

이 문제에서는 바구니의 크기와 바구니 위치의 유동성에 초점을 두고 풀어야 한다.

우선 바구니 크기가 변할 수 있으므로 바구니의 초기 front와 rear 값을 정의해준다. 가장 처음에 바구니는 왼쪽 M칸을 차지하고 있으로 front에 1을 할당하고 rear는 바구니 크기를 할당해 준다.

• front : 1
• rear : M

그리고 바구니가 이동할 조건을 찾아주면 되는데, 다음 2가지 케이스만 존재한다.

• 다음 사과의 위치가 rear보다 클 경우 -> rear와 사과 위치의 차이만큼 오른쪽으로 이동(+)
• 다음 사과의 위치가 front보다 작을 경우 -> front와 사과 위치의 차이만큼 왼쪽으로 이동(-)

이 2가지 케이스 외에는 사과가 떨어질 위치에 바구니가 이미 자리잡고 있으므로 이동할 필요가 없다.

이 풀이는 사과의 개수 J만큼 연산을 하게 되므로 시간 복잡도 O(N)으로 풀이 된다.

코드

• 코드

다솜이는 0과 1로만 이루어진 문자열 S를 가지고 있다. 다솜이는 이 문자열 S에 있는 모든 숫자를 전부 같게 만들려고 한다. 다솜이가 할 수 있는 행동은 S에서 연속된 하나 이상의 숫자를 잡고 모두 뒤집는 것이다. 뒤집는 것은 1을 0으로, 0을 1로 바꾸는 것을 의미한다.

예를 들어 S=0001100 일 때, 전체를 뒤집으면 1110011이 된다. 4번째 문자부터 5번째 문자까지 뒤집으면 1111111이 되어서 2번 만에 모두 같은 숫자로 만들 수 있다. 하지만, 처음부터 4번째 문자부터 5번째 문자까지 문자를 뒤집으면 한 번에 0000000이 되어서 1번 만에 모두 같은 숫자로 만들 수 있다.

문자열 S가 주어졌을 때, 다솜이가 해야하는 행동의 최소 횟수를 출력하시오.

제한 조건

• 시간 제한 : 2초
• 풀이 시간 : 30분

입력

• 첫째 줄에 문자열 S가 주어진다. S의 길이는 100만보다 작다.

출력

• 첫째 줄에 다솜이가 해야하는 행동의 최소 횟수를 출력한다.

예시

풀이

이 문제의 경우 입력값이 0과 1로만 구성되어 있다는 것에 초점을 두면 힌트를 얻을 수 있다. 입력값에서 0그룹의 개수와 1그룹의 개수를 파악해보면, 그룹의 개수는 동일하거나 1 차이가 난다는 특징을 발견할 수 있다. 이러한 특징을 활용해 다음과 같이 풀이가 가능하다.

1. 문자열을 하나씩 받으면서 숫자가 바뀐 횟수를 파악한다.
2. 바뀐 횟수가 홀수면 (바뀐 횟수 / 2) + 1, 짝수면 바뀐 횟수 / 2를 출력한다.

1에서 얻게 되는 바뀐 횟수는 그룹의 총 개수 - 1을 의미한다. 즉, 홀수면 각 그룹의 수가 동일하다는 것이고, 짝수면 둘 중 하나가 1개 더 많다는 것을 알 수 있다. 즉, 홀수는 그룹 수가 동일하니 2로 나눈 값에 1을 더해줘야 하고, 짝수는 그룹 수가 더 작은 값을 찾아야하니 2로 나눈 값 그대로 출력하면 된다.

이 문제는 시간 복잡도 O(N)으로 풀이가 가능하다.

코드

• 코드

3개의 시간조절용 버튼 A B C가 달린 전자레인지가 있다. 각 버튼마다 일정한 시간이 지정되어 있어 해당 버튼을 한번 누를 때마다 그 시간이 동작시간에 더해진다. 버튼 A, B, C에 지정된 시간은 각각 5분, 1분, 10초이다.

냉동음식마다 전자레인지로 요리해야할 시간 T가 초단위로 표시되어 있다. 우리는 A, B, C 3개의 버튼을 적절히 눌러서 그 시간의 합이 정확히 T초가 되도록 해야 한다. 단 버튼 A, B, C를 누른 횟수의 합은 항상 최소가 되어야 한다. 이것을 최소버튼 조작이라고 한다.

만일 요리시간이 100초라고 하면(T=100) B를 1번, C는 4번 누르면 된다. 이와 다르게 C를 10번 눌러도 100초가 되지만 이 경우 10번은 최소 횟수가 아니기 때문이 답이 될 수 없다. 이 경우 B 1번, C 4번, 총 5번이 최소버튼 조작이다. 그리고 T=234와 같이 3개의 버튼으로 시간을 정확히 맞출 수 없는 경우도 있다.

여러분은 주어진 요리시간 T초를 맞추기 위한 최소버튼 조작 방법을 구하는 프로그램을 작성해야 한다.

제한 조건

• 시간 제한 : 1초
• 풀이 시간 : 30분

입력

• 첫 번째 줄에는 요리시간 T(초)가 정수로 주어져 있으며 그 범위는 1 ≤ T ≤ 10,000 이다.

출력

• 러분은 T초를 위한 최소버튼 조작의 A B C 횟수를 첫 줄에 차례대로 출력해야 한다. 각각의 횟수 사이에는 빈 칸을 둔다.
• 해당 버튼을 누르지 않는 경우에는 숫자 0을 출력해야한다.
• 만일 제시된 3개의 버튼으로 T초를 맞출 수 없으면 음수 -1을 첫 줄에 출력해야 한다.

예시

풀이

동작 시간이 가장 큰 버튼부터 몇 번을 눌러야하는지 카운트하면 시간 복잡도 O(N)으로 간단하게 풀이가 가능하다.

먼저 입력되는 시간이 초단위이므로 각 버튼의 시간을 초단위로 변경한다.

• A : 300초
• B : 60초
• C : 10초

그리고 각 버튼별로 몇 번의 입력이 필요한지 카운트한다. 카운팅은 남은 시간 t를 버튼의 시간으로 나눈 몫을 필요한 버튼 입력 수, 나머지는 다음 버튼 연산에 사용하면 된다. 각 버튼별 연산이 종료된 후에도 남은 시간이 0이 아니라면 -1을 출력하면 된다.

코드

• 코드

타로는 자주 JOI잡화점에서 물건을 산다. JOI잡화점에는 잔돈으로 500엔, 100엔, 50엔, 10엔, 5엔, 1엔이 충분히 있고, 언제나 거스름돈 개수가 가장 적게 잔돈을 준다. 타로가 JOI잡화점에서 물건을 사고 카운터에서 1000엔 지폐를 한장 냈을 때, 받을 잔돈에 포함된 잔돈의 개수를 구하는 프로그램을 작성하시오.

제한 조건

• 시간 제한 : 1초
• 풀이 시간 : 30분

입력

• 입력은 한줄로 이루어져있고, 타로가 지불할 돈(1 이상 1000미만의 정수) 1개가 쓰여져있다.

출력

• 제출할 출력 파일은 1행으로만 되어 있다. 잔돈에 포함된 매수를 출력하시오.

예시

풀이

처음에는 HashMap을 활용하여 풀이를 생각했다.

• key -> 동전
• value -> 필요한 동전의 개수

그리고 가장 큰 동전부터 거스름 돈을 나누며 필요한 동전의 개수를 구한다.

• 몫 -> 필요한 동전의 개수
• 나머지 -> 0이 아니면 다음 동전으로 나누기 연산

그리고 HashMap의 value를 모두 더한 값을 출력하려고 했다.

하지만 코드를 작성하면서 보니 어차피 각 동전별 연산은 1번씩만 하면 충분하다. 즉, HashMap 없이 동전을 꺼내와 연산을 할 때마다 발생하는 몫을 더하면 되는 것이다.

이 풀이는 동전의 개수만큼만 연산하는 O(N)의 시간 복잡도를 가진다.

코드

• 코드

• 시간 제한 : 2초
• 풀이 시간 : 30분

문제

옛날 옛적에 수학이 항상 큰 골칫거리였던 나라가 있었다. 이 나라의 국왕 김지민은 다음과 같은 문제를 내고 큰 상금을 걸었다. 길이가 N인 정수 배열 A와 B가 있다. 다음과 같이 함수 S를 정의하자.

S = A[0] × B[0] + ... + A[N-1] × B[N-1]

S의 값을 가장 작게 만들기 위해 A의 수를 재배열하자. 단, B에 있는 수는 재배열하면 안 된다. S의 최솟값을 출력하는 프로그램을 작성하시오.

입력

• 첫째 줄에 N이 주어진다.
• 둘째 줄에는 A에 있는 N개의 수가 순서대로 주어지고, 셋째 줄에는 B에 있는 수가 순서대로 주어진다.
• N은 50보다 작거나 같은 자연수이고, A와 B의 각 원소는 100보다 작거나 같은 음이 아닌 정수이다.

출력

• 첫째 줄에 S의 최솟값을 출력한다.

예시

풀이

배열 A, B의 길이는 N으로 동일하며, 0 < N <= 50이다. 배열의 원소는 0 <= 원소 <= 100이다.

이 문제에는 배열 A를 재배열하여 S의 최솟값을 구하라고 나와 있다. 하지만 실제 출력값에 필요한 것은 S의 최솟값이다.

S의 최솟값을 구하려면 배열 A, B의 각 원소들을 곱하여 더했을 때 최솟값이 나오면 된다.

• A -> 오름차순 정렬
• B -> 내림차순 정렬

위와 같이 정렬하여 각 원소를 곱하여 더한 값을 출력하면 간단하게 풀린다.

이 문제에 필요한 자료구조는 ArrayList다.

이 문제의 시간 복잡도는 각 배열의 정렬에 O(NloN), 각 원소를 곱하고 더하는데 O(N)이 된다. 즉, O(NlogN)의 시간 복잡도를 가지게 된다. 각 배열의 최대 크기는 100이므로 이 문제를 풀이할 수 있다.

코드

• 코드

웹 사이트의 주소는 전송받고 싶은 웹 페이지를 이용하는 것으로 URL(Uniform Resource Locator)이라고 한다. URL은 스키마, 호스트명, 포트 번호, 자원의 경로로 구성된다. 포트 번호는 웰 노운 포트로 생략될 수 있다.

{스키마}://{호스트명}:{포트 번호}/경로 ex) http://www.naver.com/index.html

• 스키마 : 웹 브라우저가 웹서버에 접속하기 위한 프로토콜

URL과 URI

URL은 이름 그대로 원하는 웹 서버 내에 있는 자원의 경로를 가르킨다. 반면, URI(Uniform Resource Identifier)는 자원을 식별하기 위한 방법으로 URL보다 더 상위의 개념이다. 원하는 자원에 대한 식별 정보를 요청하면 웹 서버가 이에 해당하는 자원을 찾아 반환한다.

• http://www.naver.com는 웹 서버를 가리키므로 URL이면서 URI다.
• http://www.naver.com/page/home/document/example.pdf는 example.pdf라는 자원의 위치를 가리키므로 URL이면서 URI다.
• http://www.naver.com/admin/users/335985는 유저에 대한 식별 정보를 가지므로 URI다.
• http://www.naver.com/admin/users?id=335985는 query string이 유저에 대한 식별 정보를 제공하므로 URI다. 하지만 query string을 제외하면 user 자원이 있는 위치를 가리키고 있으므로 URL이면서 URL다.

데이터 송수신

웹 서버와 웹 브라우저는 HTTP 메시지를 통해 요청과 응답을 주고 받는다. 이 과정에서 웹 브라우저는 HTTP 메세지의 일부 내용을 쿠키로 저장하여 사용자의 로그인 정보, 웹 페이지 열람 이력 등 특정 정보를 저장한다. 이 것을 활용해 웹 페이지를 사용해 취향에 맞는 정보를 제공하는 등의 서비스를 제공하기도 한다.

HTTP Header

• HTTP Request

• HTTP Response

웹 브라우저와 웹 서버 사이에 프록시 서버를 두는 경우가 있다. 프록시는 대리라는 의미로 말 그대로 웹 사이트 접속을 대행하는 서버다. 이를 통해 요청되는 모든 URL을 모니터링이 가능하다. 여기서 URL 필터링을 통해 요청을 제한할 수도 있다. 또한 트래픽을 분산시켜 한 서버에 과부화가 걸리는 것을 방지할 수 있다.

웹 동작 흐름

1. 사용자가 브라우저에 URL 입력
2. DNS가 URL에 대응하는 IP를 찾기 위해 동작(이름 해석)
3. 네트워크를 돌아다니며 목적지 IP에 대응하는 MAC 주소를 찾기 위해 ARP 실행(주소 해석)
4. 웹 서버와 TCP 3way Handshake를 통해 커넥션 생성
5. HTTP Request 메시지 전송
6. HTTP Response 메시지 수신
7. 웹 브라우저 화면 렌더링
8. TCP 커넥션 종료(HTTP 헤더의 커넥션 옵션을 따름)

웹 접속에 이용하는 프로토콜

네트워크를 구성하는 방법 중 하나로 CSMA/CD 프로토콜을 사용해서 통신한다.

이더넷은 네트워크에 연결된 각 기기들이 48비트 길이의 고유의 MAC 주소를 가지고 이 주소를 이용해 상호간에 데이터를 주고 받을 수 있도록 만들어졌다.

이더넷은 RJ-45 잭을 인터페이스로 활용하고 UTP 케이블을 통해 데이터를 전송한다. 그리고 CSMA/CD 프로토콜을 사용하여 통신을 한다. 즉, OSI 7 Layer 중 1(물리), 2(데이터 링크) 계층에서의 통신 프로토콜을 정의하는 네트워크 기술이다. 이더넷의 규격은 IEEE 802 위원회에서 결정된다.

이더넷의 전송 범위는 이더넷 인터페이스부터 이더넷 인터페이스까지다. 이 중간에는 Layer 2/3 Switch, 라우터 등이 동일 네트워크나 다른 네트워크에 있는 이더넷 인터페이스로 데이터를 전송할 수 있도록 도와준다.

MAC 주소

MAC 주소는 이더넷 인터페이스를 식별하기 위한 48bit 주소다. MAC 주소는 벤더(제조사) 식별 코드 인 OUI(Organizationally Unique Identifier)와 각 벤더가 할당하는 시리얼 넘버로 각 24bit씩 구성된다.

표기 방법은 다음과 같이 3가지 방식을 쓴다.

• 1byte씩 '-'로 구분 : 00-00-01-02-03-04
• 1byte씩 ':'로 구분 : 00:00:01:02:03:04
• 2byte씩 '.'로 구분 : 0000.0102.0304

이더넷 헤더

CSMA/CD(Carrier Sense Multiple Access with Collision Detector)

네트워크에서 기기들을 연결하는 형태(토폴로지)는 주로 3가지가 존재한다.

CSMA/CD는 3가지 중 버스형 토폴로지는 버스형 토폴로지의 전송 제어를 위한 매커니즘이다. 초기에는 동축 케이블을 버스형 토폴로지의 전송 매체로 사용했었다. 이 방식은 하나의 전송 매체를 복수의 기기가 공유하기 때문에 한 번에 하나의 기기만 전송이 가능했다. 그래서 CSMA/CD는 다음과 같은 매커니즘을 사용한다.

• 케이블이 사용 가능하면 전송
• 케이블이 사용 중이면 대기 후 전송
• 전송 중 충돌이 발생하면 랜덤 시간 대기 후 재전송

하지만 현대에는 네트워크 허브가 등장하면서 네트워크의 형태가 버스형에서 스타형으로 변경되어었다. 허브가 업그레이드가 되어 '스위칭 허브' 또는 'L2 스위치'로 변경됨에 따라, 이더넷은 실질적으로 충돌 자체가 발생하지 않는 구조로 바뀌었다. 그래서 현재의 이더넷은 충돌이 발생하지 않는 구조지만, 과거와의 호환성 문제로 여전히 이더넷 표준으로 포함되어 있다.

• 풀이 시간 : 20분
• 시간 제한 : 1초

문제

행복 왕국의 왕실 정원은 체스판과 같은 8 × 8 좌표 평면이다. 왕실 정원의 특정한 한 칸에 나이트가 서있다. 나이트는 매우 충성스러운 신하로서 매일 무술을 연마한다. 나이트는 말을 타고 있기 때문에 이동을 할 때는 L자 형태로만 이동할 수 있으며 정원 밖으로는 나갈 수 없다. 나이트는 특정 위치에서 다음과 같은 2가지 경우로 이동할 수 있다.

1. 수평으로 두 칸 이동한 뒤에 수직으로 한 칸 이동하기
2. 수직으로 두 칸 이동한 뒤에 수평으로 한 칸 이동하기

이처럼 8 × 8 좌표 평면상에서 나이트의 위치가 주어졌을 때 나이트가 이동할 수 있는 경우의 수를 출력하는 프로그램을 작성하라. 왕실의 정원에서 행 위치를 표현할 때는 1부터 8로 표현하며, 열 위치를 표현할 때는 a 부터 h로 표현한다.

입력

• 첫째 줄에 8x8 좌표 평면상에서 현재 나이트가 위치한 곳의 좌표를 나타내는 두 문자로 구성된 문자열이 입력된다. 입력 문자는 a1 처럼 열과 행으로 이뤄진다.

출력

• 첫째 줄에 나이트가 이동할 수 있는 경우의 수를 출력하시오.

예시

풀이

나이트가 이동할 수 있는 경우의 수를 그려보면 다음과 같다.

여기서 발생할 수 있는 좌표 이동을 작성해보면 다음과 같다.

(1, 2) (1, -2) (-1, 2) (-1, -2) (2, 1) (2, -1) (-2, 1) (-2, -1)

나는 2가지 경우로 나눠서 생각했지만 좌표 이동으로 따져보니 사실은 동일한 이동이었다. 결과적으로 입력받은 좌표에 대해서 발생할 수 있는 경우의 수는 8개만 존재한다는 것이다.

즉, O(N)의 시간 복잡도로 연산해도 문제가 없으므로 입력 받은 좌표에 8개의 좌표 이동을 한 결과가 좌표 평면을 벗어났는지 확인만 하면 된다. 열 이동은 char 연산을 통해 a <= x <= h를 확인하고, 행 이동은 int 연산을 통해 1 <= y <= 8을 확인하여, 이 조건들을 충족하면 이동 가능한 경우의 수로 카운트하면 된다.

코드

• 코드
• 테스트 케이스

사람들은 IP 주소만으로는 어떤 Application을 지칭하는지 알기 어렵다. 그래서 사람들은 IP 주소 대신 호스트명을 통해 요청을 보내게 되며, DNS(Domain Name Service)가 자동으로 요청받은 호스트명에 대응하는 IP주소를 찾아주는 이름 해석을 처리한다.

이렇게 호스트명에 대응하는 IP 주소를 DNS 서버에 질의하는 기능은 DNS 리졸버라고 하며 OS에 내장되어 있다. DNS 리졸버는 Local 서버 내에 호스트명이 없을 경우 Root 서버부터 다른 서버들에게 돌아가면서 질의하는 이름 해석을 반복하게 된다. 이처럼 이름 해석을 반복해서 묻는 것을 재귀 질의라고 한다.

DNS 동작 순서

유저가 www.naver.com을 요청했을 경우 다음과 같은 순서로 DNS 리졸버가 작동한다.

1. Local Host File 참조
2. Local DNS에 질의
3. Root DNS에 질의
4. Top Level Domain에 질의 - .com
5. Second Level Domain에 질의 - .naver.com
6. Subdomain에 질의 - www.naver.com
7. Local DNS는 알아낸 IP 주소를 TTL만큼 캐싱한다.

• TTL(Time To Live) : 캐시가 유효한 시간

• 풀이 시간 : 15분
• 시간 제한 : 2초

문제

정수 N이 입력되면 00시 00분 00초부터 N시 59분 59초까지의 모든 시각 중에서 3이 하나라도 포함되는 모든 경우의 수를 구하는 프로그램을 작성하라. 예를 들어 1을 입력했을 때, 다음은 3이 하나라도 포함되어 있으므로 세어야 하는 시각이다.

• 00시 00분 03초
• 00시 13분 30초

반면에 다음은 3이 하나도 포함되어 있지 않으므로 세면 안 되는 시각이다.

• 00시 02분 55초
• 01시 27분 45초

입력

• 첫째 줄에 정수 N이 입력된다.(0<=N<=23)

출력

• 00시 00분 00초부터 N시 59분 59초까지의 모든 시각 중에서 3이 하나라도 포함되는 모든 경우의 수를 출력한다.

예시

풀이

각 시, 분, 초에서 3이 있는 경우와 없는 경우로 분리하여 경우의 수를 구하면 O(N)으로 풀이가 가능하다고 생각했다.

• 초에 3이 있는 경우

  초에 3이 있는 경우는 10초대와 1초대로 분류할 수 있다. 1초대의 경우는 03 13 23 33 43 53으로 6개가 존재한다. 10초대의 경우는 30 31 32 33 34 35 36 37 38 39으로 10개가 존재하나 1초대에 33이 이미 카운트됐으므로 9개가 존재한다. 결과적으로 초에 3이 있는 경우는 총 15개다.

• 분에 3이 있는 경우 분에 3이 있는 경우는 모든 초를 다 카운트하므로 60개다.

• 분에 3이 없는 경우 분에 3이 없는 경우는 초에 3이 있는 경우와 동일하므로 15개다.

• 시에 3이 있는 경우 시에 3이 있는 경우는 모든 분,초를 다 카운트 하므로 6060인 *3600개**다.

• 시에 3이 없는 경우 시에 3이 없는 경우는 (분에 3이 있는 경우의 수 * 모든 초(60)) + (분에 3이 없는 경우의 수 * 초에 3이 있는 경우의 수(15))이므로 (15 * 60) + (45 * 15)인 1575개다.

결과적으로 0시부터 입력되는 N시를 포함하는 시간까지 3이 있는 경우의 수와 없는 경우의 수를 찾아 각 경우의 수를 더해주면 된다.

이슈

문제를 풀고나서 해설을 확인해봤는데, 단순하게 3중 for문을 사용해서 각 시,분,초에 3이 존재하는지 확인하고 있다. 입력받는 시간의 범위가 0-23으로 정해져 있고, 분/초 또한 최대 크기가 60이다. 즉, 아무리 많이 연산해봐야 24 * 60 * 60 = 86400개 밖에 되지 않는다는 것이다. 그러므로 총 경우의 수가 10만개도 되지 않으므로 3중 for문을 활용해 모든 경우의 수를 계산해도 2초 안에 풀이가 가능하다. 이런 방식의 풀이를 완전 탐색이라고 한다.

완전 탐색 알고리즘은 비효율적인 시간 복잡도를 가지나 탐색해야 할 경우의 수가 100만개 이하라면 완전 탐색을 선택할 수 있다.

이 해설을 보고나서 깨달은 것은 무조건 더 좋은 시간 복잡도를 선택할 필요는 없다는 것이다. 코딩 테스트의 목표는 더 빠르고 더 좋은 알고리즘을 만드는 것이 것이 아닌 현재 상황에 맞는 가장 합리적인 방법을 찾아 문제를 해결하는 것이기 때문이다. 그래서 문제의 제한 조건이 여유가 있고, 입력값의 범위가 충분히 작다면 시간 복잡도가 좀 더 높아도 더 빠르고 단순하게 접근하여 풀이가 가능하다면 굳이 시간을 투자해 더 빠른 알고리즘을 구현할 필요는 없다.

코드

• 코드(내 풀이 - solution | 해설 - solutionAnswer)
• 테스트 케이스

Application 간의 데이터 전송을 위한 프로토콜이며, 신뢰성을 확보해주는 절차를 가진다.

TCP는 Connection 맺기 - Application 간 데이터 송수신 - Connection 끊기 프로세스를 가진다. Connection을 맺고 끊을 때는 각각 3way/4way Handshaking을 한다.

TCP 커넥션이 맺어지면 Application 간의 데이터를 전송하기 시작한다. 이 때 TCP는 데이터 크기나 네트워크 상황에 따라 제어를 하며, Flow Control이라고 한다.

TCP에서 한 번에 전송할 수 있는 크기를 MSS(Maximum Segment Size)라고 한다. MSS를 넘는 데이터를 전송할 경우에는 MSS를 기준으로 분할하여 전송한다.

3way Handshaking

1. Client가 Server에 연결 요청을 보낸다.
2. Server가 Client에게 요청에 대한 응답으로 Ack를 반환함과 동시에 Client에게 연결 요청을 보낸다.
3. Client가 Ack로 Server의 요청에 응답하여 TCP 연결이 성사된다.

4way Handshakinh

1. Client가 Server에게 연결 종료 요청을 보낸다.
2. Server가 요청에 대한 응답으로 Ack를 반환하고, 현재 진행 중인 데이터 통신이 있다면 끝날 때까지 기다린다.
3. 통신이 끝나면 Client에게 연결 종료 요청을 보낸다.
4. Client가 Ack로 Server의 요청에 응답하여 TCP 연결이 종료된다.

Flow Control

1. 데이터 크기가 크면 분할하고, 이 정보를 TCP 헤더에 기술한다.
2. 데이터를 전송하고 Ack(수신확인)을 받아 결과를 체크한다.
3. 네트워크 상태에 따라 전송 속도를 제한한다.
4. 데이터를 수신한 Application은 TCP 헤더를 참조하여 원본 데이터로 조립한다.

TCP 헤더

UDP(User Datagram Protocol)

전송 신뢰도를 보장하지 않고 Application에 일방적으로 데이터를 전송한다.

데이터 전송 신뢰도를 보장하지 않는 단순한 구조를 가지고 있기 때문에 TCP보다 전송 속도가 빠르다. 또한 데이터를 분할하는 기능이 없기 때문에 필요시 직접 분할하여 전송해야 한다.

UDP 헤더

• 풀이 시간 : 15분
• 시간 제한 : 1초

문제

여행가 A는 N × N 크기의 정사각형 공간 위에 서 있다. 이 공간은 1 × 1 크기의 정사각형으로 나누어져 있다. 가장 왼쪽 위 좌표는 (1, 1)이며, 가장 오른쪽 아래 좌표는 (N, N)에 해당한다. 여행가 A는 상, 하, 좌, 우 방향으로 이동할 수 있으며, 시작 좌표는 항상 (1, 1)이다. 우리 앞에는 여행가 A가 이동할 계획이 적힌 계획서가 놓여 있다.

계획서에는 하나의 줄에 띄어쓰기를 기준으로 L, R, U, D 중 하나의 문자가 반복적으로 적혀있다. 각 문자의 의미는 다음과 같다.

L: 왼쪽으로 한 칸 이동 R: 오른쪽으로 한 칸 이동 U: 위로 한 칸 이동 D: 아래로 한 칸 이동

이때 여행가 A가 N × N 크기의 정사각형 공간을 벗어나는 움직임은 무시된다. 예를 들어 (1, 1)의 위치에서 L 혹은 U를 만나면 무시된다. 다음은 N = 5인 지도와 계획이다.

이 경우 6개의 명령에 따라서 여행가가 움직이게 되는 위치는 순서대로 (1, 2), (1, 3), (1, 4), (1, 4), (2, 4), (3, 4)이므로, 최종적으로 여행가 A가 도착하게 되는 곳의 좌표는 (3, 4)이다. 다시 말해 3행 4열의 위치에 해당하므로 (3, 4)라고 적는다. 계획서가 주어졌을 때, 여행가 A가 최종적으로 도착할 지점의 좌표를 출력하는 프로그램을 작성하시오.

입력

• 첫째 줄에 공간의 크기를 나타내는 N이 주어집니다. (1 <= N <= 100)
• 둘째 줄에 여행가 A가 이동할 계획서 내용이 주어집니다. (1 <= 이동 횟수 <= 100)

출력

• 첫째 줄에 여행가 A가 최종적으로 도착할 지점의 좌표 (X, Y)를 공백으로 구분하여 출력한다.

입력 예시

풀이

이 문제에서의 포인트는 3가지다.

1. (y, x) 좌표 구성
2. y에서 down 이동이 +1 이동
3. 정사각형 공간의 지도

위 포인트를 생각하며 좌표 객체를 만들면 간단하게 해결할 수 있다.

좌표 객체는 x, y와 matrixSize를 가진다. 그리고 setter를 통해서 좌표 이동을 하도록 한다. setter는 matrixSize를 충족할 때만 set되도록 한다.

solution 메서드에서는 switch-case 구문을 이용해 L/R/U/D에 해당하는 이동을 지정해주면 끝난다.

이슈

풀이가 간단하다고 생각해서 문제가 제시하는 3가지 중요한 조건들을 제대로 파악하지 않고 코드를 작성하려고 했다. 결국 간단한 풀이임에도 불구하고 코드를 작성하는데 실패했다.

또한 작성한 코드를 리팩토링하기 전에는 solution 메서드에 moveX, moveY 메서드를 정의하여 setter가 있음에도 중복된 메서드를 만들었다. 풀이하며 객체를 정의하게 되는 경우에는 어떤 역할을 하는 객체인지 명확하게 정의하고, 해당 객체가 단일 책임(SRP)을 가지도록 하여 의존성이 발생하지 않도록 하자.

코딩 테스트 문제를 풀 때 가장 중요한 것은 문제를 빨리 푸는 것이 아니라 문제를 잘 읽고 정확한 결과를 내는 것을 명심하자.

코드

• 코드
• 테스트 케이스