두부의 코딩일기

https://www.acmicpc.net/problem/9576 9576번: 책 나눠주기 백준이는 방 청소를 하면서 필요 없는 전공 서적을 사람들에게 나눠주려고 한다. 나눠줄 책을 모아보니 총 N권이었다. 책이 너무 많기 때문에 백준이는 책을 구분하기 위해 각각 1부터 N까지의 www.acmicpc.net 🔶 풀이 그리드 알고리즘으로 충분히 해결할 수 있는 문제. 1번부터 N번까지의 책을 가지고 있고, a부터 b까지 중 하나의 책을 최대한 많은 학생에게 나눠주면 된다. 중복된 책을 나눠주면 안되기 때문에 book 배열로 나눠줌 여부를 판단해줬다. 문제를 잘 살펴보면 한 가지 예외가 있다. 1 5 4 1 5 // 1번 책을 나눔 2 5 // 2번 책을 나눔 3 4 // 3번 책을 나눔 3 3 위의 예제를..

자바에서는 선언 위치에 따라서 크게 지역 변수와 전역 변수 2개로 나눌 수 있다. 전역 변수에는 클래스 변수와 인스턴스 변수가 있다. 1. 지역 변수 (Local Variable) public class Main { public static void main(String[] args) { int localVar = 10; System.out.println(localVar); // 10 } } 메서드 내에서 선언된 변수로 해당 메서드 내에서만 사용이 가능하다. 메서드 호출이 끝나면 소멸되고, 초기화하지 않으면 컴파일 에러가 발생한다. 2. 전역 변수 전역 변수에는 클래스 변수와 인스턴스 변수가 존재한다. [인스턴스 변수] public class Main { public int globalVal; publi..

https://www.acmicpc.net/problem/19640 19640번: 화장실의 규칙 위와 같이 줄을 선 경우를 생각해보자. (x, y) 는 사원의 근무 일수가 x, 화장실이 급한 정도가 y임을 나타낸다. [x, y]는 해당 사원이 데카임을 의미한다. 즉, 위의 그림에서 데카는 3번 사원이다. www.acmicpc.net 🔶 풀이 각 줄에서 맨 앞에 있는 사람끼리 비교해야하는 문제. 1. M개의 줄로 나눠서 WaitLine 배열리스트에 사원들을 입력해준다. ArrayList[] waitLine = new ArrayList[M]; for (int i=0; i

https://www.acmicpc.net/problem/1976 1976번: 여행 가자 동혁이는 친구들과 함께 여행을 가려고 한다. 한국에는 도시가 N개 있고 임의의 두 도시 사이에 길이 있을 수도, 없을 수도 있다. 동혁이의 여행 일정이 주어졌을 때, 이 여행 경로가 가능한 것인 www.acmicpc.net 🔶 풀이 유니온-파인드 문제. 1 → 3 으로 가려고할 때, 바로 연결되어있지 않아도 1 → 2 → 3 이 연결되어있다면 갈 수 있다. 즉, 가고자하는 경로가 쭉 이어져있으면 여행이 가능하다는 뜻이다. 유니온-파인드에 대해서 처음 접하신 분들은 아래 링크를 보고 오는 것을 추천한다. 유니온-파인드를 이용한 대표적인 알고리즘을 설명하고있다. 최소 비용 신장 트리(MST), 크루스칼 알고리즘(Krus..

자바(Java)에서 발생하는 NumberFormatException 예외에 대해서 알아보겠다. ✅ 예외(Exception) ? 오류(Error) ? : 프로그램 실행 중에 예상 가능한 상황에서 발생하는 문제로 예외 처리를 통해 프로그램의 안전성을 유지할 수 있다. 오류는 예상하지 못한 상황에서 발생하는 심각한 문제로 일반적으로 오류가 발생하면 프로그램이 중단된다. 해당 예외는 "숫자로 변환할 수 없는 문자열이 입력된 경우"에 발생한다. 보통 숫자로 변환할 수 없는 문자열이 입력되면 parseInt(), parseLong() 등과 같은 숫자 변환 메서드에서 NumberFormatException 예외를 발생시킨다. NumberFormatException 예외가 발생하는 원인 1. 숫자로 변환할 수 없는 문..

비트마스크(BitMask)는 이진수를 사용하는 컴퓨터의 연산 방식을 이용하여 정수의 이진수 표현을 자료 구조로 쓰는 기법 ✅ 이진수 0 또는 1을 이용하므로 하나의 비트(Bit)가 표현할 수 있는 경우는 두 가지이다. 비트마스크 장점 1. 빠른 수행시간 비트마스크 연산은 bit 연산이기 때문에 O(1)에 구현되는 경우가 많다. 2. 짧은 코드 다양한 집합 연산들을 비트연산자로 한 줄로 작성할 수 있다. 3. 적은 메모리 사용량 ★ bit가 5인 경우에 $2^{5}$ 개의 경우를 표현할 수 있다. 하나의 정수로 많은 경우의 수를 표현할 수 있기 때문에 메모리 측면에서 효율적이다. 비트 연산자 연산 연산자 설명 AND & 두 개의 비트가 모두 1인 경우, 1을 반환함 OR | 두 개의 비트 중 하나라도 1인..

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,..