npx create-next-app@latest

프로젝트를 생성하고 나면 실행은 잘 되지만 import 라인에서 Parsing error: Cannot find module 'next/babel' 에러가 발생합니다. ESLint에서 next/babel을 읽어오지 못하는 에러인데요, eslintrc.json파일만 살짝 수정해서 ESLint 설정을 바꿔주면 해결할 수 있습니다.

//next/babel 추가
{
  "extends": ["next/babel", "next/core-web-vitals"]
}

또는 Next 공식 docs에서 제안하는 방식인 .babelrc / babel.config.js 파일을 루트 디렉토리에 직접 추가해서 source of truth을 직접 생성할 수 있습니다.

{
  "presets": ["next/babel"],
  "plugins": []
}

참고링크 Stackoverflow Next docs

JavaScript (JS)에는 함수를 정의하는 다양한 방식이 있습니다. ES6 이후로 등장한 화살표 함수(arrow function)는 그 전의 function 키워드로 정의하는 방식과는 몇 가지 중요한 차이점을 지니고 있습니다.

1.function 사용법

ES6 이전에는 함수를 정의하기 위해 function 키워드를 사용했습니다. function 키워드로 생성한 함수는 인스턴스를 생성하며 내부에 Function.prototype을 빈 객체로 생성합니다.

function foo1() {
  console.log(arguments);
}

const foo2 = () => {
  console.log(arguments);
};

console.log(foo1.prototype);
// {constructor: ƒ}
console.log(foo2.prototype);
// undefined

또한 function을 생성자 함수로 사용해 새로운 객체를 생성할 수도 있습니다. 이 경우 호출 시 앞에 new 를 붙이지 않으면 일반 함수로 작동합니다.

function Person(name) {
  this.name = name;

  this.sayHello = function () {
    console.log(`${this.name} says 'Hello World!'`);
  };
}

const person1 = new Person("AA");
const person2 = new Person("Ben Brode");
const person3 = Person("CC");

person1.sayHello(); // AA says 'Hello World!'
person2.sayHello(); // Ben Brode says 'Hello World!'
person3.sayHello(); // Uncaught TypeError TypeError: Cannot read properties of undefined (reading 'sayHello')

VSCode에서는 위와 같은 suggestion이 뜹니다. Quick Fix를 통해 친절하게 ES6부터 등장한 Class 생성자로 변환할 수 있습니다.

class Person {
    constructor(name) {
        this.name = name;

        this.sayHello = function () {
            console.log(`${this.name} says 'Hello World!'`);
        };
    }
}

일반 함수의 this는 함수 호출 위치에 따라 달라집니다.

var foo = function () {
  console.dir(this);
};

// 1. 함수 호출
foo(); // window
// window.foo();

// 2. 메소드 호출
var obj = { foo: foo };
obj.foo(); // obj

// 3. 생성자 함수 호출
var instance = new foo(); // instance

// 4. apply/call/bind 호출
var bar = { name: 'bar' };
foo.call(bar);   // bar
foo.apply(bar);  // bar
foo.bind(bar)(); // bar

이에 따라 콜백 함수에서 this가 의도치 않게 바인딩될 수도 있습니다.

const obj1 = {
    name: 'ObjectWithoutCalloutFunction',
    showName: function() {
      console.log(this.name);
    }
  };

obj1.showName(); // 'ObjectWithoutCalloutFunction',

const obj2 = {
  name: 'ObjectWithCalloutFunction',
  showName: function() {
    setTimeout(function() {
      console.log(this.name);
    }, 1000);
  }
};

obj2.showName(); // undefined(Timeout 함수의 this.name)

위의 예시의 경우, this는 setTimeout 함수의 스코프에 속한 this를 사용합니다.

이렇게 유동적인 this 문제점을 해결하기 위해 bind 메소드를 사용할 수 있습니다. 또는 var self = this 와 같이 추가 변수에 의도하는 this를 할당을 해도 됩니다.

// Solution 1 : this 바인딩
const obj3 = {
  name: "ObjectBinded",
  showName: function () {
    setTimeout(
      function () {
        console.log(this.name);
      }.bind(this),
      1000
    );
  },
};

// Solution 2 : self = this
const obj4 = {
  name: "ObjectSelf",
  showName: function () {
    const self = this;
    setTimeout(function () {
      console.log(self.name);
    }, 1000);
  },
};

3. Arrow Function의 등장

ES6에서 새롭게 추가된 화살표 함수는 이러한 문제를 해결하기 위해 등장했습니다. 화살표 함수는 this 바인딩을 하지 않고 언제나 상위 스코프의 this를 참조합니다. 이를 lexical this라고 합니다.

const obj4 = {
  name: "ObjectWithArrowFunction",
  showName: function () {
    setTimeout(() => {
      console.log(this.name);
    }, 1000);
  },
};

생성될 때의 상위 스코프의 this를 그대로 사용하므로, this 바인딩 문제를 신경 쓸 필요가 없습니다.

다만 이벤트 리스너의 콜백 함수에 화살표 함수를 전달하는 경우 this가 언제나 상위 객체인 window를 호출함에 주의합시다.

// HTML 요소 생성
const button = document.getElementById('button');
button.textContent = '버튼';

// 화살표 함수를 이벤트 핸들러로 등록
button.addEventListener('click', () => {
  console.log(this); // this는 window 객체를 가리킴
  console.log(this.textContent); // this는 window 객체를 가리키므로 undefined (textContent는 window 객체에 없음)
});

4. 화살표 함수의 특징

1. 간결한 문법: 화살표 함수는 간결한 문법을 제공합니다. 특히 단일 표현식을 반환하는 경우 중괄호와 return 키워드도 생략할 수 있습니다.

    const add = (a, b) => a + b;

2. 암묵적 반환: 중괄호가 없는 경우 표현식의 결과가 자동으로 반환됩니다.

    const square = x => x * x;

3. this 바인딩: 화살표 함수는 고유의 this를 가지지 않기 때문에 언제나 상위 스코프의 this를 반환합니다.

1. 문제 설명

마포구에는 모든 대학생이 입사를 희망하는 굴지의 대기업 ㈜승범이네 본사가 자리를 잡고 있다. 승범이는 ㈜승범이네의 사장인데, 일을 못 하는 직원들에게 화가 난 나머지 전 직원을 해고하고 신입사원을 뽑으려 한다. 1차 서류전형이 끝난 뒤 합격자들은 면접을 준비하게 되었다.

면접자들은 서로 다른 N개의 도시에 거주한다. 승범이는 면접자들의 편의를 위해 거주 중인 N개 도시 중 K개의 도시에 면접장을 배치했다. 도시끼리는 단방향 도로로 연결되며, 거리는 서로 다를 수 있다. 어떤 두 도시 사이에는 도로가 없을 수도, 여러 개가 있을 수도 있다. 또한 어떤 도시에서든 적어도 하나의 면접장까지 갈 수 있는 경로가 항상 존재한다.

모든 면접자는 본인의 도시에서 출발하여 가장 가까운 면접장으로 찾아갈 예정이다. 즉, 아래에서 언급되는 '면접장까지의 거리'란 그 도시에서 도달 가능한 가장 가까운 면접장까지의 최단 거리를 뜻한다.

속초 출신 승범이는 지방의 서러움을 알기에 각 도시에서 면접장까지의 거리 중, 그 거리가 가장 먼 도시에서 오는 면접자에게 교통비를 주려고 한다.

승범이를 위해 면접장까지의 거리가 가장 먼 도시와 그 거리를 구해보도록 하자.

• 입력 첫째 줄에 도시의 수 N(2 ≤ N ≤ 100,000), 도로의 수 M(1 ≤ M ≤ 500,000), 면접장의 수 K(1 ≤ K ≤ N)가 공백을 두고 주어진다. 도시는 1번부터 N번까지의 고유한 번호가 매겨진다. 다음 M개의 줄에 걸쳐 한 줄마다 도시의 번호 U, V(U ≠ V)와 도로의 길이 C(1 ≤ C ≤ 100,000)가 공백을 두고 순서대로 주어진다. 이는 도시 U에서 V로 갈 수 있는 도로가 존재하고, 그 거리가 C라는 뜻이다. 마지막 줄에 면접장이 배치된 도시의 번호 K개가 공백을 두고 주어진다.

• 출력 첫째 줄에 면접장까지 거리가 가장 먼 도시의 번호를 출력한다. 만약 그런 도시가 여러 곳이면 가장 작은 번호를 출력한다. 둘째 줄에 해당 도시에서 면접장까지의 거리를 출력한다.

2. 문제 접근

일반적인 다익스트라는 한 노드에서만 다른 노드까지 거리를 구하는 데 이 문제의 경우 여러 노드에서 다른 노드까지 거리를 구하는 것을 요구합니다.

여기서 일차원적으로 생각한다면 다익스트라를 여러 번 돌리면서 한 노드에서 다른 모든 노드까지 거리를 구하는 방법을 K번 반복하는 방식의 풀이를 할 수 있습니다. 사실 저도 처음에 그랬.. 아무튼 노드 수의 범위도 많고 K가 최대 N까지 커지는 최악의 경우 문제의 시간 복잡도가 일반 다익스트라 * K가 되므로 시간 제한 내에 풀이가 불가능합니다.

그래서 여러 노드에서 나머지 노드에 대한 최단 거리를 구하는 방법은 생각보다 간단합니다. 시작점을 여러 개를 둬서 시작 노드들의 거리를 0으로 놓고 동시에 출발하면 됩니다. 그러면 각 노드에서 가장 가까운 출발 노드에 대한 거리를 한 번의 다익스트라 알고리즘으로 구할 수 있습니다.

그럼에도 정답률이 유독 낮은 게 문제의 조건이 약간 까다롭습니다. 우선 면접장이 출발 노드가 아니고 도착 노드이기 때문에 그래프에 역방향으로 입력해야 합니다. 간선이 단방향이며 최악의 경우 거리의 총합이 자바의 int 범위를 벗어나므로 long 처리까지 해줘야 합니다.

3. 문제 풀이

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

public class Main {

    static class Edge implements Comparable<Edge>{

        private int to;
        private long dist;

        public Edge(int to, long dist) {
            this.to = to;
            this.dist = dist;
        }

        @Override
        public int compareTo(Edge o) {
            return Long.compare(dist, o.dist);
        }
    }

    static int n,m;
    static ArrayList<Edge>[] map;
    static Queue<Integer> queue = new LinkedList<Integer>();
    static Long[] totalDist;

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

        map = new ArrayList[n+1];
        for (int i = 0; i <= n; i++) map[i] = new ArrayList<Edge>();
        totalDist = new Long[n+1];
        Arrays.fill(totalDist, Long.MAX_VALUE);

        for (int i = 0; i < m; i++) {
            st = new StringTokenizer(br.readLine());
            int u = Integer.parseInt(st.nextToken());
            int v = Integer.parseInt(st.nextToken());
            int c = Integer.parseInt(st.nextToken());
            map[v].add(new Edge(u,c));
        }

        st = new StringTokenizer(br.readLine());
        while (st.hasMoreTokens()) {
            queue.offer(Integer.parseInt(st.nextToken()));
        }

        dijikstra();

        Long maxDist = 0L;
        int maxNode = 0;

        for (int i = n; i >= 1; i--) {
            if (maxDist <= totalDist[i]) {
                maxNode = i;
                maxDist = totalDist[i];
            }
        }

