두부의 코딩일기

https://www.acmicpc.net/problem/1102 1102번: 발전소 첫째 줄에 발전소의 개수 N이 주어진다. N은 16보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에는 발전소 i를 이용해서 발전소 j를 재시작할 때 드는 비용이 주어진다. i줄의 j번째 값이 그 www.acmicpc.net 🔶 풀이 비트마스킹 dp. 이 문제를 해결하기 위해서 비트마스크를 공부했다. 공부 내용은 추후에 올릴 예정✌️ 2023.04.17 추가 - 비트마스크 참고 포스팅 비트마스크에서 흔히 사용하는 연산은 두 가지다. 1. num | (1

https://www.acmicpc.net/problem/1028 1028번: 다이아몬드 광산 첫째 줄에 R과 C가 주어진다. R과 C는 750보다 작거나 같은 자연수이다. 둘째 줄부터 R개의 줄에는 다이아몬드 광산의 모양이 주어진다. www.acmicpc.net 🔶 풀이 처음으로 도전한 플레티넘 문제, 퇴근 후에 하루종일 풀었다... 최근에 풀었던 [가장 큰 정사각형] 문제 상위버전인듯하다. row와 col의 최대 크기는 750, 단순 완전 탐색으로는 시간초과가 발생하기 때문에 dp를 활용해야 함 1. map[row][col]에서 값이 1인 경우에 4방향(↙ ↘ ↖ ↗)으로 뻗어나가면서 변의 길이를 구한다. public static int getSize(int x, int y, int d) { int ..

https://www.acmicpc.net/problem/1915 1915번: 가장 큰 정사각형 첫째 줄에 n, m(1 ≤ n, m ≤ 1,000)이 주어진다. 다음 n개의 줄에는 m개의 숫자로 배열이 주어진다. www.acmicpc.net 🔶 풀이 처음에 완전 탐색으로 풀어보려했지만 n과 m의 범위를 보고 바로 후퇴... 어떻게 풀어야할지 감이 안잡혀서 [알고리즘 분류]를 봤더니 다이나믹 프로그래밍이였다. dp 알고리즘의 기본은 점화식을 찾아야된다. 점화식을 찾는건 정말 힘들다. 소소한 팁을 주자면 공책에 적어보면 규칙이 보인다. 가장 큰 정사각형의 넓이를 구해야한다. 우선, N=1 혹은 M=1인 상황은 무조건 1을 출력한다. (문제에서 배열의 크기는 1부터 1000이라고 명시되어있음) 2x2 이상의 ..

https://www.acmicpc.net/problem/2146 2146번: 다리 만들기 여러 섬으로 이루어진 나라가 있다. 이 나라의 대통령은 섬을 잇는 다리를 만들겠다는 공약으로 인기몰이를 해 당선될 수 있었다. 하지만 막상 대통령에 취임하자, 다리를 놓는다는 것이 아깝다 www.acmicpc.net 🔶 풀이 "섬에서 섬으로 건너갈 수 있는 가장 짧은 다리의 길이는?" 가장 먼저 해야할 건 각각의 섬에 다른 번호를 매겨주는 것이다. 여러 개의 섬이 존재하는데 번호가 같으면 bfs를 이용해서 다른 섬을 찾아가는 게 힘들다. public static void setLand (int x, int y, int num) { Queue q = new LinkedList(); q.add(new Pos(x, y,..

https://www.acmicpc.net/problem/2638 2638번: 치즈 첫째 줄에는 모눈종이의 크기를 나타내는 두 개의 정수 N, M (5 ≤ N, M ≤ 100)이 주어진다. 그 다음 N개의 줄에는 모눈종이 위의 격자에 치즈가 있는 부분은 1로 표시되고, 치즈가 없는 부분은 0으로 www.acmicpc.net 🔶 풀이 외부 공기와 접촉하고 있는 변이 2개 이상인 치즈는 1시간 뒤에 녹는다. "몇 시간 뒤에 치즈가 다 녹아서 없어질까?" 처음엔 치즈를 기준으로 bfs를 돌릴 생각으로 풀다가 시간을 많이 소비했다. 치즈가 아닌 공기를 기준으로 bfs를 돌려야 정답을 구할 수 있는데 문제는 외부 공기와 내부 공기가 나누어져 있다. (0, 0)부터 시작해서 bfs를 돌려준다. 내부 공기와 구분을 ..

