박카스러버

https://www.acmicpc.net/problem/1368 1368번: 물대기 첫 줄에는 논의 수 N(1 ≤ N ≤ 300)이 주어진다. 다음 N개의 줄에는 i번째 논에 우물을 팔 때 드는 비용 Wi(1 ≤ Wi ≤ 100,000)가 순서대로 들어온다. 다음 N개의 줄에 대해서는 각 줄에 N개의 수가 들어 www.acmicpc.net 저는 해당 문제를 PRIM 알고리즘을 통해서 문제를 해결하였습니다. 다른 PRIM문제랑의 특이점은 각 노드를 직접 우물을 파는게 더 나은지, 다른 논으로 부터 물을 끌어오는 게 더 좋은지를 판단해야합니다. PRIM알고리즘 내에 distance를 MIN(직접 우물 파는 값 , 다른 논으로 끌어오는 값)과 비교해서 초기화해야합니다. package BOJ.MST; impo..

https://www.acmicpc.net/problem/11967 11967번: 불켜기 (1, 1)방에 있는 스위치로 (1, 2)방과 (1, 3)방의 불을 켤 수 있다. 그리고 (1, 3)으로 걸어가서 (2, 1)방의 불을 켤 수 있다. (2, 1)방에서는 다시 (2, 2)방의 불을 켤 수 있다. (2, 3)방은 어두워서 갈 수 없으 www.acmicpc.net 저는 해당 문제를 BFS를 이용해 문제를 해결하였습니다. 저는 불이 켜지지 않았지만, 이동할 가능성이 있는 것들(입력에서 a,b의 값들)을 Queue에 넣었습니다. Queue는 BFS를 하면서 비어있거나 변화가 없다면 break를 하도록 하였습니다. package BOJ.DFS; import java.io.BufferedReader; impor..

https://www.acmicpc.net/problem/9252 9252번: LCS 2 LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다. 예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다. www.acmicpc.net 저는 해당 문제를 DP를 이용하여 문제를 해결하였습니다. 2차원 DP[y][x]를 통해 a의 y번째 글자와 b의 x번째 글자를 비교해 같다면 DP[y][x] = (DP[y-1][x] , DP[y][x-1] , DP[y-1][x-1] + 1) 중 최대값, 둘의 글자가 다르다면 DP[y][x] = (DP[y-1][x] , DP[y][x-1] , DP[y..

https://programmers.co.kr/learn/courses/30/lessons/81303 코딩테스트 연습 - 표 편집 8 2 ["D 2","C","U 3","C","D 4","C","U 2","Z","Z"] "OOOOXOOO" 8 2 ["D 2","C","U 3","C","D 4","C","U 2","Z","Z","U 1","C"] "OOXOXOOO" programmers.co.kr 저는 해당 문제를 LinkedList 개념을 이용해 문제를 해결하였습니다. next, prev배열을 통해 이전 또는 이후의 값이 무엇인지 확인하고 isValid를 통해 해당 값이 유효한지를 확인하였습니다. 요소(현재)를 지울 때는 이전의 다음 값을 현재의 다음 값으로 다음의 이전 값을 현재의 이전 값으로 변경하여..

https://programmers.co.kr/learn/courses/30/lessons/81302 코딩테스트 연습 - 거리두기 확인하기 [["POOOP", "OXXOX", "OPXPX", "OOXOX", "POXXP"], ["POOPX", "OXPXP", "PXXXO", "OXXXO", "OOOPP"], ["PXOPX", "OXOXP", "OXPOX", "OXXOP", "PXPOX"], ["OOOXX", "XOOOX", "OOOXX", "OXOOX", "OOOOO"], ["PXPXP", "XPXPX", "PXPXP", "XPXPX", "PXPXP"]] [1, 0, 1, 1, 1] programmers.co.kr 저는 해당 문제를 DFS를 이용해 문제를 해결하였습니다. 각각의 P에서 DFS를 이용해 깊..

