문제 https://www.acmicpc.net/problem/1103 1103번: 게임 줄에 보드의 세로 크기 N과 가로 크기 M이 주어진다. 이 값은 모두 50보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에 보드의 상태가 주어진다. 쓰여 있는 숫자는 1부터 9까지의 자연수 또는 www.acmicpc.net 게임을 진행하면서 움직일 수 있는 동전의 최대 횟수를 구하는 문제였다. 문제 풀이 많은 시행착오가 있었고, 결국 다른 블로그를 참고해서 해결했다. 처음에는 단순히 백트래킹을 이용했는데, 6%에서 시간 초과가 나타났다. 이를 해결하기 위해서 좌표와 횟수, 방향 정보를 우선순위 큐에 넣어 bfs를 돌렸는데 해결되지 않는 경우가 있었다. 그리고 map의 각 칸에 set을 만들어 이전에 방문한 적이..
문제 https://www.acmicpc.net/problem/2250 2250번: 트리의 높이와 너비 첫째 줄에 노드의 개수를 나타내는 정수 N(1 ≤ N ≤ 10,000)이 주어진다. 다음 N개의 줄에는 각 줄마다 노드 번호와 해당 노드의 왼쪽 자식 노드와 오른쪽 자식 노드의 번호가 순서대로 주어진다. www.acmicpc.net 트리의 각 레벨의 양 끝 노드간의 거리 중 최댓값을 구하는 문제였다. 문제 풀이 처음에는 트리 노드에 달려 있는 노드들의 합으로 위치를 계산하려고 했는데, 중위순회를 하면 순회하는 순서가 위치가 될 것 같아서 다시 풀었다. 1번 노드의 parent를 계속 거슬러 올라가 루트 노드를 찾는다. 루트노드에서부터 중위순회를 돌려 각 노드의 위치를 찾는다. 트리를 레벨 별로 순회를 ..
제네릭을 사용하면 타입을 컴파일러에 알려주고 컴파일러가 알아서 형변환 코드를 추가해 준다. 5장은 이런 제네릭을 사용할 때 주의사항과 팁을 알려준다. 용어 정리 제네릭 타입 제네릭 클래스/인터페이스 : 클래스와 인터페이스 선언에 타입 매개변수가 쓰인다. (List) 제네릭 클래스/인터페이스를 통틀어 제네릭 타입이라 한다. 매개변수화 타입 각 제네릭 타입은 일련의 매개변수화 타입을 정의한다. 이름 (List) 로 타입 제네릭 타입을 하나 정의하면 로 타입도 함께 정의된다. 로 타입은 제네릭 타입에서 타입 매개변수를 전혀 사용하지 않을 때를 말한다. (List에서 List) 타입 선언에서 제네릭 타입 정보가 전부 지워진 것처럼 동작한다. (제네릭 없던 코드와 호환되기 위함) 한글 용어 영문 용어 예 매개변수..
문제 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를 돌려 가장 긴 가지의 길이를 구하려고 했다. ..