오라클에서는 여러 행으로 조회된 컬럼 값을 하나로 합쳐주는 함수가 있다. 오라클 9i 이하에서는 XMLAGG, 오라클 10g - 11g R1 에서는 WM_CONCAT, 오라클 11g R2 부터는 WM_CONCAT 함수를 사용할 수 없고, LISTAGG 함수를 사용하면 된다. 오라클 버전 함수명 ~ 9i XMLAGG 10g ~ 11g R1 WM_CONCAT 11g R2 ~ LISTAGG LISTAGG 함수는 그룹 함수이므로 GROUP BY 또는 PARTITION BY 절과 함께 사용해야한다. 또한, WM_CONCAT 함수처럼 DISTINCT를 사용할 수 없지만 정규식 함수를 사용하여 중복 제거를 할 수 있고, ORDER BY절로 정렬도 가능하다. 기본 문법 SELECT LISTAGG(합칠 컬럼명, 구분자)..

https://www.acmicpc.net/problem/14499 14499번: 주사위 굴리기 첫째 줄에 지도의 세로 크기 N, 가로 크기 M (1 ≤ N, M ≤ 20), 주사위를 놓은 곳의 좌표 x, y(0 ≤ x ≤ N-1, 0 ≤ y ≤ M-1), 그리고 명령의 개수 K (1 ≤ K ≤ 1,000)가 주어진다. 둘째 줄부터 N개의 줄에 지 www.acmicpc.net 🔶 풀이 모든 면이 0으로 채워진 주사위를 굴렸을 때 발생하는 일은 아래와 같다. 1. 이동한 칸에 쓰여 있는 수가 0인 경우, 주사위의 바닥면에 쓰여 있는 수를 복사한다. 2. 이동한 칸에 쓰여 있는 수가 0이 아닌 경우, 칸에 쓰여있는 수가 주사위의 바닥면에 복사되고, 칸은 0이 된다. 주사위는 지도의 크기에서 벗어날 수 없고,..

https://www.acmicpc.net/problem/1966 1966번: 프린터 큐 여러분도 알다시피 여러분의 프린터 기기는 여러분이 인쇄하고자 하는 문서를 인쇄 명령을 받은 ‘순서대로’, 즉 먼저 요청된 것을 먼저 인쇄한다. 여러 개의 문서가 쌓인다면 Queue 자료구조에 www.acmicpc.net 🔶 풀이 Queue로 중요도만 체크해 주면 되는 간단한 문제다. 모든 문서를 FIFO 형식인 Queue에 입력해 놓고 중요도가 높은 것부터 순서대로 뽑아내면 된다. 언뜻 보면 정렬로 빠르게 뽑아낼 수 있을 것 같지만 중복된 중요도가 있을 수 있기 때문에 정렬로는 해결할 수 없다. 즉, Queue의 특성을 이용해서 해결해야 한다. 맨 앞에 있는 문서보다 중요도가 높은 문서가 있으면 맨 앞의 문서를 뒤로..

이클립스로 개발을 진행하면 svn을 사용해서 서로의 작업을 공유한다. 간혹 작업하는 과정에서 파일이 겹쳐서 충돌이 발생하게 되면 아래와 같은 에러로 인해 커밋이 안되는 경우가 있다. ✅ svn: E1600024: Commit failed 위 에러를 해결하기 위해선 'Override and Update...'를 진행해주면 된다. 충돌이 발생한 파일에 한해서 Override and Update를 진행하기 전에 본인이 했던 작업을 백업해두는 게 좋다. Update를 완료했다면 본인이 했던 작업을 덮어씌우고 Commit을 진행해주면 완료.

자바에서 문자열을 입력받는 대표적인 방법에는 Scanner와 BufferedReader가 있다. 오늘 두 개의 차이점에 대해서 알아보려고한다. 자바를 한 번이라도 접해봤으면 Scanner는 사용해봤을거라고 생각된다. 알고리즘을 풀어봤다면 BufferdReader 또한 사용해봤을것이다. 기본 문법 [Scanner] import java.util.Scanner; public class Main { public static void main(String[] args) { Scanner sc = new Scanner(System.in); String input = sc.nextLine(); System.out.println(input); } } JDK1.5부터 java.util 패키지에 포함된 클래스로 데이터를..