문제https://www.acmicpc.net/problem/2661 풀이백트래킹을 활용한 문제입니다. 처음에 문제를 보고 정말 많이 헤맸는데, 숫자형으로 표현해야한다는 무의식적인? 고집이 있었습니다. 수열이다보니 숫자로 어떻게 조합을 잘 해야겠다라고 생각한 것이 시간을 많이 잡아먹었습니다. 이 문제에서 포인트가 두 가지가 있다고 생각합니다. 첫 번째는 나타낼 수열을 String으로 받는 것, 그리고 좋은 수열인지 아닌지를 어떻게 판단할지입니다. 전체적인 구조는 백트래킹 메서드의 매개변수를 String 형의 수열로 받아, 좋은 수열이 맞다면 다시 재귀를 돌려주는 방식입니다. 좋은 수열인지를 판단하는 메서드는 String을 subString으로 나누어 반복문을 돌며 구간 검사를 진행하면 됩니..
분류 전체보기
젠킨스를 올바르게 설정했는데 9090 포트로 접속하니, 계속해서 접속이 되지 않는 상황이 생겼습니다. 세 가지를 확인해 해결했습니다. 1. 젠킨스 설정과 Docker부터 Docker-Compose까지 올바른지 전부 확인 docker-compose.yml파일이 올바른지 확인합니다. yml 파일을 작성할 때 주의해야할 점은 아래와 같습니다.1. 첫 줄에는 도커 컴포즈 버전을 적는다.2. 주 항목에는 services, networks, volumes가 있고, 들여쓰기를 해서 하위 항목들을 작성한다.3. 들여쓰기는 몇 칸이든 상관은 없지만, 2칸으로 하기로 했으면 모든 내용들이 2칸으로 동일해야한다.4. 이름 뒤에는 무조건 : 를 붙인다.5. : 과 - 뒤에는 반드시 공백이 하나 있어야한다. Docker ..
문제https://www.acmicpc.net/problem/3020 풀이 누적합을 이용해 해결한 문제입니다. 입력값이 2 ≤ N ≤ 200,000, 2 ≤ H ≤ 500,000 으로 주어지기 때문에, 이중 for문을 돌면 바로 시간 초과에 걸리게 됩니다. 문제 상황을 위처럼 그림으로 나타내볼 수 있었습니다. 각 높이별로 파괴해야하는 장애물의 개수을 표시한 것입니다. 저 개수를 어떻게 구해야할지 생각해보다가 우선 석순과 종유석 배열을 각각 나누어야겠다고 생각했습니다. 그래서 우선 입력을 석순과 종유석(bottom[], up[])배열에 나누어서 받았습니다.이 때, 주어지는 입력 값인 장애물의 크기는 bottom[], up[] 배열의 인덱스로 입력받아, 해당하는 인덱스 배열의 값을 +1 해줍니다...
문제https://www.acmicpc.net/problem/1063 풀이 구현 문제입니다. 입력값을 어떤 형식으로 받을 것인지, 그리고 구현을 위한 메서드를 어떻게 나누고 적용할 것인지가 중요한 포인트 같습니다. 처음 구현시에 입력값도 String으로 받고 메서드를 제대로 분리하지 못했더니 너무 코드가 난잡해져서, 다시 입력 자료구조와 메서드를 정의해 문제를 해결했습니다. 우선 입력 시 char[] 배열을 통해 체스의 행과 열을 각각의 인덱스에 저장을 해주었습니다. 메서드는 크게 두 가지인데, chess를 옮기는 것과 범위를 체크하는 것입니다. 이 메서드를 king과 stone을 옮길 때 모두 사용할 수 있게끔 유연하게 만들어주었습니다. 그리고 조건에 통과해야지만, 이동된 배열 값에 업데이트를..
문제https://www.acmicpc.net/problem/18223 풀이다익스트라를 활용한 문제입니다. 일반적인 다익스트라 문제와 다른 것은, 특정한 경로를 지나칠 때를 고려해야한다는 것입니다. 특정한 경로를 지나치게하기 위해서 어떤 특별한 장치를 해야하는 것은 아니고, 그 특정 지점에서 다익스트라 알고리즘을 통해 각각의 노드까지의 최단 거리를 구해주기만 하면 됩니다. 그리고 그렇게 구한 최단 거리 배열을 통해 정답을 구할 수 있습니다. 아래는 소스 코드입니다. 소스 코드import java.util.ArrayList;import java.util.Arrays;import java.util.PriorityQueue;import java.util.Scanner;public class B1822..
문제https://www.acmicpc.net/problem/15681 풀이 서브 트리에 속한 정점의 개수를 세는 문제입니다. dfs를 통해 그래프를 탐색하며, 서브 트리의 루트가 인덱스인 배열에 정점의 개수를 저장합니다. 처음에 문제를 풀이할 때, 루트가 아닌 제일 마지막 자식부터 dfs 탐색을 시작해보려고도 했지만, 그렇게 접근하면 마지막 자식도 체크해야하고, 방문 배열을 통해 접근을 막아주어야하고.. 여러모로 로직이 복잡해집니다. 그래서 루트부터 출발해 자식으로 뻗어가며 subtrees 배열에 정점의 개수를 저장합니다. 이때 부모 노드에 자식 노드가 가진 정점의 개수를 더해주면 됩니다. 주의할 것은, 부모에서 자식으로 내려갔는데 다시 부모 노드를 검사하지 않도록 하는 것입니다. 이것은 d..
