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

LIS(최장 증가 부분 수열)

Longest Increasing Subsequence 수열 수열(數列)은 수 또는 다른 대상의 순서 있는 나열이다. 나열 순서를 생각해야 하고 중복이 허용된다는 점에서 집합과 구분된다. 부분 수열 부분 수열이란, 나열 순서가 변하지 않은 채로 일부 항을 제거해 얻는 새로운 수열을 의미한다. 최장 증가 부분 수열 부분 수열 중 오름 차순으로 정렬된 가장 긴 수열을 최장 증가 부분 수열이라고 한다. 정의 최장 증가 부분 수열 문제는 동적 계획법으로 풀 수 있는 유명한 알고리즘 문제이다. 예를 들어 다음과 같은 수열이 주어졌다고 하자. 5 3 7 8 6 2 9 4위 수열에서 특정 위치에 있는 몇개의 수를 제거해 부분 수열을 만들 수 있는데, 그 중에서 최장 증가 부분 수열을 구해보자. ✔ 첫 번째 조건은 나..

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

금광 아이디어 다음 열로 이동하고자 하는 목적지에 대해 아래의 세 가지 경우만 고려하면 된다. ✔ 왼쪽 위에서 오는 경우 ✔ 왼쪽에서 오는 경우 ✔ 왼쪽 아래에서 오는 경우 위 케이스를 고려한 점화식은 다음과 같다. $$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, ..

조합(Combination)

조합(Combination) 이번 시간에는 DFS 로 조합을 구현하는 방법을 배워보자. N 명 중 R 명을 뽑는 경우의 수 nCr 은 n 개의 원소를 갖는 집합에서 r 개의 부분 집합을 고르는 경우의 수를 의미하므로 부분 집합과도 관련이 있다. 구현 // 조합(Combination) : nCr = n-1Cr-1 + n-1Cr // n 명 중에서 r 명을 뽑는 경우 // 5C3 = 4C2 + 4C3 public class Main { static int[][] store = new int[35][35]; public static void main(String[] args) { Scanner sc = new Scanner(System.in); System.out.println(combinationByDfsW..