두부의 코딩일기

https://www.acmicpc.net/problem/4485 4485번: 녹색 옷 입은 애가 젤다지? 젤다의 전설 게임에서 화폐의 단위는 루피(rupee)다. 그런데 간혹 '도둑루피'라 불리는 검정색 루피도 존재하는데, 이걸 획득하면 오히려 소지한 루피가 감소하게 된다! 젤다의 전설 시리즈의 주 www.acmicpc.net 🔶 풀이 오랜만에 나온 다익스트라 문제. 완전 탐색으로 풀려고 했지만 시간 초과가 발생할 것 같아서 다른 방향을 생각해 봄. bfs와 다익스트라 알고리즘을 헷갈려하시는 분들이 있는 것 같은데 큰 차이점은 그래프의 가중치 유무와 dp 활용이다. 두 가지 알고리즘 모두 최단 거리를 찾는 알고리즘이지만 그래프의 가중치가 생기면 다익스트라 알고리즘을 사용하는 것이 좋다. 또한, 그래프의..

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 위의 예제를..

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

비트마스크(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,..

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를 돌려준다. 내부 공기와 구분을 ..