두부의 코딩일기

최장 증가 부분 수열 (LIS, Longest Increasing Subsequence) 정의 주어진 수열에서 원소들의 순서를 유지하면서 증가하는 가장 긴 부분 수열을 찾는 알고리즘으로 별도로 정렬이 필요 없다. 위 그림은 주어진 배열에서의 증가하는 부분 수열을 나타낸 예시로 최장 증가 부분 수열(LIS)은 두 번째로 보이는 그림이다. 최장 증가 부분 수열 작동 원리 최장 증가 부분 수열을 찾기 위해서는 다이나믹 프로그래밍(dp)을 사용해야 된다. dp[i]는 i번째 수를 마지막 원소로 가지는 최장 증가 부분 수열의 길이다. i번째의 LIS 길이를 구하는 방법은 0부터 i-1번째까지의 값에서 i번째 수보다 값이 작고 dp값이 가장 큰 값의 +1이다. 위의 그림으로 예제를 보겠다. arr 배열에 첫 번째 ..

자바에서 문자열을 자르는 방법은 substring() 메서드와 split() 메서드가 대표적이다. substring(beginIndex, [endIndex]) substring 메서드는 기본적으로 인자2개를 받을 수 있지만 두 번째 인자값 endIndex는 생략할 수 있다. 생략하게 되면 해당 문자열의 마지막 인덱스까지 반환한다. String str = "Hello World"; System.out.println(str.substring(6)); // World System.out.println(str.substring(0, 4)); // Hello split(String regex) split 메서드는 정규 표현식을 기반으로 문자열을 나누어 배열로 반환한다. String tmp = "Hello,Worl..

https://www.acmicpc.net/problem/18430 18430번: 무기 공학 첫째 줄에는 길동이가 가지고 있는 나무 재료의 세로, 가로 크기를 의미하는 두 자연수 N, M이 주어진다. (1 ≤ N, M ≤ 5) 다음 N개의 줄에 걸쳐서, 매 줄마다 나무 재료의 각 위치의 강도를 나타내 www.acmicpc.net ✅ 골드 Ⅳ 🔶 풀이 N x M 크기의 고급 나무 재료가 주어졌을 때, 'ㄱ'자 모양 부메랑들의 강도 합이 최댓값을 구하라. N과 M의 크기가 작으므로 완전 탐색으로 해결할 수 있다. 우선 백트래킹을 사용하기 위해서 dfs를 이용한다. idx를 0부터 순차적으로 늘리면서 좌표값 (x, y)를 제어해 줬다. int x = idx/M; int y = idx%M; idx가 N*M에 도..

https://www.acmicpc.net/problem/17266 17266번: 어두운 굴다리 인하대학교 후문 뒤쪽에는 어두운 굴다리가 있다. 겁쟁이 상빈이는 길이 조금이라도 어둡다면 가지 않는다. 따라서 굴다리로 가면 최단거리로 집까지 갈수 있지만, 굴다리는 어둡기 때문에 빙 www.acmicpc.net ✅실버 Ⅳ 🔶 풀이 굴다리 길이(N)와 가로등 개수(M), 가로등 설치 위치가 주어지고, 굴다리의 모든 곳을 비추어라. 가로등 높이가 1 증가할 때마다 길이 1만큼 더 주위를 비출 수 있다. 이분 탐색을 이용해서 가로등의 적정 높이를 찾아주면 된다. 가로등의 높이를 기준으로 굴다리의 모든 곳을 비출 수 있는지 확인하면서 가능하다면 최댓값(right)를 mid-1로, 불가능하다면 최솟값(left)를 m..