        System.out.println(maxNode);
        System.out.println(maxDist);

    }

    private static void dijikstra() {
        PriorityQueue<Edge> pq = new PriorityQueue<>();
        Long[] dist = new Long[n+1];
        Arrays.fill(dist, -1L);

        for (int start : queue) {
            dist[start] = 0L;
            pq.offer(new Edge(start, 0));
        }

        while (!pq.isEmpty()) {
            Edge cur = pq.poll();
            if (dist[cur.to] == -1 || dist[cur.to] < cur.dist) continue;
            for (Edge next: map[cur.to]) {
                if (dist[next.to] == -1 || dist[next.to] > dist[cur.to] + next.dist) {
                    dist[next.to] = dist[cur.to] + next.dist;
                    pq.offer(new Edge(next.to, dist[next.to]));

                }

            }
        }

        for (int i = 1; i <= n; i++) {
            totalDist[i] = Math.min(totalDist[i], dist[i]);
        }

    }
}

! [rejected]   master -> master (fetch first)
error: failed to push some refs to '<Git 레포지토리명>'

성질이 급한 나머지 구글링을 통해 강제로 push를 시도했는데요..

git push origin +master
git push origin -master --force

.. 등의 커맨드로 강제 푸시가 가능합니다.

프로젝트 초기 단계라서 별 문제는 없었지만 찜찜해서 나중에 에러의 원인을 찾아봤습니다.

에러 발생 이유는 콘솔에 적힌 그대로 fetch를 하지 않아서입니다. fetch는 원격 저장소의 브랜치에 생긴 변경 사항을 찾아내는 작업입니다(fetch change). 그 후 merge를 통해 fetch한 변경 사항과 본래 내용을 병합해줘야 합니다. 똑같은 파일에 대해 내용이 다른 conflict가 발생한다면 git에서 어떤 내용을 반영할지 결정할 수 있습니다. 아니면 pull을 통해 fetch+merge를 동시에 할 수 있습니다. 이러한 정상적인 병합 과정이 끝나면 push가 가능해집니다.

git fetch origin
git merge origin/master 
// 
git pull origin master
-> 
commit, push

규모가 큰 프로젝트에서 귀찮다고 push --force를 떄려버리면 커밋이 완전히 얽히는 불상사가 발생할 수 있겠죠?

N층 빌딩이 있다. 이 빌딩의 F층은 금고를 떨어뜨렸을 때에 부서지는 최소 층이다. 다시 말하면, F층을 포함하여 그 위의 층에서 금고를 떨어뜨리면 무조건 부서지며, F층의 아래층에서 금고를 떨어뜨릴 때에는 금고는 절대 부서지지 않는다. N층에서도 부서지지 않을 수도 있으며, 1층에서도 부서질 수도 있다.

새로 개발한 금고의 견고함을 측정해보기 위해서 K개의 금고를 이용하여 이 빌딩의 F층을 구하려고 한다. 이를 위해서 직접 금고를 떨어뜨려 보면서 그 결과를 확인하려 한다. 금고가 부서진 경우에는 그 금고를 다시 사용할 수 없으며, 부서지지 않았다면 다시 사용할 수 있다.

이런 상황에서 K개의 금고를 가지고 F층이 몇 층이던지 간에 F층을 알아낼 수 있는 최소한의 금고 낙하 회수를 E(N, K)라 하자. 예를 들어 K=1이라면 F를 알아내기 전에 금고가 부서지면 안 되기 때문에 1층부터 차례로 올라가면서 금고를 떨어뜨려야 한다. 따라서 E(N, 1)=N이 된다.

두 정수 N, K가 주어졌을 때 E(N, K)를 구하는 프로그램을 작성하시오.

• 입력 첫째 줄에 두 정수 N(1 ≤ N ≤ 500), K(1 ≤ K ≤ N)가 주어진다.

• 출력 첫째 줄에 E(N, K)를 출력한다.

2. 문제 접근

금고가 몇 층에서 떨어졌을 때 안 부셔지는지 임계값을 찾는 문제입니다.

저희는 알고리즘을 공부하는 이성을 갖춘 사람이므로 기본 탐색은 이분 탐색이라 가정할 수 있습니다. 그런데 문제는, 금고를 열심히 부셔서 한 개의 금고만 남게 된다면, 안전했던 가장 낮은 층부터 마지막으로 금고를 부순 층까지 밑에서부터 한 층씩 금고를 계속 떨어뜨려야 합니다. 처음부터 금고가 한 개만 있다면 선택지 없이 1층부터 n층까지 전부 다 떨어뜨려봐야 합니다.

DP 배열을 어떻게 정의하냐에 따라서 다양한 방식의 DP 풀이가 가능합니다.

가장 일반적으로 생각할 수 있는 풀이는 배열의 정의를 $r$ = 남은 금고의 수, $k$ = 탐색 높이일 때, $DP[r][k]$ = 탐색이 필요한 횟수로 놓는 겁니다. 임의의 높이에서 떨어뜨리면 깨지느냐 안깨지느냐 두 경우가 있겠죠. 깨진다면 현재 높이보다 낮은 범위를 탐색하고, 깨지지 않는다면 높게 탐색합니다. 이때 초기값으로 $r$ = 1일때 $DP[1][k] = k$로 첫 행을 초기화 해줍니다.

반대로 DP 배열을 $r$ = 남은 금고의 수, $c$ = 남은 이동 횟수로 정의할 수 있습니다. 이때 $DP[r][c]$ = 탐색 가능한 최대 층수가 됩니다.

또한 이번 문제와 같이 다음 행의 값을 도출하는데 필요한 행의 개수가 한 개라면 메모이제이션도 간단해집니다.

GOG Egg-Dropping Problem 구글링을 하다가 찾은 유사한? 문제입니다. 아니 유사한 게 아니고 100프로 똑같은 문제입니다. 원문을 번역하면서 겨란이 금고가 된 게 아닌가 의심이 되는 부분입니다.

3. 문제 풀이

1. r = 남은 금고의 수 , c = 높이

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

public class Main {

static StringTokenizer st;

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

    int[][] dp = new int[r+1][c+1];
    for (int i = 0; i <= c; i++) dp[1][i] = i;
    for (int i = 0; i <= r; i++) dp[i][1] = 1;

    for (int i = 2; i <= r; i++) for (int j = 2; j <= c; j++) dp[i][j] = Integer.MAX_VALUE;

    for (int i = 2; i <= r; i++) 
        for (int j = 2; j <= c; j++) 
            for (int k = 1; k < j; k++) 
                dp[i][j] = Math.min(dp[i][j], Math.max(dp[i-1][k-1], dp[i][j-k]) + 1);

    System.out.println(dp[r][c]);

}

}

2. r = 금고의 수, c = 필요한 탐색 횟수
``` java 8
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
    static int minTrials(int n, int k) {
        int dp[][] = new int[k + 1][n + 1];
        int m = 0; 
        while (dp[m][n] < k) {
            m++;
            for (int x = 1; x <= n; x++) 
                dp[m][x] = 1 + dp[m - 1][x - 1] + dp[m - 1][x];

        }
        return m;
    }

    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());

        System.out.println(minTrials(k, n));
    }
}

3. 2번 메모이제이션 최적화

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

public class Main { static int minTrials(int n, int k) { int[] dp = new int[n + 1]; int m; for (m = 0; dp[n] < k; m++) for (int x = n; x > 0; x--) dp[x] += 1 + dp[x - 1];

    return m;
}

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());

    System.out.println(minTrials(k, n));
}

}

```

1. 문제 설명

N(2 ≤ N ≤ 10,000)개의 섬으로 이루어진 나라가 있다. 이들 중 몇 개의 섬 사이에는 다리가 설치되어 있어서 차들이 다닐 수 있다.

영식 중공업에서는 두 개의 섬에 공장을 세워 두고 물품을 생산하는 일을 하고 있다. 물품을 생산하다 보면 공장에서 다른 공장으로 생산 중이던 물품을 수송해야 할 일이 생기곤 한다. 그런데 각각의 다리마다 중량제한이 있기 때문에 무턱대고 물품을 옮길 순 없다. 만약 중량제한을 초과하는 양의 물품이 다리를 지나게 되면 다리가 무너지게 된다.

한 번의 이동에서 옮길 수 있는 물품들의 중량의 최댓값을 구하는 프로그램을 작성하시오.

• 입력 첫째 줄에 N, M(1 ≤ M ≤ 100,000)이 주어진다. 다음 M개의 줄에는 다리에 대한 정보를 나타내는 세 정수 A, B(1 ≤ A, B ≤ N), C(1 ≤ C ≤ 1,000,000,000)가 주어진다. 이는 A번 섬과 B번 섬 사이에 중량제한이 C인 다리가 존재한다는 의미이다. 서로 같은 두 섬 사이에 여러 개의 다리가 있을 수도 있으며, 모든 다리는 양방향이다. 마지막 줄에는 공장이 위치해 있는 섬의 번호를 나타내는 서로 다른 두 정수가 주어진다. 공장이 있는 두 섬을 연결하는 경로는 항상 존재하는 데이터만 입력으로 주어진다.

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

2. 문제 접근

크게 두 가지 풀이 방법이 있습니다.

1. 최대 중량을 이분 탐색으로 찾으며 BFS 또는 DFS로 그래프 탐색을 진행합니다. 이 경우에는 탐색 대상인 중량보다 중량 제한이 큰 다리만 통과 가능하다고 하여 목표 지점 A에서 B를 갈 수 있는지 판단해야 합니다.

2. 중량 제한이 가장 큰 간선부터 유니온-파인드 알고리즘을 이용해 연결하며 간선의 두 섬을 유니온 합니다. 어느 지점이 되면 A와 B가 같은 집합에 속하게 되면 A에서 B를 갈 수 있다고 판단하고 사용한 다리 중 최저 중량 제한을 찾습니다.

저는 2번 방법으로 풀었습니다. 유니온 파인드 풀이의 시간복잡도가 최대 $O(M)$인데 이분 탐색의 경우 $O(logC*N)$이고 BFS의 메모리 부담 문제도 있어서 그런지 실행 속도가 빠른 코드들은 대부분 이 풀이를 사용하고 있었습니다. 일종의 역 크루스칼 같은 풀이라고 생각합니다.

3. 문제 풀이

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.List;
import java.util.PriorityQueue;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {

    static StringTokenizer st;
    static int n;
    static int[] parent;

    static class Edge implements Comparable<Edge>{
        int from;
        int to;
        int weight;
        public Edge(int from, int to, int weight) {
            this.from = from;
            this.to = to;
            this.weight = weight;
        }
        @Override
        public int compareTo(Edge o) {
            return o.weight - weight;
        }

    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        st = new StringTokenizer(br.readLine());
        n = Integer.parseInt(st.nextToken());
        int m = Integer.parseInt(st.nextToken());
        parent = new int[n + 1];
        for (int i = 1; i <= n; i++) parent[i] = i;

        Queue<Edge> queue = new PriorityQueue<>();
        while (m --> 0) {
            st = new StringTokenizer(br.readLine());
            int from = Integer.parseInt(st.nextToken());
            int to = Integer.parseInt(st.nextToken());
            int weight = Integer.parseInt(st.nextToken());
            queue.add(new Edge(from, to, weight));
        }
        st = new StringTokenizer(br.readLine());
        int a = Integer.parseInt(st.nextToken());
        int b = Integer.parseInt(st.nextToken());
        int ans = 0;
        while (!isUnion(a,b)) {
            Edge cur = queue.poll();
            int from = cur.from;
            int to = cur.to;
            int weight = cur.weight;
            union(from, to);
            ans = weight;
        }
        System.out.println(ans);

    }

    static boolean isUnion(int a, int b) {
        if (find(a) == find(b)) return true;
        return false;
    }

    static void union(int a, int b) {
        a = find(a);
        b = find(b);
        if (a != b) parent[a] = b;
    }

    static int find(int a) {
        if (parent[a] != a) return (parent[a] = find(parent[a]));
        return a;
    }

}

