코딩테스트/백준_Java
-
Q. 25758 자바 : 유전자 조합코딩테스트/백준_Java 2023. 8. 16. 23:27
문제 : 유전자 조합 실버 1 난이도의 문제이다. 유전자가 주어지고 이를 조합한다. 두 유전자를 조합하면 첫 번째 유전자의 첫 번째 형질(글자)와 두 번째 유전자의 두 번재 형질(글자)가 붙는다 주의해야 할 점은 들어오는 입력값은 최대 10만개이지만 실제로 유효한 값은 AA - ZZ, 중복 최대 1개 => 26 * 26 * 2 = 1352개이므로 중복 처리가 필요하다. 아래와 같은 방식으로 풀었다. 1. 유전자들을 Set에 저장하되, 중복을 한 번은 허용해야 하므로 만약 중복된 값이 들어온다면 중복 값들을 저장한 Set에 추가한다. (두 번 까지만 고려하면 된다) 2. 유전자들을 문제 조건에 따라 섞는다. 이 때 중복해서 들어온 유전자를 따로 처리하면 시간을 좀 더 줄일 수 있다 3. 문제 조건에 따라 ..
-
Q. 15657 자바 : N과 M(8)코딩테스트/백준_Java 2023. 4. 25. 23:29
Q. 15657 자바 : N과 M(8) 문제 : boj.kr/15657 실버 3 난이도의 문제이다. N개의 자연수와 자연수 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오. N개의 자연수는 모두 다른 수이다. - N개의 자연수 중에서 M개를 고른 수열 - 같은 수를 여러 번 골라도 된다. - 고른 수열은 비내림차순이어야 한다. - 길이가 K인 수열 A가 A1 ≤ A2 ≤ ... ≤ AK-1 ≤ AK를 만족하면, 비내림차순이라고 한다. 수열에서 원소를 선택할 때는 중복을 허용하지만, 수열은 중복하면 안된다.주의해야 할 점은 수열은 사전 순으로 증가하는 순서로 출력한다 라는 내용 때문에 수열을 입력 받은 뒤 정렬이 한번 필요하다. 이 문제는 백트래킹과 재귀함수를..
-
Q. 15654 자바 : N과M(5)코딩테스트/백준_Java 2023. 4. 24. 22:59
Q. 15654 자바 : N과M(5) 문제 : boj.kr/15654 실버 3 난이도의 문제이다. N개의 자연수와 자연수 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오. N개의 자연수는 모두 다른 수이다. - N개의 자연수 중에서 M개를 고른 수열을 출력하는 문제이다. 주의해야 할 점은 수열은 사전 순으로 증가하는 순서로 출력한다 라는 내용 때문에 수열을 입력 받은 뒤 정렬이 한번 필요하다. 이 문제는 백트래킹과 재귀함수를 이용해 풀었고, 이전 계산한 결과를 배열에 저장하고, 깊이가 최대일 때 까지 탐색을 완료하면 저장한 결과를 출력하는 방식으로 풀었다. 시간 복잡도를 계산하면, M과 N이 최대 8이므로 1. 계산 - O(N^M) 2. 출력 - O(NM) ..
-
Q. 14940 자바 : 쉬운 최단거리코딩테스트/백준_Java 2023. 4. 22. 23:20
Q. 14940 자바 : 쉬운 최단거리 문제 : boj.kr/14940 실버 1 난이도의 문제이다. 그래프가 주어지고, 시작 정점이 주어질 때 모든 정점의 최단거리를 출력하는 문제이다 주의해야 할 점은 원래 갈 수 있는 땅인 부분 중에서 도달할 수 없는 위치는 -1을 출력한다는 점 이다 아래와 같은 방법으로 풀었다. 1. 입력은 bool 타입의 2차원 배열로 받았으며, 방문 가느한 위치를 true로 표시했다. (이 때 시작 정점의 위치는 따로 저장해 주었다.) 2. 이후 BFS 순회를 통해 모든 정점을 탐색하며 결과값은 ResArr이라는 2차원 int형 배열에 저장했다. (벽이 아닌 경우 - !Graph[y][x], 방문한 경우 visit[y][x] 에는 방문하지 않았다) 3. 탐색이 끝난 뒤 출력을 위..
-
Q. 4179 자바 : 불!코딩테스트/백준_Java 2023. 4. 21. 18:52
Q. 4179 자바 : 불! 문제 : boj.kr/4179 골드 4 난이도의 문제이고, 탈출 문제와 유사하다 탈출해야 하는 지훈이와 불이 주어지고 불은 점점 확산된다. 이 때 얼마나 빨리 지훈이가 탈출할 수 있는지 계산하는 문제이다. 주의해야 할 점은 불과 지훈이가 같이 있는 경우 탈출할 수 없다. 그래서 BFS 탐색을 사용하기 전에 불을 먼저 queue에 넣어주고 지훈이의 위치를 마지막에 넣었다. 또한 탈출하는 경우는 미로의 가장자리에 있는 경우이고, 탈출 시 이동 횟수가 하나 늘어난다. 아래와 같은 방식으로 풀었다. 1. 입력값은 visit 배열을 이용해서 받았고, 벽(#), 지훈이(J), 화염(F) 모두 방문 체크를 했다. 2. 입력을 받을 때 지훈이와 불의 위치를 모두 저장한 뒤 BFS 탐색 전 ..
-
Q. 2660 자바 : 회장 뽑기코딩테스트/백준_Java 2023. 4. 20. 16:50
Q. 2660 자바 : 회장 뽑기(BFS) 문제 : boj.kr/2660 골드 5 난이도의 문제이다. 간선들이 주어지고, 모든 정점에 방문 가능한 깊이가 가장 적은 사람을 구하는 문제이다. 주의해야 할 점은 출력할 때 회장 후보를 오름차순으로 모두 출력한다는 내용 때문이 있으므로 결과값을 계산한 뒤 정렬이 한번 필요하다. 아래와 같은 방식으로 풀었다. 1. 모든 정점을 계산해야 하므로 모든 정점에 대해 bfs 탐색이 필요하다. 2. 탐색을 할 때 만약 깊이를 줄일 수 있다면 방문한 정점도 다시 탐색한다. (이전 정점을 탐색하지 않도록 주의) 3. 탐색이 끝난 뒤 모든 정점 방문 시 깊이에 대한 값을 계산한다. 이 때 회장 후보일 수 있으므로 결과값과 현재 회장 후보의 값을 비교해 저장한다. 4. 깊이의 ..
-
Q. 12427 자바 : 회사 문화 1코딩테스트/백준_Java 2023. 4. 19. 15:16
Q. 12427 자바 : 회사 문화 1 문제 : boj.kr/12427 골드 4 난이도의 문제이고, 앞의 트리와 쿼리 문제와 유사하다. 트리형 그래프가 주어지고, 칭찬의 횟수가 주어진다. 이 때 칭찬은 칭찬을 받은 사람과 모든 자식(=칭찬을 받은 사람의 서브트리) 전부 받는다. 문제는 아래와 같이 풀었다. 처음 문제를 봤을 때 칭찬을 받을 때 마다 dfs 순회를 하려 했지만, 시간 초과가 날 것 같고 출제자의 의도도 아닌 것 같아 전부 저장하고 한 번만 순회하는 방식으로 풀었다. 1. 칭찬을 받을 때 마다 int 배열에 해당 정점에 값을 저장한다. 2. 칭찬이 끝난 뒤 부모의 칭찬을 자식에 더하는 방식으로 dfs 순회를 한다. 직원수가 n, 칭찬의 수가 m이고 둘 값은 최대 100,000이다.시간 복잡도..
-
Q. 15681 자바 : 트리와 쿼리코딩테스트/백준_Java 2023. 4. 17. 16:48
Q. 15681 자바 : 트리와 쿼리 문제 : boj.kr/15681 골드 5 난이도의 문제이다. 트리와 간선이 주어진다. 이후 Q개의 정점이 주어지고 각 정점을 루트로 하는 서브트리의 정점의 수를 구하는 문제이다. 아래와 같은 풀이로 풀었다. 0. 간선이 주어지므로 ArrayList를 사용해 트리 구조를 만든다. 1. 루트 노드가 주어지므로, dfs 탐색을 이용해 탐색한다. 2. 서브트리의 정점의 수를 구하기 위해 탐색 이후 종료 전에 자식을 루트로 하는 서브트리의 정점의 수를 저장한다.(메모제이션 방식) 3. 이후 Q개의 정점에 대해 각 정점을 루트로 하는 서브트리의 정점의 수를 2번에서 저장한 값을 이용해 결과를 출력한다. 시간 복잡도는 정점의 수 N 이 최대 10,000이고 탐색하는 정점 Q도 최..