java
-
[백준 1476번] 날짜 계산 (자바)Algorithm/기타 2022. 6. 27. 19:39
백준알고리즘 1476번 : 날짜 계산 (Solved.ac 난이도 Silver5) https://www.acmicpc.net/problem/1476 1476번: 날짜 계산 준규가 사는 나라는 우리가 사용하는 연도와 다른 방식을 이용한다. 준규가 사는 나라에서는 수 3개를 이용해서 연도를 나타낸다. 각각의 수는 지구, 태양, 그리고 달을 나타낸다. 지구를 나타 www.acmicpc.net 숫자 3개를 가지고 날짜를 계산하는 문제이다. N에서 x를 뺀 숫자가 15의 배수, y를 뺀 숫자가 28의 배수, z를 뺀 숫자가 19의 배수가 되는 정답 N을 구하는 문제이다. 예시에 나온 것처럼 1 2 3이 주어지는 경우, 정답 N(5266)은 5266에서 1을 뺀 수가 15의 배수이고, 5266에서 2를 뺀 수가 28..
-
[백준 15651번] N과 M(3) (자바)Algorithm/DFS 2022. 6. 22. 13:06
백준알고리즘 15651번 : N과 M(3) (Solved.ac 난이도 Silver3) https://www.acmicpc.net/problem/15651 15651번: N과 M (3) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net 배열에 값을 담은뒤에 DFS를 이용하여 출력하는 문제이다. 처음에는 출력해야하는 길이값에 따른 배열에 담지않고 바로 출력할수는 없을까.. 라고 생각해서 풀어보았다. 당연하게도 앞에서 여러번 출력되어야하는 숫자들이 한번씩만 출력된다. 요지는 배열의 길이만큼 숫자를 채울때까지 DFS를 돌리고, 다 찬 시점에 바로바..
-
[백준 2164번] 카드2 (자바)Algorithm/큐(Queue) 2022. 6. 21. 11:49
백준알고리즘 2164번 : 카드2(Solved.ac 난이도 Silver4) https://www.acmicpc.net/problem/2164 2164번: 카드2 N장의 카드가 있다. 각각의 카드는 차례로 1부터 N까지의 번호가 붙어 있으며, 1번 카드가 제일 위에, N번 카드가 제일 아래인 상태로 순서대로 카드가 놓여 있다. 이제 다음과 같은 동작을 카드가 www.acmicpc.net Queue에 오름차순으로 숫자를 넣은뒤에 규칙대로 빼고, 뺀 숫자를 뒤에 add하여 Queue의 size가 1이될 때 남은 값을 출력하면 된다. 풀이 과정 1. Queue에 오름차순으로 숫자를 add한다. 2. while문으로 Queue의 size가 1이 넘는동안 규칙을 반복한다. 3. Queue size가 1이 될 때 해..
-
[백준 10844번] 쉬운 계단 수 (자바)Algorithm/Dynamic Programming(DP, 동적 프로그래밍) 2022. 5. 30. 15:16
백준알고리즘 10844번 : 쉬운 계단 수 (Solved.ac 난이도 Silver1) https://www.acmicpc.net/problem/10844 10844번: 쉬운 계단 수 첫째 줄에 정답을 1,000,000,000으로 나눈 나머지를 출력한다. www.acmicpc.net DP(Dynamic programming) 문제이다. 초항의 길이별 정답을 통해 규칙을 찾고, 그 규칙들로 길이 N인 계단 수를 찾을 수 있다. 규칙을 찾기위해 자리 길이가 1일때와 2일때를 계산해보았다. N=1일때 경우의수? 1~9 까지 총 9가지(0으로 시작하는 수는 계단 수가 아님) N=2일 경우의 수? 맨 뒤에 9가 붙는 경우(앞에 8이 있는 갯수) - 1 맨 뒤에 8이 붙는 경우 (앞에 7,9가 있는 갯수) 맨 뒤에 ..
-
[백준 1037번] 약수 (Java 풀이)Algorithm/정렬(Sort) 2022. 5. 29. 11:16
백준알고리즘 1037번 : 약수 (Solved.ac 난이도 Silver5) https://www.acmicpc.net/problem/1037 1037번: 약수 첫째 줄에 N의 진짜 약수의 개수가 주어진다. 이 개수는 50보다 작거나 같은 자연수이다. 둘째 줄에는 N의 진짜 약수가 주어진다. 1,000,000보다 작거나 같고, 2보다 크거나 같은 자연수이고, 중복되 www.acmicpc.net 문제를 꼼꼼히 읽어야한다는 것을 다시한번 상기하게되었다. 얼핏 보고 나열된 숫자들의 최소공배수를 구하는 문제인 줄 알았는데, 나열된 약수들을 갖고 있는 숫자를 맞추는 문제였다. 양수 A가 정답이라면, A와 1은 약수로 치지않는다. 약수들의 목록을 오름차순으로 정렬하고, 최소 값과 최댓 값의 곱을 구해주면 간단하게 해..
-
[백준 2644번] 촌수 계산 (Java 풀이)Algorithm/DFS 2022. 5. 23. 21:13
백준알고리즘 2644번 : 촌수 계산 (Solved.ac 난이도 Gold5) https://www.acmicpc.net/problem/2644 2644번: 촌수계산 사람들은 1, 2, 3, …, n (1 ≤ n ≤ 100)의 연속된 번호로 각각 표시된다. 입력 파일의 첫째 줄에는 전체 사람의 수 n이 주어지고, 둘째 줄에는 촌수를 계산해야 하는 서로 다른 두 사람의 번호가 주어 www.acmicpc.net 촌수를 이동함에 따라 count를 해주어야하는 부분에서 약간 헤멨다. 특이사항이 있다면, 일반적인 dfs와는 달리 한번 check한 LinkedList에 대해서는 다시 확인을 할 필요가 없다는 점이다. 그렇게 해도 되는 이유는 문제에서 '각 사람의 부모는 최대 한 명만 주어진다.'라고 명시되어 있기 때..
-
[백준 11725번] 트리의 부모 찾기 (Java 풀이)Algorithm/DFS 2022. 5. 17. 18:34
백준알고리즘 11725번 : 트리의 부모 찾기 (Solved.ac 난이도 Silver2) https://www.acmicpc.net/problem/11725 11725번: 트리의 부모 찾기 루트 없는 트리가 주어진다. 이때, 트리의 루트를 1이라고 정했을 때, 각 노드의 부모를 구하는 프로그램을 작성하시오. www.acmicpc.net DFS와 BFS 모두를 이용해서 풀 수 있는 문제였다. LinkedList 타입의 배열을 정의하는 것이 문제 해결에 도움이 많이 되었다. 아직 DFS 및 BFS에 익숙치않아 2가지버전 모두 사용해서 풀어보았다. 실제 소스의 차이는 그리 크지 않다. method를 재귀로 할 것인지, while문을 낀 queue로 할 것인지의 차이정도? 속도 차이도 유의미하게 크지는 않았다...
-
[백준 14502번] 연구소(자바)Algorithm/BFS 2022. 5. 14. 18:07
백준알고리즘 14502번 : 연구소 (Solved.ac 난이도 Gold5) https://www.acmicpc.net/problem/14502 14502번: 연구소 인체에 치명적인 바이러스를 연구하던 연구소에서 바이러스가 유출되었다. 다행히 바이러스는 아직 퍼지지 않았고, 바이러스의 확산을 막기 위해서 연구소에 벽을 세우려고 한다. 연구소는 크 www.acmicpc.net 벽을 세우는 경우의 수만큼 BFS를 돌려보는 방식으로 풀 수 있었다. 우리는 배열에서 0을 갖고있는 위치 3군데를 1로 바꾸어 벽으로 만들 수 있다. 3중 for문을 돌려서 0 3개를 1로 바꾼 뒤, BFS를 적용하여 바이러스를 침투시켜본다. 그 후에 남은 0의 개수를 count하면 해당 case의 안전 영역 크기를 도출할 수 있다. ..