축구는 지구에서 가장 인기있는 스포츠 중의 하나입니다. n 팀으로 이루어진 축구 리그가 있습니다. 하나의 팀은 다른 모든 팀과 정확히 한 번씩만 경기를 합니다. 그러므로, 각 팀은 n - 1 번의 경기를 하게 됩니다. 무승부는 승부차기를 하기 때문에 없습니다. 한 경기 후에 이긴 한 팀은 1 점을 얻게 되고, 진 팀은 0 점을 얻게 됩니다.

베스트 팀 선정을 위해 경기 일정이 끝난 후에 각 팀은 리그 사무소에 획득한 점수를 보고하게 됩니다. 리그 사무소는 각 팀이 보고한 점수가 실수가 없는지 확실히 해두고 싶습니다. 즉, 보고한 점수가 유효한지 아닌지 알고 싶은 것이고, 이 말은 리그 룰에 따르는 경우 이 점수들을 각 팀에 할당하는 것이 가능해야 합니다.

주어진 n 개의 정수들은 각 팀에서 보고한 점수들로 이 점수들이 유효한지 아닌지 알아내는 프로그램을 작성해야 합니다.

• 입력 프로그램은 표준 입력에서 읽어야 합니다. 입력은 두 줄로 이루어져 있고, 첫째 줄은 하나의 정수 n (2 ≤ n ≤ 10,000) 이고, 팀의 개수를 의미합니다. 다음 줄은 각 팀에서 보고한 점수들입니다. 각 정수는 0 보다 같거나 크고 n - 1 보다 같거나 작습니다.

• 출력 프로그램은 표준 출력에 써야 합니다. 보고한 점수들이 유효한 경우라면 1 을 출력하고, 그렇지 않으면 -1 을 출력합니다.

2. 문제 접근

문제 조건 상 n개의 모든 팀은 다른 n - 1개의 팀 모두와 경기를 치뤄야 합니다.

이를 그림으로 그려보면 complete graph와 같은 형태입니다. 모든 노드가 서로 연결되어 있습니다. 각 간선은 모두 방향이 있는 간선입니다. 반드시 승 또는 패가 결정되기 때문입니다. 편의상 패에서 승으로 방향이 있다고 가정하겠습니다.

이론상 점수가 최대로 높은 팀은 점수가 n - 1점입니다. 해당 노드에 연결된 모든 간선이 그 노드로 향한다고 볼 수 있습니다. 그럼 다음으로 점수가 높은 팀은 점수가 최대 n - 2점입니다. 최소 1개의 간선은 다른 노드로 향하기 때문입니다. 이런 식으로 팀들을 점수별로 정렬하며 더했을 때 점수의 최대 limit을 구할 수 있습니다.

이걸 반대로 점수가 제일 낮은 팀부터 탐색한다 하면, 최소 점수가 0일때 다음으로 점수가 낮은 팀의 최소 점수는 1입니다. 최소 하나의 간선은 그 팀으로 간다고 보는 식으로 말이죠. 역으로 낮은 팀부터 합을 구하면 i번째 팀까지 합의 최솟값은 $i * (i - 1) / 2$입니다.

마지막으로 점수의 최종 합이 $n * (n - 1) / 2$가 맞는지만 확인해 주시면 되겠습니다.

3. 풀이

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

public class Main {

    static StringTokenizer st;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        st = new StringTokenizer(br.readLine());
        int[] arr = new int[n];
        for (int i = 0; i < n; i++) arr[i] = Integer.parseInt(st.nextToken());
        Arrays.sort(arr);
        boolean flag = true;
        int sum = 0;
        for (int idx = 1; idx <= n; idx++) {
            sum += arr[n - idx];
            if (sum > n * idx - (idx) * (idx + 1) / 2) {
                flag = false; break;
            }
        }
        if (sum != (n) * (n - 1) / 2) flag = false;
        System.out.println(flag? 1: -1);
    }
}

n = int(input())
li = list(map(int ,input().split()))
li.sort()

sum = 0
ans = 1

for i in range(n):
    sum += li[i]
    if sum < i * (i + 1) // 2: ans = -1
if sum != n * (n - 1) // 2 : ans = -1
print(ans)

자바는 역순으로, 파이썬은 정순으로 풀었습니다.

1. 문제 설명

피에스고등학교의 교장 이환이는 학교를 매우 사랑한다. 그래서 이환이는 매일 점심시간에 학교의 모든 건물을 돌아다닌다. 비가 오는 어느 날, 이환이는 학교 곳곳을 돌아다니고 싶었지만 비를 끔찍이 싫어하기 때문에 그럴 수 없었다.

비 때문에 고민하던 이환이는 결국 비를 맞지 않고 학교의 모든 건물을 방문할 수 있도록 건물과 건물 사이에 구름다리를 설치하기로 했다. 하지만 학생들은 비가 오는 날마저 이환이가 돌아다니면 게임을 하다 걸릴까 봐 구름다리 설치를 반대했다. 건물 $i$ 와 다른 건물을 잇는 구름다리가 $k$개 설치되면, 건물 $i$에서 게임을 하던 학생들은 $k$개의 구름다리에서 이환이가 오는지 확인해야 하기 때문에 $k^2$만큼의 불만을 가진다.

점심시간에 건물 1에는 학생 1명, 건물 2에는 학생 2명, 건물 3에는 학생 3명이 게임한다고 가정하자. 아래와 같이 구름다리를 건설하면 건물 2와 건물 3에 있는 학생들은 불만을 1씩 가지고 건물 1에 있는 학생은 불만을 4 가진다. 따라서 이때 생기는 학생들의 불만은 $1×4+2×1+3×1=9$이다. 불만이 9보다 작도록 구름다리를 건설하는 것은 불가능하다.

실제로 피에스고등학교에는 $N$개의 건물이 있고, $i$번 건물에서는 $ai$명의 학생이 게임을 한다. 학생의 불만이 크면 이환이가 상처받기 때문에, 이환이를 위해 불만의 최솟값을 구해줘야 한다.

• 입력 첫 번째 줄에 건물의 수 $N$이 주어진다.
  두 번째 줄에는 각 건물에서 게임을 하는 학생의 수를 나타내는 음이 아닌 정수 $a_1,a_2,⋯,a_N$이 공백으로 구분되어 주어진다.

• 출력 첫 번째 줄에 불만의 최솟값을 출력한다.

2. 문제 접근

불만의 값을 최소로 하면서 모든 건물을 연결을 하고자 합니다. 언뜻 보기엔 MST 문제 같지만, 불만을 산출하는 과정이 단순 간선의 건물(노드)가 가진 값의 합의 누적이 아니기 때문에 그런 방식으로 구할 수 없습니다. 애초에 MST 알고리즘대로 하면 가장 값이 적은 건물에 모든 건물을 연결하는 깊이 1의 트리 같은 구조가 될텐데, 당연히 그렇게는 답을 구할 수 없습니다.

따라서 이번 문제에서는 그래프를 차수열(Degree Sequence)로 표현해 보겠습니다. 차수열의 개념은 간단합니다. 각 노드의 차수를 단순히 나열한 수열입니다.

위 그래프의 차수를 1부터 6까지 나타내면 [2, 3, 2, 3, 3, 1] 입니다.

차수열의 유효성을 확인할 수 있는 특징이 몇 가지 있습니다. 첫 번째로 수열의 합은 반드시 짝수여야 합니다. 간선 하나당 차수가 2씩 올라가서 그렇습니다. 또한 같은 차수열를 나타내는 그림이 하나 이상 있을 수 있습니다. 같은 차수열을 공유하는 전혀 다른 그래프입니다.

차수열의 유효성을 확인하는 가장 강력한 정리는 하벨-하키미 정리(Havel-Hakimi Theorem)입니다. 차수열를 내림차순 정렬한 뒤, 차수가 가장 큰 노드를 하나 제거하고 그 노드의 차수의 개수만큼 다음으로 큰 노드들의 차수를 1씩 빼주는 과정을 반복합니다. 그 과정에서 생성되는 모든 새로운 차수열이 그래프로 표현 가능하다면 유효한 차수열입니다.

자세한 증명은 어려우니 위 그래프에 적용을 해보겠습니다.

1. 차수열을 정렬하면 [3,3,3,2,2,1]이 됩니다. 노드 번호는 [2,4,5,1,3,6]이라 합시다.
2. 첫 번째 노드를 제거합니다. 차수가 3인 2번 노드를 제거하는데, 편의를 위해 다음으로 차수가 큰 3개 노드인 4, 5, 1번에 연결되어 있다고 가정합니다.
3. 수열은 [2, 2, 1, 2, 1], 노드 번호는 [4,5,1,3,6]이 됩니다. 이는 위 그래프와 같으며, 같은 방법으로 노드를 하나씩 제거할 수 있습니다.

같은 방법으로 [3, 3, 3, 1] 이 유효하지 않은 차수열임을 보일 수 있습니다.

1. [3, 3, 3, 1]에서 첫 번째 항을 제거합니다. 이후 차수열은 [3-1, 3-1, 1-1] = [2, 2, 0] 이 됩니다.
2. [2, 2, 0]은 그래프로 나타낼 수 없습니다. 그림을 그려 보려 시도해 보면 알 수 있습니다.

문제에서 찾는 그래프는 트리인데 다행히 트리에서는 위와 같은 유효성 확인 과정이 필요 없습니다. 총 노드가 $n$개면,

1. 차수열의 총 합이 $2n - 2$ 이고,
2. 모든 노드의 최소 degree가 1이며,
3. 모든 노드의 최대 degree가 n - 1이여야 합니다.

노드의 값이 $k$, 차수가 $d$일 때 차수가 1 증가할 때 증가하는 불만의 값은 $k(2d+1)$입니다. 따라서 매번 증가하는 불만이 가장 적은 노드의 차수를 1 증가싴키고, 다음 증가하는 불만의 값을 $k(2d+3)$으로 업데이트 해줍니다. 차수가 $d+1$이고 한번 더 증가할 때는 $d+2$가 되기 때문입니다. 이는 PriorityQueue를 사용해 구현할 수 있습니다.

3. 문제 풀이

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

public class Main {

    static class Node implements Comparable<Node> {
        long num, degree;

        public Node(long num, long degree) {
            this.num = num;
            this.degree = degree;
        }

        public int compareTo(Node o) {
            if (this.num > o.num) return 1;
            else return -1;
        }
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        long ans = 0;
        PriorityQueue<Node> queue = new PriorityQueue<>();

        Node[] graph = new Node[n];
        StringTokenizer st = new StringTokenizer(br.readLine());

        for (int i = 0; i < n; i++) {
            long a = Long.parseLong(st.nextToken());
            graph[i] = new Node(a, 1);
            queue.offer(new Node((graph[i].degree * 2 + 1) * graph[i].num, i));
        }

