문제 https://www.acmicpc.net/problem/16236 16236번: 아기 상어 N×N 크기의 공간에 물고기 M마리와 아기 상어 1마리가 있다. 공간은 1×1 크기의 정사각형 칸으로 나누어져 있다. 한 칸에는 물고기가 최대 1마리 존재한다. 아기 상어와 물고기는 모두 크기를 가 www.acmicpc.net 아기상어가 최대 몇 초 동안 물고기를 먹을 수 있는지 구하는 문제였다. 문제의 조건은 다음과 같았다. 아기상어는 크기가 작은 물고기만 먹을 수 있다. 크기가 같은 물고기일 경우 지나갈 수 있다. 먹을 수 있는 물고기 1마리 → 먹으러 감 먹을 수 있는 물고기 2마리 이상 → 거리 가장 가까운 물고기 거리 : 지나야 하는 칸 개수 최솟값 가까운 물고기가 많으면 가장 위, 위인 물고기도 ..
문제 https://www.acmicpc.net/problem/17144 17144번: 미세먼지 안녕! 미세먼지를 제거하기 위해 구사과는 공기청정기를 설치하려고 한다. 공기청정기의 성능을 테스트하기 위해 구사과는 집을 크기가 R×C인 격자판으로 나타냈고, 1×1 크기의 칸으로 나눴다. 구사 www.acmicpc.net 1초마다 먼지가 확산되고 공기청정기가 가동되는 상황에서 T초 후의 방 안에 남은 먼지 개수를 구하는 문제였다. 문제 풀이 문제에서 요구하는 대로 구현하기만 하면 되는 문제였다. 1초마다 먼지가 확산되는 메서드와 공기청정기가 가동되는 메서드를 실행시키고, T초가 끝난 후에 map에 있는 먼지를 다 더해준 것이 답이었다. #define _CRT_SECURE_NO_WARNINGS #include..
문제 https://school.programmers.co.kr/learn/courses/30/lessons/258707 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 카드 게임을 진행해서 게임에서 도달 가능한 최대 라운드 수를 구하는 문제였다. 문제 풀이 게임을 진행하면서 카드를 살 수 있는 경우에 바로 사거나 보류하도록 했다. 각 카드의 상대 숫자의 라운드가 0일 때는 코인이 1개가 필요하고, 현재 라운드보다 작거나 같을 때에는 코인이 2개가 필요하다. 상대 카드가 현재 라운드보다 큰 라운드에 위치해 있다면 아직 살 수 없다. coin 1개 필요 ->..
문제 https://www.acmicpc.net/problem/1106 1106번: 호텔 첫째 줄에 C와 형택이가 홍보할 수 있는 도시의 개수 N이 주어진다. C는 1,000보다 작거나 같은 자연수이고, N은 20보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에는 각 도시에서 홍보할 때 www.acmicpc.net 각 도시별 홍보 비용과 이 비용으로 유치할 수 있는 고객이 정해져 있을 때, 호텔 고객을 C명 이상 늘리기 위해 투자해야 하는 비용의 최솟값을 구하는 전형적인 DP 문제였다. 문제 풀이 점화식을 세워서 dp 값을 계속 갱신했다. i는 비용이고 각 dp[i]의 값은 해당 비용으로 늘릴 수 있는 최대 사람 수로 정했다. 이때 dp 값이 C 이상일 때의 i가 정답이 된다. dp[i] = max..
문제 https://www.acmicpc.net/problem/20924 20924번: 트리의 기둥과 가지 첫 번째 줄에는 노드의 개수 $N$($1 \le N \le 200\,000$)과 루트 노드의 번호 $R$($1 \le R \le N$)이 주어진다. 이후 $N-1$개의 줄에 세 개의 정수 $a$, $b$, $d$($1 \le a, b \le N$, $ a \ne b$)가 주어진다. 이는 $a$번 www.acmicpc.net 트리의 기둥 길이(루트~기가)와 가장 긴 가지의 길이(기가~리프)를 구하는 문제였다. 문제 풀이 처음에는 단순하게 size가 2보다 작은 노드가 나올 때까지 dfs를 돌려 기가 노드를 구하고, 기가 노드에서부터 각 노드들까지 dfs를 돌려 가장 긴 가지의 길이를 구하려고 했다. ..
4장은 클래스와 인터페이스를 사용할 때 주의할 점과 유용한 팁을 알려준다. 15. 클래스와 멤버 접근 권한 최소화 잘 설계된 컴포넌트는 내부 구현 정보를 완벽하게 숨겨, 구현과 API를 깔끔하게 분리한다. 다른 컴포넌트와 소통할 때에는 오직 API만 사용하고 서로의 내부 동작 방식은 알 필요가 없다. 이 개념은 정보 은닉 또는 캡슐화로, 소프트웨어 설계의 근간이 되는 원리다. 정보 은닉 장점 정보 은닉을 잘 하면 컴포넌트들을 서로 분리해 개발, 테스트, 최적화, 적용, 분석, 수정을 개별적으로 할 수 있게 해준다. 여러 컴포넌트 병렬로 개발해 개발 속도 높임 컴포넌트 파악이 쉽고 교체 부담도 적어 시스템 관리 비용 낮춤 성능 최적화에 도움을 줌 소프트웨어 재사용성 높임 개별 컴포넌트 동작을 검증할 수 있..
문제 https://www.acmicpc.net/problem/22251 22251번: 빌런 호석 LED를 2개까지 바꿀 수 있을 때, 5층에서 3층, 6층, 8층, 그리고 9층으로 바꿔버릴 수 있다. www.acmicpc.net 치르보기 빌딩의 엘리베이터 디스플레이의 숫자를 변경할 수 있는 경우의 수를 계산하는 문제였다. 아래는 각각의 숫자가 보이는 방식이다. 문제 풀이 0~9까지의 숫자들의 7개의 표시등을 모두 저장하고 각각의 숫자가 다른 숫자로 바뀔 때 필요한 반전 횟수를 계산해 저장했다. 그리고 숫자를 변경할 때 K자리의 LED이기 때문에 12라는 숫자를 0012라고 표기해야 하기 때문에 string 으로 변환해준 후, 백트래킹을 하며 앞자리부터 계속해서 바꿔줬다. 처음에 아무리 생각해도 로직상 ..
3장은 모든 Object를 상속받는 객체가 공통적으로 가지는 equals와 hashcode, tostring과 같은 final이 아닌 메서드를 구현할 때 주의할 점에 대해 다룬다. 10. equals 재정의 java에서는 객체 식별성을 확인해 동치성을 확인한다. 이때 논리적인 동치성을 확인해야 할 때 equals를 재정의해야 한다. equals를 재정의하지 않는 상황 각 인스턴스가 본질적으로 고유할 때 동작하는 개체를 표현하는 클래스 (Thread) 인스턴스의 논리적 동치성을 검사할 일이 없을 때 상위 클래스에서 재정의한 equals가 하위 클래스에 딱 맞을 때 대부분의 Set 구현체 : AbstractSet이 구현한 equals를 상속받아 사용 클래스가 private, package-private이고 ..