본문 바로가기
728x90

[IT] 코딩테스트/[문제 및 풀이] 백준

[백준] 2589 보물섬 / 자바(Java) 문제 https://www.acmicpc.net/problem/2589 2589번: 보물섬 보물섬 지도를 발견한 후크 선장은 보물을 찾아나섰다. 보물섬 지도는 아래 그림과 같이 직사각형 모양이며 여러 칸으로 나뉘어져 있다. 각 칸은 육지(L)나 바다(W)로 표시되어 있다. 이 지도에서 www.acmicpc.net 해설 BFS를 사용하면 될 듯한 문제입니다. 단 문제의 조건에서 최단거리 중 가장 먼 곳의 거리를 구해야합니다. 다행히 각 섬별로가 아닌 단 한 가지 경우만 찾으면 되므로 2차원 배열에 지도 정보를 넣고 각 땅 별로 BFS를 통해 갈 수 있는 최대 거리를 구해 각각을 비교하는 방식으로 해결할 수 있는 BFS의 기본을 익힐 수 있는 문제였습니다. 코드 import java.io.BufferedRe.. 더보기
[백준] 2565 전깃줄 / 자바(Java) 문제 https://www.acmicpc.net/problem/2565 2565번: 전깃줄 첫째 줄에는 두 전봇대 사이의 전깃줄의 개수가 주어진다. 전깃줄의 개수는 100 이하의 자연수이다. 둘째 줄부터 한 줄에 하나씩 전깃줄이 A전봇대와 연결되는 위치의 번호와 B전봇대와 연결되는 www.acmicpc.net 해설 어느 전기줄들을 제거해야 교차되는 전기줄이 없을까 확인하는 문제입니다. 풀이방식을 어떻게 잡을지 몰라 고민했지만 DP를 사용해 해결하였습니다. DP배열의 의미는 dp[i] => i번째 까지에서 교차되지 않으려면 설치하는 최소 전기줄 수 로 하였습니다. 제거가 아닌 설치를 기준으로 생각해서 좀 더 문제를 해석하기 쉽도록 되었습니다. 같은 위치에는 2개이상의 전기줄이 연결될 수 없으므로 입력 값을.. 더보기
[백준] 2467 용액 / 자바(Java) 문제 https://www.acmicpc.net/problem/2467 2467번: 용액 첫째 줄에는 전체 용액의 수 N이 입력된다. N은 2 이상 100,000 이하의 정수이다. 둘째 줄에는 용액의 특성값을 나타내는 N개의 정수가 빈칸을 사이에 두고 오름차순으로 입력되며, 이 수들은 모두 - www.acmicpc.net 해설 정렬되어 있는 수들 중 2개의 값의 합이 가장 0에 가까운 수의 조합을 찾는 문제이다. 모든 수의 조합을 확인하려면 100,000 * 99,999가 되어 너무 많은 조합을 확인해야하므로 배열에서 2개의 포인터를 사용해 원하는 조건에 맞춰 확인하는 방식을 사용한다. 입력값은 오름차순으로 정렬되어 있으므로 입력을 배열로 변경한다면 왼쪽에는 가장 작은 수, 오른쪽에는 가장 큰 수가 있을.. 더보기
[백준] 1759 암호 만들기 / 자바(Java) 문제 https://www.acmicpc.net/problem/1759 1759번: 암호 만들기 첫째 줄에 두 정수 L, C가 주어진다. (3 ≤ L ≤ C ≤ 15) 다음 줄에는 C개의 문자들이 공백으로 구분되어 주어진다. 주어지는 문자들은 알파벳 소문자이며, 중복되는 것은 없다. www.acmicpc.net 해설 모든 가지수를 정렬된 순으로 확인해야하는 문제이므로 브루트포스를 조합을 사용해 해결한다. 조건들이 간단한 조합문제보다 더 다양함으로 이에 주의한다. 조건 최소 하나의 모음과 두개의 자음으로 구성 알파벳들은 정렬되어있음 코드 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; im.. 더보기
[백준] 2170 선 긋기 / 자바(Java) 문제 https://www.acmicpc.net/problem/2170 2170번: 선 긋기 첫째 줄에 선을 그은 횟수 N (1 ≤ N ≤ 1,000,000)이 주어진다. 다음 N개의 줄에는 선을 그을 때 선택한 두 점의 위치 x, y (-1,000,000,000 ≤ x < y ≤ 1,000,000,000)가 주어진다. www.acmicpc.net 해설 입력값의 범위가 넓어 정렬이 필요하지만 양이 너무 많아 우선순위큐를 통해 문제를 해결한다. 우선순위큐에 넣을 때 NlogN번, 하나씩 빼면서 답을 계산할때 N번으로 총 O(NlonN)만큼의 시간복잡도로 해결이 가능하다. 주의점 입력 값의 범위가 너무커 Long타입을 사용한다. 코드 import java.io.BufferedReader; import jav.. 더보기
[백준] 1074 Z / 자바(Java) 문제 https://www.acmicpc.net/problem/1074 1074번: Z 한수는 크기가 2N × 2N인 2차원 배열을 Z모양으로 탐색하려고 한다. 예를 들어, 2×2배열을 왼쪽 위칸, 오른쪽 위칸, 왼쪽 아래칸, 오른쪽 아래칸 순서대로 방문하면 Z모양이다. N > 1인 경우, 배열을 www.acmicpc.net 해설 Z형태가 반복되는 형상에 재귀 및 분할정복이 필요하다 생각들었습니다. findz 함수를 통해 각 단계별로 r,c가 어느 사분면에 존재하는지를 구하고 그 단계의 사각형의 크기를 통해 그 사분면의 첫 숫자의 크기만큼 더해주어 마지막으로 사각형의 크기가 1인 경우에는 해당 사각형의 탐색 순서를 구할 수 있도록 하였습니다. 주의점 각 사분면단위로 계산하기 때문에 범위를 잘 판단해야한다.. 더보기
[백준] 1309 동물원 / 자바(Java) 문제 https://www.acmicpc.net/problem/1309 1309번: 동물원 첫째 줄에 우리의 크기 N(1≤N≤100,000)이 주어진다. www.acmicpc.net 해설 dfs와 같은 탐색으로 해결하기에는 N의 길이가 너무 길다(답을 9901로 나눈 나머지를 출력하라는 부분도 값이 크게 되리라는 예상이 된다) 따라서 DP를 사용해 이전의 경우의 수에서 가능한 가능성을 구하는 점화식의 형태로 문제를 해결한다. arr[i][j]에서 i 는 사자우리의 세로번째의 수, j는 0~2까지 각각 사자가 들어가지 않는 경우, 왼쪽칸에 들어간경우, 오른쪽 칸에 들어간 경우를 나타내어 arr[i][j]는 i번째에 각 가능성이 될 경우의 수가 들어가게 된다. 사자우리는 바로 이전 번째에서만 영향을 받아 a.. 더보기
[백준] 1013 Contact / 자바(Java) 문제 https://www.acmicpc.net/problem/1013 1013번: Contact 입력의 첫 줄에는 테스트 케이스의 개수 T가 주어진다. 그 다음 줄부터 각각의 테스트 케이스에 대해 전파를 표현하는, { 0, 1 }만으로 이루어진 문자열이 공백 없이 주어진다. 문자열 길이는 (1 ≤ www.acmicpc.net 해설 문제에서부터 정규표현식을 사용해줌으로써 자바의 String 내부에 있는 정규표현식을 사용해 쉽게 해결할 수 있었습니다. 유사한 문제에 대한 접근법으로 정규표현식을 사용할 수 있음을 알아 학습하는 계기가 되었습니다. 주의점 정규 표현식을 써보자 코드 import java.io.BufferedReader; import java.io.IOException; import java.i.. 더보기
728x90

티스토리툴바