        if (n == 1) {
            System.out.println(0);
            System.exit(0);
        }

        for (int i = 1; i < n - 1; i++) {
            Node cur = queue.poll();
            graph[(int) cur.degree].degree++;
            queue.offer(new Node((graph[(int) cur.degree].degree * 2 + 1) * graph[(int) cur.degree].num, cur.degree));
        }

        for (int i = 0; i < n; i++) ans += graph[i].num * graph[i].degree * graph[i].degree;     

        System.out.println(ans);
    }

}

1. 문제 설명

걷기 전에 동전을 던진 다음, 앞 면이면 왼쪽으로 한 칸, 뒷 면이면 오른쪽으로 한 칸 이동하는 방법을 랜덤 걷기라고 한다. 이 랜덤 걷기의 위치의 기댓값은 항상 0이 된다. 즉, 랜덤 걷기를 아무리 많이 한다고 해도, 평균 위치는 처음 시작한 지점과 같다.

랜덤 걷기에서 왼쪽으로 갈 확률과 오른쪽으로 갈 확률, 그리고 동전을 던지는 횟수가 주어졌을 때, 가장 오른쪽 위치의 기댓값을 구하는 프로그램을 작성하시오.

• 입력 첫째 줄에는 테스트 케이스의 P가 주어진다. 각 테스트 케이스는 모두 독립적이다. 각 테스트 케이스는 한 줄로 이루어져 있다. 이 줄에는 총 세 개의 숫자가 주어지는데, 왼쪽부터 순서대로 n, L, R이다. n(1 ≤ n ≤ 1000)은 동전을 던지는 횟수이다. L과 R은 각각 왼쪽으로 갈 확률과 오른쪽으로 갈 확률이다. ( 0 ≤ L ≤ 1, 0 ≤ R ≤ 1, 0 ≤ L+R ≤ 1) 이 문제에서 사용하는 동전은 조금 독특해서, 앞 면과 뒷 면이 나올 확률이 서로 다를 수도 있다. 또, 1-L-R은 동전의 옆 면이 나올 확률로, 옆 면이 나온 경우에는 그 자리에 그대로 있는다.

• 출력 각 테스트 케이스에 대해서, 가장 오른쪽 위치의 기댓값(평균)을 소수점 넷째 자리 까지 출력한다.

2. 문제 접근

DP는 DP인데 문제 풀이를 위한 점화식 접근이 매우매우 어려웠던 문제입니다.

.. 해서 구글링을 좀 했습니다!