https://programmers.co.kr/learn/courses/30/lessons/81301 코딩테스트 연습 - 숫자 문자열과 영단어 네오와 프로도가 숫자놀이를 하고 있습니다. 네오가 프로도에게 숫자를 건넬 때 일부 자릿수를 영단어로 바꾼 카드를 건네주면 프로도는 원래 숫자를 찾는 게임입니다. 다음은 숫자의 일부 자 programmers.co.kr 저는 substring을 통해 해당 문제를 해결하였습니다. for문마다 매번 10을 곱해 각자리 수를 구분하였습니다. 문자가 숫자라면 더해주고, 문자라면 substring을 통해 문자를 숫자의 문자열과 비교해 같은 것의 인덱스를 더해주었습니다. import java.util.*; class Solution { /* zero , one , two , t..

https://www.acmicpc.net/problem/16900 16900번: 이름 정하기 첫째 줄에 S와 K가 주어진다. S는 알파벳 소문자로만 이루어져 있고, 길이는 500,000보다 작거나 같다. K는 1,000,000보다 작거나 같은 자연수이다. www.acmicpc.net 저는 해당 문제를 KMP를 통해 문제를 해결하였습니다. 저의 실수는 KMP에서 제일 길게 매칭되는 부분을 리턴하였었는데, 문제를 다시 읽고 이해하여 fail배열의 마지막 인덱스의 값을 리턴해야하는 것을 알았습니다. 이유는 해당 문자열이 반복적으로 나와야하는데 접두사와 접미사가 얼마나 매칭되는지만이 중요하기 때문입니다. package BOJ.String; import java.io.BufferedReader; import j..

https://www.acmicpc.net/problem/2302 2302번: 극장 좌석 주어진 조건을 만족하면서 사람들이 좌석에 앉을 수 있는 방법의 가짓수를 출력한다. 방법의 가짓수는 2,000,000,000을 넘지 않는다. (2,000,000,000 < 231-1) www.acmicpc.net 저는 다음 문제를 DP를 이용하여 문제를 해결하였습니다. 저는 좌석을 뒷 사람만 하고 변경 가능하다고 문제를 재해석하였습니다. (2번,1번 좌석 변경 == 1번,2번 좌석 변경) 그래서 현재 좌석과 다음 좌석이 VIP인지 판별하고 VIP라면 좌석 변경이 불가능하기 때문에 DP[depth] = DP[depth+1]로 하였습니다. 만약 VIP가 아니라면 현재 좌석을 변경가능하기 때문에 DP[depth] = DP[..

https://www.acmicpc.net/problem/2638 2638번: 치즈 첫째 줄에는 모눈종이의 크기를 나타내는 두 개의 정수 N, M (5 ≤ N, M ≤ 100)이 주어진다. 그 다음 N개의 줄에는 모눈종이 위의 격자에 치즈가 있는 부분은 1로 표시되고, 치즈가 없는 부분은 0으로 www.acmicpc.net 저는 해당 문제를 더미 배열과 BFS를 이용해 문제를 해결하였습니다. 배열의 상하좌우에 더미 배열로 한칸씩 추가하였고 0,0부터 BFS를 그래프 탐색을 하여 공기와 접촉되었는지를 확인하였습니다. 마지막으로 1일때 근처에 공기와 접촉한 0이 몇개인지를 확인하여 2개 이상이면 녹도록 구현하였습니다. package BOJ.BFS; import java.io.BufferedReader; im..

https://www.acmicpc.net/problem/2630 2630번: 색종이 만들기 첫째 줄에는 전체 종이의 한 변의 길이 N이 주어져 있다. N은 2, 4, 8, 16, 32, 64, 128 중 하나이다. 색종이의 각 가로줄의 정사각형칸들의 색이 윗줄부터 차례로 둘째 줄부터 마지막 줄까지 주어진다. www.acmicpc.net 저는 해당 문제를 재귀를 이용하여 문제를 해결하였습니다. 재귀를 이용해 시작점과 해당 길이 만큼 color가 같은지를 확인하고 이를 결과에 반영하였습니다. 길이가 1이라면 바로 결과에 반영하고 끝냈습니다. package BOJ.Recursion; import java.io.BufferedReader; import java.io.InputStreamReader; impor..