코딩테스트140

• 

  [JAVA] 백준 1759 : 암호 만들기 https://www.acmicpc.net/problem/1759 1759번: 암호 만들기 첫째 줄에 두 정수 L, C가 주어진다. (3 ≤ L ≤ C ≤ 15) 다음 줄에는 C개의 문자들이 공백으로 구분되어 주어진다. 주어지는 문자들은 알파벳 소문자이며, 중복되는 것은 없다. www.acmicpc.net 1. 암호는 최소 한 개의 모음(a, e, i, o, u)과 최소 두 개의 자음으로 구성되어 있다. 2. 알파벳이 증가하는 순서로 배열되어 있다. 위 조건에 해당하는 길이 L의 암호를 C개의 문자를 가지고 가능성 있는 암호를 모두 출력하는 문제이다. 입력받은 알파벳을 알파벳 순으로 정렬하고 만들 수 있는 모든 조합을 가지고 적합한 비밀번호인가 검증하면 된다. 예제 입력의 a t c i s w 는 정렬하.. 코딩테스트/백준 2023. 2. 28.

• 

  [JAVA] 백준 9251 : LCS https://www.acmicpc.net/problem/9251 9251번: LCS LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다. 예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다. www.acmicpc.net 문자열이 두 개가 입력이 되었을 때, 각 문자열의 부분수열에 해당하면서 가장 긴 수열을 찾는 문제이다. ACAYKP CAPCAK 이렇게 두개의 문자열이 입력이 되었다면 두 문자열의 LCS는 ACAYKP , CAPCAK 해서 ACAK이다. str1을 ACAYKP라고 하고, str1을 기준으로 str2를 비교하여 최대 길이를 알아내야 한다. 1. str1=.. 코딩테스트/백준 2023. 2. 27.

• 

  [Java] 백준 7569 : 토마토 https://www.acmicpc.net/problem/7569 7569번: 토마토 첫 줄에는 상자의 크기를 나타내는 두 정수 M,N과 쌓아올려지는 상자의 수를 나타내는 H가 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M ≤ 100, 2 ≤ N ≤ 100, www.acmicpc.net 이 문제는 7576번 토마토문제와 같은 방식으로 풀면 되는 문제이다. 이전 문제와 차이점은 2차원에서 3차원으로 늘어났다는 것이다. 어렵지 않다. 첫 번째로 할 일은 3차원의 배열을 입력받는 것이다. 두 번째로는 입력받은 토마토 배열을 가지고 토마토가 익어 있을 경우를 판단하는 것이다. 보통 너비우선 탐색을 진행하면 차근차근 처음부터 탐색해 가면서 큐를 사용하여 탐색을 하지.. 코딩테스트/백준 2023. 2. 27.

• 

  [Java] 백준 10026 : 적록색약 https://www.acmicpc.net/problem/10026 10026번: 적록색약 적록색약은 빨간색과 초록색의 차이를 거의 느끼지 못한다. 따라서, 적록색약인 사람이 보는 그림은 아닌 사람이 보는 그림과는 좀 다를 수 있다. 크기가 N×N인 그리드의 각 칸에 R(빨강), G(초록) www.acmicpc.net 적록색약이 봤을 때와 아닌 사람이 봤을 때 각각 이렇게 보인다. 적록색약이 아닐 때 너비우선 탐색을 우선 해주고, 완료한 다음 입력받은 배열의 G값을 R값으로 바꾸어 주고 너비우선 탐색을 진행하면 된다. import java.io.*; import java.util.*; public class Main { static int num; static String[][] arr; static b.. 코딩테스트/백준 2023. 2. 24.

• 

  [Java] 백준 1011 : Fly to the Alpha Centauri https://www.acmicpc.net/problem/1011 1011번: Fly me to the Alpha Centauri 우현이는 어린 시절, 지구 외의 다른 행성에서도 인류들이 살아갈 수 있는 미래가 오리라 믿었다. 그리고 그가 지구라는 세상에 발을 내려 놓은 지 23년이 지난 지금, 세계 최연소 ASNA 우주 비행 www.acmicpc.net 행성 X에서 행성 Y로 이동하는데 조건은 아래와 같다. 이전에 k 광년을 이동했을 시 그다음 움직일 수 있는 거리는 k-1, k, k+1 이다. 처음과 마지막은 1광년만을 움직일 수 있다. k=1, 1,2를 이동 가능 k=2, 1,2,3을 이동 가능 거리별로 움직일 수 있는 방법을 그림으로 간단히 일부만 그려봤다. 이 그림을 가지고 규칙이 있는지 찾아볼.. 코딩테스트/백준 2023. 2. 23.

• [Java] 백준 12865 : 평범한 배낭 https://www.acmicpc.net/problem/12865 12865번: 평범한 배낭 첫 줄에 물품의 수 N(1 ≤ N ≤ 100)과 준서가 버틸 수 있는 무게 K(1 ≤ K ≤ 100,000)가 주어진다. 두 번째 줄부터 N개의 줄에 거쳐 각 물건의 무게 W(1 ≤ W ≤ 100,000)와 해당 물건의 가치 V(0 ≤ V ≤ 1,000) www.acmicpc.net N=4 k=7이고, 물건 1 = 6 13 물건 2 = 4 8 물건 3 = 3 6 물건 4 = 5 12 일 때, 담을 수 있는 무게가 0일 때부터 7일 때까지 최대 가치를 찾으면 된다. 물건 1번을 담게 되면 무게 6 가치 13 이기 때문에 0~5까지는 담을 수 없기 때문에 0, 6과 7에서는 1번 외에는 더 담을 수 없기 때문에 1.. 코딩테스트/백준 2023. 2. 22.