문제의 원형은 Random Walk이라는 수학의 확률론적 개념에 근거합니다. [(링크)] (https://en.wikipedia.org/wiki/Random_walk) 하지만 안타깝게도 Random Walk은 앞으로 갈 확률과 뒤로 갈 확률이 0.5로 같음이 전제이므로 적용하기 조금 힘들 수 있습니다.

그래서 찾은 링크가 여깁니다. www.reddit.com/r/dailyprogrammer/comments/16dbyh/011113_challenge_116_hard_maximum_random_walk/

DP를 2차원 배열로 놓고, DP[i][j] 를 i번 이동했고, j번 이동 기회가 남았을 때 이동할 수 있는 가장 먼(rightmost) 거리로 놓습니다. 따라서 0번째 row의 값을 DP[0][j] = j로 놓을 수 있습니다. 이론상 j번 오른쪽으로 이동할 수도 있으니까요.

앞면이 나올 확률을 head, 뒷면은 tail, 옆면은 side로 하겠습니다. 각 이동 기회에서 세 가지 경우의 수가 있습니다.

1. 이동하지 않는 경우 : 움직이지 않으므로 거리의 기대치도 변하지 않습니다. DP[i][j] += DP[i-1][j] x side

2. 왼쪽으로 이동한 경우 : 한 칸 왼쪽으로 거리의 기대치가 1 줄어듭니다. 거기다 오른쪽으로 한 번 더 이동해서 원래 위치로 다시 가야 동전을 던지기 전의 기대치와 같아집니다. 동전을 한 번 던지기 전 + 기회가 한 번 더 있는 상황입니다. DP[i][j] += * (DP[i-1][j+1] - 1) x tail

3. 오른쪽으로 이동한 경우 : 한 칸 오른쪽으로 가서 거리의 기대치가 1 증가합니다. 왼쪽으로 이동한 경우와 반대로 생각해 줍니다. 동전을 던질 기회를 한 번 아꼈다고 볼 수 있습니다.

   DP[i][j] += * (DP[i-1][j-1] - 1) x tail

   j가 0인 경우는 : 이동 횟수를 모두 소진한 경우입니다. j - 1 이 인덱스에서 벗어나기도 하고, i번 이동한 뒤 head가 나와 한 칸 더 앞으로 이동할 확률 -> DP[i][0] += (DP[i-1][0] + 1) x tail이므로

자바는 소수점 처리가 특이해서 round 함수를 쓰거나 Math.format, printf 등을 사용하면 특정 케이스에서 반올림으로 인해 소수점 오류가 납니다. 제 경우엔 DecimalFormat을 사용하니 오류가 나지 않았습니다.

3. 문제 풀이

• 자바

  import java.io.BufferedReader;
  import java.io.IOException;
  import java.io.InputStreamReader;
  import java.text.DecimalFormat;
  import java.util.Arrays;
  import java.util.StringTokenizer;
  
  

public class Main {

static int toss;
static double tail, head;

public static void main(String[] args) throws IOException {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    StringTokenizer st;
    int T = Integer.parseInt(br.readLine());
    while (T --> 0) {
        st = new StringTokenizer(br.readLine());
        toss = Integer.parseInt(st.nextToken());
        tail = Double.parseDouble(st.nextToken());
        head = Double.parseDouble(st.nextToken());
        DP();
    }
}
// DP 의 정의는 다음과 같음
// DP[i][j] : i번 이동했고, j번 이동 횟수 남았을 때 최상의 상황에서 가능한 오른쪽 끝 쪽 위치
// DP[0][i] : i번 던질 수 있고, 이동하지 않았으므로 최상의 경우 i번 오른쪽 이동 -> DP[0][i] = i
static void DP() {
    double side = 1D - tail - head;
    double[][] DP = new double[toss + 1][toss + 1];
    for (int i = 0; i <= toss; i++) DP[0][i] = (double) i;

    for (int i = 1; i <= toss; i++) for (int j = 0; j <= toss - i; j++) 
            DP[i][j] = side * DP[i-1][j] 
            + tail * (DP[i-1][j+1] - 1) 
            + head * (DP[i-1][Math.max(j-1, 0)] + 1);
    DecimalFormat format = new DecimalFormat("0.0000");
    System.out.println(format.format(DP[toss][0]));
}

}

- 파이썬
```Python
def DP(toss, tail, head):
    DP = [[0] * (toss + 1) for _ in range(toss + 1)]

    for i in range(toss + 1): DP[0][i] = i
    for i in range(1, toss + 1):
        for j in range(toss - i + 1):
            DP[i][j] = (1 - tail - head) * DP[i-1][j]  + tail * (DP[i-1][j+1] - 1) + head * (DP[i-1][max(j-1, 0)] + 1)

    print(f'{DP[toss][0]:.4f}')



T = int(input())
for _ in range(T):
    toss, tail, head = map(float, input().split())
    toss = int(toss)
    DP(toss, tail, head)

격자 정사각형은 모든 꼭짓점이 격자점 위에 있는 정사각형이다. 격자점은 x좌표와 y좌표가 모두 정수인 점이다. 예를 들어, (1,5)는 격자점이지만, (1, 1.5)는 아니다.

m×n 격자 위에 격자 정사각형은 총 몇 개가 있을까?

위의 그림은 4×4 격자 위에서 찾을 수 있는 격자 정사각형의 일부이다. 그림 1, 2, 3과 같이 축에 평행한 격자 정사각형도 있고, 4, 5, 6과 같이 평행하지 않은 정사각형도 있다. 그림 2, 4, 6의 정사각형은 넓이가 짝수이고, 1, 3, 5는 홀수이다.

격자의 크기가 주어졌을 때, 넓이가 홀수인 격자 정사각형은 총 몇 개가 있는지 구하는 프로그램을 작성하시오.

두 격자 정사각형이 네 변을 모두 공유하지 않으면 다른 정사각형이다.

• 입력 입력은 최대 50000줄로 이루어져 있다. 각 줄에는 m과 n이 주어진다. (1 ≤ m, n ≤ 100000) 입력의 마지막 줄에는 0이 두 개 주어진다.

• 출력 각 입력마다 넓이가 홀수인 격자 정사각형의 수를 출력한다. 정답은 항상 64비트 정수(64-bit signed integer) 범위이다.

2. 문제 접근

$m \ X \ n$ 격자 내에 넣을 수 있는 정사각형 중 넓이가 홀수인 경우를 세는 문제입니다.

일단은 비스듬한 정사각형은 고려하지 않고 $l \ X \ l$ 정사각형을 채워 넣는다고 가정해 봅시다. 당연히 $l \ <\ m, n$ 이며 넣을 수 있는 $l \ X \ l$ 정사각형의 개수는 $(m-l+1)(n-l+1)$개입니다.

이제 $l \ X \ l$ 정사각형 내에 채워 넣을 수 있는 비스듬한 정사각형의 경우를 고려해 봅시다. 내부에 있는 정사각형의 넓이는 $(a+b)^2 - 4ab$ 입니다. $4ab$는 반드시 짝수이므로 $a+b$가 홀수여야 내부의 정사각형의 넓이도 홀수가 됩니다.

문제 조건상 네 변을 공유하지 않기만 하면 별도의 정사각형으로 카운트 하므로 한 변이 $k$인 정사각형 내에 들어가는 정사각형의 개수 역시 $k$개입니다. 따라서 $m \ X \ n$ 격자 내에 넣을 수 있는 변의 길이가 홀수인 정사각형의 개수를 구하면 답을 찾을 수 있습니다.

3. 코드

파이썬

def find_square(m, n):
    ans = 0
    for i in range(1, min(m, n) + 1, 2):
        ans += (m - i + 1) * (n - i + 1) * i
    print(ans)

while True:
    m, n = map(int, input().split())
    if (m == 0 and n == 0): exit()
    find_square(m, n)

자바

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

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

        while (true) {
            st = new StringTokenizer(br.readLine());
            long m = Long.parseLong(st.nextToken());
            long n = Long.parseLong(st.nextToken());

            if (m == 0 && n == 0) {
                break;
            }

            long ans = 0;
            for (long i = 1; i <= Math.min(m, n); i += 2) {
                ans += (m - i + 1) * (n - i + 1) * i;
            }

            System.out.println(ans);
        }

    }
}

문제 분류가 DP긴 한데 변의 길이가 주어질 때 정사각형의 개수를 바로 구할 수 있으므로 별도의 DP 배열이 필요 없습니다.

역시 수학문제 풀때는 파이썬이 좋네요~ 형변환도 알아서 해주고 말이죠 ㅋㅋㅋㅋ 자바로 풀 때는 합의 범위에 유의합니다. 개수가 n^3에 비례하기 때문에 반드시 long으로 지정해줘야 합니다.

단순 누적합 문제이므로 m, n, l을 안다면 공식화 시켜서 한 번에 풀 수도 있습니다. 그러면 O(1)의 선형 시간 내에 문제를 풀 수 있습니다.

1. 문제 설명

예은이는 요즘 가장 인기가 있는 게임 서강그라운드를 즐기고 있다. 서강그라운드는 여러 지역중 하나의 지역에 낙하산을 타고 낙하하여, 그 지역에 떨어져 있는 아이템들을 이용해 서바이벌을 하는 게임이다. 서강그라운드에서 1등을 하면 보상으로 치킨을 주는데, 예은이는 단 한번도 치킨을 먹을 수가 없었다. 자신이 치킨을 못 먹는 이유는 실력 때문이 아니라 아이템 운이 없어서라고 생각한 예은이는 낙하산에서 떨어질 때 각 지역에 아이템 들이 몇 개 있는지 알려주는 프로그램을 개발을 하였지만 어디로 낙하해야 자신의 수색 범위 내에서 가장 많은 아이템을 얻을 수 있는지 알 수 없었다.

각 지역은 일정한 길이 l (1 ≤ l ≤ 15)의 길로 다른 지역과 연결되어 있고 이 길은 양방향 통행이 가능하다. 예은이는 낙하한 지역을 중심으로 거리가 수색 범위 m (1 ≤ m ≤ 15) 이내의 모든 지역의 아이템을 습득 가능하다고 할 때, 예은이가 얻을 수 있는 아이템의 최대 개수를 알려주자.

주어진 필드가 위의 그림과 같고, 예은이의 수색범위가 4라고 하자. ( 원 밖의 숫자는 지역 번호, 안의 숫자는 아이템 수, 선 위의 숫자는 거리를 의미한다) 예은이가 2번 지역에 떨어지게 되면 1번,2번(자기 지역), 3번, 5번 지역에 도달할 수 있다. (4번 지역의 경우 가는 거리가 3 + 5 = 8 > 4(수색범위) 이므로 4번 지역의 아이템을 얻을 수 없다.) 이렇게 되면 예은이는 23개의 아이템을 얻을 수 있고, 이는 위의 필드에서 예은이가 얻을 수 있는 아이템의 최대 개수이다.

• 입력
  첫째 줄에는 지역의 개수 n (1 ≤ n ≤ 100)과 예은이의 수색범위 m (1 ≤ m ≤ 15), 길의 개수 r (1 ≤ r ≤ 100)이 주어진다.
  둘째 줄에는 n개의 숫자가 차례대로 각 구역에 있는 아이템의 수 t (1 ≤ t ≤ 30)를 알려준다.
  세 번째 줄부터 r+2번째 줄 까지 길 양 끝에 존재하는 지역의 번호 a, b, 그리고 길의 길이 l (1 ≤ l ≤ 15)가 주어진다.
  지역의 번호는 1이상 n이하의 정수이다. 두 지역의 번호가 같은 경우는 없다.

• 출력
  예은이가 얻을 수 있는 최대 아이템 개수를 출력한다.

2. 문제 접근

각 노드에서 모든 노드에 대한 최단 거리를 찾아야 하는 문제이므로 모든 노드 간 최단 거리를 구할 수 있는 플로이드-워셜 알고리즘을 통해 답을 구할 수 있습니다. 한 번의 수행으로 모든 최단 거리를 갱신한 후 각 노드별로 조회하며 거리가 range보다 작으면 sum에 더하는 식으로 노드 별 구할 수 있는 아이템의 최대 개수를 구할 수 있습니다.

또한 노드에 대해 다른 노드로 가는 최단거리를 구해야 하는 문제이므로 한 노드에 대해 다른 노드로 가는 최단거리를 구하는 다익스트라 알고리즘을 모든 노드에 대해 적용해보는 식으로도 풀 수 있습니다. 물론 다익스트라가 코드 길이가 더 길고 구현이 번거로운 만큼 플로이드-워셜 풀이가 좀 더 적절하지만 연습삼아 한 번 풀어봤습니다.

위가 플로이드-워셜, 아래가 다익스트라 풀이입니다. 탐색하는 노드의 개수가 같다 보니 실행 시간에 큰 차이는 없고, 큐를 사용하다 보니 다익스트라의 메모리 사용량이 살짝 더 높습니다.

다음 시간에는 최단 거리를 구하는 알고리즘인 다익스트라, 플로이드-워셜 알고리즘에 대해 알아보도록 할게용

코드

// 플로이드
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {

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

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

        int n = Integer.parseInt(st.nextToken()); // 전체 노드의 개수
        int range = Integer.parseInt(st.nextToken()); // 탐색 범위
        int route = Integer.parseInt(st.nextToken()); // 간선의 개수

        int[] value = new int[n + 1]; // 아이템 개수 
        st = new StringTokenizer(br.readLine());
        for (int i = 1; i <= n; i++) value[i] = Integer.parseInt(st.nextToken());

        int[][] map = new int[n+1][n+1];
        while (route --> 0) { // 그래프 2차원 배열 구현
            st = new StringTokenizer(br.readLine());
            int start = Integer.parseInt(st.nextToken());
            int end = Integer.parseInt(st.nextToken());
            int dist = Integer.parseInt(st.nextToken());
            map[start][end] = map[end][start] = dist;
        }
        // map 초기화
        for (int i = 1; i <= n; i++) for (int j = 1; j <= n; j++) if (map[i][j] == 0 && i != j) map[i][j] = 100000;
        // 플로이드-워셜 알고리즘
        for (int k = 1; k <= n; k++) {
            for (int i = 1; i <= n; i++) {
                for (int j = 1; j <= n; j++) {
                    if (map[i][j] > map[i][k] + map[k][j]) map[i][j] = map[i][k] + map[k][j];
                }
            }
        }

        int max = 0;
        // 배열 최대값 구하기
        for (int i = 1; i <= n; i++) {
            int sum = 0;
            for (int j = 1; j <= n; j++) {
                if (map[i][j] <= range) sum += value[j];
            }
            max = Math.max(max, sum);
        }
        System.out.println(max);

    }
}

// 다익스트라
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.PriorityQueue;
import java.util.Queue;
import java.util.StringTokenizer;

class Node implements Comparable<Node>{
    int n,d; // n for num, d for dist
    public Node(int n, int d) {
        this.n = n;
        this.d = d;
    }
    @Override
    public int compareTo(Node o) {
        return d - o.d;
    }

}

public class Main {
    static int n, range;
    static int[] value;
    static List<Node>[] map;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        st = new StringTokenizer(br.readLine());
        n = Integer.parseInt(st.nextToken());
        range = Integer.parseInt(st.nextToken());
        int route = Integer.parseInt(st.nextToken());
        value = new int[n + 1];
        st = new StringTokenizer(br.readLine());
        for (int i = 1; i <= n; i++) value[i] = Integer.parseInt(st.nextToken());
        map = new ArrayList[n+1]; // 그래프 인접 리스트 구현
        for (int i = 0; i <= n; i++) map[i] = new ArrayList<Node>();
        while (route --> 0) {
            st = new StringTokenizer(br.readLine());
            int start = Integer.parseInt(st.nextToken());
            int end = Integer.parseInt(st.nextToken());
            int dist = Integer.parseInt(st.nextToken());
            map[start].add(new Node(end,dist));
            map[end].add(new Node(start,dist));
        }
        int ans = 0;
        for (int i = 1; i <= n; i++) ans = Math.max(ans, dijikstra(i));
        System.out.println(ans);
    }
    // 다익스트라
    static int dijikstra(int start) {
        int[] dist = new int[n+1];
        Arrays.fill(dist, -1);
        dist[start] = 0; // 시작 지점 거리 = 0
        Queue<Node> queue = new PriorityQueue<>();
        queue.add(new Node(start, 0));
        while (!queue.isEmpty()) {
            Node cur = queue.poll();
            if (dist[cur.n] == -1 || dist[cur.n] < cur.d) continue; // 방문할 수 없거나 최단경로를 갱신할 수 없는 경우
            for (Node next : map[cur.n]) { // 연결된 다음 노드에 대해 최단 경로 갱신
                if (dist[next.n] == -1 || dist[next.n] > dist[cur.n] + next.d) {
                    dist[next.n] = dist[cur.n] + next.d;
                    queue.offer(new Node(next.n, dist[next.n]));
                }
            }
        }
        int cnt = 0;
        for (int i = 1; i <= n; i++) {
            if (dist[i] != -1 && dist[i] <= range) cnt += value[i];
        }
        return cnt;
    }
}

1. 문제 설명

요세푸스 문제는 다음과 같다.

1번부터 N번까지 N명의 사람이 원을 이루면서 앉아있고, 양의 정수 K(≤ N)가 주어진다. 이제 순서대로 K번째 사람을 제거한다. 한 사람이 제거되면 남은 사람들로 이루어진 원을 따라 이 과정을 계속해 나간다. 이 과정은 N명의 사람이 모두 제거될 때까지 계속된다. 원에서 사람들이 제거되는 순서를 (N, K)-요세푸스 순열이라고 한다. 예를 들어 (7, 3)-요세푸스 순열은 <3, 6, 2, 7, 5, 1, 4>이다.

N과 K가 주어지면, 마지막으로 남는 사람의 번호를 구하는 프로그램을 작성하시오.

입력 첫째 줄에 N과 K가 빈 칸을 사이에 두고 순서대로 주어진다. (1 ≤ K ≤ N ≤ 5,000,000)

출력 첫째 줄에 마지막으로 남는 사람의 번호를 출력한다.

2. 문제 접근

요세푸스 문제의 일반해를 구하는 문제입니다.

전에 올렸던 카드2 문제처럼 K=2일 경우에는 비교적 쉽게 마지막에 남는 카드를 빠르게 구할 수 있습니다. 전체 카드의 수가 $N$일 때 한 사이클이 끝난 후 남은 카드의 수는 $N * \frac{(K-1)}{K}$이므로 $N = 2^i$(i = 자연수)일 때 첫 번째 카드가 남는다는 것을 찾을 수 있습니다.

하지만 K > 3일 경우 $(\frac{K+1}{K}) ^ i$가 정수일 수 없습니다. 따라서 K가 주어졌을 때 전체 사이클에 몇 장이 남았을 때 마지막 카드가 1일 것이다! 라는 그리디한 해를 구할 수 없습니다.

문제의 알고리즘 분류가 DP이므로 점화식을 구해 아래서부터 올라가야 합니다. N = 1이면 당연히 1이고 N = 2이면 (1 + K) % 2 (값이 0이면 2) 식으로 구할 수 있습니다. 이를 점화식으로 표현하면 다음과 같습니다.

$J_{(n,k)} = (J_{(n-1,k)} + m - 1)(mod \ n) + 1$

$J_{(n-1,k)} + m = n$일때 0이 나오므로 빼기에 약간 주의해야 합니다.

N, K 범위가 크지 않으므로 일반적인 DP처럼 풀어도 시간 초과가 나지 않습니다.

3. 문제 풀이

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

public class Main {
    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 m = Integer.parseInt(st.nextToken());
        int ans = 1;
        for (int i =1; i <= n; i++) ans = (ans + (m-1)) % i + 1;
        System.out.println(ans);
    }
}

1. 문제 설명

라면매니아 교준이네 집 주변에는 N개의 라면 공장이 있다. 각 공장은 1번부터 N번까지 차례대로 번호가 부여되어 있다. 교준이는 i번 공장에서 정확하게 Ai개의 라면을 구매하고자 한다(1 ≤ i ≤ N).

교준이는 아래의 세 가지 방법으로 라면을 구매할 수 있다.

i번 공장에서 라면을 하나 구매한다(1 ≤ i ≤ N). 이 경우 비용은 3원이 든다. i번 공장과 (i+1)번 공장에서 각각 라면을 하나씩 구매한다(1 ≤ i ≤ N-1). 이 경우 비용은 5원이 든다. i번 공장과 (i+1)번 공장, (i+2)번 공장에서 각각 라면을 하나씩 구매한다(1 ≤ i ≤ N-2). 이 경우 비용은 7원이 든다. 최소의 비용으로 라면을 구매하고자 할 때, 교준이가 필요한 금액을 출력하는 프로그램을 작성하시오.

입력 첫 번째 줄에 라면 공장의 개수를 의미하는 자연수 N가 주어진다.

두번째 줄에 N개의 정수 A1, ···, AN가 사이에 공백을 두고 주어진다.

출력 첫 번째 줄에 교준이가 필요한 최소 금액을 출력한다.

2. 문제 접근

문제를 처음 봤을 땐 DP 문제인 줄 알았지만, 라면 공장의 최대 개수가 $10^4$개이므로 각각의 선택지마다 라면을 한 개, 두 개, 또는 세 개를 산다는 선택지를 모두 고려해 버리면 $O(n^3) = 10^{12}$만큼 시간이 걸리므로 시간 초과가 됩니다.

라면을 한 개를 사면 3원, 두 개를 사면 5원, 세 개를 사면 7원입니다. 언뜩 보면 세 개를 사면 평균 가격이 가장 낮기 때문에 3개를 최대한 많이 사면 정답이지 않을까 싶습니다. 그렇게 해서 앞에서부터 세 개씩 최대한 사면 되지 않을까 싶지만 쉬운 반례가 있습니다. [1 2 1 1] 을 앞에서 세 개를 사 버리면 [0 1 0 1] 이 되어 13원이 들지만 앞에서 두 개, 뒤에서 세 개를 사면 12원으로 해결할 수 있습니다.

라면을 한 개를 사면 3원, 두 개를 사면 하나는 3원 + 다음 하나는 2원, 세 개를 사면 하나는 3원 + 다음 두 개는 2원입니다. 핵심은 어떻게 하면 최대한 많은 3원 단가의 라면을 2원에 구매할 수 있을까 입니다.

배열을 길이 3 기준으로 살펴보겠습니다. 가장 앞의 원소들은 어쩔 수 없이 3원으로 사야 하는 라면들입니다. 가운데 라면들을 최대한 많이 앞의 라면들과 같이 구매해 2원으로 구매하는 최선의 방법을 찾아야 합니다.

가운데 원소의 크기가 마지막 원소의 크기보다 작다면 두 가지 방법으로 앞에서부터 처리해주면 됩니다.

1. list[i] < list[i + 1] < list[i + 2] : list[i]개만큼 3개를 최대한 합니다. 나머지 부분은 뒤의 원소를 조회하며 판단합니다. 예를 들어 [1 2 3] 일때, [1 1 1] 만큼 산 다음 [0 1 1] 은 다음에 뒤의 원소를 받아서 어떻게 구매할 지 판단할 수 있습니다.

2. list[i] > list[i + 1] < list[i + 2] : list[i + 1]개만큼 3개를 최대한 사고 배열 앞의 list[i] - list[i + 1]개는 2개씩 혹은 개별로 삽니다. 예를 들어 [2 1 3] 이라면 [1 1 1] 후 앞의 1개를 개별 구매하게 됩니다.

가운데 원소의 크기가 마지막 원소의 크기보다 클 때는 앞에서부터 처리하는 식으로 처리할 수 없습니다. 가운데 원소를 최대한 두 개 도는 세 개로 묶을 방법을 찾아야 합니다.

1. list[i] > list[i+1] - list[i+2] : 마지막 원소가 충분히 큰 경우입니다. 예제 배열이 [4 5 3] 일때, 앞에서 2개씩 2개를 사서 [2 3 3] 이 되면 3개씩 2번 구매합니다. 나머지 [0 1 1] 은 바로 처리하지 않고 뒤의 원소를 조회하며 판단합니다.
2. list[i] < list[i+1] - list[i+2] : 마지막 원소가 매우 작은 경우입니다. [3 5 1]일때, 앞에서 [3 3] 만큼 3개씩 2개를 구매한 뒤 [0 2 1]은 뒤의 원소를 조회하며 판단합니다.

쉽게 생각하면 배열을 길이 3 단위로 순회하면서 두 번째 라면을 가능한 한 많이 첫 번째 라면과 묶어서 처리하는 작업이라고 생각할 수 있습니다.

3. 문제 풀이

1. 자바 코드

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

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

    int n = Integer.parseInt(br.readLine());
    int[] li = new int[n + 2];
    StringTokenizer st = new StringTokenizer(br.readLine());

    for (int i = 0; i < n; i++) {
        li[i] = Integer.parseInt(st.nextToken());
    }
    li[n] = 0;
    li[n + 1] = 0;

    int ans = 0;

    for (int i = 0; i < n; i++) {
        if (li[i + 1] > li[i + 2]) {
            int a = Math.min(li[i], li[i + 1] - li[i + 2]);
            ans += 5 * a;
            li[i] -= a;
            li[i + 1] -= a;

            int b = Math.min(li[i], Math.min(li[i + 1], li[i + 2]));
            ans += 7 * b;
            li[i] -= b;
            li[i + 1] -= b;
            li[i + 2] -= b;
        } else {
            int b = Math.min(li[i], Math.min(li[i + 1], li[i + 2]));
            ans += 7 * b;
            li[i] -= b;
            li[i + 1] -= b;
            li[i + 2] -= b;

            int a = Math.min(li[i], li[i + 1]);
            ans += 5 * a;
            li[i] -= a;
            li[i + 1] -= a;
        }

        ans += 3 * li[i];
    }

    System.out.println(ans);
    br.close();
}

}

2. 파이썬 코드

n = int(input()) li = list(map(int, input().split())) + [0,0] ans = 0

for i in range(n): if li[i + 1] > li[i + 2]: a = min(li[i], li[i + 1] - li[i + 2])
ans += 5 * a li[i] -= a li[i + 1] -= a

    b = min(li[i], li[i + 1], li[i + 2])  
    ans += 7 * b
    li[i] -= b
    li[i + 1] -= b
    li[i + 2] -= b


else: 
    b = min(li[i], li[i + 1], li[i + 2]) 
    ans += 7 * b
    li[i] -= b
    li[i + 1] -= b
    li[i + 2] -= b

    a = min(li[i], li[i + 1])
    ans += 5 * a
    li[i] -= a
    li[i + 1] -= a

ans += 3 * li[i]

print(ans) ```

1. 문제 설명

N-Queen 문제는 크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다.

N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하는 프로그램을 작성하시오.

입력 첫째 줄에 N이 주어진다. (1 ≤ N < 15)

출력 첫째 줄에 퀸 N개를 서로 공격할 수 없게 놓는 경우의 수를 출력한다.

2. 문제 접근

매우매우 유명한 백트래킹의 대표격 문제입니다. 백트래킹은 브루트 포스 알고리즘과 같이 모든 가능한 경우를 탐색하지만 탐색을 하며 해가 될 수 없는/유망하지 않은 (Unpromising) 분기들을 차단하여 탐색량을 줄이는 알고리즘입니다. 재귀적 방식을 통해 탐색 중 유망하지 않은 조건 분기를 만나면 선택을 철회하여 이전 상태로 돌아가는 방식입니다. 또한 DFS처럼 탐색할 수 있는 최대 깊이의 분기까지 탐색한 후 다음 분기로 넘어갑니다.

N-Queens 문제를 풀기 위해 체스판의 각 열마다 퀸을 배치해 가고 있습니다. 새로운 퀸을 놓을 때 1. 다른 열에 퀸이 놓여 있는 행, 2. 다른 열의 퀸과 대각선상의 행들을 제외하고 가능한 행에 퀸을 배치할 수 있습니다. 퀸을 놓으면 놓을수록 다음 열에 퀸을 놓을 수 있는 행은 줄어들 것이고, 중간에 더 이상 놓을 수 있는 행이 없다면 가장 마지막에 놓은 퀸을 다른 곳에 놓아 보며 탐색하는 식으로 문제를 풀 수 있습니다.

3. 문제 풀이

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

public class Main {
    static int N;
    static int[] board;
    static boolean[] visited;
    static int result;

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

        nqueen(0);
        System.out.println(result);
    }

    static void nqueen(int depth) {
        if (depth == N) { // 최대 분기에 도달하면(모두 배치) 정답 + 1
            result++;
            return;
        }

        for (int i = 0; i < N; i++) {
            if (!visited[i]) {
                board[depth] = i;

                if (check(depth)) {
                    visited[i] = true;
                    nqueen(depth + 1);
                    visited[i] = false; // 더 이상의 탐색이 불가능하다면 이전 분기로 되돌아감
                }
            }
        }
    }

    static boolean check(int n) { // 같은 행에 있거나 (board[n] == board[i])
        for (int i = 0; i < n; i++) { // 대각선상에 있다면 불가능
            if (board[n] == board[i] || n - i == Math.abs(board[n] - board[i])) {
                return false;
            }
        }
        return true;
    }
}

