분류 전체보기

문제 접근 방식문제가 너무 대놓고 그래프로 네 방향을 탐색하라고 나와 있는데 이거에 낚이면 시간초과에 걸린다. 장애물이 없는 지도가 주어져서 현재 지점의 좌표와 이동하고자 하는 지점의 좌표의 차를 구하면몇 칸을 이동해야하는지 알 수 있기 때문에 직접 한 칸씩 움직일 필요가 없다. 그래서 집의 좌표와 민초우유의 좌표만 구해두고 집의 위치에서부터 시작해서현재 좌표와 민초우유의 좌표의 차를 구하고 현재 체력보다 작거나 같다면 이동해주면 된다. 풀이public class Main { static int n, m, h, max = 0, milk = 0; static Pair home; static ArrayList milks = new ArrayList(); static boolean[] isVisited; pu..

문제 16928번: 뱀과 사다리 게임 첫째 줄에 게임판에 있는 사다리의 수 N(1 ≤ N ≤ 15)과 뱀의 수 M(1 ≤ M ≤ 15)이 주어진다. 둘째 줄부터 N개의 줄에는 사다리의 정보를 의미하는 x, y (x < y)가 주어진다. x번 칸에 도착하면, y번 칸으 www.acmicpc.net 접근 방식 여러 풀이가 존재하는 문제 같지만 BFS를 사용해서 풀어봤다. 우선 문제에서는 10*10 맵이라고 했지만 그냥 100칸짜리 1차원 배열을 사용하는 것이 문제의 입력 양식을 처리하기가 편해서 맵과 방문 배열을 모두 1차원 배열을 사용했다. 평범한 BFS 문제와 방식은 비슷하지만 주사위의 눈만큼 이동하기 위해 방향 배열을 사용하는 것이 아닌 1 ~ 6까지 반복문을 돌아주었다. 사다리나 뱀은 무조건 타야 하..

문제 11054번: 가장 긴 바이토닉 부분 수열 첫째 줄에 수열 A의 크기 N이 주어지고, 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ N ≤ 1,000, 1 ≤ Ai ≤ 1,000) www.acmicpc.net 접근 방식 바이토닉 수열인 오름차순, 내림차순, 오름차순 + 내림차순 수열 중 가장 긴 것을 찾아야 한다. 이전에 풀었던 문제 중 가장 긴 증가하는 부분 수열을 응용하면 풀 수 있는 문제인데 vvvvv 1521434521 만약에 위와 같은 수열이 있다면 1, 2, 3, 4, 5가 가장 긴 증가하는 부분 수열일 것이고 vvvvv 1521434521 가장 긴 감소하는 부분 수열은 위와 같을 것이다. 가장 긴 증가하는 부분 수열과 감소하는 부분 수열의 길이를 표로 정리하면 다음과 같..

문제 18352번: 특정 거리의 도시 찾기 첫째 줄에 도시의 개수 N, 도로의 개수 M, 거리 정보 K, 출발 도시의 번호 X가 주어진다. (2 ≤ N ≤ 300,000, 1 ≤ M ≤ 1,000,000, 1 ≤ K ≤ 300,000, 1 ≤ X ≤ N) 둘째 줄부터 M개의 줄에 걸쳐서 두 개 www.acmicpc.net 접근 방식 노드 간의 거리가 모두 1로 동일할 때, 시작점 X에서 거리가 K인 정점을 출력해야 한다. 즉 탐색은 X에서 K번 까지의 이동만 진행해주면 되고, K번째 방문한 정점들을 모두 저장해주면 되는데 문제에서 요구하는 출력값이 정점의 번호를 오름차순으로 출력하는 것이기 때문에 트리셋이나 우선순위큐, 정렬 등을 사용해서 출력해주면 된다. 풀이 public class Main { pub..

개요 스프링을 처음 배우면 누구나 IoC와 DI에 대해서 학습을 하지만 작성자처럼 개발자가 개발에만 집중할 수 있게 하기 위해 객체의 생성과 관계 설정 같은 번거로운 작업들을 컨테이너에 떠넘기는 것 혹은 이와 비슷하게 개념적으로만 그런가 보다 하고 넘어가는 일들이 많은 거 같다. (아님 말고...) 그래서 스터디에서 발표도 준비할 겸 토비의 스프링을 다시 정독하면서 DI가 무엇이고, 왜 필요한지, 적용함으로 얻을 수 있는 이득 등에 대해 최대한 간단하게 살펴보려 한다. (쓰다 보면 길어질 수도 있다) 객체 스스로 사용할 객체를 선택하고 생성하는 것이 맞을까? 클라이언트의 주문에 대한 처리를 담당하는 주문 서비스 객체의 관심사는 무엇일까라고 생각하면 당연히 요청에 맞게 주문을 처리하는 것이다. 하지만 만약..

문제 1202번: 보석 도둑 첫째 줄에 N과 K가 주어진다. (1 ≤ N, K ≤ 300,000) 다음 N개 줄에는 각 보석의 정보 Mi와 Vi가 주어진다. (0 ≤ Mi, Vi ≤ 1,000,000) 다음 K개 줄에는 가방에 담을 수 있는 최대 무게 Ci가 주어진다. (1 ≤ Ci www.acmicpc.net 접근 방식 mv 165 298 295 599 596 590 보석의 무게와 가치를 위와 같이 무게가 가벼운 순으로, 같다면 가치가 높은 순으로 정렬한 후에 오름차순으로 정렬된 가방을 하나씩 보면서 현재 가방의 무게 이하인 보석을 모두 우선순위 큐에 넣고 가장 큰 값을 하나만 꺼내서 누적합에 더해주면 된다. 2 2 10 10 가방의 무게가 다음과 같을 때 [2]98 95 65 [2]95 65 [10]..

문제 16946번: 벽 부수고 이동하기 4 N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 한 칸에서 다른 칸으로 이동하려면, 두 칸이 인접해야 한다. 두 칸이 www.acmicpc.net 접근 방식 맵의 최대 크기가 1000 * 1000이기 때문에 매번 벽을 기준으로 BFS나 DFS를 이용해 탐색하면 시간초과가 발생한다. 그래서 0을 기준으로 각 구역의 크기를 계산한 후에 1을 기준으로 상하좌우로 맞닿은 구역의 크기를 더해주면 되는데 이때 중복이 있을 수 있기 때문에 Set을 사용해서 처리해 주면 된다. 예를 들어 현재 벽과 맞닿은 구역이 1, 1, 2, 3 구역이라면 1 구역은 한 번만 계산하면 되기 때문에 중복을 처리..

문제 2239번: 스도쿠 스도쿠는 매우 간단한 숫자 퍼즐이다. 9×9 크기의 보드가 있을 때, 각 행과 각 열, 그리고 9개의 3×3 크기의 보드에 1부터 9까지의 숫자가 중복 없이 나타나도록 보드를 채우면 된다. 예를 들어 다 www.acmicpc.net 접근 방식 스도쿠의 빈칸을 채우는 문제다. 특별한 규칙은 없기 때문에 백트래킹으로 매번 행과 열, 3*3칸을 확인해 주며 가능한 숫자들을 모두 시도해보아야 한다. 문제의 설명이 조금 헷갈렸는데 81 자리의 수가 제일 작은 경우라는 말이 81번째 칸을 말하는 게 아니라 9*9칸을 일렬로 늘어놨을 때 나오는 81자리 수를 말하는 것이기 때문에 백트래킹 자체를 1 ~ 9까지의 수를 오름차순으로 대입하다 보면 처음 나오는 결과가 가장 작은 수이기 때문에 그 ..