• 

  [Java] 백준 2447 : 별 찍기 -10 https://www.acmicpc.net/problem/2447 2447번: 별 찍기 - 10 재귀적인 패턴으로 별을 찍어 보자. N이 3의 거듭제곱(3, 9, 27, ...)이라고 할 때, 크기 N의 패턴은 N×N 정사각형 모양이다. 크기 3의 패턴은 가운데에 공백이 있고, 가운데를 제외한 모든 칸에 별이 www.acmicpc.net 문제를 이해하기 위해서 예제 출력을 분해해 봤다. 크기가 3(=3 ¹)일 때는 가운데 공백이 있고, 가운데를 제외한 모든 칸에 별이 있는 모양이다. 그리고 N이 3보다 클 경우, 크기 N의 패턴은 공백으로 채워진 가운데의 (N/3) ×(N/3) 정사각형을 크기 N/3의 패턴으로 둘러싼 형태이다. 예를 들어, N = 3²=9일때, 가운데에 3*3의 공백이 있고 그 주위를 .. 코딩테스트/백준 2023. 2. 22.

• 

  [Java] 백준 7576 : 토마토 https://www.acmicpc.net/problem/7576 7576번: 토마토 첫 줄에는 상자의 크기를 나타내는 두 정수 M,N이 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M,N ≤ 1,000 이다. 둘째 줄부터는 하나의 상자에 저장된 토마토 www.acmicpc.net -1은 토마토가 없는 칸 1은 익은 토마토 0은 안 익은 토마토 일 때, 며칠이면 상자 안에 있는 토마토가 모두 익는지에 대한 문제이다. bfs를 사용해 문제를 풀면 된다. 그러기 위해서는 우선 토마토의 상태를 입력받는 코드를 작성해야 하는데, 익어있는 토마토의 xy좌표를 큐에 저장해야 한다. for (int i = 0; i < N; i++) { String[] nums = br... 코딩테스트/백준 2023. 2. 21.

• [Java] 백준 1309 : 동물원 https://www.acmicpc.net/problem/1309 1309번: 동물원 첫째 줄에 우리의 크기 N(1≤N≤100,000)이 주어진다. www.acmicpc.net dp [N+1][3]에서 dp [n][0] 은 사자가 n행에 한 마리도 없을 때, dp [n][1] 은 사자가 1행에서 왼쪽에 한 마리 있을 때, dp [n][2] 은 사자가 1행에서 오른쪽에 한 마리 있을 때를 의미한다. i=0일 때, dp [i][0] 일 때는 i-1행에서 사자가 어느 곳에 있어도 되므로, 앞행에 사자가 없거나 왼쪽에 있거나 오른쪽에 있는 경우를 더한다. => dp [i][0]=dp [i-1][0]+dp [i-1][1]+dp [i-1][2]; dp [i][1] 일 때는 i-1행에서 사자가 없거나 오른쪽에만 있어.. 코딩테스트/백준 2023. 2. 21.

• [Java] 백준 1946 : 신입 사원 https://www.acmicpc.net/problem/1946 1946번: 신입 사원 첫째 줄에는 테스트 케이스의 개수 T(1 ≤ T ≤ 20)가 주어진다. 각 테스트 케이스의 첫째 줄에 지원자의 숫자 N(1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N개 줄에는 각각의 지원자의 서류심사 성 www.acmicpc.net import java.io.*; import java.util.*; public class Main { static int T, num; static int[][] score; public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStre.. 코딩테스트/백준 2023. 2. 20.

• 

  [Java] 백준 1389 : 케빈 베이컨의 6단계 법칙 https://www.acmicpc.net/problem/1389 1389번: 케빈 베이컨의 6단계 법칙 첫째 줄에 유저의 수 N (2 ≤ N ≤ 100)과 친구 관계의 수 M (1 ≤ M ≤ 5,000)이 주어진다. 둘째 줄부터 M개의 줄에는 친구 관계가 주어진다. 친구 관계는 A와 B로 이루어져 있으며, A와 B가 친구라는 뜻 www.acmicpc.net import java.util.*; public class Main { static int N,M; static int[][] arr; private static int INF = 99999; public static void main(String[] args) { Scanner sc = new Scanner(System.in); N = sc.nex.. 코딩테스트/백준 2023. 2. 20.

• 

  [Java] 백준 11660 : 구간 합 구하기 5 https://www.acmicpc.net/problem/11660 11660번: 구간 합 구하기 5 첫째 줄에 표의 크기 N과 합을 구해야 하는 횟수 M이 주어진다. (1 ≤ N ≤ 1024, 1 ≤ M ≤ 100,000) 둘째 줄부터 N개의 줄에는 표에 채워져 있는 수가 1행부터 차례대로 주어진다. 다음 M개의 줄에는 네 www.acmicpc.net 왼쪽 아래의 표를 중간과정을 반복해 구한 누적합이 오른쪽표의 값이다. 입력 예시의 2 2 3 4의 답은 27이다. 밑에 사진은 답을 구하기 위한 과정이다. 결과인 빨간 부분의 누적합은 (파란 부분의 누적합 -) (초록 부분 2개 각 누적합) + (초록색 겹친 부분)이다. import java.io.*; public class Main { static in.. 코딩테스트/백준 2023. 2. 17.