1. 문제 설명

N줄에 0 이상 9 이하의 숫자가 세 개씩 적혀 있다. 내려가기 게임을 하고 있는데, 이 게임은 첫 줄에서 시작해서 마지막 줄에서 끝나게 되는 놀이이다.

먼저 처음에 적혀 있는 세 개의 숫자 중에서 하나를 골라서 시작하게 된다. 그리고 다음 줄로 내려가는데, 다음 줄로 내려갈 때에는 다음과 같은 제약 조건이 있다. 바로 아래의 수로 넘어가거나, 아니면 바로 아래의 수와 붙어 있는 수로만 이동할 수 있다는 것이다. 이 제약 조건을 그림으로 나타내어 보면 다음과 같다.

별표는 현재 위치이고, 그 아랫 줄의 파란 동그라미는 원룡이가 다음 줄로 내려갈 수 있는 위치이며, 빨간 가위표는 원룡이가 내려갈 수 없는 위치가 된다. 숫자표가 주어져 있을 때, 얻을 수 있는 최대 점수, 최소 점수를 구하는 프로그램을 작성하시오. 점수는 원룡이가 위치한 곳의 수의 합이다.

입력 첫째 줄에 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 숫자가 세 개씩 주어진다. 숫자는 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 중의 하나가 된다.

출력 첫째 줄에 얻을 수 있는 최대 점수와 최소 점수를 띄어서 출력한다.

2. 문제 접근

문제 자체는 어렵지 않은 DP 문제입니다. 점화식도 DP[i][0] += max(DP[i-1][0], DP[i-1][1]).. 등 쉽게 찾을 수 있습니다. 다만 최대, 최소값을 구해야 하므로 다른 점화식으로 두 개의 DP 배열을 만들어야 합니다.

이런 식으로 문제가 왜이리 쉽지? 하고 제출을 해서 메모리 부족으로 실패했습니다. 배열 두 개를 동시에 조회하면서 갱신하다 보니 일반적인 DP 문제보다 메모리를 많이 차지할 수 있습니다. DP 등 재귀적 문제에서 전체 배열을 저장하는 대신 다음 연산에 필요한 만큼의 값만 저장을 하면서 갱신하면서 해결하는 알고리즘을 메모이제이션(Memoization) 이라 합니다.

