본문 바로가기

Tech/Problem Solving

[백준 10021] Watering the Fields (Java) www.acmicpc.net/problem/10021 10021번: Watering the Fields Input Details There are 3 fields, at locations (0,2), (5,0), and (4,3). The contractor will only install pipes of cost at least 11. Output Details FJ cannot build a pipe between the fields at (4,3) and (5,0), since its cost would be only 10. He therefore b www.acmicpc.net 풀이 N개의 필드 간 수로 파이프를 설치하는데, 모든 필드가 연결되도록 하는 최소 비용을 구하는 문제. 즉, 모든 필드를..
[백준 15591] MooTube (Silver) (Java) www.acmicpc.net/problem/15591 15591번: MooTube (Silver) 농부 존은 1번 동영상과 2번 동영상이 USADO 3을 가지고, 2번 동영상과 3번 동영상이 USADO 2를 가지고, 2번 동영상과 4번 동영상이 USADO 4를 가진다고 했다. 이것에 기반해서 1번 동영상과 3번 동영상의 www.acmicpc.net 풀이 그래프 문제라고 2차원 배열을 사용하면 시간 초과가 발생한다. 불필요한 연결을 탐색하기 때문에 ArrayList를 담는 배열을 만들어 입력 받은 연결만 탐색하도록 구현하였다. 코드 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; impor..
[프로그래머스] 카카오 블라인드 리쿠르트 2020 - 블록 이동하기 (Java) https://programmers.co.kr/learn/courses/30/lessons/60063 코딩테스트 연습 - 블록 이동하기 [[0, 0, 0, 1, 1],[0, 0, 0, 1, 0],[0, 1, 0, 1, 1],[1, 1, 0, 0, 1],[0, 0, 0, 0, 0]] 7 programmers.co.kr 문제 설명 로봇개발자 무지는 한 달 앞으로 다가온 카카오배 로봇경진대회에 출품할 로봇을 준비하고 있습니다. 준비 중인 로봇은 2 x 1 크기의 로봇으로 무지는 0과 1로 이루어진 N x N 크기의 지도에서 2 x 1 크기인 로봇을 움직여 (N, N) 위치까지 이동 할 수 있도록 프로그래밍을 하려고 합니다. 로봇이 이동하는 지도는 가장 왼쪽, 상단의 좌표를 (1, 1)로 하며 지도 내에 표시된..
[프로그래머스] 카카오 윈터 인턴십 2019 - 징검 다리 건너기 (Java) https://programmers.co.kr/learn/courses/30/lessons/64062 코딩테스트 연습 - 징검다리 건너기 [2, 4, 5, 3, 2, 1, 4, 2, 5, 1] 3 3 programmers.co.kr 문제 설명 [본 문제는 정확성과 효율성 테스트 각각 점수가 있는 문제입니다.] 카카오 초등학교의 니니즈 친구들이 라이언 선생님과 함께 가을 소풍을 가는 중에 징검다리가 있는 개울을 만나서 건너편으로 건너려고 합니다. 라이언 선생님은 니니즈 친구들이 무사히 징검다리를 건널 수 있도록 다음과 같이 규칙을 만들었습니다. 징검다리는 일렬로 놓여 있고 각 징검다리의 디딤돌에는 모두 숫자가 적혀 있으며 디딤돌의 숫자는 한 번 밟을 때마다 1씩 줄어듭니다. 디딤돌의 숫자가 0이 되면 더 ..
[프로그래머스] 카카오 블라인드 리크루트 2020 - 외벽 점검 (Java) https://programmers.co.kr/learn/courses/30/lessons/60062 코딩테스트 연습 - 외벽 점검 레스토랑을 운영하고 있는 스카피는 레스토랑 내부가 너무 낡아 친구들과 함께 직접 리모델링 하기로 했습니다. 레스토랑이 있는 곳은 스노우타운으로 매우 추운 지역이어서 내부 공사를 하는 programmers.co.kr 문제 설명 레스토랑을 운영하고 있는 스카피는 레스토랑 내부가 너무 낡아 친구들과 함께 직접 리모델링 하기로 했습니다. 레스토랑이 있는 곳은 스노우타운으로 매우 추운 지역이어서 내부 공사를 하는 도중에 주기적으로 외벽의 상태를 점검해야 할 필요가 있습니다. 레스토랑의 구조는 완전히 동그란 모양이고 외벽의 총 둘레는 n미터이며, 외벽의 몇몇 지점은 추위가 심할 경우 ..
[백준 3197] 백조의 호수 (Java) https://www.acmicpc.net/problem/3197 3197번: 백조의 호수 문제 두 마리의 백조가 호수에서 살고 있었다. 그렇지만 두 마리는 호수를 덮고 있는 빙판으로 만나지 못한다. 호수는 가로로 R, 세로로 C만큼의 직사각형 모양이다. 어떤 칸은 얼음으로 덮여있� www.acmicpc.net 풀이 문제를 처음 보고 다음과 같은 방법으로 시도를 했다. 1. BFS로 얼음을 녹이고 map을 업데이트 시킨다. 2. 해당 map에서 두 백조가 만날 수 있는지 BFS 탐색을 시도한다. 3. 만날 수 없다면 day++를 하고 1, 2번을 반복한다. 4. 만나는 경우에 day를 출력한다. 위 방법으로는 시간 초과가 발생할 수 있다. 예를 들어 백조가 만날 수 있는 날이 n일차라면 (이 n이 아주 ..
[백준 1665] 가운데를 말해요 (Java) https://www.acmicpc.net/problem/1655 1655번: 가운데를 말해요 첫째 줄에는 수빈이가 외치는 정수의 개수 N이 주어진다. N은 1보다 크거나 같고, 100,000보다 작거나 같은 자연수이다. 그 다음 N줄에 걸쳐서 수빈이가 외치는 정수가 차례대로 주어진다. 정수는 -1 www.acmicpc.net 풀이 배열이나 ArrayList를 이용하여 풀이를 시도하였더니 메모리초과, 시간초과 문제가 발생했다. MaxHeap, MinHeap 개념을 이용하여 문제를 풀었다. (Heap은 PriorityQueue로 구현) 입력받는 숫자를 MaxHeap과 MinHeap에 번갈아 가면서 add를 하되, MaxHeap의 첫번째 값과 MinHeap의 첫번째 값을 비교했을 때 (MaxHaep.peek..
[백준 1976] 여행 가자 (Java) https://www.acmicpc.net/problem/1976 1976번: 여행 가자 동혁이는 친구들과 함께 여행을 가려고 한다. 한국에는 도시가 N개 있고 임의의 두 도시 사이에 길이 있을 수도, 없을 수도 있다. 동혁이의 여행 일정이 주어졌을 때, 이 여행 경로가 가능한 것인 www.acmicpc.net 풀이 union-find 알고리즘을 이용해 푸는 문제였다. int[][] map : 입력받은 도시 간 연결을 나타내는 행렬을 담음 int[] route : 여행자의 이동 경로 도시 번호를 담음 int[] join : 도시 간 집합 index를 담음. 집합 원소 중 가장 도시 번호가 작은 번호 기준으로 담김. map을 탐색해 1인 경우의 좌표값 i, j를 기준으로 union()메소드에서 집합을 합친..

티스토리툴바