박카스러버

https://www.acmicpc.net/problem/17142 17142번: 연구소 3 인체에 치명적인 바이러스를 연구하던 연구소에 승원이가 침입했고, 바이러스를 유출하려고 한다. 바이러스는 활성 상태와 비활성 상태가 있다. 가장 처음에 모든 바이러스는 비활성 상태이고 www.acmicpc.net 저는 해당 문제를 BFS와 조합을 이용해서 문제를 해결하였습니다. 조합을 통해 바이러스 중에 활성화 시킬 것을 선택하고 이를 BFS를 통해 몇초만에 모두 방문하는지를 확인하였습니다. 확인은 check함수를 통해 해당 좌표에 방문했는지 방문안했다면 1, 2이 아니라면 false를 리턴하였습니다. package BOJ.BFS; import java.io.BufferedReader; import java.io...

https://www.acmicpc.net/problem/13905 13905번: 세부 첫 번째 줄에는 섬에 존재하는 집의 수 N(2≤N≤100,000)와 다리의 수 M(1≤M≤300,000)이 주어진다. 두 번째 줄에는 숭이의 출발 위치(s)와 혜빈이의 위치(e)가 주어진다. (1≤s, e≤N, s≠e). 다음 M개의 줄 www.acmicpc.net 저는 해당 문제를 크루스칼을 통해서 문제를 해결하였습니다. 처음에는 프림 알고리즘을 통해 접근하였지만 시간초과가 나왔습니다. 다음으로는 edge가 vertex^2에 대비 적기 때문에 크루스칼을 통해 문제를 접근하였습니다. 크루스칼 알고리즘을 진행하면서 start와 end가 연결되있는지 확인하여 연결되어있다면 지금의 weight를 리터하도록 하였습니다. 만약..

https://www.acmicpc.net/problem/4673 4673번: 셀프 넘버 셀프 넘버는 1949년 인도 수학자 D.R. Kaprekar가 이름 붙였다. 양의 정수 n에 대해서 d(n)을 n과 n의 각 자리수를 더하는 함수라고 정의하자. 예를 들어, d(75) = 75+7+5 = 87이다. 양의 정수 n이 주어졌을 때, www.acmicpc.net 저는 boolean배열을 통해 해당 숫자가 셀프 넘버인지를 확인하였습니다. 셀프 넘버는 1부터 시작하여 셀프 넘버를 확인하였습니다. 문제에서는 높은 자리수 부터 더하였지만, 덧셈은 순서가 상관 없기 때문에 저는 가장 낮은 자리부터 더해나가서 구현을 조금 더 쉽게 하였습니다. package BOJ.Bruteforce; public class BOJ_..

https://programmers.co.kr/learn/courses/30/lessons/77486 코딩테스트 연습 - 다단계 칫솔 판매 민호는 다단계 조직을 이용하여 칫솔을 판매하고 있습니다. 판매원이 칫솔을 판매하면 그 이익이 피라미드 조직을 타고 조금씩 분배되는 형태의 판매망입니다. 어느정도 판매가 이루어진 후, programmers.co.kr 저는 해당 문제를 map과 재귀적인 방법을 이용해 문제를 해결하였습니다. map을 통해 각각의 사람에 대한 배열 인덱스를 저장하여 이를 통해 결과값에 접근할 수 있도록 하였습니다. parent배열을 통해 해당 인덱스의 사람이 판매를 하면 그 위에 누가 있는지를 가리켰습니다. parent배열을 따라가면서 -1(root)가 나올때까지 재귀적으로 돈을 구하였습니..

https://programmers.co.kr/learn/courses/30/lessons/77485 코딩테스트 연습 - 행렬 테두리 회전하기 6 6 [[2,2,5,4],[3,3,6,6],[5,1,6,3]] [8, 10, 25] 3 3 [[1,1,2,2],[1,2,2,3],[2,1,3,2],[2,2,3,3]] [1, 1, 5, 3] programmers.co.kr 저는 로테이션을 하면서 최소값을 계속 구하여 문제를 해결하였습니다. 로테이션은 4방향을 while을 통해 조건에 맞을 때 계속 한칸씩 이동하도록 구현하였습니다. import java.util.*; class Solution { private static int[][] init(int n,int m){ int[][] arr = new int[n]..