3. 문제 풀이

import sys

input = sys.stdin.readline

n = int(input())

max_dp = [0] * 3
min_dp = [0] * 3

max_tmp = [0] * 3
min_tmp = [0] * 3

for i in range(n):
    a, b, c = map(int, input().split())
    for j in range(3):
        if j == 0:
            max_tmp[j] = a + max(max_dp[j], max_dp[j + 1])
            min_tmp[j] = a + min(min_dp[j], min_dp[j + 1])
        elif j == 1:
            max_tmp[j] = b + max(max_dp[j - 1], max_dp[j], max_dp[j + 1])
            min_tmp[j] = b + min(min_dp[j - 1], min_dp[j], min_dp[j + 1])
        else:
            max_tmp[j] = c + max(max_dp[j], max_dp[j - 1])
            min_tmp[j] = c + min(min_dp[j], min_dp[j - 1])

    for j in range(3):
        max_dp[j] = max_tmp[j]
        min_dp[j] = min_tmp[j]

print(max(max_dp), min(min_dp))

문제에서 다음 DP항을 계산하는데 필요한 항은 바로 이전 DP 항의 값 3개면 충분합니다. 따라서 이전 계산값을 저장하는 tmp 배열에 저장된 값을 이용해 다음 배열의 값을 구하고 이를 다시 tmp에 저장하는 식의 풀이가 가능합니다!

1. 문제 설명

1부터 N까지의 수를 한 번씩 이용해서 가장 긴 증가하는 부분 수열의 길이가 M이고, 가장 긴 감소하는 부분 수열의 길이가 K인 수열을 출력한다.

2. 문제 접근

아이디어는 간단합니다. 주어진 수 1부터 N을 순서대로 M개의 집합으로 나눕니다. M개의 집합 내부를 내림차순 정렬한 뒤 이어 붙입니다. 각 집합의 원소의 개수는 최대 k개이며, 최소한 하나의 집합은 k개의 원소를 가지고 있어야 합니다.

이 수열의 가장 긴 증가하는 부분 수열의 길이는 M입니다. 각 집합은 부분적으로 감소수열이기 때문에 각 집합에서 최대 한 개의 원소만 부분 수열에 포함할 수 있습니다. 가장 긴 감소하는 부분 수열의 길이도 K입니다. 한 집합의 모든 원소를 전부 다 포함하면 다른 집합의 원소를 포함할 수 없습니다. 각 집합은 오름차순 정렬되어 있으니까요.

N = 10, M = 4, K = 3일 때를 생각해 봅시다. 4개의 집합에 최대 3개의 숫자를 넣을 수 있으므로, 집합 1,2,3의 크기는 3, 4의 크기는 1입니다. 1부터 10까지 숫자를 차례대로 앞의 집합에 넣어 줍니다.

$1 : [1,2,3] ;, 2 : [4,5,6] ;, 3 : [7,8,9] ;, 4 : [10]$

이후 집합마다 뒤집어서 붙여주면 :

$[3,2,1 / 6,5,4 / 9,8,7/ 10]$

정답 수열을 구할 수 있습니다.

숫자 N개를 크기 K인 M개 집합에 넣는 문제이므로 예외 케이스가 발생합니다. N이 M * K보다 커서 숫자를 모두 집어 넣을 수 없거나, N개의 숫자가 충분치 않아서 첫 번째 집합에 K개의 원소가 있고 나머지 원소의 크기가 1인 최소 개수 $(M + (K - 1))$보다 모자르는 경우입니다. 이 두 가지 경우 예외 처리를 해줘야 합니다.

3. 문제 풀이

n, m, k = map(int, input().split())

if (n + 1 < m + k) or (n > m * k):
    print(-1)
    exit()

arr = [1] * m
if k == 1:
    print(*[i for i in range(1, m + 1)])
    exit()

d, r = (n - m) // (k-1) , (n - m) % (k-1)
for i in range(d):
    arr[i] = k
if r > 0 :
    arr[d] += r

ans = []
temp = 0
for a in arr:
    for i in range(temp + a, temp, -1):
        ans.append(i)
    temp += a

print(*ans)

정말 정말 가고 싶었던 싸피 10기에 비전공자 전형으로 합격을 했습니다! 면접을 인터뷰 첫날인 6월 7일에 봤는데.. 발표날 20일까지 시간이 정말 느리게 가더라고요.. 그래도 1지망 서울캠에 합격했을 때 기쁨은 이루 말할 수 없었습니다. 히히히히힣ㅎㅎ 아무튼 합격 기념으로 싸피 준비 과정이나 팁 같은 것들을 말씀드려 볼게요.

1. 지원 당시 스펙

학점 : 3.3/4.5 (수학과) 졸업 예정 프로젝트 경험 : 졸업 프로젝트(데이터 분석) 1회

예.. 뭐 거의 전무합니다.

SW 관련 경험은 거의 없다고 봐도 무방합니다. 개발 공부는 한 지는 6개월 정도, 블로그를 시작한 지는 3개월 정도 되었네요. 백준은 150문제 정도 풀어서 실버 1, 프로그래머스는 100문제 정도 풀었습니다. 앞으로 계속 말하겠지만 스펙보다는 구체적인 노력과 동기를 강조하는 게 정말 중요합니다.

자격증으로는 ADSP와 정처기를 땄습니다. ADSP는 학과 수업을 들으며 준비했고, 정처기는 면접 이후에 합격해서 서류 제출도 못했습니다. 사실 지원할 때 자격증 제출란이 없기 때문에 전혀 중요하지 않다는 사실!

2. 지원 일정

지원서 기간 : 2023.4.24(월) 10:00 ~ 5.8(월) 17:00 적성진단 : 2023.5.13(토) 9,11,13,15시 (지원할 때 희망 시간 제출) 에세이 : 2023.5.9(화) ~ 2023.5.20(토) 23:59 인터뷰 대상 발표 : 2023.5.30(화) 15사 인터뷰 기간 : 2023.6.7(수) ~ 2023.6.13(화) 발표일 : 2023.6.20(수) 15시

3. 지원서

적을 수 있는 것도 적고 정말 심플합니다. 기본 인적사항, 학력, 희망지역, 경력/병역사항, 어학성적을 제출할 수 있습니다. 적을 게 너무 없어서 민망했지만.. 싸피는 여러분의 열쩡!과 학습 의지를 가장 중요하게 보는 것 같아요!

4. SW 적성진단

수리논리 30분, CT 30분으로 진행됩니다. 졸업 예정이기도 하고 적성진단 시험을 한 번도 본 적이 없어서 에듀윌 싸피 문제집으로 준비했습니다. 다 풀지는 않았고, 문제 유형만 훑어보고 모의고사를 몇 회 풀었습니다. 그런데 출제 난이도가 상당히 높더군요. 오히려 CT 문제가 더 쉬웠습니다. CT 쪽이 오히려 전공과 더 유사한 느낌이였네요. 몇 가지 알고리즘과 간단한 풀이법 정도를 알고 보면 좋을 거 같습니다.

5. 에세이

✏️ 에세이 주제 : 어려웠던 경험과 극복 방법 및 지원 동기 관련, 500자 내외(최대 600자)

에세이 분량도 굉장히 적습니다. 글자 수가 적으니까 오히려 분량조절에 실패해서 쓰는데 오래 걸렸네요. 처음에는 내가 이것 저것 했다 식으로 경험들을 나열하다 보니까 분량은 빡빡한데 알맹이가 없는 느낌이였어요.

그래서 경험을 한 가지로 줄이고 어려웠던 이유, 내가 노력을 통해 이를 극복한 방법, 그대로 이어서 싸피가 이러한 어려움을 어떻게 해결해 줄 것이다 까지 관통된 스토리라인을 가지고 쓰려고 노력했습니다. 싸피는 분명히 교육 과정인 걸 잊지 말고 내가 얼마나 완성이 되어있고 뛰어난지 보다는 나의 노력과 열정으로 싸피에서 내 부족한 부분을 어떻게 채울 수 있을지 말하는 게 좋은 것 같아요!

싸피 사이트에 있는 인재상도 참고했습니다. 인재상에서 강조하는 세 가지 항목을 에세이 뿐만 아니라 인터뷰에서도 중요한 키워드로 활용해 봐야지 하고 준비했습니다.

6. 인터뷰 준비

서류 합격을 확인하고 바로 오픈채팅방에서 스터디를 구했습니다. 물론 스터디를 꼭 해야만 하는건 아니지만 저처럼 면접 경험이 없는 분들은 스터디를 통해 많은 도움을 받으실 수 있을 거에요! 노션을 이용해서 공통 질문 리스트에 대한 각자의 예상 답변을 올리고, 모의 면접을 하면서 서로 피드백을 주고받는 시간을 가졌습니다.

• 에세이 기반 예상질문
• 1분 자기소개

(공통 인성질문)

• 프로젝트 경험, 경험 속에서 갈등 해결/리더쉽 발휘 사례
• 싸피 관련 지원동기(왜 싸피여야 하는가, 싸피에서 듣고 싶은 커리큘럼)
• 개발/iT에 관심을 가지게 된 동기
• 열정을 갖고 스스로 공부한 경험 등등..

PT 면접은 다른 많은 분들처럼 강민혁 님의 PT면접 영상을 봤습니다. (영상 링크) 또 스터디에서 IT 트렌드 기사들을 모아논 다음 몇개를 랜덤으로 뽑아서 하는 식으로 모의 PT 면접도 했습니다. 5분이라는 시간은 짧아 보이지만 발표 내용의 구조를 충분히 탄탄히 짜놓지 않으면 생각보다 채우기 힘들기 때문에 연습을 해 보는게 중요합니다.

7. 면접 당일

저는 면접이 좀 일찍 끝난 편이였어요. 긴장해서 말을 너무 빨리 하기도 했고, 머리가 하얘져서 준비한 대답들을 많이 까먹고 똑같은 말을 반복하는 느낌이 있어서 나오자마자 '아 망했네'라고 생각했습니다.

그래도 끝까지 희망의 끈을 놓지 않은 이유가 몇 가지 있었습니다. PT 면접은 모의 연습을 한 게 도움이 많이 되어서 자신이 있었고, 내가 스스로 얼마나 열심히 공부하는지, 또 앞으로 얼마나 열심히 할 건지를 열심히 어필한 게 도움이 되지 않았나 싶어요.

싸피는 비전공자 여러분들의 열쩡! 넘치는 동기와 학습 의지를 정말 중요하게 생각합니다. 그래서 SW 관련 경험이 거의 없으시지만 새로운 분야에 도전 의지가 충만하다면 반드시 붙으실 수 있을 거라 생각합니다.

1. 문제 설명

준호는 요즘 디펜스 게임에 푹 빠져 있습니다. 디펜스 게임은 준호가 보유한 병사 n명으로 연속되는 적의 공격을 순서대로 막는 게임입니다. 디펜스 게임은 다음과 같은 규칙으로 진행됩니다.

