Algorithm 171

[BOJ] 17265. 나의 인생에는 수학과 함께

단순한 DFS문제였다. 맨처음 백트래킹으로 접근하려했으나, 오른쪽과 아래로만 접근이 가능하기에 DFS를 적용하여 풀어주었다. 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 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 package algostudy3; import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.StringTokenizer; publi..

Algorithm 2021.07.28

[BOJ] 18223. 민준이와 마산 그리고 건우

다익스트라를 활용한 문제였다. 총 2번의 다익스트라를 활용하였는데, 출발점 기준 그리고 친구 기준으로 두번 다익스트라를 활용하였다. 출발에서 목적지까지의 거리랑 출발에서 친구 + 친구에서 목적지 까지의 거리를 비교하는 간단한 문제였다. 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 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92..

Algorithm 2021.07.20

[BOJ] 14752. 개미굴

Trie와 DFS를 활용한 문제였다. Trie를 활용하기 위해 Node라는 클래스를 만들고, 그안에 child라는 Map구조의 Node를 주었다. 일반 적인 Trie문제와 다르게 배열대신 Map을 활용해보았다. 그렇게 모든 입력들을 root아래 저장 후, DFS를 활용하여 출력을 해주었다. 단, 이때 알파벳순 출력이 필요하기때문에 Map의 keySet을 정렬된 리스트의 형태로 만들고 문제를 풀었다. 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 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61..

Algorithm 2021.07.20

[BOJ] 1701. Cubeditor

KMP를 활용하는 문자열 문제이다. 이 문제를 맨처음엔 모든 문자열 패턴을 구해서 입력문자열에서 패턴을 찾는 방식으로 생각해보았다. 하지만 문자열 최대 길이가 5000이기에 모든 패턴을 구하는건 불가능했다. 그래서 생각해보니 KMP를 사용할때 접두사와 접미사를 이용하여 패턴의 길이를 구하는 pi를 활용하는 방안을 떠올렸다. 이것을 이용하면 2번이상 등자하며 최장길이를 구할 수 있게 되기에 적용해보았다. 단, abbcbba와 같은 패턴에서는 bb를 못찾기에 이것을 위해선 bbcbba를 확인해야하는 반례가 생긴다. 그래서 입력문자열의 앞에서부터 하나씩 줄여주며 pi를 구하는 방식으로 풀어보았다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 ..

Algorithm 2021.07.14

[BOJ] 9935. 문자열 폭발

패턴을 찾는 문자열 문제이다. 맨처음 패턴을 찾는 문제이기에 KMP를 사용하여 접근해보았다. 하지만 KMP가 반복적으로 호출되기때문에 시간초과가 발생한다. 따라서 다른방법을 사용해보았다. 스택을 사용하여 주어진 문자열의 앞에서부터 하나씩 스택에 집어넣고, 그 후 찾아야하는 패턴보다 같거나 큰길이를 스택이 가진다면 맨뒤에 스택의 맨뒤의 문자열이 패턴문자열과 똑같은지를 찾고, 똑같다면 제거해주는 방식의 알고리즘을 사용할 수 있다. 다만, 스택은 구조상 비효율적이기에 StringBuilder를 적용하여 풀어보았다. 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 38 39 40..

Algorithm 2021.07.13

[BOJ] 16438. 원숭이 스포츠

분할정복을 이용하여 해결할 수 있던 문제였다. 이 문제 같은경우 맨처음 문제자체를 이해하지 못하였다. 하지만 분할정복이라는게 떠올랐고, 머지소트와 비슷한 원리로 접근해보았다. 우선 7일을 출력하기 위해 result란 이차원배열을 만들어두고, 분할정복을 시도하였다. 우선 start와 end값을 받고, 이들의 중간값인 mid를 구하게 된다. 이렇게 start~mid, mid~end 까지 두 그룹으로 나누고 알파벳을 각 각 배정해준다. 이렇게 되면 두그룹은 서로 한번은 적으로 만나는 것이 보장이되게 된다. 이런식으로 재귀호출하여 분할정복을 적용해보았다. 단 맨끝 결과에 오로지 B로만 차있는 경우가 생기게 되는데 이경우엔 A를 임의로 하나 넣어주었다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 ..

Algorithm 2021.07.09

[BOJ] 16432. 떡장수와 호랑이

DFS를 이용하는 문제였다. 맨처음 문제를 접했을때 아무생각없이 바로 DFS를 적용해봤는데, 역시나 최악의 경우 8^1000(전날의 떡을제외한 경우^날짜수)이 나오기때문에 시간초과를 면할 수 없었다. 그래서 바로 방문체크로 가지치는 방법을 택해주었다. visit[i번째날][떡]을 하나 만들어서 만일 이전날의 떡과 다르면서 visit[오늘][떡]이 방문 가능하다면 방문을 하고 방문체크를 해주는 방식으로 구현해보았다. 이렇게 된다면 어떠한 방식으로든 오늘에서 가질수 있는 떡을 중복으로 방문하는 것을 막을 수 있게 된다. 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 38 3..

Algorithm 2021.07.08

[BOJ] 1967. 트리의 지름

DFS를 이용하여 트리의 구조에서 지름을 찾는 문제였다. 트리의 지름은 리프노드에서 리프노드까지의 거리를 의미하기 때문에 브루트포스의 형식으로 모든 노드를 탐색하면서 리프노드라고 판별될 경우 그 노드를 기준으로 DFS를 돌아서 다른 리프노드까지의 거리를 찾아서 비교하여 최대값을 구하는 방식으로 풀이해보았다. 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 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 package algostudy2..

Algorithm 2021.07.02

[BOJ] 16437. 양 구출 작전

위상정렬 혹은 DFS를 사용할 수 있는 문제였다. 이 문제는 트리 문제로써 각 위치마다 양 또는 늑대가 존재하고, 루트까지의 양의 총합을 구하는 문제였다. 트리를 형성하고, 전체를 순회하는 구조이기에 맨처음 DFS로 접근해보았다. 1번(루트)에서 DFS를 한번도는 방식을 구상하였는데, 양의 수를 구하기 위해 DFS를 돌때 리턴값(양의 수)을 가지게 되고 최종적으로 자식노드 부터 리턴값을 보내어 1번(루트)에서 받아보는 방식을 생각해보았다. 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 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 ..

Algorithm 2021.07.02

[BOJ] 1507. 궁금한 민호

플로이드 와샬을 활요하는 문제였다. 이 문제같은 경우 잘생각할 필요가 있는 문제이다. 이미 주어지는 입력이 최소 이동 시간이고, 여기서 구해야할 것이 필요없는 도로를 골라내는 문제이다. 즉 입력을 이용하여 다시 플로이드와샬을 돌면서 map[i][j] = map[i][k] + map[k][j] 인 경우 map[i][j] 경로가 필요없게 됨으로 이것을 찾아주었다. 또한 불가능한 경우는 최소값을 갱신할 수 있을경우이기에 이것에 대한 처리도 같이 해주었다. 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 38 39 40 41 42 43 44 45 46 47 48 49 50 51 ..

Algorithm 2021.06.24