계단을 오르듯이

처음 입력받는 값은 각 노드의 연결 여부를 나타내는 배열을 입력받는다. 출력해야하는 결과값은 각 노드의 연결 여부를 최대한 이용하여 서로의 노드를 연결할 수 있는지 여부를 나타내는 결과값을 의미한다. 모든 노드의 연결 상태를 모두 확인하여 최소한의 연결 경로의 값을 찾는 플로이드 워샬 알고리즘을 이용하였다. 해당 알고리즘을 이용해 모든 연결 상태의 경우를 이용해 해당 노드들이 연결 상태인지를 알아내었다. 단지 최소의 값을 찾는 플로이드 워샬 알고리즘을 연결여부만을 나타내는 것으로 약간 바꾸어 연산을 하게 하였다. 최소의 값을 찾는 것이 아닌 0이면 연결이 되지 않은 상태이고, 1이면 연결 상태임을 나타내고, k를 경로로 하여 i-k와 k-j가 연결 상태이면 i-j를 연결상태로 나타내는 방식으로 연산을 진..

백준에 비슷한 문제가 있다. 이 문제를 푼 경험을 통해 조금더 쉽게 할 수 있었다. 2636번: 치즈 아래 과 같이 정사각형 칸들로 이루어진 사각형 모양의 판이 있고, 그 위에 얇은 치즈(회색으로 표시된 부분)가 놓여 있다. 판의 가장자리(에서 네모 칸에 X친 부분)에는 치즈가 놓 www.acmicpc.net 처음 가장 고민한 부분은 안쪽 치즈를 녹이지 않고 밖에 존재하는 외부 치즈만 녹이는 법을 어떻게 해야하는지 고민을 했었다. 우리는 항상 빈곳이 아닌 곳을 방문처리하고, bfs를 하였는데 이 경우는 반대로 치즈가 존재하지 않은 곳을 시작으로 계속해서 0인 곳을 큐로 넣고 연산을 시작하면, 놀랍게도 안쪽의 치즈는 영향을 받지 않게 된다. 계속해서 0인 곳만을 큐에 넣기 때문에 밖에서 외부의 치즈 방어막..

0 의 숫자가 입력으로 들어오면 가장 마지막에 받은 수를 지워야하므로 스택의 자료구조를 이용하였다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 package algo; import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.Stack; public class B_10773_제로 { public static void main(String[] args) throws Exception { BufferedReader in = new BufferedReader(new InputStreamReader(System.in)); int N = I..

문자열을 받아 각 문자의 방문처리 체크로 문제를 해결하였다. 주석과 코드로 설명을 대체하겠다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 package algo; import java.io.BufferedReader; import java.io.InputStreamReader; public class B_1316_그룹단어체커 { public static void main(String[] args) throws Exception { BufferedReader in = new BufferedReader(new InputStreamReader(System.in)); int..

2차원과 같은 방식으로 접근하였고, 차이점은 방문처리도, 토마토를 넣는 배열도 3차원이고, 방향을 나타내는 배열의 방향이 2개 늘어 6개가 되었다는 점이다. 방향을 나타내는 dir 배열은 똑같은 2차원 배열에서 2차원의 수가 2에서 3으로 늘었다. 배열은 [높이][세로][가로] 로 하였다. 토마토에서 아직 덜 익은 0의 값의 수를 구하였고, 큐에 미리 익은 토마토를 넣어주었다. 큐에는 Node 클래스를 이용해 시간을 나타내는 time의 변수로 연산의 시간을 측정하였다. 익지 않은 토마토가 익게 되면 덜 익은 토마토의 수를 감소시켰고, 그 수가 0이 되면 연산이 종료되며 그 토마토가 익은 시간을 출력한다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22..

상하의 알파벳은 수월했으나 좌우의 커서이동 부분이 힘들었다. 커서이동을 최소로 하기 위해 A가 연속되는 부분의 연산을 해주어야 한다. 또한 가장 key-point는 BBBBAAAAAABB 라고 가정하면, 이 경우에는 뒤를 탐색한 후 다시 앞으로 돌아오는 경로가 가장 적은 수의 커서이동이 된다. 그 이유는 커서를 이동을 하여 연산을 한 후 다시 방향을 돌려야 할 때 커서로 이동한 만큼 다시 반대방향으로 돌아오는 이동을 해야하기 때문이다. 즉 앞에서 시작하면 (좌 -> 우를 시작으로) 3번을 갔다가 다시 3번을 돌아와 2번을 가는 경우는 8번의 커서이동이 되고, 뒤에서부터 앞으로 오는 경우는 2번으로 맨 뒤 오른쪽으로 가서 다시 2번으로 앞으로 돌아오며 3번의 커서이동을 더해 커서이동이 마무리 된다. 이 경..

h의 범위가 될 수 있는 최대의 범위는 citations 배열의 길이만큼이므로 0부터 길이까지만큼 탐색한다. 배열은 오름차순으로 정렬한 후 해당 배열의 큰 수부터(뒤에서부터) 탐색하여 해당 수만큼의 개수를 만족하면 빠져나오고 answer의 값을 갱신해주고, 더 이상 만족하지 못할 시 모든 탐색을 종료한다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 import java.util.*; class Solution { public int solution(int[] citations) { int answer = 0; int len = citations.length; Arrays.sort(citations); for(int i=0;i=0;..

처음에는 입력받는 문자열의 문자를 배열에 저장하였고, 중복을 줄이기 위해 set을 이용했으나 메모리 초과가 나왔다. 예상은 했으나 딱히 다른 방법이 생각나지 않았다. 검색을 해보니 방식은 26개의 알파벳으로 한정되어있기 때문에 26개의 배열을 마련하고 거기서 해당 문자의 수만큼 배열의 값을 증가시키는 방식을 통해 구현하였고, 그렇게 되면 for문을 돌리면 해당 알파벳의 배열에서 값이 0보다 크면 그 알파벳을 사용하고 아니면 사용하지 못하며, 중복을 방지할 수 있다. 즉, 알파벳 하나씩을 배열에 넣으면 arr[0]도 arr[1] 도 a를 가지고 있다면 for문을 통해 중복이 되지만, arr[0]에 2라는 값으로 2번 들어있다는 것을 의미하면 for문은 0일 때만 a를 선택하므로 중복을 없앨 수 있게 되는 ..