DeJa
Techvu
DeJa
전체 방문자
51,021
오늘
19
어제
54
  • Techvu (60)
    • DesignPatterns (3)
      • 생성 (0)
      • 구조 (1)
      • 행동 (2)
    • Refactoring (0)
    • DataStructures (0)
    • Algorithms (24)
      • 기본 지식 (12)
      • 문제 풀이 (12)
    • OOP (0)
    • TDD (2)
    • DDD (0)
    • Programming Languages (9)
      • Java (9)
      • Kotlin (0)
    • Spring (1)
    • JPA (7)
    • Web (1)
      • 기본 지식 (1)
      • 실무 경험 (0)
    • CS (12)
      • Network (1)
      • OS (8)
      • DataBase (3)
      • Server (0)
    • Git (1)
    • Conferences (0)

블로그 메뉴

  • 홈
  • 태그
  • 미디어로그
  • 위치로그
  • 방명록

공지사항

  • Study
  • GitHub
  • Medium Blog

인기 글

  • 스키마(Schema)
    2022.01.08
    스키마(Schema)
  • 자바 버전별 역사 및 특징
    2022.01.12
    자바 버전별 역사 및 특징
  • 깃허브 사용 방법
    2021.12.15
    깃허브 사용 방법
  • 동시성 이슈(Concurrency Issue)
    2022.03.20
    동시성 이슈(Concurrency Issue)
  • JPA 는 과연 1차 캐시를 통해서 Repeatable R⋯
    2021.12.27
    JPA 는 과연 1차 캐시를 통해서 Repeatable R⋯

태그

  • TDD
  • network
  • CS
  • DATABASE
  • 알고리즘
  • java
  • JPA
  • web
  • Spring
  • OS
  • 디자인패턴

최근 댓글

  • 글 잘읽고 가요.
    아이폰
  • 컴파일러자체에서 꼬리재귀를 지원하지 않으니 static으로⋯
    aaa
  • 압도적 감사
    ㅇㅇㅇ

최근 글

  • Write a test code right now
    2022.03.24
    Write a test code right now
  • 동시성 이슈(Concurrency Issue)
    2022.03.20
    동시성 이슈(Concurrency Issue)
  • POJO, JavaBean, Entity, VO, DTO
    2022.02.08
    POJO, JavaBean, Entity, VO, DTO
  • TDD with Agile
    2022.02.05
    TDD with Agile
  • Java Stream 기초
    2022.01.23
    Java Stream 기초

티스토리

hELLO · Designed By 정상우.
DeJa

Techvu

[BOJ 18353] 병사 배치하기
Algorithms/문제 풀이

[BOJ 18353] 병사 배치하기

2022. 1. 11. 14:27
728x90

병사 배치하기

BOJ 18353 : 병사 배치하기

해설

이 문제는 최장 증가 부분 수열(LIS) 문제로, 부분 수열에 대한 개념과 LIS 알고리즘 풀이 방법을 모른다면 링크를 통해 배우도록 하자.

  • ✔ 병사를 배치할 때, 앞쪽에 있는 병사의 전투력이 항상 뒤쪽보다 높아야 한다.
    • ✔ 즉, 최종 결과 안에 전투력이 중복된 병사가 존재하면 안된다.
  • ✔ 특정 위치에 있는 병사를 열외 시킨다는 의미
    • ✔ 입력 값이 주어지면 따로 내림차순 혹은 오름차순으로 정렬한 다음 계산하는 것이 아니라, 주어진 입력 값에서 특정 위치에 있는 병사를 제거하여 문제의 조건을 만족하라는 의미

따라서, 주어진 입력 값에서 특정 위치에 있는 병사를 제거하여, 앞쪽에 있는 병사의 전투력이 뒤 쪽에 있는 병사의 전투력보다 높도록 하되, 남아있는 병사의 수가 최대가 되도록 해라

이 문제는, 입력 값을 뒤집어서 LIS 알고리즘을 사용하여 해결할 수 있다.

문제에서 입력 값이 2000 으로 제한되어있기 때문에 O(N^2) 으로 풀어도된다. 만약에 2000이 넘어 갔다고하면 O(NlogN) 방식으로 문제를 풀어야 한다.

구현 : O(N^2)

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.Scanner;

// 병사 배치하기
public class Main {

