2020 카카오 신입 공채 : 문자열 압축

문자열 압축 프로그래머스 문자열 압축 해설 aabbaccc -> 2a2ba3c s 의 길이는 1

이것이 코딩 테스트다 : 편집 거리

편집 거리 책 이것이 코딩 테스트다의 편집 거리 해설 ✔ 두 문자가 같은 경우 : dp[i][j] = dp[i - 1][j - 1] ✔ 두 문자가 다른 경우 : dp[i][j] = 1 + MIN(dp[i][j - 1], dp[i - 1][j], dp[i - 1][j - 1]) 두 문자가 같은 경우 점화식이 위 처럼 되는 이유는 다음과 같다. 두 번째 그림에서 3번을 예시로 설명하겠다. S 를 가지고 SA 를 만들기 위한 최소 편집 거리에 교체 연산을 추가로 실시 즉, SAU -> SAT 로 만들기 위한 것이라고 생각하면 된다. * DP[2][3] = DP[1][2] + 교체 연산 근데 만약에 U 랑 T 문자가 같다고하면 교체 연산을 추가로 할 필요가 없기 때문에 왼쪽 위의 값을 그대로 대입해주면 된다. ..

[BOJ 18353] 병사 배치하기

병사 배치하기 BOJ 18353 : 병사 배치하기 해설 이 문제는 최장 증가 부분 수열(LIS) 문제로, 부분 수열에 대한 개념과 LIS 알고리즘 풀이 방법을 모른다면 링크를 통해 배우도록 하자. ✔ 병사를 배치할 때, 앞쪽에 있는 병사의 전투력이 항상 뒤쪽보다 높아야 한다. ✔ 즉, 최종 결과 안에 전투력이 중복된 병사가 존재하면 안된다. ✔ 특정 위치에 있는 병사를 열외 시킨다는 의미 ✔ 입력 값이 주어지면 따로 내림차순 혹은 오름차순으로 정렬한 다음 계산하는 것이 아니라, 주어진 입력 값에서 특정 위치에 있는 병사를 제거하여 문제의 조건을 만족하라는 의미 따라서, 주어진 입력 값에서 특정 위치에 있는 병사를 제거하여, 앞쪽에 있는 병사의 전투력이 뒤 쪽에 있는 병사의 전투력보다 높도록 하되, 남아있..

이것이 코딩테스트다 : 금광

금광 아이디어 다음 열로 이동하고자 하는 목적지에 대해 아래의 세 가지 경우만 고려하면 된다. ✔ 왼쪽 위에서 오는 경우 ✔ 왼쪽에서 오는 경우 ✔ 왼쪽 아래에서 오는 경우 위 케이스를 고려한 점화식은 다음과 같다. $$dp[x][y] = dp[x][y] + max(leftUp, left, leftDown)$$ 구현 public class Main { static int T; static List testcases = new ArrayList(); static int[][] dp; public static void main(String[] args) { input(); solution(); } static void input() { Scanner sc = new Scanner(System.in); T =..

[BOJ 14502] 연구소

연구소 BOJ 14502 : 연구소 해설 연구소 문제는 치킨 배달 이 문제와 상당히 유사하다. 핵심 아이디어는 조합(Combination)을 사용하는 것이다. ✔ 연구소는 N X M 크기의 직사각형 ✔ 직사각형은 1 x 1 크기를 갖는 정사각형들의 집합 ✔ 연구소는 빈칸과 벽으로 이루어져 있음 ✔ 일부 칸에는 바이러스 존재 ✔ 바이러스는 상하좌우로 인접한 빈칸으로 퍼져나감 ✔ 바이러스 퍼지는 것을 막기 위해 새로운 벽을 3개 세워야 함 ✔ 벽을 3개 세운 뒤, 바이러스가 퍼질 수 없는 곳을 안전영역이라 함 0 : 빈칸 1 : 벽 2 : 바이러스💡일단 안전 영역의 최댓값은 곧 빈칸(Empty)의 최댓값이니까 빈칸 좌표들을 List 에 담고 💡List 에 담긴 빈칸들 중에서 3개를 뽑는 조합을 사용 💡벽을 ..

[BOJ 15686] 치킨 배달

치킨 배달 BOJ 15686 : 치킨 배달 해설 ✔ N X N 크기의 도시 존재 ✔ 도시는 1 X 1 크기 ✔ 도시의 각 칸은 좌표 형태(r,c) 이며 '빈칸' OR '치킨집' ✔ r 과 c 는 1부터 시작 ✔ 치킨 거리 : 집과 가장 가까운 치킨집 사이의 거리 ✔ 도시의 치킨 거리는 모든 집의 치킨 거리의 합 ✔ (r1, c1) 과 (r2, c2) 사이의 거리는 Math.abs((r1 - r2) + (c1 - c2)) ✔ 0은 빈칸, 1은 집, 2는 치킨집 # 입력 예시 1번 (1, 1, #0) (1, 2, #0) (1, 3, #HOUSE) (1, 4, #0) (1, 5, #0) (2, 1, #0) (2, 2, #0) (2, 3, #CHICKEN) (2, 4, #0) (2, 5, #HOUSE) (3, ..

[BOJ 16234] 인구 이동

인구 이동 BOJ 16234 : 인구 이동 해설 이 문제는 2차원 배열의 탐색 문제이기 때문에 좌표 형태를 그래프로 바꿔야 한다는 생각을 먼저 하였다. 문제의 입력 예시 4번을 가지고 해설할 것이다. 입력 N : 3, L : 5, R : 10 3 5 10 10 15 20 20 30 25 40 22 10 L 인구 이동이 불가능 할 때 까지 반복 구현 class Country { private int x; private int y; public Country(int x, int y) { this.x = x; this.y = y; } public int getX() { return x; } public int getY() { return y; } } public class Main { private stati..

[BOJ 1715] 카드 정렬하기

카드 정렬하기 BOJ 1715 : 카드 정렬하기 해설 구현 public class Main { private static int N; private static PriorityQueue pQ = new PriorityQueue(); public static void main(String[] args) { input(); solution(); } private static void input() { Scanner sc = new Scanner(System.in); N = sc.nextInt(); for (int i = 0; i ..