https://programmers.co.kr/learn/courses/30/lessons/77484 코딩테스트 연습 - 로또의 최고 순위와 최저 순위 로또 6/45(이하 '로또'로 표기)는 1부터 45까지의 숫자 중 6개를 찍어서 맞히는 대표적인 복권입니다. 아래는 로또의 순위를 정하는 방식입니다. 1 순위 당첨 내용 1 6개 번호가 모두 일치 2 5개 번호 programmers.co.kr 저는 로또 번호에 어떤 숫자가 나왔는지를 구하는 함수(init), 번호를 맞춘 개수와 0의 개수를 구하는 함수(calCorrrect), 맞춘 개수에 따른 순위를 구하는 함수(changeCntToGrade)로 나눠서 문제를 해결하였습니다. import java.util.*; class Solution { private..

https://www.acmicpc.net/problem/2776 2776번: 암기왕 연종이는 엄청난 기억력을 가지고 있다. 그래서 하루 동안 본 정수들을 모두 기억 할 수 있다. 하지만 이를 믿을 수 없는 동규는 그의 기억력을 시험해 보기로 한다. 동규는 연종을 따라 다니며, www.acmicpc.net 저는 해당 문제를 이분탐색을 이용하여 문제를 해결하였습니다. 정렬 후 Arrays.binarySearch 를 활용하여 각각의 값이 존재하는지 확인하였습니다. Arrays.binarySearch는 해당 값이 존재하면 해당하는 인덱스를 반환하고 없으면 들어가야하는 자리값의 음수 -1 를 반환합니다. package BOJ.BinarySearch; import java.io.BufferedReader; imp..

https://www.acmicpc.net/problem/1786 1786번: 찾기 첫째 줄에, T 중간에 P가 몇 번 나타나는지를 나타내는 음이 아닌 정수를 출력한다. 둘째 줄에는 P가 나타나는 위치를 차례대로 공백으로 구분해 출력한다. 예컨대, T의 i～i+m-1번 문자와 P의 1～m www.acmicpc.net 저는 해당 문제를 KMP 방법을 이용하여 문제를 해결하였습니다. KMP는 접두사와 접미사가 얼마나 일치하는가를 통해 중간에 틀렸을 때 특정 인덱스로 점프해 일치했던 부분은 검사하지 않는 방법입니다. 저는 일치하였을때 j를 어디로 보내야하는지에 대해 헷갈려 오래걸렸습니다. j를 fail[j]로 바꿔야 합니다. package BOJ.String; import java.io.BufferedRead..

https://www.acmicpc.net/problem/1991 1991번: 트리 순회 첫째 줄에는 이진 트리의 노드의 개수 N(1 ≤ N ≤ 26)이 주어진다. 둘째 줄부터 N개의 줄에 걸쳐 각 노드와 그의 왼쪽 자식 노드, 오른쪽 자식 노드가 주어진다. 노드의 이름은 A부터 차례대로 알파 www.acmicpc.net 저는 해당 문제를 Tree와 Node 클래스를 만들어서 해결하였습니다. 전위 순회는 root - leftChild - rightChild 중위 순회는 leftChild - root - rightChild 후위 순회는 leftChild - rightChild - root 순으로 방문합니다. package BOJ.Tree; import java.io.BufferedReader; import..

https://www.acmicpc.net/problem/16172 16172번: 나는 친구가 적다 (Large) 첫 번째 줄에는 알파벳 소문자, 대문자, 숫자로 이루어진 문자열 S가 주어진다. (1 ≤ |S| ≤ 200,000) 두 번째 줄에는 성민이가 찾고자 하는 알파벳 소문자, 대문자로만 이루어진 키워드 문자열 K가 www.acmicpc.net 저는 해당 문제를 KMP를 이용하여 문제를 해결하였습니다. 일단 먼저 입력받을 것에서 숫자를 제거한 문자열을 kmp알고리즘을 사용하여 같은지를 확인하였습니다. KMP 알고리즘은 접두사와 접미사를 비교하여 얼마나 같은지를 체크하고 불일치하면 점프해서 같은 부분들은 비교하지 않는 알고리즘입니다. package BOJ.String; import java.io.Bu..