타이머 기본 구조 자바에서는 Timer() 클래스와 TimerTask() 클래스를 이용해서 주기적으로 작업을 진행할 수 있다. 해당 클래스는 JDK 1.3에 새롭게 추가되었다고한다. Timer() : 실제 타이머의 기능을 수행 TimerTask(): 수행되는 내용을 run() 메소드를 재정의함으로써 실행 import java.io.IOException; import java.util.Timer; import java.util.TimerTask; public class Main { public static void main(String[] args) throws IOException { Timer t = new Timer(); TimerTask task = new TimerTask() { public vo..

자바스크립트를 실행하려면 웹브라우저와 에디터만 있으면 된다. 웹브라우저는 크롬, 에디터는 Notepad++를 사용했다. (노트패드가 없는 경우에는 메모장을 사용해도 된다.) 1. 노트패드를 실행하고 아래 구문을 입력한다. HTML 기본 구조다.

플로이드-워셜 (Floyd-Warshall) vs 다익스트라 (Dijkstra) 다익스트라 플로이드-워셜 사용 목적 단일 출발점 최단 경로를 찾음 모든 정점 쌍 간의 최단 경로를 찾음 가중치 제약 음의 가중치를 가진 간선을 처리할 수 없음 음의 가중치를 가진 간선을 처리할 수 잇음 기본 구조 그래프의 인접 리스트 혹은 인접 행렬을 사용함 그래프의 인접 행렬을 사용함 시간 복잡도 O(V+E)logV (우선 순위 큐를 사용했을 경우) O($N^{3}$) 알고리즘 유형 그리드 알고리즘 동적 프로그래밍 플로이드-워셜 개요 플로이드-워셜은 a → b 로 가는 비용과 a → c → b 로 가는 비용 중에 더 적은 값을 최단 거리로 판단하는 알고리즘으로 다음과 같은 점화식을 가진다. dpab= Math.min(dpa..

https://www.acmicpc.net/problem/11052 11052번: 카드 구매하기 첫째 줄에 민규가 구매하려고 하는 카드의 개수 N이 주어진다. (1 ≤ N ≤ 1,000) 둘째 줄에는 Pi가 P1부터 PN까지 순서대로 주어진다. (1 ≤ Pi ≤ 10,000) www.acmicpc.net ✅ 실버 Ⅰ 🔶 풀이 N개의 카드를 구매하기 위해 지불해야 하는 금액의 최댓값을 구하시오. 다이나믹 프로그래밍 문제다. 예제 2번으로 규칙을 찾아보겠다. 카드팩은 총 5개이고, 카드 5개를 구매하기 위해 지불해야 하는 최대 금액을 찾으면 된다. P1 = 10, P2 = 9, P3 = 8, P4 = 7, P5 = 6 card[1] = 10, card[2] = 9, card[3] = 8, card[4] = ..

https://www.acmicpc.net/problem/1759 1759번: 암호 만들기 첫째 줄에 두 정수 L, C가 주어진다. (3 ≤ L ≤ C ≤ 15) 다음 줄에는 C개의 문자들이 공백으로 구분되어 주어진다. 주어지는 문자들은 알파벳 소문자이며, 중복되는 것은 없다. www.acmicpc.net ✅ 골드 Ⅴ 🔶 풀이 최소 한 개의 모음과 두 개의 자음으로 구성된 길이 L의 암호를 출력하라. 백트래킹으로 풀어야 된다. 해당 문제에서는 알파벳이 증가하는 순서로 배열되었을 것이라고 한다. 정렬은 필수다. 우선, 이미 선택한 알파벳보다 큰 알파벳을 선택해서 임의의 L 길이를 가진 암호를 만든다. L 길이가 완성됐다면 최소 모음 1개, 자음 2개를 가지고 있는지 판단해 준다. public static ..

https://www.acmicpc.net/problem/1238 1238번: 파티 첫째 줄에 N(1 ≤ N ≤ 1,000), M(1 ≤ M ≤ 10,000), X가 공백으로 구분되어 입력된다. 두 번째 줄부터 M+1번째 줄까지 i번째 도로의 시작점, 끝점, 그리고 이 도로를 지나는데 필요한 소요시간 Ti가 들어 www.acmicpc.net ✅ 골드 Ⅲ 🔶 풀이 각 각의 마을에서 파티가 열린 마을 X를 방문했다가 다시 돌아왔을 때 가장 많이 시간을 소비한 학생을 구하라. 모든 가중치가 양수이고, 한 정점에서 다른 모든 정점까지의 최단 거리를 구해야하므로 다익스트라. 다익스트라를 두 번 나누어서 해결했다. 1. X에서 각 마을까지의 최단 거리 2. 각 마을에서 X까지의 최단 거리 (역방향) 위 두가지를 구..