두부의 코딩일기

https://www.acmicpc.net/problem/2073 2073번: 수도배관공사 아기염소들이 언덕에서 풀을 뜯고 놀다 보면 항상 도중에 목이 마르곤 했다. 그들은 불편함을 참지 못하고 수도관을 설치하여 거리 D(7 ≤ D ≤ 100,000)만큼 떨어진 곳의 강에서 물을 끌어오기로 www.acmicpc.net ✅ 골드 Ⅳ 🔶 풀이 해당 문제는 다이나믹 프로그래밍(dp)로 문제의 조건은 아래와 같다. 1️⃣ 파이프는 하나씩 사용이 가능하고, 수도배관 길이는 강까지의 거리(D)와 동일해야 한다. 2️⃣ 수도배관을 완성했을 경우, 가장 적은 용량을 가진 파이프가 해당 수도배관의 용량이다. 3️⃣ 동일한 길이를 가진 여러 개의 수도배관 중에 가장 큰 용량을 구하라. 파이프의 길이를 정확하게 강까지의 거..

최장 증가 부분 수열 (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 ..