분류 전체보기 243

[SWEA] 5653. 줄기세포배양

BFS를 이용하여 구현하는 문제이다. 이 문제에서 유의할게 여러가지 있었다. 갱신을 하는 과정에서 생명력 수치가 높은 줄기 세포가 그리드 셀을 차지 하는 것, X시간 동안 비활성 상태를 거치고 X시간이 지나는 순간 X시간 동안 활성상태가 되는 것, 맵의 크기가 제대로 주어지지 않는 점등 구현에 까다로운 점이 많았다. 다음과 같이 해결하였다. 생명력 수치가 높은 세포로 갱신 -> PriorityQueue를 이용하여 생명력이 높은 세포들이 가장 위에 올수있도록 사용 X시간 후 X시간 동안 활성 -> curLive가 0이 되기전까지 계속 PrioirtyQueue에 남겨두기 맵의 크기 -> 주어진 r,c값에 time*2를 더해준 만큼 크기를 잡기 구현의 고려요소가 많아서 상당히 오랜시간을 풀었고, 많은 것을 참..

Algorithm 2020.04.27

[BOJ] 1748. 수 이어 쓰기1

브루트 포스 문제이다. 그러나 단순 브로트포스로 풀게되면 시간초과가 생기기 때문에 최적화를 시키고 풀어야한다. 다음과 같이 풀수 있다. N=120 - 1 ~ 9 => (9 - 1 +1) X 1 - 10 ~ 99 => (99 - 10 +1) X 2 - 100 ~ 120 => (120 - 100 +1) X 3 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 online.practice; import java.io.BufferedReader; import java.io.InputStreamReader; public class Main_bj_1748_수이어쓰기1 {..

Algorithm 2020.04.22

[BOJ] 6087. 레이저 통신

C에서 C까지의 최단경로를 찾는 BFS문제이다. 최단경로를 찾을때 다익스트라 알고리즘 또한 사용가능하지만, 이 문제에선 BFS를 사용하여 구현하였다. 이 문제는 자신의 방향과 방향전환횟수를 알고있어야해서 Pos라는 class에 담아둔 상태로 구현하였다. 맨처음엔 일반 visti[][] 배열을 사용하여 방문하지 않았으면 방문하고, 만일 방문했더라도 갱신이 가능하다면 다시 방문하는 방식을 사용하였다. 하지만 어느부분에서 처리가 잘되지않아 다른방법을 사용하였다. 벽을 부수고 이동하기 처럼 visit[][][] 3차원 배열을 사용하였다. 즉 visit[row][col][조건]으로 두고 풀었다. 이 문제에선 조건 부분이 방향을 뜻하는 4가지방법을 의미하여 이와같이 풀어 해결하였다. 1 2 3 4 5 6 7 8 9..

Algorithm 2020.04.19

[BOJ] 1107. 리모컨

모든 경우를 다해보는 브루트포스 문제이다. 브루트포스는 기본적으로 다음4가지로 구현할 수 있다. 1. for문 2. 순열 3. 재귀 4. 비트마스크 이 문제에서는 만들 수 있는 숫자를 모두 해봐야하 알 수 있는 브루트포스 문제여서 숫자를 만들때 재귀를 이용하여 풀었다. 그리고 모든 숫자의 경우에서 answer를 계속 갱신해주는 방식으로 해주었다. 이 문제는 특히 주의할 점이 상당히 많다. 시작점이 100이라는 것과 또한 2번째 입력이 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 28 29 30..

Algorithm 2020.04.18

[BOJ] 13023. ABCDE

인접리스트를 활용한 DFS문제이다. 맨처음 문제접근을 BFS로 하였는데, 이 문제에선 5개의 이어진 노드를 찾는 것이여서 DFS를 활용하여 depth가 5가 될때까지를 찾는게 맞는 방향이라 생각해 DFS로 바꾸어 풀었다. 이 문제에서는 주의할 것은 다양한 방법으로 여러갈래로 찾을 수 있기에 visit[i]=false로 다시 바꾸어 주는 작업이 필수적이다. 이것을 해주지 않아 계속 틀렸었다. 예를 들어 위와 같은 그래프가 있고 1번 정점부터 탐색한다고 생각하자. 첫번째 DFS를 실행시킨 결과가 1-2-4-5-3 이라고 생각한다면 depth는 최대 4까지 밖에 찾지를 못한다. 그렇기에 종료조건을 만족하지 못하고, 재귀가 끝나면서 다시 재귀호출을 하게 된다. 1-2 이상황에서 4를 방문했었기네 1-2-3을 해..

Algorithm 2020.04.17

[BOJ] 1260. DFS와 BFS

그래프를 사용하여 DFS와 BFS를 하는 기본 문제이다. 그래프를 인접리스트로 구현하여 DFS와 BFS각 각 구현하였다. DFS를 구현할 때는 stack을 사용하는 대신 재귀의 형태로 구현하였다. BFS를 구현할 때에는 queue를 사용하여 구현하였다. DFS에서는 방문할때 바로 visit 체크를 해주었고, BFS에서는 queue에 offer하는 동시에 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 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 ..

Algorithm 2020.04.17

[BOJ] 14226. 이모티콘

BFS를 활용하는 문제이다. 그러나 일반적인 BFS를 사용한다면 틀린 답을 출력할 것이다. 왜냐하면 클립보드라는 개념을 이문제에선 가지고 있는데 S개의 아이콘을 만드는데 걸리는 시간을 T라고 한다면, 같은 S개를 만들더라도 클립보드의 수에 따라 각 각 다른 T를 가지게 된다. 이 이유는 그래프에서 예를 찾을 수 있는데, 정점 A에서 B를 가고 싶을때, 간선1을 선택해서 가는 경우랑 간선2를 선택해서 가는경우가 있다 가정하자. 같은 B를 도달했더라도 다른 간선을 선택하여 왔기때문에 다른 경우의 수라 생각할 수 있다. 즉, 문제로 다시 돌아와본다면 클립보드의 수에 따라 같은 S개를 만들더라도 다른 T시간을 가질 수 있기 때문에 시간을 저장하는 배열 visit를 2차원의 배열의 형태로 작성하였다. 즉 visi..

Algorithm 2020.04.14

[BOJ] 15658. 연산자 끼워넣기(2)

재귀를 사용해야만 풀수있는 문제이다. 14888.연산자 끼워넣기 와 비슷한 문제이지만 이문제는 연산자의 갯수가 최대 4N개가 주어질 수 있으므로 순열 또는 조합의 방법을 사용할 수 가 없다. 따라서 재귀를 사용해야하는데, 재귀의 조건은 연산자의 종류인 총 4가지가 될 수가 있다. 즉, 숫자와 숫자사이에서 가지고 있는 연산자의 갯수에 따라 4개중 어떤것을 호출하냐를 결정할 수 있다. 기저조건으로는 마지막 index까지 도달했을 경우로 두었다. 보통 재귀는 '했다', '안했다'를 재귀의 요소로 두지만, 이 경우는 '4가지중 어떤것을 했다' 로 두고 풀었다. 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 3..

Algorithm 2020.04.14

[BOJ] 14501. 퇴사

이 문제는 재귀를 사용하는 문제이다. 재귀를 함에 있어 1)선택하고 , 2)선택하지 않고를 기준으로 재귀를 반복하였다. 기저조건으로는 날짜 N의 범위를 넘어갈때를 체크하였다. 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 package online.base; import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.StringTokenizer; public cl..

Algorithm 2020.04.14

[BOJ] 1753. 최단경로

최단경로를 구하는 문제이다. 이 문제에서 그래프의 가중치가 음을 가지지 않으므로 Dijkstra알고리즘을 사용하여 해결하였다. Dijkstra알고리즘은 Prim알고리즘 기법과 동일하지만 단한가지 차이점을 가진다. 그차이점은 단순 d값의 비교가 아니라 d[dest]와 weight+d[start]를 해주는 것이다. 즉, 단순거리가 아니라 누적거리를 비교해준다. 이렇게 되면 d배열에는 출발점에서 각 index까지의 최단 거리가 저장이 된다. 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..

Algorithm 2020.04.12