    static int N;
    static int[] dp;
    static int answer;
    static List<Integer> list = new ArrayList<>();

    public static void main(String[] args) {
        input();
        solution();
        System.out.println(answer);
    }

    static void input() {
        Scanner sc = new Scanner(System.in);
        N = sc.nextInt();
        for (int i = 0; i < N; i++) {
            list.add(sc.nextInt());
        }
    }

    static void solution() {
        dp = new int[list.size()];

        Collections.reverse(list);

        // dp 초기화
        for (int i = 0; i < N; i++) {
            dp[i] = 1;
        }

        for (int i = 1; i < list.size(); i++) {
            for (int k = 0; k < i; k++) {
                int prev = list.get(k);
                int next = list.get(i);
                if(next > prev) {
                    dp[i] = Math.max(dp[i], dp[k] + 1);
                }
            }
        }

        // 열외해야 하는 병사의 최소 수를 출력
        int maxValue = 0;
        for (int i = 0; i < N; i++) {
            maxValue = Math.max(maxValue, dp[i]);
        }
        answer = N - maxValue;
    }
}

구현 : O(NlogN)

import java.util.*;

public class Main {

    static int N;
    static int[] dp;
    static int answer;
    static List<Integer> list = new ArrayList<>();

    public static void main(String[] args) {
        input();
        solution();
        System.out.println(getAnswer());
    }

    static void input() {
        Scanner sc = new Scanner(System.in);
        N = sc.nextInt();
        for (int i = 0; i < N; i++) {
            list.add(sc.nextInt());
        }
    }

    static void solution() {
        dp = new int[list.size()];

        Collections.reverse(list);

        Arrays.fill(dp, Integer.MAX_VALUE);
        dp[0] = list.get(0);

        int dpIndexByLastUpdated = 0;
        for (int i = 1; i < list.size(); i++) {
            int next = list.get(i);
            int lastValueInDp = dp[dpIndexByLastUpdated];
            if(lastValueInDp < next) {
                dp[++dpIndexByLastUpdated] = next;
            } else {
                int findIndex = binarySearch(0, dpIndexByLastUpdated, next);
                dp[findIndex] = next;
            }
        }
    }

    /**
     * 이진 탐색을 통해서 next 가 dp 의 어느 index 에 들어가야하는지, 알맞은 index 를 찾는다.
     * @param start 0
     * @param end dpIndexByLastUpdated
     * @param target 비교 대상인 다음 값(next)
     */
    static int binarySearch(int start, int end, int target) {
        int index = 0;
        while(start <= end) {
            int middle = (start + end) / 2;

            if(dp[middle] >= target) {
                end = middle - 1;
                index = middle;
            }
            else{
                start = middle + 1;
            }
        }
        return index;
    }

    /**
     * dp 에 Integer.MAX_VALUE 가 아닌 값들에 대해서 개수를 카운트한다.
     */
    static int getAnswer() {
        int count = 0;
        for(int i = 0; i < dp.length; i++) {
            if(dp[i] == Integer.MAX_VALUE) {
                break;
            }
            count++;
        }
        answer = N - count;
        return answer;
    }
}
728x90
저작자표시 비영리 동일조건
  • 카카오스토리
  • 트위터
  • 페이스북

'Algorithms > 문제 풀이' 카테고리의 다른 글

2020 카카오 신입 공채 : 문자열 압축  (0) 2022.01.18
이것이 코딩 테스트다 : 편집 거리  (0) 2022.01.18
이것이 코딩테스트다 : 금광  (0) 2022.01.07
[BOJ 14502] 연구소  (0) 2022.01.06
[BOJ 15686] 치킨 배달  (0) 2022.01.03
    'Algorithms/문제 풀이' 카테고리의 다른 글
    • 2020 카카오 신입 공채 : 문자열 압축
    • 이것이 코딩 테스트다 : 편집 거리
    • 이것이 코딩테스트다 : 금광
    • [BOJ 14502] 연구소
    알고리즘
    DeJa
    DeJa
    Tech Blog
    댓글쓰기
    이것이 코딩 테스트다 : 편집 거리
    다음 글
    이것이 코딩 테스트다 : 편집 거리
    이것이 코딩테스트다 : 금광
    이전 글
    이것이 코딩테스트다 : 금광

    티스토리툴바