준호는 처음에 병사 n명을 가지고 있습니다. 매 라운드마다 enemy[i]마리의 적이 등장합니다. 남은 병사 중 enemy[i]명 만큼 소모하여 enemy[i]마리의 적을 막을 수 있습니다. 예를 들어 남은 병사가 7명이고, 적의 수가 2마리인 경우, 현재 라운드를 막으면 7 - 2 = 5명의 병사가 남습니다. 남은 병사의 수보다 현재 라운드의 적의 수가 더 많으면 게임이 종료됩니다. 게임에는 무적권이라는 스킬이 있으며, 무적권을 사용하면 병사의 소모없이 한 라운드의 공격을 막을 수 있습니다. 무적권은 최대 k번 사용할 수 있습니다. 준호는 무적권을 적절한 시기에 사용하여 최대한 많은 라운드를 진행하고 싶습니다.

준호가 처음 가지고 있는 병사의 수 n, 사용 가능한 무적권의 횟수 k, 매 라운드마다 공격해오는 적의 수가 순서대로 담긴 정수 배열 enemy가 매개변수로 주어집니다. 준호가 몇 라운드까지 막을 수 있는지 return 하도록 solution 함수를 완성해주세요.

제한사항

• 1 ≤ n ≤ 1,000,000,000

• 1 ≤ k ≤ 500,000

• 1 ≤ enemy의 길이 ≤ 1,000,000

• 1 ≤ enemy[i] ≤ 1,000,000 enemy[i]에는 i + 1 라운드에서 공격해오는 적의 수가 담겨있습니다.

• 모든 라운드를 막을 수 있는 경우에는 enemy[i]의 길이를 return 해주세요.

• 입출력 예

2. 문제 접근

무적권을 이용해 최대 k번 공격을 넘길 수 있지만 대부분의 경우 k가 주어진 배열 enemy의 길이보다 크지 않습니다. 따라서 k가 enemy 배열의 길이보다 작아서 무적권을 선택적으로 사용해야 하는 경우를 고려해야 합니다. 현재 라운드가 $k + 1$ 번째 라운드라 합시다. $k + 1$ 번의 enemy 웨이브 중에 가장 어려운 $k$개의 무적권을 사용한다고 가정해도 가장 약한 한 번의 라운드는 병사를 소모할 수 밖에 없습니다. 따라서 $k + 1$ 번째부터 이후 계속 가장 약한 라운드마다 병사를 소모한다고 가정하며 진행해야 합니다. 이럴 때 사용할 수 있는 가장 좋은 자료구조는 우선순위배열, 힙(heap)입니다.

3. 문제 풀이

from heapq import heappush, heappop

def solution(n, k, enemy):
    hq = []
    for round, monster in enumerate(enemy):
        heappush(hq, monster)
        if len(hq) > k:
            n -= heappop(hq)
        if n < 0:
            return round

    return len(enemy)

우선 enemy 배열의 원소를 heap에 하나씩 넣어 줍니다. 만약에 k가 enemy보다 크다면(if len(hq) < k:) 바로 enemy 배열의 길이를 return해주면 됩니다. heap의 길이가 k보다 커질 경우 매번 heap에서 가장 작은 원소를 제거하고 n(병사의 수)에서 빼줍니다. n이 음수가 된다면 더 이상의 라운드를 진행할 수 없는 상태가 됩니다. 따라서 그 전 라운드의 숫자를 반환해 주면 되는데, enumerate를 통해 인덱스를 호출하면 라운드의 순서를 찾을 수 있습니다.

1. 문제 설명

우현이는 어린 시절, 지구 외의 다른 행성에서도 인류들이 살아갈 수 있는 미래가 오리라 믿었다. 그리고 그가 지구라는 세상에 발을 내려 놓은 지 23년이 지난 지금, 세계 최연소 ASNA 우주 비행사가 되어 새로운 세계에 발을 내려 놓는 영광의 순간을 기다리고 있다.

그가 탑승하게 될 우주선은 Alpha Centauri라는 새로운 인류의 보금자리를 개척하기 위한 대규모 생활 유지 시스템을 탑재하고 있기 때문에, 그 크기와 질량이 엄청난 이유로 최신기술력을 총 동원하여 개발한 공간이동 장치를 탑재하였다. 하지만 이 공간이동 장치는 이동 거리를 급격하게 늘릴 경우 기계에 심각한 결함이 발생하는 단점이 있어서, 이전 작동시기에 k광년을 이동하였을 때는 k-1 , k 혹은 k+1 광년만을 다시 이동할 수 있다. 예를 들어, 이 장치를 처음 작동시킬 경우 -1 , 0 , 1 광년을 이론상 이동할 수 있으나 사실상 음수 혹은 0 거리만큼의 이동은 의미가 없으므로 1 광년을 이동할 수 있으며, 그 다음에는 0 , 1 , 2 광년을 이동할 수 있는 것이다. ( 여기서 다시 2광년을 이동한다면 다음 시기엔 1, 2, 3 광년을 이동할 수 있다. )

김우현은 공간이동 장치 작동시의 에너지 소모가 크다는 점을 잘 알고 있기 때문에 x지점에서 y지점을 향해 최소한의 작동 횟수로 이동하려 한다. 하지만 y지점에 도착해서도 공간 이동장치의 안전성을 위하여 y지점에 도착하기 바로 직전의 이동거리는 반드시 1광년으로 하려 한다.

김우현을 위해 x지점부터 정확히 y지점으로 이동하는데 필요한 공간 이동 장치 작동 횟수의 최솟값을 구하는 프로그램을 작성하라.

2. 문제 접근

출발할 때 0의 속도로 출발하며, 도착할 때도 0까지 속도를 줄여야 합니다. 가장 이상적인 케이스는 최고 속도가 $n$일 때 $1\rightarrow 2\rightarrow3\rightarrow...\rightarrow n\rightarrow (n-1)\rightarrow .... \rightarrow 1$ 으로 가는 경우입니다. 이 때 이동한 거리는 $n^2$가 됩니다. 하지만 당연히 주어진 모든 수가 제곱수일 수 없습니다. 이동해야 할 거리가 $n^2+k(0<k<2n-1)$이라고 하면, $k/n$은 0보다 크고 2보다 작게 됩니다. 예를 들어서 $k=n+1$이라 하면, $n\rightarrow (n-1)\rightarrow...\rightarrow 1$ 부분을 $n\rightarrow n\rightarrow (n-1)\rightarrow...\rightarrow 1\rightarrow 1$과 같이 2번 더 가주면 됩니다. $k$를 $n$으로 나눈 값이 1보다 크면 2번, 1보다 작으면 1번 더 이동하게 됩니다. 저는 그냥 나누기를 해서 소수 올림 처리 했는데, 이런 성질을 사용하면 좀 더 깔끔한 코드가 나올 것 같습니다.

3. 문제 풀이

import sys
from math import ceil, sqrt
T = int(sys.stdin.readline())
for _ in range(T):
    a,b = map(int, sys.stdin.readline().split())
    n = b - a
    print(2*int(sqrt(n))-1+ceil((n - int(sqrt(n))**2)/int(sqrt(n))))

int(sqrt(b-a))을 하면 주어진 거리에 대한 n을 찾을 수 있습니다. 처음에는 2*n+1만큼 이동을 한다고 가정을 하고, 뒷 부분에 나머지 부분을 처리해 줬습니다.

1. 문제 설명

혼자서도 잘 노는 범희는 어느 날 방구석에 있는 숫자 카드 더미를 보더니 혼자 할 수 있는 재미있는 게임을 생각해냈습니다.

숫자 카드 더미에는 카드가 총 100장 있으며, 각 카드에는 1부터 100까지 숫자가 하나씩 적혀있습니다. 2 이상 100 이하의 자연수를 하나 정해 그 수보다 작거나 같은 숫자 카드들을 준비하고, 준비한 카드의 수만큼 작은 상자를 준비하면 게임을 시작할 수 있으며 게임 방법은 다음과 같습니다.

준비된 상자에 카드를 한 장씩 넣고, 상자를 무작위로 섞어 일렬로 나열합니다. 상자가 일렬로 나열되면 상자가 나열된 순서에 따라 1번부터 순차적으로 증가하는 번호를 붙입니다.

그 다음 임의의 상자를 하나 선택하여 선택한 상자 안의 숫자 카드를 확인합니다. 다음으로 확인한 카드에 적힌 번호에 해당하는 상자를 열어 안에 담긴 카드에 적힌 숫자를 확인합니다. 마찬가지로 숫자에 해당하는 번호를 가진 상자를 계속해서 열어가며, 열어야 하는 상자가 이미 열려있을 때까지 반복합니다.

이렇게 연 상자들은 1번 상자 그룹입니다. 이제 1번 상자 그룹을 다른 상자들과 섞이지 않도록 따로 둡니다. 만약 1번 상자 그룹을 제외하고 남는 상자가 없으면 그대로 게임이 종료되며, 이때 획득하는 점수는 0점입니다.

그렇지 않다면 남은 상자 중 다시 임의의 상자 하나를 골라 같은 방식으로 이미 열려있는 상자를 만날 때까지 상자를 엽니다. 이렇게 연 상자들은 2번 상자 그룹입니다.

1번 상자 그룹에 속한 상자의 수와 2번 상자 그룹에 속한 상자의 수를 곱한 값이 게임의 점수입니다.

상자 안에 들어있는 카드 번호가 순서대로 담긴 배열 cards가 매개변수로 주어질 때, 범희가 이 게임에서 얻을 수 있는 최고 점수를 구해서 return 하도록 solution 함수를 완성해주세요.

제한사항

• 2 ≤ cards의 길이 ≤ 100

• cards의 원소는 cards의 길이 이하인 임의의 자연수입니다.

• cards에는 중복되는 원소가 존재하지 않습니다.

• cards[i]는 i + 1번 상자에 담긴 카드에 적힌 숫자를 의미합니다.

• 입출력 예

• 입출력 예 설명

1, 4, 7, 8이 속하는 상자의 그룹과 2, 5, 6이 속하는 상자의 그룹과 3이 속하는 상자의 그룹이 존재합니다. 따라서 3번 상자를 고르지 않았을 때, 두 번의 시행에서 3과 4를 기록하며 최고 점수 12를 얻을 수 있습니다.

2. 문제 접근

주어진 문자열 cards에서 주어진 규칙을 따라 생성되는 loop들을 찾은 뒤, 합이 가장 큰 loop 둘의 곱을 구하는 문제입니다. 주어진 수열은 수열의 길이 이하의 자연수들이 중복 없이 구성하는 수열이므로 반드시 하나 이상의 loop을 만들 수 있습니다. 규칙에 따라 loop을 만들되 loop이 하나만 생성되면 문제의 조건에 따라 0을 return해줘야 합니다. loop를 구하는 방법은 많지만 반드시 loop가 생성된다는 전제가 있으므로 DFS가 매우 효율적이겠다고 생각했습니다. 실제로 처리 시간도 매우 빨랐습니다.

3. 문제 풀이

def dfs(card, path, cards, visited, loops):
    path.append(card)
    visited.add(card)
    next_card = cards[card - 1]

    if next_card in path:
        loop_start = path.index(next_card)
        loop = path[loop_start:]
        loops.append(loop)
        return

    if next_card not in visited:
        dfs(next_card, path, cards, visited, loops)

def solution(cards):
    visited = set()
    loops = []

    for card in range(len(cards)):
        if card not in visited:
            dfs(card, [], cards, visited, loops)

    loops.sort(key=len, reverse=True)

    if len(loops) == 1:
        return 0
    return len(loops[0]) * len(loops[1])